手帳と試行

学んだことをアウトプットしていきます。 日々、ノートあるのみ。
2023-02-16
モンテカルロ法 マルコフ連鎖モンテカルロ法

マルコフ連鎖モンテカルロ法

ある確率分布に従う乱数を生成する方法であるMCMCを導入し、MCMCが満たすための条件を確認する。

目次
マルコフ連鎖モンテカルロ法 1. マルコフ性 2. 既約性 3. 非周期性 4. 釣り合い条件 詳細釣り合い条件

マルコフ連鎖モンテカルロ法

マルコフ連鎖モンテカルロ法 (Marcov Chain Monte Carlo; MCMC) は、目的の分布を定常分布とするマルコフ連鎖を構築し、確率分布から標本を生成する計算手法である。

  1. 新しいサンプルの候補を提案
  2. マルコフ連鎖が目的の分布に収束することを保証する確率的なルールに基づいて、それらを受け入れるか拒否するかを決定する

というシンプルな方法で確率分布に従う標本を生成する。得られたサンプルは統計量の推定や目標分布の予測に使用することができる。

以下、MCMCが成り立つための条件を列挙する。

1. マルコフ性

MCMCで生成される乱数列 {xi}i=0n\{x^i\}_{i=0}^n はマルコフ性を満たす確率変数列、すなわちマルコフ連鎖 {Xi}\{X^i\} の実現値である。

マルコフ性とは、確率変数列の tt 番目の確率変数 XtX^t の実現値が xtx^t である確率が、その直前の実現値 xt−1x^{t-1} のみに依存することをいう。

p(xt∣xt−1,xt−2,…,x0)=p(xt∣xt−1)\begin{aligned} p(x^{t} | x^{t-1}, x^{t-2}, \dots, x^0) = p(x^{t} | x^{t-1}) \end{aligned}

より正確には次のようなことをいう。

Pr[Xt=xt∣Xt−1=xt−1,Xt−2=xt−2,…,X0=x0]=Pr[Xt=xt∣Xt−1=xt−1]\begin{aligned} & \mathop\mathrm{Pr}[X^t = x^t | X^{t-1} = x^{t-1}, X^{t-2} = x^{t-2}, \dots, X^{0} = x^{0}] \\ ={} & \mathop\mathrm{Pr}[X^t = x^t | X^{t-1} = x^{t-1}] \end{aligned}

このような性質を満たす確率変数列 {Xi}i=0n\{X^i\}_{i=0}^n をマルコフ連鎖 (Markov chain) という。

2. 既約性

MCMCで生成される乱数列 {xi}i=1n\{x^i\}_{i=1}^n は既約なマルコフ連鎖の実現値でなくてはならない。

マルコフ連鎖 {Xi}i=1n\{X^i\}_{i=1}^n が既約である (irreducible) とは、どの状態 x0∈Xx^0 \in {\cal X} からでも、有限回の遷移によって、別の任意の状態 xn∈Xx^n \in \mathcal X に到達できるということを意味する。

Pr[Xn=xn∣X0=x0]>0∀xn,x0∈X\begin{aligned} \mathop\mathrm{Pr}[X^n = x^n | X^0 = x^0] \gt 0 \quad {}^\forall x^n, x^0 \in \mathcal X \end{aligned}

基本的に P(x)P(x) の台 (support) X\mathcal X が連続なら問題ないが、たとえば p(x)∝exp⁡(−x2−x−2)p(x) \propto \exp(-x^2 - x^{-2}) など、複数の島に分かれる場合、素朴なアルゴリズムだとマルコフ連鎖が既約性を満たさない可能性もあるため注意が必要である。

3. 非周期性

MCMCで生成される乱数列 {xi}i=1n\{x^{i}\}_{i=1}^n は非周期的なマルコフ連鎖の実現値でなくてはならない。

マルコフ連鎖 {Xi}i=1n\{X^i\}_{i=1}^n が非周期的である (aperiodic) とは次のようなことを意味する。ある時刻 ttにおける実現値 xtx^t と、時刻 t+nt+n の実現値 xt+nx^{t+n} が一致するというような事象を考え、これが起こりうるような n∈Z+n \in \mathbb Z_+ の集合に注目する。

