MCMC 算法

前面学习了 马尔科夫蒙特卡罗算法

蒙特卡罗的核心是寻找一个随机的序列,那么二者结合会有怎样的火花呢?

从名字我们可以看出,MCMC由两个MC组成,即蒙特卡罗方法(Monte Carlo Simulation,简称MC)和马尔科夫链(Markov Chain ,也简称MC)。

背景

给定一个的概率分布 P(x), 我们希望产生服从该分布的样本。

前面介绍过一些随机采样算法(如拒绝采样、重要性采样)可以产生服从特定分布的样本,但是这些采样算法存在一些缺陷(如难以选取合适的建议分布,只适合一元随机变量等)。

下面将介绍一种更有效的随机变量采样方法:MCMC 和 Gibbs采样,这两种采样方法不仅效率更高,而且适用于多元随机变量的采样。

抽样方式

我们是如此的需要随机抽样,而样本的构建却有各种各样的问题。

抽样简介

MCMC 采样

随机矩阵

在MCMC采样中先随机一个状态转移矩阵Q,然而该矩阵不一定能满足细致平稳定理,一次会做一些改进,具体过程如下

image

算法具体流程

MCMC采样算法的具体流程如下

image

M-H 算法

然而关于MCMC采样有收敛太慢的问题,所以在MCMC的基础上进行改进,引出M-H采样算法

image

具体流程

M-H 算法的具体流程如下

image

高维适用性

M-H算法在高维时同样适用

image

小结

一般来说M-H采样算法较MCMC算法应用更广泛,然而在大数据时代,M-H算法面临着两个问题:

1)在高维时的计算量很大,算法效率很低,同时存在拒绝转移的问题,也会加大计算量

2)由于特征维度大,很多时候我们甚至很难求出目标的各特征维度联合分布,但是可以方便求出各个特征之间的条件概率分布(因此就思考是否能只知道条件概率分布的情况下进行采样)。

Gibbs 采样

image

image

二维的流程

因此可以得出在二维的情况下Gibbs采样算法的流程如下

image

多维

而在多维的情况下,比如一个n维的概率分布π(x1, x2, …xn),我们可以通过在n个坐标轴上轮换采样,来得到新的样本。

对于轮换到的任意一个坐标轴xi上的转移,马尔科夫链的状态转移概率为 P(xi|x1, x2, ..., xi−1, xi+1, ..., xn),即固定n−1个坐标轴,在某一个坐标轴上移动。

而在多维的情况下Gibbs采样算法的流程如下

image

小结

由于Gibbs采样在高维特征时的优势,目前我们通常意义上的MCMC采样都是用的Gibbs采样。

当然Gibbs采样是从M-H采样的基础上的进化而来的,同时Gibbs采样要求数据至少有两个维度,一维概率分布的采样是没法用Gibbs采样的,这时M-H采样仍然成立。

其他算法

除了最常见的MH那几个算法,后来还有很多新的比较惊艳的算法出现,比如说slice sampling,elliptical slice sampling,generalized elliptical slice sampling,上面说的BPS, forward event chain MC,还有和神经网络结合的NNGHMC,A-Nice-MC,以及利用了batch optimization思想的stochastic gradient HMC以及stochastic gradient Langevin dynamic等。

参考资料

统计之都-MCMC

HANS-MCMC 算法及其应用

知乎-MCMC 专栏

机器学习之MCMC算法

知乎-MCMC 算法

知乎-MCMC 算法中接受概率是什么意思

MCMC 和 Metropolis–Hastings 算法

马尔可夫链蒙特卡洛(MCMC)算法

CSDN-MCMC

MCMC相关算法介绍及代码实现

算法资料

http://civs.stat.ucla.edu/MCMC/MCMC_tutorial.htm

http://www.soe.ucsc.edu/classes/cmps290c/Winter06/paps/mcmc.pdf

http://public.lanl.gov/kmh/talks/maxent00b.pdf

http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo


google keywords: MCMC tutorial


MCMC preprint service:

http://www.statslab.cam.ac.uk/~mcmc/


David MacKay’s book (electronic version availiable):

http://www.inference.phy.cam.ac.uk/mackay/itila/

Radford M. Neal’s review: Probabilistic Inference using Markov Chain Monte Carlo Methods

http://www.cs.toronto.edu/~radford/review.abstract.html