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

マルコフ連鎖モンテカルロ法（マルコフれんさモンテカルロほう、英: 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 は分布が大正準集団である問題（箱の中の分子の数が変動する場合など）を解くのに統計力学の分野で長い間使われている。

脚注

^ 来嶋 & 松井 2005a.
^ 来嶋 & 松井 2005b.
^ 来嶋 & 松井 2005c.
^ 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.
^ Radford M. Neal (2003). “Slice sampling”. The Annals of Statistics (Institute of Mathematical Statistics) 31 (3): 705 -767. doi:10.1214/aos/1056562461.
^ 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.

参考文献

『オペレーションズ・リサーチ』第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
Robert, Christian P; Casella, G (2004). Monte Carlo statistical methods (Second Edition ed.). New York: Springer. 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.

表話編歴確率分布
離散単変量で有限台	ベンフォードベルヌーイベータ二項（英語版）二項 categorical（英語版）超幾何ポワソン二項ラーデマッハ（英語版）離散一様ジップジップ–マンデルブロー（英語版）
離散単変量で無限台	ベータ負二項（英語版）ボレル（英語版）コンウェイ–マクスウェル–ポワソン（英語版）離散位相型（英語版）ドラポルト（英語版）拡張負二項（英語版）ガウス–クズミン幾何対数（英語版）負の二項放物フラクタル（英語版）ポワソンスケラム（英語版）ユール–サイモン（英語版）ゼータ（英語版）
連続単変量で有界区間に台を持つ	逆正弦（英語版） ARGUS（英語版）バルディング–ニコルス（英語版）ベイツ（英語版）ベータ beta rectangular（英語版）アーウィン–ホール（英語版）クマラスワミー（英語版）ロジット-正規（英語版）非中心ベータ（英語版） raised cosine（英語版） reciprocal（英語版）三角 U-quadratic（英語版）一様ウィグナー半円
連続単変量で半無限区間に台を持つ	ベニーニ（英語版）ベンクタンダー第一種（英語版）ベンクタンダー第二種（英語版）第2種ベータ Burr（英語版）カイ二乗カイ（英語版） Dagum（英語版）デービス（英語版）指数-対数（英語版）アーラン指数 F folded normal（英語版） Flory–Schulz（英語版）フレシェガンマ gamma/Gompertz（英語版）一般逆ガウス（英語版） Gompertz（英語版） half-logistic（英語版） half-normal（英語版） Hotelling's T-squared（英語版）超アーラン（英語版）超指数（英語版） hypoexponential（英語版）逆カイ二乗（英語版） scaled inverse chi-squared（英語版）逆ガウス逆ガンマコルモゴロフレヴィ対数コーシー対数ラプラス（英語版）対数ロジスティック（英語版）対数正規ロマックス（英語版）行列指数（英語版）マクスウェル–ボルツマンマクスウェル–ユットナー（英語版）ミッタク-レフラー（英語版）仲上（英語版）非心カイ二乗パレート位相型（英語版） poly-Weibull（英語版）レイリー relativistic Breit–Wigner（英語版）ライス（英語版） shifted Gompertz（英語版）切断正規タイプ2ガンベル（英語版）ワイブル離散ワイブル（英語版）ウィルクスのラムダ（英語版）
連続単変量で実数直線全体に台を持つ	コーシー（ローレンツ、ブライト・ウィグナー）指数冪（英語版）フィッシャーの z（英語版）ガウスの q（英語版）一般正規（英語版）一般化双曲型幾何安定（英語版）ガンベルホルツマルク（英語版）双曲線正割ジョンソンの S_U（英語版）ランダウラプラス非対称ラプラス（英語版）ロジスティック非心 t 正規 (ガウス) 正規逆ガウス（英語版）歪正規（英語版）スラッシュ安定スチューデントの t タイプ1ガンベル（英語版）トレイシー–ウィダム（英語版）分散ガンマ（英語版）フォークト
連続単変量でタイプの変わる台を持つ	一般極値一般パレート（英語版）マルチェンコ–パストゥール（英語版） q-指数（英語版） q-ガウス q-ワイブル（英語版） shifted log-logistic（英語版）トゥーキーのラムダ（英語版）
混連続-離散単変量	rectified Gaussian（英語版）
多変量 (結合)	【離散】エウェンズ（英語版）多項ディリクレ多項（英語版）負多項（英語版）【連続】ディリクレ一般ディリクレ（英語版）多変量正規多変量安定（英語版）多変量 t（英語版）正規逆ガンマ（英語版）正規ガンマ（英語版）【行列値】逆行列ガンマ（英語版）逆ウィッシャート（英語版）行列正規（英語版）行列 t（英語版）行列ガンマ（英語版）正規逆ウィッシャート（英語版）正規ウィッシャート（英語版）ウィッシャート
方向	【単変量 (円周) 方向】円周一様（英語版）単変数フォン・ミーゼス wrapped 正規（英語版） wrapped コーシー（英語版） wrapped 指数（英語版） wrapped 非対称ラプラス（英語版） wrapped レヴィ（英語版）【二変量 (球面)】ケント（英語版）【二変量 (トロイダル)】二変数フォン・ミーゼス（英語版）【多変量】フォン・ミーゼス–フィッシャー（英語版）ビンガム（英語版）
退化と特異	【退化】ディラックのデルタ関数【特異】カントール
族	円周（英語版）混合ポワソン（英語版）楕円（英語版）指数自然指数（英語版）位置尺度（英語版）最大エントロピー（英語版）混合（英語版）ピアソン（英語版）トウィーディ（英語版） wrapped（英語版）
サンプリング法（英語版）	逆関数サンプリング法マルコフ連鎖モンテカルロ法（メトロポリス・ヘイスティングス法・ギブスサンプリング・スライスサンプリング）粒子フィルタボックス＝ミュラー法棄却サンプリング（英語版）ジッグラト法（英語版）マルサグリア法（英語版）
一覧（英語版）カテゴリ

ランダムウォーク法

散漫な動きの回避

次元の変化

脚注

参考文献

関連項目