{n}={n∣Pr[Xt+n=Xt]>0}\begin{aligned} \{n\} = \{n | \mathop\mathrm{Pr}[X^{t+n} = X^t] > 0\} \end{aligned}

この集合 {n}\{n\} の最大公約数が TsT_s であるとき、TsT_s を周期という。

Ts=gcd({n∣Pr[Xt+n=Xt]>0})\begin{aligned} T_s = \mathop\mathrm{gcd} (\{n | \mathop\mathrm{Pr}[X^{t+n} = X^t] > 0\}) \end{aligned}

任意の時刻の実現値 xtx^t に対して、周期 TsT^s の周期が 11 であるならば、マルコフ連鎖 {Xi}i=1n\{X^i\}_{i=1}^n は非周期的である。

gcd({n∣Pr[Xn=x∣X0=x]>0})=1\mathop\mathrm{gcd} (\{n | \mathop\mathrm{Pr}[X^n = x | X^0 = x] > 0\}) = 1

4. 釣り合い条件

MCMCで生成される乱数列 {xi}i=1n\{x^i\}_{i=1}^n は釣り合い条件を満たすようなマルコフ連鎖の実現値でなくてはならない。

時刻 tt における実現値が xx である確率を Pt(x)P_t(x)、時刻 t+1t+1 に x′x' である確率を Pt+1(x′)P_{t+1}(x') と表すことにする。

Pt(x)≔Pr ⁣[Xt=x]Pt+1(x′)≔Pr ⁣[Xt+1=x′]\begin{aligned} P_t(x) &\coloneqq \mathop\mathrm{Pr} \! \left[ X^t = x \right] \\ P_{t+1}(x') &\coloneqq \mathop\mathrm{Pr} \! \left[ X^{t+1} = x' \right] \\ \end{aligned}

さらに、ある時刻 tt において xx であるという条件のもと、その次の時刻 t+1t+1 において x′x' であるような条件付き確率を T(x′∣x)T(x' | x) と表すことにする。

T(x′∣x)≔Pr ⁣[Xt+1=x′∣Xt=x]\begin{aligned} T(x' | x) \coloneqq \mathop\mathrm{Pr} \! \left[ X^{t+1} = x' | X^{t} = x \right] \end{aligned}

確率変数列 {Xi}\{X^i\} がマルコフ連鎖であることから、次のような関係が成立する。

Pt+1(x′)=∫dxPt(x)T(x′∣x)\begin{aligned} P_{t+1}(x') = \int dx P_t(x) T(x' | x) \end{aligned}

乱数列 {xi}i=1n\{x^i\}_{i=1}^n が釣り合い条件を満たしているとは、上式において任意の tt について Pt+1=PtP_{t+1} = P_t が成り立つこと、すなわち次式が成り立つことをいう。

P(x′)=∫dxP(x)T(x′∣x)\begin{aligned} P(x') = \int dx P(x) T(x' | x) \end{aligned}
詳細釣り合い条件

釣り合い条件が成り立つための十分条件の1つに、詳細釣り合い条件がある。

P(x′)T(x∣x′)=P(x)T(x′∣x)\begin{aligned} P(x') T(x | x') = P(x) T(x' | x) \end{aligned}

この式の両辺を xx で積分すれば、

(左辺)=∫dxP(x′)T(x∣x′)=P(x′)∫dxT(x∣x′)=P(x′),(右辺)=∫dxP(x)T(x′∣x)\begin{aligned} ({\small \text{左辺}}) ={}& \int dx P(x') T(x | x') \\ ={}& P(x') \int dx T(x | x') \\ ={}& P(x'), \\ ({\small \text{右辺}}) ={}& \int dx P(x) T(x' | x) \end{aligned}

ゆえ次式が成り立ち、確かに釣り合い条件が成り立っていることがわかる。

P(x′)=∫dxP(x)T(x′∣x)\begin{aligned} P(x') = \int dx P(x) T(x' | x) \end{aligned}
モンテカルロ法 マルコフ連鎖モンテカルロ法