棄却サンプリング法

棄却サンプリング法（ききゃくサンプリングほう、）とは、数値解析やにおいて確率分布からの観測点を生成する上での基礎的な技術の1つである。同じサンプリング法を、採択棄却法（さいたくききゃくほう、acceptance-rejection method）や採択棄却アルゴリズム（さいたくききゃくアルゴリズム、accept-reject algorithm）と呼ぶこともある。この手法は上の任意の確率密度関数に対して適応することができる。

棄却サンプリング法は、一次元である確率密度関数に従う確率変数をサンプリングする際の手順として、まず二次元空間上での連続一様分布からのサンプルを生成し、次にとなるような点だけを保持し、残ったサンプルの座標だけをとるという手順を利用することが可能であるという考察に基づいている。 なお、この特性の利用はさらに高次元へと拡張できる。

 理論 
棄却サンプリングでは、任意の確率密度関数に従う目的確率変数  のサンプリングを、提案確率分布に従う確率変数  のサンプルを用いて行う。具体的には、 を直接サンプルする代わりに、 のサンプルを利用して、そのサンプルを確率  で受け入れるという手順を繰り返すことにより、 のサンプルを入手することができる。ここで、  は定数であり、 の台全体で の上界である。言い換えれば、 は全ての  に対して  を満たさなければならない。なお、この条件により  の台は  の台を含んでいなければならない。すなわち、 となるような  に対して  でなければならない。

のペアをサンプルすると、 は0からまでの一様分布となる。ここで  となる  のペアだけを採択することで、 は  以下の領域からの一様分布からのサンプルとみなすことができる。したがって、 の周辺分布がとなっており、この手法の有効性が示される。

このことから、十分な反復回数のもとで、このアルゴリズムは目的分布からのサンプルを生成できる。

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

二次元空間からの採択確率は、提案されたサンプルのうち採択されるものの割合であり、これはと計算される。ここで、であり、 は提案分布に従う確率変数  のサンプルとした。なお、最後の式変形の途中で  の台が  の台を含んでいることを用いている。

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

上の式は、と書ける。 は定義上  を満たすため、  はに含まれ、したがって確率の公理を満たす。 は  の上界であるので、この比率の最大値が小さいほど採択確率も大きくなる。実用上は、 として  に近い値が好まれるが、これは平均的に棄却されるサンプルの数が少なくなるので、結果としてアルゴリズムの反復回数が減るためである。この意味で、 は小さければ小さいほど好ましい。全領域で を満たしながら  を小さくするには、一般的には提案分布  と目的分布  がある意味で似ている必要がある。なお、実際には  の場合は  を意味することになり、したがって通常のサンプリングに一致する。

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

 アルゴリズム 
密度  をもつ確率変数  のサンプルを、密度  をもつ確率変数  からサンプルするアルゴリズムとして、ジョン・フォン・ノイマンに用いられ、その起源がビュフォンとその針にまで遡るアルゴリズムは以下の通り:

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

このアルゴリズムでは、１つのサンプルを得るために平均  回の反復を要求される。

 関連項目 
 逆関数法




 脚注 

Category:モンテカルロ法
Category:数学に関する記事