マルコフ連鎖モンテカルロ法(MCMC)の理論を簡単にまとめた。
MCMCするモチベーション
というのがモチベーション。
どうやってサンプリングするか？
確率変数$\boldsymbol{w}$のデータ$\boldsymbol{X}$観測後の事後分布$P(\boldsymbol{w}|\boldsymbol{X})$を求めたいとする。
MCMCでは、$P(\boldsymbol{w}|\boldsymbol{X})$が定常分布となるようなマルコフモデルを作り、このマルコフモデルからサンプリングを行う。
なぜそうするかというと、定常分布は時間が経過してもずっと同じ分布となる分布で、この分布となるようなマルコフモデルはずっと分布が変わることがないため、このサンプルが$P(\boldsymbol{w}|\boldsymbol{X})$からのサンプルであることを保証してくれるから。
どうやって上のようなマルコフモデルを作るか？
- 詳細釣り合い条件
- エルゴード性
を満たす遷移確率を持つようなマルコフモデルを作ればOK。
詳細釣り合い条件
マルコフモデルの$\boldsymbol{w} \rightarrow \boldsymbol{w'}$の遷移確率を$T(\boldsymbol{w}'|\boldsymbol{w})$としたとき、
$$ T(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t})P^*(\boldsymbol{w}^{t})=T(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1})P^*(\boldsymbol{w}^{t+1}) $$
が成立するならば、$P^*(\boldsymbol{w})$は定常分布。
証明
両辺で$\boldsymbol{w}^{t}$について和を取ると
となる。
これは左辺で$\boldsymbol{w}^{t}$が$\boldsymbol{w}^{t+1}$に遷移したとしても$\boldsymbol{w}$の分布$P^*(\boldsymbol{w})$が変化しないことを意味する。
つまり、詳細釣り合い条件が満たされるとき、$P^*(\boldsymbol{w})$は定常分布。
エルゴード性
これは$\boldsymbol{w}$の初期値に関わらず、$t\rightarrow\infty$で$P(\boldsymbol{w})$が定常分布$P^*(\boldsymbol{w})$に収束する性質のこと。
ちゃんとした証明は調べてないけど、基本的に$\boldsymbol{w}$の初期値に関わらず、$\boldsymbol{w}$が取りうる値全てにいずれは遷移できるようなマルコフモデルならOK。
MCMCアルゴリズム例：MH法
うまく目的の分布からサンプルを得るためには、詳細釣り合い条件とエルゴード性を持ったマルコフモデルを用意しなければならない。 Metropolis-Hastings(MH)法では以下の遷移確率で定義されたマルコフモデルを使用する。
$P(\boldsymbol{w}|\boldsymbol{X})=\frac{P(\boldsymbol{X}|\boldsymbol{w})P(\boldsymbol{w})}{\int P(\boldsymbol{X}, \boldsymbol{w})d\boldsymbol{w}}=\frac{f(\boldsymbol{w})}{Z}$としたとき、 $$ \begin{align} T(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) &= q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) \times \min(1, \frac{ f(\boldsymbol{w^{t+1}}) q(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) }{ f(\boldsymbol{w^{t}}) q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) }) \\ T(\boldsymbol{w}^{t}|\boldsymbol{w}^{t}) &= 1 - T(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) \end{align} $$ ここで、$q(\boldsymbol{w}'|\boldsymbol{w})$は提案分布と呼ばれ、$\boldsymbol{w}$が遷移する候補の値を取ってくるための分布。
手順は、
- $q(\boldsymbol{w}'|\boldsymbol{w})$から遷移先の候補点$\boldsymbol{w}'$を取ってくる
- $a = \frac{ f(\boldsymbol{w^{t+1}}) q(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) }{ f(\boldsymbol{w^{t}}) q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) }$を計算する
- $a$が1以上だったら候補点$\boldsymbol{w}'$をサンプルとして受理し、1より小さかったら$a$の確率で$\boldsymbol{w}'$をサンプルとして受理する
- 受理された場合は$\boldsymbol{w}\rightarrow\boldsymbol{w}'$と遷移させ、されなかった場合は遷移させず$\boldsymbol{w}\rightarrow\boldsymbol{w}$とする
- 上記を繰り返す
のようにしてサンプリングを行う。
証明
詳細釣り合い条件が成立するか確かめる。 $$ \begin{align} T(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) P(\boldsymbol{w^{t}}|\boldsymbol{X}) &= q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) \times \min(1, \frac{ f(\boldsymbol{w^{t+1}}) q(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) }{ f(\boldsymbol{w^{t}}) q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) }) \frac{f(\boldsymbol{w}^{t})}{Z} \\ &= \min( f(\boldsymbol{w}^{t}) q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}), f(\boldsymbol{w}^{t+1}) q(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) ) \frac{1}{Z} \\ &= q(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) \times \min(\frac{ f(\boldsymbol{w^{t}}) q(\boldsymbol{w}^{t+1}|\boldsymbol{w}^{t}) }{ f(\boldsymbol{w^{t+1}}) q(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) }, 1) \frac{f(\boldsymbol{w}^{t+1})}{Z} \\ &= T(\boldsymbol{w}^{t}|\boldsymbol{w}^{t+1}) P(\boldsymbol{w^{t+1}}|\boldsymbol{X}) \end{align} $$ で詳細釣り合い条件が成立するので、$P(\boldsymbol{w}|\boldsymbol{X})$が定常分布となることがわかる。
エルゴード性は提案分布$q(\boldsymbol{w}'|\boldsymbol{w})$が$\boldsymbol{w}$の取りうる値へ遷移できるような分布であればOK。
