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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

マルコフ連鎖モンテカルロ法(マルコフれんさモンテカルロほう、: Markov chain Monte Carlo methods、MCMC)とは、求める確率分布均衡分布として持つマルコフ連鎖を作成することをもとに、確率分布のサンプリングを行うアルゴリズムの総称である。具体的には、同時事後分布に従う乱数を継時的に生成する(例:θ(a)(a=1,…,A)とするとき、第1期から第A期までを生成するのであるが、このときバーンイン期間の乱数を切り捨てて、バーンイン期間以降からA期までのチェインを、継時aに沿って、トレースプロットとして表現する)。

代表的なマルコフ連鎖モンテカルロ法としてM-H アルゴリズムギブスサンプリングがある。充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。

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

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

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

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

ランダムウォーク法[編集]

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

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

散漫な動きの回避[編集]

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

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

次元の変化[編集]

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

参考文献[編集]

  1. ^ 来嶋秀治、松井知己、完璧にサンプリングしよう、 "オペレーションズ・リサーチ",vol. 50 (2005),第一話「遥かなる過去から」, no. 3, pp. 169--174, 第二話「天と地の狭間で」, no. 4, pp. 264--269, 第三話「終りある未来」, no. 5, pp. 329--334.
  2. ^ 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: pp. 1593–1623. http://jmlr.org/papers/v15/hoffman14a.html. 
  3. ^ Radford M. Neal, "Slice Sampling". The Annals of Statistics, 31(3):705-767, 2003.
  4. ^ P. J. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82(4):711-732, 1995
  • 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 
  • 大森裕浩, [www.omori.e.u-tokyo.ac.jp/MCMC/mcmc.pdf マルコフ連鎖モンテカルロ法の最近の展開], 日本統計学会誌, 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.

関連項目[編集]