マルコフ性とマルコフ連鎖
時刻 \(t\) が離散的な値（例: \(t=1, 2, 3, \dots\)）であり、それぞれの時刻に確率変数 \(x^{(t)}\) を持つ系列を考えます。
- マルコフ連鎖: 確率変数 \(x^{(1)}, x^{(2)}, x^{(3)}, \dots\) の系列が、ある規則に従って生成されるシステムです。
- マルコフ性: ある時刻の状態が、それ以前の全ての状態ではなく、直前の（あるいは限られた過去の）状態のみに依存して決まる性質です。
- 1次マルコフ性: \(x^{(t)}\) の状態が \(x^{(t-1)}\) のみに依存して決まります。
- \(n\)次マルコフ性: \(x^{(t)}\) の状態が \(x^{(t-1)}, \dots, x^{(t-n)}\) のみに依存して決まります。
- 遷移確率 \(p(x^{(t)}|x^{(t-1)})\): 時刻 \(t-1\) の状態 \(x^{(t-1)}\) から時刻 \(t\) の状態 \(x^{(t)}\) へ遷移する確率です。
- 定常分布 \(\pi(x)\): マルコフ連鎖が十分に長い時間続いたときに、各状態が出現する確率分布です。定常分布は、以下の関係式（詳細釣り合い条件）を満たします。 \( \pi(y) = \sum_x p(y|x)\pi(x) \)
マルコフ連鎖モンテカルロ法 (MCMC)
MCMCは、直接サンプリングが困難な複雑な確率分布から、その分布に従うサンプルを生成するための手法です。マルコフ連鎖の定常分布が目的の分布と一致するように遷移確率を設計し、そのマルコフ連鎖をシミュレーションすることでサンプルを生成します。
MCMCで生成されるサンプルの系列 \(x^{(1)}, x^{(2)}, \dots\) のうち、初期のサンプルはマルコフ連鎖の初期値に強く依存するため、これらはバーンイン期間として破棄されます。十分に長いバーンイン期間の後（\(t\) が十分に大きくなった後）のサンプル \(x^{(t)}, x^{(t+1)}, \dots\) を使用します。
MCMCで広く使われているアルゴリズムの一つが、メトロポリス・ヘイスティングス法です。
メトロポリス・ヘイスティングス法
目的の分布 \(p(x)\) からサンプルを得たいとします。
- 初期状態 \(x^{(1)}\) をランダムに設定します。
- 以下のステップを繰り返します (\(t=1, 2, \dots\)): a. 現在の状態 \(x^{(t)}\) から、提案分布 \(q(\hat{y}|x^{(t)})\) に従って新しい候補状態 \(\hat{y}\) をサンプリングします。 b. 採択確率 \(\alpha(x^{(t)}, \hat{y})\) を計算します。 \( \alpha(x^{(t)}, \hat{y}) = \min\left(1, \frac{p(\hat{y})q(x^{(t)}|\hat{y})}{p(x^{(t)})q(\hat{y}|x^{(t)})}\right) \) ここで、\(p(x)\) は目的の分布です。 c. \([0, 1]\) の一様乱数 \(u\) を生成し、\(u < \alpha(x^{(t)}, \hat{y})\) であれば、候補状態 \(\hat{y}\) を次の状態 \(x^{(t+1)}\) として採択します。そうでなければ、\(x^{(t+1)} = x^{(t)}\) とし、現在の状態を維持します。
このプロセスを繰り返すことで、生成される系列は目的の分布 \(p(x)\) に収束します。
参考
- 手塚 太郎, 『しくみがわかるベイズ統計と機械学習』, 講談社 (2017)