オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

トップ > 【機械学習】Markov Chain Monte Carlo / MCMC 法

【機械学習】Markov Chain Monte Carlo / MCMC 法

Index

マルコフ連鎖モンテカルロ法 / Markov Chain Monte Carlo Method / MCMC 法

目的

確率分布を生成するための方法.

Monte Carlo Method / モンテカルロ法 にマルコフ連鎖の考えを導入した.

Monte Carlo Method / モンテカルロ法

数値計算・数値解析を乱数を用いて行う手法の総称.

乱数を用いた試行を繰り返すことで、ある問題に対する近似解を数値的に求める.



一般論

n 個の変数 x_{1},\ \cdots,\ x_{n} を用いて以下の確率

P(x_{1},\ \cdots,\ x_{n})\ =\ P(\ \{x\}\ )


が与えられているとする.



MCMC 法では、 x_{1},\ x_{2},\ \cdots,\ x_{n} の値を、各点での滞在時間が P(\{x\}) に比例するように変化させる. 十分時間が長ければ、平均への近似になる.

変数の列 \{x\}^{0}\ \rightarrow\ \{x^{1}\}\ \rightarrow\ \cdots\ \rightarrow\ \{x^{k}\}\ \rightarrow\ \{x^{k+1}\}\ \rightarrow を次のように構成していく.

基本条件

  • マルコフ連鎖であること
  • 既約性
    • あらゆる変数の組 \{x\},\ \{x^{'}\} は有限回のステップで移り合うことが可能.
  • 非周期性
    • ステップ数 n_{s} で \{x\} から \{x\} に戻ってくることができるとする.
    • n_{s} としては色々な値が考えられるが、その最大公約数を周期と呼ぶ.
    • すべての \{x\} に対して周期が 1 であるとき非周期的であるという.
  • 詳細釣り合い条件 (詳細平衡条件)
    • あらゆる \{x\},\ \{x^{'}\} に対して、遷移確率 T が以下を満たす.
    • P(\{x\})\ \cdot\ T(\{x\}\ \rightarrow\ \{x^{'}\})\ =\ P(\{x^{'}\})\ \cdot\ T(\{x^{'}\}\ \rightarrow\ \{x\})



以上の条件がみたされると、 {x^{k}}\ (k=1,\ 2,\ \cdots) の確率分布が P({x}) に収束する.

マルコフ連鎖

\{x^{(0)}\}\ \rightarrow\ \{x^{(1)}\}\ \rightarrow\ \cdots\ \rightarrow\ \{x^{(k)}\}\ \rightarrow がマルコフ連鎖であるとは、 \{x^{(k)}\} から \{x^{(k+1)}\} で得られる確率が過去の履歴には依らずに \{x^{(k)}\} だけで決定すること.

サンプリング法

メトロポリス・ヘイスティング法

メトロポリス法

評価法

ジャックナイフ法

応用

ランジュバン・モンテカルロ法

参考

書籍

Web サイト