マルコフ連鎖モンテカルロ法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/07 09:50 UTC 版)
ナビゲーションに移動 検索に移動出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。(2016年3月) |
MCMCで充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。
求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適切な連鎖なら任意の位置から始めても定常分布に速く達し、これを高速混合(rapid mixing)とよぶ。
典型的なMCMCは常にある程度の初期値の影響が残るため目標分布しか近似することができない。CFTP法(coupling from the past)などの、より洗練されたMCMCベースのアルゴリズムは完全標本を作成することができるが、より多くの計算と(期待値では有限だが)限界のない実行時間を要する[1]。
このアルゴリズムの最も一般的な応用は多重積分を数値的に計算することである。ランダムに歩き回る粒子の集団を想定し、粒子が点を通過するたびに、その点の被積分関数の値を積分に加算する。粒子は次に積分への貢献が高い所を探して複数の仮の動作をする。このような方法はランダムウォーク法とよばれ、これは乱数的なシミュレーションつまりモンテカルロ法の一種である。従来のモンテカルロ法で用いられる被積分関数のランダムな標本が独立であるのに対して、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法[2](No-U-Turn Sampler)が採用されている。
- スライスサンプリングの一部は散漫な動きを回避する[3]。
- ^ 来嶋秀治、松井知己、完璧にサンプリングしよう、 "オペレーションズ・リサーチ",vol. 50 (2005),第一話「遥かなる過去から」, no. 3, pp. 169--174, 第二話「天と地の狭間で」, no. 4, pp. 264--269, 第三話「終りある未来」, no. 5, pp. 329--334.
- ^ 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 .
- ^ Radford M. Neal, "Slice Sampling". The Annals of Statistics, 31(3):705-767, 2003.
- ^ P. J. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82(4):711-732, 1995
- 1 マルコフ連鎖モンテカルロ法とは
- 2 マルコフ連鎖モンテカルロ法の概要
- 3 次元の変化
- マルコフ連鎖モンテカルロ法のページへのリンク