《深度学习导论及案例分析》一2.12马尔可夫链蒙特卡罗方法

2.12马尔可夫链蒙特卡罗方法

在统计学中，马尔可夫链蒙特卡罗方法是一类根据概率分布进行采样的方法，起源于物理学科［133］。这类方法以构造一个马尔可夫链为基础，其期望分布（desired distribution）就是平衡分布（equilibrium distribution）、极限分布（limiting distribution）或稳态分布（stationary disrtibution）。经过若干步骤之后，马尔可夫链的状态便被用作期望分布的一个样本。样本的质量随着步骤数目的增加而不断提高，并且在一定条件下能够渐近地收敛于平衡分布（或真实分布）。

随机游走蒙特卡罗（random walk Monte Carlo）方法是马尔可夫链蒙特卡罗方法的一大子类，其中包括MH算法（MetropolisHastings algorithm）和吉布斯采样（Gibbs sampling）。

MH算法的目的是根据一个期望分布P（X）产生一组马尔可夫过程的状态，逐渐逼近一个唯一的稳态分布Π（X），而且使得Π（X）=P（X）。在直接采样困难时，MH算法可以用来从一个概率分布产生一列随机样本。而这列随机样本能够用来逼近该分布（即生成一个直方图），或者计算一个积分（如一个期望值）。MH算法一般用来从高维分布采样，特别是在维数很高时。对任意概率分布P（X），只要能够计算一个与P(X)的密度成正比的函数值f（X），MH算法就可以从P（X）抽取样本。MH算法生成一列样本的工作目标是：随着产生的样本值越来越多，它们的分布会更加逼近期望分布P（X）。这些样本值是用仅依赖于当前样本值的下一个样本分布，通过一步一步迭代产生的，因此使得产生的样本序列是一个马尔可夫链。具体地说，MH算法首先选择一个转移概率函数P（XY）（如任意一个条件概率密度函数），又称提议密度（proposal density）、提议分布（proposal distribution）或者跳跃分布（jumping distribution）；然后，在每一次迭代中，利用这个转移函数基于当前的样本值挑选下一个样本候选值，并让候选值以一定的概率被接受在下一次迭代中使用，或被拒绝丢弃而在下一次迭代中继续使用当前值。接受的概率是通过比较关于期望分布P(X)的当前采样值和候选采样值的函数值f(X)确定的。在多维变量分布的情况下，如果维数较高，MH算法的缺点是很难找到正确或合适的转移函数。此时，吉布斯采样常常是效果更好的替代方法。

吉布斯采样是在直接采样困难时，从一个特定多变量概率分布得到一列近似样本的算法。这个序列是一个马尔可夫链，也称为吉布斯链（Gibbs chain），能够用来逼近多变量联合分布（如产生一个分布的直方图）、逼近多变量中的一个或若干变量（如未知参数或潜在变量）的边际分布，或者计算一个积分（如其中一个变量的期望值）。吉布斯采样通常被用作一种统计推断（statistical inference）的工具，特别是贝叶斯推断（Bayesian inference）。作为一种随机算法（randomized algorithm），吉布斯采样是确定性统计推断算法（如期望最大化算法）的一种替代算法。吉布斯采样在本质上可以看作是MH算法的特例，其关键在于给定一个多变量分布，从条件分布采样比在联合分布上通过积分求边际更容易。在吉布斯采样中，已知观测值的变量无需采样。假定要从联合概率分布p（x1，…，xn）获得k个样本X=（x1，…，xn）。如果把第i个样本记作Xi=（xi1，…，xin），那么吉布斯采样的详细过程可以由算法2.1描述。

算法2.1吉布斯采样

1.初始化X0=（x01，…，x0n）；

2.根据条件分布p(xi+11xi2，…，xin)采样xi+11；

3.根据条件分布p(xi+1jxi+11，…，xi+1j-1，xij+1，…，xin)采样xi+1j，1<j<n；

4.根据条件分布p(xi+1nxi+11，…，xi+1n-1)采样xi+1n；

5.重复上述步骤k次。