马尔可夫链蒙特卡洛

马尔可夫链蒙特卡洛（，）方法（含随机游走蒙特卡洛方法）是一组用马氏链从随机分布取样的算法，之前步骤的作为底本。步数越多，结果越好。

建立一个具有期望属性的马氏链并非难事，难的是如何决定通过多少步可以达到在许可误差内的稳定分布。一个好的马氏链具有快速混合——从开始阶段迅速获得的一个稳定状态——请参考马氏链最大时间。

因于初始样本，最常见的MCMC取样只能近似得到分布。复杂的MCMC改进算法如过往耦合，但是会消耗更多的计算资源和时间。

典型用法是模拟一个随机行走的行人来进行路径优化等。每一步都算作是一个状态。而统计经过次数最多的地方将在下一步中更有可能为目的地。马氏蒙特卡洛方法是一种结合了蒙特卡罗法的解决方案。但不同于以往的蒙特卡洛integration是统计独立的，MCMC中的是统计相关的。

本方法的相关应用包括：贝叶斯统计、计算物理、计算生物学以及计算语言学。

随机游走算法
马氏链性质决定了下一个方位取决于当前状态和随机变量。这样的性质决定了最终所有的空间将被覆盖但是却需要花费较长时间。下面给出MCMC方法：

梅特罗波利斯-黑斯廷斯算法：给出预见密度和回绝按照给出方向前进的方法。
吉布斯采样：取目标区域所有的条件分布样本。
平滑取样
多重实验Metropolis：梅特罗波利斯-黑斯廷斯算法的改良版本。

基本原理
算法的收敛性。马尔科夫链蒙特卡洛尝试用橙色分布逼近蓝色分布。]]

设非周期正常返的马尔可夫链的平稳分布为\pi，S为马尔可夫链的状态，对于任意S上有界函数h有：
P(\lim_{n \rightarrow \inf}\frac{1}{n}\sum_{k=0}^{n}h(X_k) = \sum_{x \in S}\pi(x)h(x))=1，也就是说，该马尔可夫链在取的变量X_k在n比较大时会趋向于服从概率分布\pi。

在设计一个马尔可夫链满足细致平衡的条件下，对马尔科夫链的模拟就可以看作对概率分布\pi的采样。

基本步骤
MCMC方法是使用马尔科夫链的蒙特卡洛积分，其基本思想是：构造一条Markov链使其平稳分布为待估参数的后验分布\pi(x)，通过这条马尔科夫链产生后验分布的样本，并基于马尔科夫链达到平稳分布时的样本（有效样本）进行蒙特卡罗积分。设n为产生的总样本数，m为Markov链达到平稳时的样本数则MCMC方法的基本思路可概括为：

构造Markov链。构造一条Markov链，给定马尔科夫链状态转移矩阵Q，使其收敛到平稳分布\pi(x)；
产生样本：从初始状态x_0\sim p_0出发，利用从条件概率分布Q(x|x_t)生成样本，并通过转移条件判断是否转移，通过m次更新达到平稳，此后生成的即为\pi(x)的样本，我们记为x^{(1)},\cdots,x^{(n)}；
蒙特卡罗积分。任一函数f(x)的期望估计为：\frac{1}{n}\sum_{i=1}^{n} f(x^{(i)})

在采用MCMC方法时马尔科夫链转移核的构造至关重要，不同的转移核构造方法将产生不同的MCMC方法，目前常用的MCMC方法主要有两种：吉布斯採樣和梅特罗波利斯-黑斯廷斯算法。

抽样算法

吉布斯採樣

吉布斯採樣是现实中最简单应用最广泛的MCMC方法，由傑曼兄弟最初命名提出其基础思路如下：

给定任意的初始向量；

从中抽取样本

…

从中抽取样本

…

从中抽取样本

至此，完成的转移。经过n次迭代，可得后验样本。根据后验样本可计算后验分布的各阶矩，进行相应的统计推断。

梅特羅波利斯-黑斯廷斯算法

梅特羅波利斯-黑斯廷斯算法是较早出现且比较一般化的MCMC方法，最初由尼古拉斯·梅特羅波利斯等人在1953年提出之后由W·K·黑斯廷斯对其加以推广形成了梅特羅波利斯-黑斯廷斯算法。该方法的基本思路是：选择一转移函数和初始值，若第次迭代开始时的参数值为

，则第次迭代过程为：

从中抽取一个备选值

计算接受概率

以概率，置，以概率，置；
重复i –iii 次，则可得后验样本。根据后验样本可计算后验分布的各阶矩，进行相应的统计推断。

参见
*贝叶斯推理

圖模式
马尔可夫链
马尔可夫逻辑网络

注释
参考文献

Christophe Andrieu et al., [http://www.cs.princeton.edu/courses/archive/spr06/cos598C/papers/AndrieuFreitasDoucetJordan2003.pdf "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, [http://www.cs.utoronto.ca/~radford/review.abstract.html 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." [https://web.archive.org/web/20090220065530/http://www.math.ucsb.edu/~atzberg/spring2006/monteCarloMethod.pdf].
Bolstad, William M.（2010）Understanding Computational Bayesian Statistics, John Wiley ISBN 0-470-04609-8

延展阅读

Diaconis, Persi, [http://www.ams.org/bull/2009-46-02/S0273-0979-08-01238-X/S0273-0979-08-01238-X.pdf "The Markov chain Monte Carlo revolution"], Bull. Amer. Math. Soc.（2009）

*
*Richey, Matthew, "The Evolution of Markov Chain Monte Carlo Methods", The American Mathematical Monthly, May 2010, 383-413

外部链接
*[https://web.archive.org/web/20110531150413/http://www.bioss.ac.uk/students/alexm/MCMCintroPresentation.pdf MCMC sampling and other methods in a basic overview], by Alexander Mantzaris
*[http://www.lbreyer.com/classic.html Visual demonstration of MCMC sampling methods (Java applet)] , by Laird Breyer
*[https://web.archive.org/web/20120316212706/http://www.ece.sunysb.edu/~zyweng/MCMCexample.html A Toy Example of MCMC sampling], by Zhiyuan Weng
*[http://micans.org/mcl/ MCL - a cluster algorithm for graphs] , by Stijn van Dongen

评论 (0)