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

提供: miniwiki
2018/8/19/ (日) 17:28時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

マルコフ連鎖モンテカルロ法（マルコフれんさモンテカルロほう、英: Markov chain Monte Carlo methods、MCMC）とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することをもとに、確率分布のサンプリングを行うアルゴリズムの総称である。M-H アルゴリズムやギブスサンプリングなどのランダムウォーク法もこれに含まれる。充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。

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

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

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

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

ランダムウォーク法

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

  • M-H アルゴリズム：提案密度（proposal density）と提案された候補の棄却法を用いてランダムウォークを生成する。
  • ギブスサンプリング：対象となる確率分布の全ての条件付分布が正確にサンプルできることを必要とする。「調整」の必要がないこともこの手法がよく用いられる要因の一つである。
  • スライスサンプリング：密度関数の曲線下の領域を一様にサンプルすることによって確率分布をサンプルすることができるという原理に基づく。この手法では垂直方向への一様なサンプリングと、現在の垂直位置の水平方向への「スライス」のサンプリングが交互に行われる。
  • MTM アルゴリズム（English版）：M-H アルゴリズムの変種で各点において複数の試行を行う。一般的にこの手法は一回ごとの歩幅を大きめにとることができ、高次元にまつわる問題の解消に役立つ。

ランダムウォークの回避

より洗練されたマルコフ連鎖モンテカルロ法は粒子が折り返してしまうのを防ぐなんらかの方策を用いる。これらのアルゴリズムの実装は難しくなるが、より高速な収束を得られることがある。つまり、少ない試行から正確な結果を得られるということである。

  • SOR法：モンテカルロ法を応用したSOR法はギブスサンプリングの一種とみなすことができ、ランダムウォークを避けることがある。
  • ハイブリッドモンテカルロ法（English版）|（HMC法）： ハミルトニアンモンテカルロ法とも。補助の運動量ベクトルを導入しポテンシャルが目標の分布となるハミルトニアンを構築する。サンプリングの後で運動量は標本から棄却される。結果としてHMC法での粒子は標本空間をより大きなステップで移動するため、相関が弱く、目標の分布により素早く収束する。
  • スライスサンプリングの一部はランダムウォークを回避する[2]。

次元の変化

リバーシブルジャンプ法（English版）はM-H アルゴリズムの拡張で、次元の異なる空間からの候補を許容する。この手法は1995年にブリストル大学のピーター・グリーン（Peter Green）によって考案された[3]。次元の変化する MCMC は分布が大正準集団である問題（箱の中の分子の数が変動する場合など）を解くのに統計物理学の分野で長い間使われている。

参考文献

  1. ↑ 来嶋秀治、松井知己、完璧にサンプリングしよう、 "オペレーションズ・リサーチ"，vol. 50 (2005),第一話「遥かなる過去から」, no. 3, pp. 169--174, 第二話「天と地の狭間で」, no. 4, pp. 264--269, 第三話「終りある未来」, no. 5, pp. 329--334.
  2. ↑ Radford M. Neal, "Slice Sampling". The Annals of Statistics, 31(3):705-767, 2003.
  3. ↑ P. J. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82(4):711-732, 1995
  • (2008) Bayesian methods: a social and behavioral sciences approach, Second Edition, London: Chapman and Hall/CRC. ISBN 1-58488-562-9. 
  • (2004) Monte Carlo statistical methods, Second Edition, New York: Springer. ISBN 0-387-21239-6. 
  • 大森裕浩, マルコフ連鎖モンテカルロ法の最近の展開, 日本統計学会誌, 31:305-344，2001.
  • C.M. ビショップ, "パターン認識と機械学習下: ベイズ理論による統計的予測". シュプリンガー・ジャパン株式会社, 2008.
  • 来嶋秀治, 松井知己, 平衡状態を探す：マルコフ連鎖／CFTP, 数学セミナー, vol. 43, NO. 8, 2004年8月号, pp. 42--46.
  • 福島孝治, マルコフ連鎖モンテカルロ法の実践, 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.

関連項目



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=マルコフ連鎖モンテカルロ法&oldid=112227」から取得