马尔科夫蒙特卡洛

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

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

本方法的相关应用包括:贝叶斯统计计算物理计算生物以及计算语言学,此外还有Gill先生的一些著作。

Jeff Gill. Bayesian methods: a social and behavioral sciences approach Second Edition. London: Chapman and Hall/CRC. 2008. ISBN 1-58488-562-9.  </ref> and Robert & Casella.[1]

随机游走算法[编辑]

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

基本步序[编辑]

MCMC方法是使用马尔科夫链的蒙特卡罗积分,其基本思想是:构造一条Markov链使其平稳分布为待估参数的后验分布,通过这条马尔科夫链产生后验分布的样本,并基于马尔科夫链达到平稳分布时的样本(有效样本)进行蒙特卡罗积分。设17px为某一空间n为产生的总样本数m为链条达到平稳时的样本数则 MCMC方法的基本思路可概括为:

  • 构造Markov链。构造一条Markov链,使其收敛到平稳分布35px
  • 产生样本:由17px中的某一点25px出发,用i中的Markov链进行抽样模拟,产生点序列:73px
  • 蒙特卡罗积分。任一函数36px的期望估计为:180px

在采用MCMC方法时马尔科夫链转移核的构造至关重要,不同的转移核构造方法将产生不同的MCMC方法,目前常用的MCMC方法主要有两种Gibbs抽样和Metropo-Lis-Hastings算法。

抽样算法[编辑]

l Gibbs '抽样'

Gibbs抽样是现实中最简单应用最广泛的MCMC方法,由Geman最初命名提出其基础思路如下:

给定任意的初始向量119px

119px中抽取样本24px

121px中抽取样本24px

121px中抽取样本24px

121px中抽取样本24px

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

  • Metropolis-Hastings '算法'

Metropolis-Hastings算法是较早出现且比较一般化的MCMC方法,最初由Metropolis等人在1953年提出之后由Hastings对其加以推广形成了,Metropolis-Hastings方法。该方法的基本思路是:选择一转移函数68px和初始值25px,若第9px次迭代开始时的参数值为

33px,则第29px次迭代过程为:

  • 计算接受概率253px
  • 以概率73px,置52px,以概率93px,置69px
  • 重复i –iii 次,则可得后验样本101px。根据后验样本可计算后验分布的各阶矩,进行相应的统计推断。

参见[编辑]

注释[编辑]

  1. ^ Christian P Robert & Casella G. Monte Carlo statistical methods Second Edition. New York: Springer. 2004. ISBN 0-387-21239-6. 

参考文献[编辑]

  • 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

延展阅读[编辑]

外部链接[编辑]