入門ランダムウォーク：Metropolis Algorithm

Doing Bayesian Data Analysis の 第 7 章 Inferring a Binomial Proportion via the Metropolis Algorithm から。


「離散型分布て素晴らしい（数学的制約からの開放）」で「ベータ分布など数学的な分布が不可能な場合は、離散型分布が使える」と記したが、この特徴はかなり有意義な分析に発展する、かの有名な MCMC (Markov chain Monte Carlo methods マルコフ連鎖モンテカルロ法 ) 。ここでは先ず、Metropolis algorithm（正しくは Metropolis-Hastings algorithm かもしれないが、今のところは無視）で「ランダムウォーク」によるサンプリングのイメージを掴む。

詳細な Metropolis algorithm の前に、ランダムウォークの目的は

By being able to do those three things, we are able to do indirectly something we could not necessarily do directly: We can generate random samples from the target distribution. Moreover, we can generate those random samples from the target distribution even when the target distribution is not normalized.

つまり

• 予測する分布の標本を、直接ではなく間接的に得ることができる
• 予測する分布は正規化されている必要はない

アンケート調査などの、標本抽出が直接可能なことだけが、分析対象ではない。そんな、標本が直接抽出できない場合に有効なサンプリング手法の一つが Metroplis algorithm （ランダムウォーク法の一種）ということ。


単純な分布をランダムウォーク

Metroplis algorithm の単純な例で示す。

左は本書 Figure 7.1 、最下段の離散型分布が予測する分布。この分布が「答え」で、これを「ランダムウォーク」の結果で導き出すというもの。

中央が「ランダムウォーク」した結果。最上段が予測結果で、最下段の分布に一致している。このランダムウォークの仕方が Metropolis algorithm 。この「動き」を解説する。

最下段の分布は、度数が 1 から 7 まで昇順に並んだもの。ランダムウォークの開始は、今回は中央値の 4 から。

ランダムウォークの動きは 1 回につき y 軸を 1 段上昇、x 軸は {左, 右, 止まる} のいずれか。

左右への動きを 50 : 50 の確率で選び、選ばれた方が大きい θ であれば右に動く。小さい θ であれば「左 / 現在位置」の確率で左に動く。例えば、スタート位置の 4 の位置から右に動く確率は 0.5、左に動くのは 0.5 × 3/4 = 0.375 、4 に止まるのは 0.5 - 0.375 = 0.125 の確率となる。

中断のグラフの y 軸は Time とあるが「ステップ数」とも解釈できる。このグラフからも、ステップ数の中盤以降から徐々に元のグラフを描画し始めている。これは、開始地点の動く確率が「右 = 0.5, 左 = 0.375, 止まる = 0.125」からも、このランダムウォークが相対的に x 軸の大きい方に偏っていることが分かる。

ランダムウォークの軌跡

次は図 7.2 、先のランダムウォークを時系列 t 毎に示したもの。左上隅の t = 1 から開始して t 値が増加する順に見る、縦軸は確率。

末尾の「 t = 3 までの確率算出」で、t = 1 から 3 まで順に確率を算出した。

注目すべきは、t = 3 までの 2 ステップで、すでに θ の 2 から 6 までの確率が算出できていること。開始の θ = 4 から左右に θ の 2 つ分の広がり。

今回は θ が 7 つの単純な分布なので、t = 13 で実際の分布に近づいている。しかし現実的には、もっと複雑な分布の予測が通常で、実際の分布に近づく "burn-in" 期間は排除することなる。ランダムウォークの開始は任意なので、burn-in 期間部分の排除は重要になる。

今回は単純な分布を分析したが、それでも Metropolis algorigthm のランダムウォークの結果が、target distribution（目的分布）を正確に導いていることは明らか。

次回は、これまで直接サンプリングしたデータで事後確率を求めた例題を、R での Metropolis algorithm 実装で求める。


「Metropolis Algorithm の実装例」に続く。


t = 3 までの確率算出

ランダムウォーク開始から t = 3 まで順に確率を算出した。

t = 1
　P(θ = 4) だけで 1.0 。

t = 2
　先に計算したように「P(θ = 5) = 0.5,  P(θ = 3) = 0.375,  P(θ = 4) = 0.125

t = 3
　P(θ = 6) は、θ = 4 から θ = 6 になる：0.5 × 0.5 = 0.25 

　P(θ = 5) は 2 通り
　　θ = 4 から θ = 5 になり、止まる：0.5*(0.5*(1-4/5))
　　θ = 4 に止まった後で θ = 5 になる：(0.5*(1-4/5))*0.5
　　よって 0.1 = 0.5*(0.5*(1-4/5))+(0.5*(1-4/5))*0.5

　P(θ = 4) は 3 通り
　　θ = 4 から θ = 5 になり、θ = 4 になる：0.5*(0.5*4/5)
　　θ = 4 から θ = 3 になり、θ = 4 になる：(0.5*3/4)*0.5
　　θ = 4 に止まり、また止まる：(0.5*(1-3/4))^2
　　よって 0.403125 = 0.5*(0.5*4/5)+(0.5*3/4)*0.5+(0.5*(1-3/4))^2

　P(θ = 3) は 2 通り
　　θ = 4 からθ = 3 になり、止まる：(0.5*3/4)*(0.5*(1-2/3))
　　θ = 4 に止まり、θ = 3 になる：(0.5*(1-3/4))*(0.5*3/4)
　　よって 0.109375 =  (0.5*3/4)*(0.5*(1-2/3)) + (0.5*(1-3/4))*(0.5*3/4)

　P(θ = 2) は θ = 3 になり、θ = 2 になる
　　(0.5*3/4)*(0.5*2/3) = 0.125

これらの値と、図 7.2 の 各 t のグラフが一致する。