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

マルコフ連鎖モンテカルロ法（マルコフれんさモンテカルロほう、英: Markov chain Monte Carlo methods、通称MCMC）とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することによって確率分布のサンプリングを行う種々のアルゴリズムの総称である。具体的には、同時事後分布に従う乱数を継時的に生成する。代表的なMCMCとしてメトロポリス・ヘイスティングス法やギブスサンプリングがある。

MCMCで充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。

求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適切な連鎖なら任意の位置から始めても定常分布に速く達し、これを高速混合（rapid mixing）とよぶ。

典型的なMCMCは常にある程度の初期値の影響が残るため目標分布しか近似することができない。CFTP法（coupling from the past）などの、より洗練されたMCMCベースのアルゴリズムは完全標本を作成することができるが、より多くの計算と（期待値では有限だが）限界のない実行時間を要する^[1][2][3]。

このアルゴリズムの最も一般的な応用は多重積分を数値的に計算することである。ランダムに歩き回る粒子の集団を想定し、粒子が点を通過するたびに、その点の被積分関数の値を積分に加算する。粒子は次に積分への貢献が高い所を探して複数の仮の動作をする。このような方法はランダムウォーク法とよばれ、これは乱数的なシミュレーションつまりモンテカルロ法の一種である。従来のモンテカルロ法で用いられる被積分関数のランダムな標本が独立であるのに対して、MCMCで用いられる標本は相関がある。被積分関数を均衡分布に持つようなマルコフ連鎖を作成する必要があるが、多くの場合において容易に行うことができる。

多重積分はベイズ統計学、計算物理学、計算生物学などにしばしば現れるため、そのような分野でMCMCが広く使われている。例としては Gill 2008 や Robert & Casella 2004 を参照。

生成された乱数列はトレースプロット（英: trace plots）の形で可視化できる。

ランダムウォーク法

マルコフ連鎖モンテカルロ法 (MCMC) では、均衡分布の近辺を小さなステップで無作為に動き回る粒子を想定したアルゴリズムが多い。これをランダムウォーク（酔歩）という。この方法は実装や解析が容易だが、粒子はしばしば折り返して既に調べた空間を調べ始めてしまうため、粒子が全空間を調べるのに長い時間がかかってしまう。以下にランダムウォークを用いたMCMCのいくつかを並べる：

• メトロポリス・ヘイスティングス法：提案密度（proposal density）によって新しい候補を提案し、提案された候補を棄却もしくは採択する手続き用いてマルコフ連鎖を生成する。下記の様々な手法を特別な方法として含む、最も一般的なMCMCである。
• ギブスサンプリング：対象となる確率分布の条件付き分布を用いて状態を更新するMCMCである。必要となる全ての条件付分布からの乱数が正確に生成できることを必要とする。必ず提案が採択されるメトロポリス・ヘイスティングス法と捉えることもできる。他の多くの手法で必要となる、調整パラメータを基本的に必要としないことも、この手法がよく用いられる理由の一つである。
• スライスサンプリング：密度関数の曲線下の領域を一様にサンプルすることによって、対象となる確率分布を生成することができるという原理に基づく。この手法では垂直方向への一様なサンプリングと、現在の垂直位置の水平方向への、密度関数の「スライス」のサンプリングが交互に行われる。
• MTM アルゴリズム（英語版）：M-H アルゴリズムの変種で各点において複数の試行を行う。一般的にこの手法は一回ごとの歩幅を大きめにとることができ、高次元にまつわる問題の解消に役立つ。

散漫な動きの回避

マルコフ連鎖モンテカルロ法の効率を下げる要因の一つは、マルコフ連鎖が近い状態を行きつ戻りつする散漫 (diffusive) な動きである。散漫な動きを防ぐ工夫を持つアルゴリズムが様々提案されている。これらのアルゴリズムは実装が難しくなるが、より高速な収束を得られる可能性がある。つまり、少ない試行から正確な結果を得られるということである。

• SOR法 – モンテカルロ法を応用したSOR法はギブスサンプリングの一種とみなすことができ、散漫な動きを避けることがある。
• ハイブリッドモンテカルロ法（HMC法）– ハミルトニアン・モンテカルロ法とも。補助の運動量ベクトルを導入しポテンシャルが対象となる確率分布の負の対数密度関数となるハミルトニアンを構築する。標準的な方法では，ハミルトニアン方程式を近似的に解く確定的動きと、運動量ベクトルを更新する確率的動きによって候補を生成する。確定的な動きのおかげでHMC法でのマルコフ連鎖は標本空間をより大きなステップで移動し、相関が弱く、目標の分布により素早く収束することが期待される。
• NUTS法 – ベイズ統計学で広く用いられる、統計モデリングプラットフォームである Stan では、HMC法の変法である NUTS法^[4]（No-U-Turn Sampler）が採用されている。
• スライスサンプリングの一部は散漫な動きを回避する^[5]。

次元の変化

