スマートフォン用の表示で見る

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

サイエンス

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

まるこふれんさもんてかるろ

定義

統計物理学から統計学の文脈に輸入され目覚しい成果をあげている統計手法のひとつで、マルコフ連鎖サンプリングを用いてモンテカルロ積分を行うのがクリティカルなステップであることからマルコフ連鎖モンテカルロ法と総称される。具体的なアルゴリズムには、

  • Gibbs sampler
  • Metropolis-Hastings algorithm

がある。実は、ギブスサンプラーはMHアルゴリズムの特殊な場合であることが知られており、本質的にはMHアルゴリズムが重要である。

Metropolis-Hastings algorithm を用いて確率分布P(X)に従う変数 X のサンプリングを行う手順は以下のとおり。まず現在の値 X_0 から(一般的にはすこしだけ異なる)次の値 X_1 を選ぶ。この時にX_1 を確率T(X_0|X_1)で選ぶとする。原則的にはどのような確率でもよい。次に新しい値X_1を採用するかどうかを決める。A(X0|X1)=¥frac{P(X_0)T(X_0|X_1)}{P(X_1)T(X_1|X_0)}と置くと、A(X_0|X_1) ¥geq 1の時は常に採用、A(X_0|X_1)¥lt 1の場合は確率A(X_0|X_1)で採用(採用しない場合はそのまま)というステップを繰り返して行くと変数X は分布P(X)に従う。注意すべきこととして、T をうまく選ばないとX のとりうる値(一般には非常に次元の大きい空間)すべてをサンプリングすることができないという点がある。

統計力学の分野では単純にモンテカルロ法と呼ばれることが多く、シミュレーションではメトロポリス法と熱浴法が主に用いられるが、このどちらもMHアルゴリズムの特殊な場合であると見なせる。

補足説明

マルコフ連鎖モンテカルロ法は通常ベイズ統計?学の枠組みにおいて用いられる。そして、MCMCベイズ統計学に革命的な変化をもたらした。ベイズ統計学は理論的には頻度主義に立脚した通常の統計学より優れている面が多々ある。しかしながら、計算可能性の問題からある程度以上に複雑なモデルになると実装が不可能である、という欠点を抱えていた。その欠点はマルコフ連鎖モンテカルロ法の出現によりほぼ克服され、ベイズ統計学の適用範囲はいまやすばらしく広がったといえよう。

また、ベイズ統計学の文脈を離れて、理論的には考えられうるが尤度が解析的にはuntractableになるような複雑なモデルの計算において非常に強力なsolutionたりうる手法として注目を集めている、と言う点は付記しておかねばなるまい。

単純サンプリングとの違い

単純サンプリングマルコフ連鎖モンテカルロの違いは、以下の入門記事(英語)でうまく解説されている。http://arxiv.org/abs/cond-mat/9612186 たとえば円周率モンテカルロ法で計算する有名な例として、正方形に内接する円を描き、そこにランダムにゴマを撒いて円の内部に入る確率を測定する、という方法があるが、これは典型的な単純サンプリングである。一方、高次元空間での関数の数値積分などをする場合には、高次元空間にランダムにゴマを撒いても関数の値の小さいところばかりにゴマが行って「無駄撃ち」が多く、精度が上がらないという場合がよくある。マルコフ連鎖モンテカルロ関数の値に比例した確率で高次元空間をランダムウォークするアルゴリズムなのでそのような問題を回避できる。しかし、蛋白質の折りたたみ問題やスピングラスモデルなどのいわゆる「複雑系」によく見られる問題として、ウェイトの大きい部分が孤立した領域として無数に存在して値の小さい部分に隔てられているような場合には有効なサンプリングが困難になる。

参考文献

  • N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller. "Equations of State Calculations by Fast Computing Machines", Journal of Chemical Physics, 21 1087-1091 (1953).
  • W.K. Hastings, "Monte Carlo Sampling Methods Using Markov Chains and Their Applications", Biometrika, 57 97-109 (1970).

リスト::数学関連