Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

马尔可夫链蒙特卡尔理论

马尔可夫链蒙特卡洛方法(MCMC)本质上是将马尔可夫链用于对蒙特卡洛方法的积分过程中,贝叶斯学派(有时亦包括频率派学者)常常需要对高维概率分布进行积分,从而推断出其模型的参数,或利用模型作出预测。传统蒙特卡洛积分的理念是从所要求的概率分布中进行抽样、得到样品平均值、并估算出期望值;而MCMC则是在抽样分布中构造出一条马尔可夫链,即建立一个随机抽样过程,弥补了传统蒙特卡洛积分过去只能静态模拟的缺陷,并为贝叶斯理论在高维分布的应用开辟了新的道路。目前有许多种算法来构造这样一条马尔可夫链,但所有的算法,甚至包括*吉布斯采样*,都是*梅特罗波利斯-黑斯廷斯算法(Metropolis–Hastings algorithm)*总体框架的特例。

简介

马尔可夫链蒙特卡洛方法(MCMC)本质上是将马尔可夫链用于对蒙特卡洛方法的积分过程中,贝叶斯学派(有时亦包括频率派学者)常常需要对高维概率分布进行积分,从而推断出其模型的参数,或利用模型作出预测。传统蒙特卡洛积分的理念是从所要求的概率分布中进行抽样、得到样品平均值、并估算出期望值;而MCMC则是在抽样分布中构造出一条马尔可夫链,即建立一个随机抽样过程,弥补了传统蒙特卡洛积分过去只能静态模拟的缺陷,并为贝叶斯理论在高维分布的应用开辟了新的道路。目前有许多种算法来构造这样一条马尔可夫链,但所有的算法,甚至包括吉布斯采样,都是梅特罗波利斯-黑斯廷斯算法(Metropolis–Hastings algorithm)总体框架的特例。

(描述来源:“Markov Chain Monte Carlo in Practice” byW.R. Gilks,S. Richardson,David Spiegelhalter)

定义:马尔可夫链蒙特卡洛方法是一种将马尔可夫链用于概率分布抽样的方法,多用于对贝叶斯推断及数值积分的数据模型中。

算法:

  1. 梅特罗波利斯-黑斯廷斯算法:通过使用预见密度(proposal density)和回绝其中一些移动的方法构造出一条随机游走过程(Random Walk)。
  2. 吉布斯采样:这种方法需要取所有目标分布的条件分布来作为样本。
  3. 切片采样:该算法基于一种前提,即可以通过均匀地对密度函数曲线下的区域进行抽样,从而实现对该分布的抽样方法。
  4. 多重实验梅特罗波利斯算法:是一种对梅特罗波利斯-黑斯廷斯算法的改良算法,从而帮助解决维数灾难问题。
  5. 可逆跳转算法:一种基于梅特罗波利斯-黑斯廷斯算法改良,允许改变空间维度的算法。

(描述来源:https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo)

基本思路:

通过贝叶斯原理已知,对于某概率密度函数$f(x)$,其期望值可用以下公式表示:

$$E\[f(X)\] = \frac{\int f(x) \pi (x) dx}{\int \pi (x) dx}$$

*其中$\pi (x)$为贝叶斯统计学中的后验概率函数

蒙特卡洛积分通过从$\pi (.)$抽取样本集合$\{X_t, t = 1,...,n\}$对以上期望值进行估算:

$$E\[f(X)\] \sim \frac{1}{n} \sum^{n}_{t=1}f(X_t)$$

运用不同的算法构建一条马尔可夫链,并使其收敛到$\pi (.)$, 之后从样本集合$\{X_t\}$中的某一点$x^{(0)}$出发,并利用之前构建的马尔可夫链进行抽样模拟,抽取的新样本集合为$\{X^(i), 1 \leq i \leq n \}$,最后得到新的蒙特卡洛积分,即遍历均值(Ergodic average):

$$\bar{f} = \frac{1}{n-m} \sum^{n}_{t=m+1} f(X_t)$$

(描述来源:“Markov Chain Monte Carlo in Practice” by W.R. Gilks,S. Richardson,David Spiegelhalter )

发展历史

描述

蒙特卡洛方法于1950年左右起源于摩纳哥蒙特卡洛市的赌场,而MCMC则由梅特罗波利斯于1953年在洛斯阿拉莫斯国家实验室提出。那时美国洛斯阿拉莫斯是当时少数几个拥有大规模计算机的城市,梅特罗波利斯则利用这种计算优势,在蒙特卡洛方法的基础上引入马尔可夫链,用于模拟某种液体在气化之后的平衡状态。此后随着计算机的大规模普及,梅特罗波利斯算法成功于七十年代引起了统计学家的注意,该算法于1970年由多伦多大学统计学家黑斯廷斯完善,并发表了论文《使用马尔可夫链的蒙特卡洛抽样方法及其应用》,从而创立了梅特罗波利斯-黑斯廷斯算法,为MCMC建立了理论框架。

(描述来源:Introduction to Markov Chain Monte Carloby Charles J. Geyer)

主要事件

1950

蒙特卡洛方法成立

n.a.

1953

梅特罗波利斯将蒙特卡洛方法引入马尔可夫链

Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward (1953). "Equation of State Calculations by Fast Computing Machines".

1984

格曼兄弟首次提出吉布斯采样

Geman, S.; Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1984, 6 (6): 721–741. doi:10.1109/TPAMI.1984.4767596

2000

多重实验梅特罗波利斯算法由三位中国学者首次提出

Liu, J. S., Liang, F. and Wong, W. H. (2000). The multiple-try method and local optimization in Metropolis sampling, Journal of the American Statistical Association, 95(449): 121-134 JSTOR

发展分析

瓶颈

  1. MCMC运行速度慢于普通蒙特卡洛方法或其他抽样方法(在保证同等准确率下需要更多的样本资源)。
  2. 目前的算法很难检测其准确性及其收敛性。

(描述来源:ST407 Lecture Notes, University of Warwick, Statistics Department)

未来发展方向

试图把目前存在的许多次优算法与MCMC相结合将会对解决机器学习领域的很多问题提供无限可能,目前得益于抽样算法的机器学习领域有:

  1. 计算视觉:追踪,立体匹配,色恒定性,老电影修复,图像分割等
  2. 网页统计:估算搜索引擎的覆盖范围
  3. 声音处理:信号增强
  4. 回归与分类:神经网络与核机器,高斯过程,CART,MARS等

(描述来源:An Introduction to MCMC for Machine Learningby CHRISTOPHE ANDRIEU, NANDO DE FREITAS, ARNAUD DOUCET, MICHAEL I. JORDAN)

Contributor: Han Zhang

简介