棄却サンプリング法

Summarize Timeline Top Qs Fact Check

棄却サンプリングでは、任意の確率密度関数${\displaystyle f(x)}$に従う目的確率変数 ${\displaystyle X}$ のサンプリングを、提案確率分布${\displaystyle g(y)}$に従う確率変数 ${\displaystyle Y}$ のサンプルを用いて行う。具体的には、${\displaystyle X}$ を直接サンプルする代わりに、${\displaystyle Y}$ のサンプルを利用して、そのサンプルを確率 ${\displaystyle f(x)/(Mg(x))}$ で受け入れるという手順を繰り返すことにより、${\displaystyle X}$ のサンプルを入手することができる。ここで、 ${\displaystyle M<\infty }$ は定数であり、${\displaystyle X}$ の台全体で${\displaystyle f(x)/g(x)}$ の上界である。言い換えれば、${\displaystyle M}$ は全ての ${\displaystyle x}$ に対して ${\displaystyle f(x)\leq Mg(x)}$ を満たさなければならない。なお、この条件により ${\displaystyle Y}$ の台は ${\displaystyle X}$ の台を含んでいなければならない。すなわち、${\displaystyle f(x)>0}$ となるような ${\displaystyle x}$ に対して ${\displaystyle g(x)>0}$ でなければならない。

${\textstyle (x,v=u\cdot Mg(x))}$のペアをサンプルすると、${\displaystyle v}$ は0から${\textstyle Mg(x)}$までの一様分布となる。ここで ${\textstyle u<f(x)/(Mg(x))}$ となる ${\displaystyle (x,v)}$ のペアだけを採択することで、 ${\displaystyle (x,v)}$は ${\displaystyle f(x)}$ 以下の領域からの一様分布からのサンプルとみなすことができる。したがって、${\displaystyle x}$ の周辺分布が${\displaystyle f(x)}$となっており、この手法の有効性が示される。

このことから、十分な反復回数のもとで、このアルゴリズムは目的分布${\displaystyle f(x)}$からのサンプルを生成できる。

この手法はモンテカルロ法一般的な分野に応用される。例として、マルコフ連鎖モンテカルロ法では提案分布を利用して目的分布からのサンプリングを行う。また、メトロポリス・ヘイスティングス法の基礎をなす。

二次元空間からの採択確率は、提案されたサンプルのうち採択されるものの割合であり、これは$${\displaystyle {\begin{aligned}\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)&=\operatorname {E} _{U,Y}\left[\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}\right]\\&=\operatorname {E} _{Y}\left[\operatorname {E} _{U}\left[\mathbf {1} _{\left[U\leq {\frac {f(Y)}{Mg(Y)}}\right]}|Y\right]\right]\\&=\int \int _{u=0}^{u={\frac {f(y)}{Mg(y)}}}g(y){\text{d}}u{\text{d}}y\\&=\int {\frac {f(y)}{Mg(y)}}g(y){\text{d}}y\\&=\int {\frac {f(y)}{M}}{\text{d}}y\\&={\frac {1}{M}}\end{aligned}}}$$と計算される。ここで、${\displaystyle U\sim \mathrm {Unif} (0,1)}$であり、${\displaystyle y}$ は提案分布${\displaystyle g(\cdot )}$に従う確率変数 ${\displaystyle Y}$ のサンプルとした。なお、最後の式変形の途中で ${\displaystyle Y}$ の台が ${\displaystyle X}$ の台を含んでいることを用いている。

${\displaystyle Y}$ からのサンプルで ${\displaystyle X}$ のサンプルとして採択されるサンプルを得る上で必要となるサンプルの数は確率 ${\displaystyle 1/M}$ の幾何分布に従い、その期待値は ${\displaystyle M}$ となる。直感的には ${\displaystyle M}$ は必要となる反復回数の期待値であり、これがアルゴリズムの計算複雑度の尺度となる。

上の式は、$${\displaystyle M={\frac {1}{\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}}}$$と書ける。${\displaystyle M}$ は定義上 ${\textstyle 1\leq M<\infty }$ を満たすため、 ${\textstyle \mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}\right)}$ は${\displaystyle [0,1]}$に含まれ、したがって確率の公理を満たす。${\displaystyle M}$ は ${\textstyle f(x)/g(x)}$ の上界であるので、この比率の最大値が小さいほど採択確率も大きくなる。実用上は、${\displaystyle M}$ として ${\displaystyle 1}$ に近い値が好まれるが、これは平均的に棄却されるサンプルの数が少なくなるので、結果としてアルゴリズムの反復回数が減るためである。この意味で、${\displaystyle M}$ は小さければ小さいほど好ましい。全領域で${\displaystyle f(x)\leq Mg(x)}$ を満たしながら ${\displaystyle M}$ を小さくするには、一般的には提案分布 ${\displaystyle g(x)}$ と目的分布 ${\displaystyle f(x)}$ がある意味で似ている必要がある。なお、実際には ${\displaystyle M=1}$ の場合は ${\displaystyle f(x)=g(x)}$ を意味することになり、したがって通常のサンプリングに一致する。

棄却サンプリングは、${\displaystyle f(x)}$ が直接サンプリングすることが困難な場合に頻繁に利用される。 棄却サンプリング1回の反復あたり、提案分布からのサンプリング、一様分布からのサンプリング、 ${\displaystyle f(x)/(Mg(x))}$ の評価が要求される。そのため、これらの計算コストの ${\displaystyle M}$ 倍 (1個の採択されるサンプルが得られるまでに必要な反復回数の期待値)が他の手法の計算コストより小さい場合、棄却サンプリング法が効率の良い選択肢となる。

密度 ${\displaystyle f}$ をもつ確率変数 ${\displaystyle X}$ のサンプルを、密度 ${\displaystyle g}$ をもつ確率変数 ${\displaystyle Y}$ からサンプルするアルゴリズムとして、ジョン・フォン・ノイマンに用いられ^[4]、その起源がビュフォンとその針^[5]にまで遡るアルゴリズムは以下の通り:

• 確率変数 ${\displaystyle Y}$ のサンプル ${\displaystyle y}$ と、単位区間上の連続一様分布からのサンプル ${\displaystyle u}$ をとる。
• ${\displaystyle u}$ と ${\textstyle f(y)/Mg(y)}$ の大小を比較する。
  • ${\textstyle f(y)/Mg(y)}$の方が大きい場合、 ${\displaystyle f}$ からのサンプルとして${\displaystyle y}$ を採択する。
  • そうでなければ、提案された ${\displaystyle y}$ を棄却し、サンプリングのステップに戻る。

このアルゴリズムでは、１つのサンプルを得るために平均 ${\displaystyle M}$ 回の反復を要求される^[6]。

• 逆関数法
• Ratio of uniforms（英語版）
• Non-uniform random variate generation（英語版）
• Ziggurat algorithm（英語版）