MCMC 算法

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

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

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

背景

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

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

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

抽样方式

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

抽样简介

MCMC 采样

随机矩阵

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

算法具体流程

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

M-H 算法

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

具体流程

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

高维适用性

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

小结

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

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

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

Gibbs 采样

二维的流程

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

多维

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

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

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

小结

由于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等。