馬可夫鏈蒙地卡羅

馬可夫鏈蒙地卡羅（英語：Markov chain Monte Carlo，MCMC）方法（含隨機漫步蒙地卡羅方法）是一組用馬氏鏈從隨機分布取樣的演算法，之前步驟的作為底本。步數越多，結果越好。

建立一個具有期望值屬性的馬氏鏈並非難事，難的是如何決定通過多少步可以達到在許可誤差內的穩定分布。一個好的馬氏鏈具有快速混合——從開始階段迅速獲得的一個穩定狀態——請參考馬氏鏈最大時間。

因於初始樣本，最常見的MCMC取樣只能近似得到分布。複雜的MCMC改進演算法如過往耦合，但是會消耗更多的計算資源和時間。

典型用法是類比一個隨機行走的行人來進行路徑最佳化等。每一步都算作是一個狀態。而統計經過次數最多的地方將在下一步中更有可能為目的地。馬氏蒙地卡羅方法是一種結合了蒙特卡羅法的解決方案。但不同於以往的蒙地卡羅integration是統計獨立的，MCMC中的是統計相關的。

本方法的相關應用包括：貝氏統計、計算物理、計算生物以及計算語言學，此外還有Gill先生的一些著作。

Jeff Gill. Bayesian methods: a social and behavioral sciences approach Second Edition. London: Chapman and Hall/CRC. 2008 [2012-02-07]. ISBN 1-58488-562-9. （原始內容存檔於2009-05-23）. 引文格式1維護：冗餘文字 (link) </ref> and Robert & Casella.^[1]

隨機漫步演算法

馬氏鏈性質決定了下一個方位取決於當前狀態和隨機變數。這樣的性質決定了最終所有的空間將被覆蓋但是卻需要花費較長時間。下面給出MCMC方法：

• Metropolis–Hastings演算法：給出預見密度和回絕按照給出方向前進的方法。
• 吉布斯採樣：取目標區域所有的條件分布樣本。
• 平滑取樣
• 多重實驗Metropolis：Metropolis–Hastings演算法的改良版本。

基本原理

設非週期正常返的馬可夫鏈的平穩分布為${\displaystyle \pi }$，${\displaystyle S}$為馬可夫鏈的狀態，對於任意${\displaystyle S}$上有界函數${\displaystyle h}$有： ${\displaystyle P(\lim _{n\rightarrow \inf }{\frac {1}{n}}\sum _{k=0}^{n}h(X_{k})=\sum _{x\in S}\pi (x)h(x))=1}$，也就是說，該馬可夫鏈在取的變數${\displaystyle X_{k}}$在${\displaystyle n}$比較大時會趨向於服從機率分布${\displaystyle \pi }$。

在設計一個馬可夫鏈滿足細緻平衡的條件下，對馬爾科夫鏈的類比就可以看作對機率分布${\displaystyle \pi }$的採樣。^[2]

基本步驟

MCMC方法是使用馬爾科夫鏈的蒙地卡羅積分，其基本思想是：構造一條Markov鏈使其平穩分布為待估參數的事後分布${\displaystyle \pi (x)}$，通過這條馬爾科夫鏈產生事後分布的樣本，並基於馬爾科夫鏈達到平穩分布時的樣本（有效樣本）進行蒙特卡羅積分。設${\displaystyle n}$為產生的總樣本數，${\displaystyle m}$為Markov鏈達到平穩時的樣本數則MCMC方法的基本思路可概括為：

• 構造Markov鏈。構造一條Markov鏈，給定馬爾科夫鏈狀態轉移矩陣${\displaystyle Q}$，使其收斂到平穩分布${\displaystyle \pi (x)}$；
• 產生樣本：從初始狀態${\displaystyle x_{0}\sim p_{0}}$出發，利用從條件機率分布${\displaystyle Q(x|x_{t})}$生成樣本，並通過轉移條件判斷是否轉移，通過${\displaystyle m}$次更新達到平穩，此後生成的即為${\displaystyle \pi (x)}$的樣本，我們記為${\displaystyle x^{(1)},\cdots ,x^{(n)}}$；
• 蒙特卡羅積分。任一函數${\displaystyle f(x)}$的期望值估計為：${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}f(x^{(i)})}$

在採用MCMC方法時馬爾科夫鏈轉移核的構造至關重要，不同的轉移核構造方法將產生不同的MCMC方法，目前常用的MCMC方法主要有兩種Gibbs抽樣和Metropolis-Hastings演算法。

抽樣演算法

l Gibbs '抽樣'

Gibbs抽樣是現實中最簡單應用最廣泛的MCMC方法，由Geman最初命名提出其基礎思路如下：

給定任意的初始向量；

從中抽取樣本

從中抽取樣本

…

從中抽取樣本

…

從中抽取樣本

至此，完成的轉移。經過n次迭代，可得後驗樣本。根據後驗樣本可計算事後分布的各階矩，進行相應的統計推論。

• Metropolis-Hastings '演算法'

Metropolis-Hastings演算法是較早出現且比較一般化的MCMC方法，最初由Metropolis等人在1953年提出之後由Hastings對其加以推廣形成了，Metropolis-Hastings方法。該方法的基本思路是：選擇一轉移函數和初始值，若第次迭代開始時的參數值為

，則第次迭代過程為：

• 從中抽取一個備選值

• 計算接受機率

• 以機率，置，以機率，置；
• 重複i –iii 次，則可得後驗樣本。根據後驗樣本可計算事後分布的各階矩，進行相應的統計推論。

參見

• 貝葉斯推理
• 圖模式
• 馬可夫鏈
• 馬可夫邏輯網路

注釋

1. Christian P Robert & Casella G. Monte Carlo statistical methods Second Edition. New York: Springer. 2004 [2012-02-07]. ISBN 0-387-21239-6. （原始內容存檔於2010-01-12）. 引文格式1維護：冗餘文字 (link)
2. 李東風. 统计计算. 2022-08-29 （中文）.

參考文獻

• 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. ISBN 978-0470177945
• 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." [1].
• Bolstad, William M.（2010）Understanding Computational Bayesian Statistics, John Wiley ISBN 0-470-04609-8

延展閱讀

• Diaconis, Persi, "The Markov chain Monte Carlo revolution", Bull. Amer. Math. Soc.（2009）
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP, Section 15.8. Markov Chain Monte Carlo, Numerical Recipes: The Art of Scientific Computing 3rd, New York: Cambridge University Press, 2007 [2012-02-07], ISBN 978-0-521-88068-8, （原始內容存檔於2011-08-11）
• Richey, Matthew, "The Evolution of Markov Chain Monte Carlo Methods", The American Mathematical Monthly, May 2010, 383-413

外部連結

• MCMC sampling and other methods in a basic overview, by Alexander Mantzaris
• Visual demonstration of MCMC sampling methods (Java applet) （頁面存檔備份，存於網際網路檔案館）, by Laird Breyer
• A Toy Example of MCMC sampling, by Zhiyuan Weng
• MCL - a cluster algorithm for graphs （頁面存檔備份，存於網際網路檔案館）, by Stijn van Dongen