Metropolis-Hastings Algorithm

https://youtu.be/7IpvsfRgTTY?si=ylJwTWvwT-s2ccjH

この動画はMetropolis Algorithmを解説している（が、とてもわかりやすい）appbird.icon

目的

目標分布そのものから直接は引けない場合に

受理・棄却つきのランダムウォークで、その分布を定常分布にもつ連鎖を作る方法

更新手順

1. 現在の状態を $ x_t とする。

2. 提案分布 $ q(x' \mid x_t) から、次の候補 $ x' をサンプルする。

3. 受理確率 $ \alpha(x_t, x') を計算する。 $ \alpha(x_t, x') = \min\left(1, \frac{\pi(x')q(x_t \mid x')}{\pi(x_t) q(x' \mid x_t)}\right)

4. 確率 $ \alpha で $ x' を受理し、次の状態を $ x_{t+1} = x' とする。

5. 受理しなければ、現在の状態に留まり $ x_{t+1} = x_t とする。

各記号の意味

$ x_t：時刻 $ t における現在の状態。

$ x'：提案された次状態の候補。

$ \pi(x)：サンプルしたい目標分布。

正規化定数を知らなくても使える。

$ q(x' \mid x_t)：現在の状態 $ x_t から候補 $ x' を出す提案分布。

$ \alpha：候補 $ x' を受理する確率。

受理確率の見方

$ \pi(x') が大きいほど、候補 $ x' は受理されやすい。

ただし、提案分布が非対称な場合は、行きやすさ $ q(x' \mid x_t) と戻りやすさ $ q(x_t \mid x') の補正が必要になる。

その補正込みで、長期的に目標分布 $ \pi(x) を定常分布にもつように設計されている。

対称提案の場合

もし $ q(x' \mid x_t) = q(x_t \mid x') なら、受理確率は簡単になる。

$ \alpha(x_t, x') = \min\left(1, \frac{\pi(x')}{\pi(x_t)}\right)

これは元のMetropolis algorithmの形。

直観

目標分布で確率が高い場所への移動は受理されやすい。

確率が低い場所への移動も、一定確率で許される。

そのため、単なる山登りではなく、分布全体を反映したサンプル列になる。