リバーシブルジャンプ法（英語版）はメトロポリス・ヘイスティングス法の拡張で、次元の異なる空間からの候補を許容する。この手法は1995年にブリストル大学のピーター・グリーン（Peter Green）によって考案された^[6]。次元の変化する MCMC は分布が大正準集団である問題（箱の中の分子の数が変動する場合など）を解くのに統計力学の分野で長い間使われている。

脚注

1. 来嶋 & 松井 2005a.
2. 来嶋 & 松井 2005b.
3. 来嶋 & 松井 2005c.
4. Hoffman, Matthew D.; Gelman, Andrew (April 2014). “The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo”. Journal of Machine Learning Research 15: 1593-1623. http://jmlr.org/papers/v15/hoffman14a.html.
5. Radford M. Neal (2003). “Slice sampling”. The Annals of Statistics (Institute of Mathematical Statistics) 31 (3): 705 -767. doi:10.1214/aos/1056562461. https://doi.org/10.1214/aos/1056562461.
6. GREEN, PETER J. (1995-12). “Reversible jump Markov chain Monte Carlo computation and Bayesian model determination”. Biometrika 82 (4): 711-732. doi:10.1093/biomet/82.4.711. ISSN 0006-3444. https://doi.org/10.1093/biomet/82.4.711.

参考文献

• 『オペレーションズ・リサーチ』第50巻、日本オペレーションズ・リサーチ学会、2005年1月、ISSN 00303674。
  • 来嶋秀治, 松井知己「完璧にサンプリングしよう!(1)遥かなる過去から」（PDF）第50巻第3号、2005年3月。
  • 来嶋秀治, 松井知己「完璧にサンプリングしよう!(第2話)天と地の狭間で」（PDF）第50巻第4号、2005年4月。
  • 来嶋秀治, 松井知己「完璧にサンプリングしよう!(第3話)終わりある未来」（PDF）第50巻第5号、2005年5月。
• Gill, Jeff (2008). Bayesian methods: a social and behavioral sciences approach (Second Edition ed.). London: Chapman and Hall/CRC. ISBN 1-58488-562-9. http://worldcat.org/isbn/1-58488-562-9
• Robert, Christian P; Casella, G (2004). Monte Carlo statistical methods (Second Edition ed.). New York: Springer. ISBN 0-387-21239-6. http://worldcat.org/isbn/0-387-21239-6

• 大森裕浩「マルコフ連鎖モンテカルロ法の最近の展開」『日本統計学会誌』第31巻第3号、日本統計学会、2001年12月、305-344頁、ISSN 03895602、国立国会図書館書誌ID:6910356。
• C.M. ビショップ, "パターン認識と機械学習下: ベイズ理論による統計的予測". シュプリンガー・ジャパン株式会社, 2008.
• 来嶋秀治, 松井知己「平衡状態を探す:マルコフ連鎖/CFTP」『数学セミナー』第43巻第8号、日本評論社、2004年8月、42-46頁、ISSN 03864960、国立国会図書館書誌ID:7026567。
• 福島孝治, マルコフ連鎖モンテカルロ法の実践, 2005年度東京工業大学大学院総合理工研究科知能システム科学特別講義資料
• Christophe Andrieu et al, "An Introduction to MCMC for Machine Learning", 2003
• Bernd A. Berg. "Markov Chain Monte Carlo Simulations and Their Statistical Analysis". Singapore, World Scientific 2004.
• George Casella and Edward I. George. "Explaining the Gibbs sampler". The American Statistician, 46:167-174, 1992. (Basic summary and many references.)
• A.E. Gelfand and A.F.M. Smith. "Sampling-Based Approaches to Calculating Marginal Densities". J. American Statistical Association, 85:398-409, 1990.
• Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. London: Chapman and Hall. First edition, 1995. (See Chapter 11.)
• S. Geman and D. Geman. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741, 1984.
• Radford M. Neal, Probabilistic Inference Using Markov Chain Monte Carlo Methods, 1993.
• Gilks W.R., Richardson S. and Spiegelhalter D.J. "Markov Chain Monte Carlo in Practice". Chapman & Hall/CRC, 1996.
• C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.
• R. Y. Rubinstein and D. P. Kroese. "Simulation and the Monte Carlo Method" (second edition). New York: John Wiley & Sons, 2007.
• R. L. Smith "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions", Operations Research, Vol. 32, pp. 1296-1308, 1984.
• Asmussen and Glynn "Stochastic Simulation: Algorithms and Analysis", Springer. Series: Stochastic Modelling and Applied Probability, Vol. 57, 2007.
• P. Atzberger, An Introduction to Monte-Carlo Methods.
• A Mantzaris, MCMC sampling and other methods in a basic overview.

関連項目

• ベイズ推定
• 逐次モンテカルロ法
• 焼きなまし法
• 魔方陣、ラテン方陣
• メトロポリス法
• メトロポリス・ヘイスティングス法
• 量子モンテカルロ法
• パラレルテンパリング
• レプリカ交換法