Metropolisアルゴリズム

まだキモはわかっていないが、A-Rアルゴリズムからの発展系みたいなもんのよう。また、Importance samplingはMetropolis Hastingsに対応するようだ。

確率密度関数π(x)からサンプリングしたい。ここで対称サンプラーq(x,y)=q(y,x)を利用する。

1. 初期値X₀を決める。
2. q(Y|X₀)からサンプルYを取りだす。
3. u~U[0,1]を発生。
4. u < π(Y)/π(X₀)ならX₁=Y、そうでなければX₁=X₀

この操作を繰り返して得たX₁,..,X_nはπ(x)からのサンプルである。

u < \frac{\pi(Y)}{\pi(X_0)}

を基準としているが、これが

1 < \frac{\pi(Y)}{\pi(X_0)}

なら逐次改良法となる。メトロポリス法では、かならずしも新しいモデルが古いモデルより確率が高くなくても、確率uで採用するという方法である。

local maximaから逃れられる方法であることは理解できるが・・・

A-R サンプリングの例

たとえばπ(x)=N(1,3)からのサンプリングはこんな感じ。h(x)=1/60、c=10としてる。なんで？ch(x)=0.167となる。これがN(1,3)の最大値0.133より大きいから。c=8くらいでもよさそうだけど。とりあえずh(x)は均一分布の確率密度関数(-30~30の範囲について）になる。

u~U(0,1)

Z~h(x)=U(-30,30)

について、

u<=f(Z)/ch(Z)

にてサンプリングされたものが赤丸で表わされている。棄却されたものは黒。10000のZに対し、998のサンプルがacceptされた。

たとえばh(x)=1/40、c=7とするなら1412とかのサンプルがacceptされたりする。

いずれにせよA-Rサンプリングでは棄却が多すぎて非効率的なこと、またch(x)が求められない場合があることから、MCMCを行うことになるということらしい。

acceptance-rejection (A-R) サンプリング

確率密度関数π(x)=f(x)/Kからサンプリングしたい。f(x)はunnormalized (非標準？)分布で、Kはnormalizing constant。f(x)は離散分布でも連続分布でもよい。

ここでf(x)<=ch(x)なるcとh(x)をとる。

アルゴリズム

1. Z~h(・)、u~U(0,1)をとる。
2. u<=f(Z)/ch(Z)ならZ=Xを返す。
3. そうでなければ元に戻る。

2がacceptance、3がrejection。意味的には、横にZ、縦にuの座標を取り各Zにおいてランダムにとったu<=f(Z)/ch(Z)となる点を返す(f(x)/ch(x)<=1なので、点が返されないZはない)。

意味は？

P(X≦x)=P(Z≦x|u≦f(Z)/ch(Z))

ところでP(Z≦x)=∫-∞~x h(y)dyで、

P(Z≦x, u≦f(Z)/ch(Z))=∫ f(y)/ch(y) ・ h(y)dy=(K/c) ∫-∞~x π(y)dy

ここでx→∞とすると

P(u≦f(Z)/ch(Z))=K/c

なので

P(X≦x)=P(Z≦x|u≦f(Z)/ch(Z))=P(Z≦x, u≦f(Z)/ch(Z))/P(u≦f(Z)/ch(Z))=∫-∞~x π(y)dy

というわけでZは確率密度関数f(Z)/cからのランダムなサンプリングとなる。