马尔可夫链仿真推理

14.5.2 马尔可夫链仿真推理

在本节中我们描述贝叶斯网络推理的马尔可夫链蒙特卡洛方法（Markov chain Monte Carlo，缩写为 MCMC）。我们首先描述算法做什么，然后阐述其工作机理，并解释为什么会有这么复杂的一个名字。

一、马尔可夫链蒙特卡洛（MCMC）算法

和其它两种为每个事件都重新生成样本的采样算法不同，马尔可夫链蒙特卡洛算法总是通过对前一个事件进行随机改变而生成每个事件样本。因此可以认为网络处于为每一个变量指定了值的一个特定的当前状态。而下一个状态则通过对某个非证据变量 Xi 进行采样来产生，取决于Xi的马尔可夫覆盖中的变量当前值（回忆一下，第 14.2.2 节中的单变量马尔可夫覆盖是由节点的父节点、子节点以及子节点的父节点组成的）。因此马尔可夫链蒙特卡洛方法可以被视为在状态空间中——所有可能的完整赋值的空间——的随机走动——每次改变一个变量，但是保持证据变量的值固定不变。

考虑把查询P(Rain|Sprinkler=true,WetGrass=true)应用于图14.11（a）中所示的网络。证据变量Sprinkler和WetGRass固定为它们的观察值，而隐变量Cloudy和Rain则随机地初始化——比如，分别为true和false。因此，初始状态为[true, true, false, true]。现在，反复执行下面的步骤：

（1）对Cloudy采样，给定它的马尔可夫覆盖变量的当前值：在这里，我们根据P(Cloudy|Sprinkler =true, Rain = false)来采样。（不久，我们将说明如何计算这个分布）。假设采样的结果为Cloudy =false。那么新的当前状态是[false, true, false, true]。

（2）对节点Rain采样，给定它的马尔可夫覆盖变量的当前值：在这里，我们要根据P(Rain|Cloudy= false, Sprinkler = true, WetGrass = true)进行采样。假设采样结果为Rain = true。新的当前状态是[false, true, true, true]。

这个过程中所访问的每一个状态都是一个样本，能对查询变量Rain的估计有所贡献。如果这个过程访问了20个Rain为真的状态和60个Rain为假的状态，则所求查询的解为NORMALIZE(20,60)=0.25, 0.75。完整的算法如图14.15所示。

图14.15 贝叶斯网络推理中的MCMC算法（图中MB(Zi)表示节点Zi的马尔可夫覆盖，而mb(Zi)则表示其一种取值——译者注。）

二、MCMC的工作机理

现在我们要证明 MCMC 能够为后验概率返回一致估计。这一节的材料技术性很强，但基本观点却是非常直接的：采样过程最终会进入一种“动态平衡”，处于这样的情况下，长期来看在每个状态上花费的时间都与其后验概率成正比。这个不寻常的特性来自于特定的转移概率（transition probability），也就是过程从一种状态转移到另一种状态的概率，通过被采样变量在给定马尔可夫覆盖下的条件概率分布而定义。

令q(x → x')为过程从状态x转移到状态x'的概率。这个转移概率定义了状态空间上的所谓马尔可夫链（Markov chain）。（在第十五章和第十七章中还将着重描绘马尔可夫链）。现在假设马尔可夫链已经运行了t步（时刻t），并令πt(x)为系统在时刻t处于状态x的概率。类似地，令πt+1(x')表示在时刻t+1处于状态x' 的概率。给定πt(x)，我们可以对于算法可能于时刻t到达的所有状态，通过对处于该状态的概率与从该状态转移到状态x' 的概率的乘积求和来计算πt+1(x')：

当πt=πt+1时，我们说马尔可夫链到达了其稳态分布（stationary distribution）。让我们称之为稳态分布π；因此其定义式可以写成：

在某些关于转移概率分布q的标准假设下1，对于任何给定的q都正好存在一个分布π满足这个公式。

公式（14.9）可以认为表达了这样一个事实：从每个状态（也就是当前的“总体”）的期望“流出”等于来自于所有状态的期望“流入”。一个明显满足这个关系的方式是任何两个状态之间沿两个方向的期望流量相等。这个性质称为细致平衡（detailed balance）：

由q所定义的马尔可夫链必须是可遍历的（ergodic）——也就是说，从每个状态出发都一定可到达其它每个状态，并且其中没有严格的周期环（strictly periodic cycle）。

简单地通过对公式（14.10）中的x求和，我们就可以证明细致平衡中蕴涵着稳态分布：

其中必然得到最后一步，是因为由x'出发的转移是保证会发生的。

现在我们证明通过MCMC-ASK中的采样步骤定义的转移概率q(x → x')满足细致平衡公式，并且其稳态分布等于P(x|e)（即隐变量的真实后验分布）。证明分两步。首先我们定义一个马尔可夫链，其中每个变量被限制在所有其它变量的当前取值条件下进行采样，我们将证明这个马尔可夫链满足细致平衡。然后我们将容易地观察到，对于贝叶斯网络，这等价于在马尔可夫覆盖中的变量上进行条件采样（参见第14.2.2节）。

令Xi表示被采样的节点，表示除Xi以外的所有隐变量。它们在当前状态下的值为 及。如果我们对Xi的一个新的取值x'i在所有其它变量（包括证据变量）上进行条件采样，则有：

此转移概率被称为吉布斯采样器（Gibbs sampler），它是MCMC的一种特别方便的形式。现在我们证明吉布斯采样器满足与真实后验概率一致的细致平衡：

如第14.2.2节所述，给定马尔可夫覆盖的一个变量独立于其它所有变量。因此，

其中，mb(Xi)表示Xi的马尔可夫覆盖MB(Xi)中各变量的取值。如习题14.10所示，给定马尔可夫覆盖后，一个变量的概率正比于给定父节点的变量概率与给定各自父节点的每个子节点条件概率的乘积：

因此，当改变各变量Xi的取值时，所需的乘法次数等于Xi的子节点个数。

这里我们只讨论了马尔可夫链蒙特卡洛方法的一种简单变体，即吉布斯采样器。在它最一般的形式中，MCMC是概率模型计算中的一种强有力的方法，目前已经发展出了很多变形，包括第四章中介绍的模拟退火算法，第七章中介绍的随机可满足性算法（stochastic satisfiability algorithm），以及将在第十五章中讨论的Metropolis-Hastings采样器。