17.3 马尔可夫链蒙特卡罗方法
在许多实例中，我们希望采用蒙特卡罗方法，然而往往又不存在一种简单的方法可以直接从目标分布pmodel(x)中精确采样或者一个好的（方差较小的）重要采样分布q(x)。在深度学习中，当分布pmodel(x)表示成无向模型时，这种情况往往会发生。在这种情况下，为了从分布pmodel(x)中近似采样，我们引入了一种称为马尔可夫链（Markov Chain）的数学工具。利用马尔可夫链来进行蒙特卡罗估计的这一类算法被称为马尔可夫链蒙特卡罗（Markov Chain Monte Carlo，MCMC）方法。Koller and Friedman（2009）花了大量篇幅来描述马尔可夫链蒙特卡罗算法在机器学习中的应用。MCMC技术最标准、最一般的理论保证只适用于那些各状态概率均不为零的模型。因此，这些技术最方便的使用方法是用于从基于能量的模型（Energy-based model）即p(x)∝exp(−E(x))中采样，见第16.2.4节。在EBM的公式表述中，每一个状态所对应的概率都不为0。事实上，MCMC方法可以被广泛地应用在包含0概率状态的许多概率分布中。然而，在这种情况下，关于MCMC方法性能的理论保证只能依据具体不同类型的分布具体分析证明。在深度学习中，我们通常依赖于那些一般的理论保证，其在所有基于能量的模型都能自然成立。
为了解释从基于能量的模型中采样困难的原因，我们考虑一个包含两个变量的EBM的例子，记p(a,b)为其分布。为了采a，我们必须先从p(a｜b)中采样；为了采b，我们又必须从p(b｜a)中采样。这似乎成了棘手的先有鸡还是先有蛋的问题。有向模型避免了这一问题因为它的图是有向无环的。为了完成原始采样（ancestral sampling），在给定每个变量的所有父结点的条件下，我们根据拓扑顺序采样每一个变量，这个变量是确定能够被采样的（详见第16.3节）。原始采样定义了一种高效的、单遍的方法来抽取一个样本。
在EBM中，我们通过使用马尔可夫链来采样，从而避免了先有鸡还是先有蛋的问题。马尔可夫链的核心思想是从某个可取任意值的状态x出发。随着时间的推移，我们随机地反复更新状态x。最终x成为了一个从p(x)中抽出的（非常接近）比较一般的样本。在正式的定义中，马尔可夫链由一个随机状态x和一个转移分布T(x＇｜x)定义而成，T(x＇｜x)是一个概率分布，说明了给定状态x的情况下随机地转移到x＇的概率。运行一个马尔可夫链意味着根据转移分布T(x＇｜x)采出的值x＇来更新状态x。
为了给出MCMC方法为何有效的一些理论解释，重参数化这个问题是很有用的。首先我们关注一些简单的情况，其中随机变量x有可数个状态。我们将这种状态简单地记作正整数x。不同的整数x的大小对应着原始问题中x的不同状态。
接下来我们考虑如果并行地运行无穷多个马尔可夫链的情况。不同马尔可夫链的所有状态都采样自某一个分布q(t)(x)，在这里t表示消耗的时间数。开始时，对每个马尔可夫链，我们采用一个分布q0来任意地初始化x。之后，q(t)与所有之前运行的马尔可夫链有关。我们的目标是q(t)(x)收敛到p(x)。
因为我们已经用正整数x重参数化了这个问题，我们可以用一个向量ν来描述这个概率分布q，
然后我们考虑更新单一的马尔可夫链，从状态x到新状态x＇。单一状态转移到x＇的概率可以表示为
根据状态为整数的参数化设定，我们可以将转移算子T表示成一个矩阵A。矩阵A的定义如下：
使用这一定义，我们可以改写式（17.18）。不同于之前使用q和T来理解单个状态的更新，我们现在可以使用ν和A来描述当我们更新时（并行运行的）不同马尔可夫链上整个分布是如何变化的：
重复地使用马尔可夫链更新相当于重复地与矩阵A相乘。换言之，我们可以认为这一过程就是关于A的幂乘：
矩阵A有一种特殊的结构，因为它的每一列都代表一个概率分布。这样的矩阵被称为随机矩阵（Stochastic Matrix）。如果对于任意状态x到任意其他状态x＇存在一个t使得转移概率不为0，那么Perron-Frobenius定理（Perron，1907；Frobenius，1908）可以保证这个矩阵的最大特征值是实数且大小为1。我们可以看到所有的特征值随着时间呈现指数变化：
这个过程导致了所有不等于1的特征值都衰减到0。在一些额外的较为宽松的假设下，我们可以保证矩阵A只有一个对应特征值为1的特征向量。所以这个过程收敛到平稳分布（Stationary Distribution），有时也被称为均衡分布（Equilibrium Distribution）。收敛时，我们得到
这个条件也适用于收敛之后的每一步。这就是特征向量方程。作为收敛的稳定点，ν一定是特征值为1所对应的特征向量。这个条件保证收敛到了平稳分布以后，再重复转移采样过程不会改变所有不同马尔可夫链上状态的分布（尽管转移算子自然而然地会改变每个单独的状态）。
如果我们正确地选择了转移算子T，那么最终的平稳分布q将会等于我们所希望采样的分布p。我们会将第17.4节介绍如何选择T。
可数状态马尔可夫链的大多数性质可以被推广到连续状态的马尔可夫链中。在这种情况下，一些研究者把这种马尔可夫链称为哈里斯链（Harris Chain），但是我们将这两种情况都称为马尔可夫链。通常在一些宽松的条件下，一个带有转移算子T的马尔可夫链都会收敛到一个不动点，这个不动点可以写成如下形式：
这个方程的离散版本就相当于重新改写方程式（17.23）。当x是离散值时，这个期望对应着求和，而当x是连续值时，这个期望对应的是积分。
无论状态是连续的还是离散的，所有的马尔可夫链方法都包括重复、随机地更新直到最后状态开始从均衡分布中采样。运行马尔可夫链直到它达到均衡分布的过程通常被称为马尔可夫链的磨合（Burning-in）过程。在马尔可夫链达到均衡分布之后，我们可以从均衡分布中抽取一个无限多数量的样本序列。这些样本服从同一分布，但是两个连续的样本之间会高度相关。所以一个有限的序列无法完全表达均衡分布。一种解决这个问题的方法是每隔n个样本返回一个样本，从而使得我们对于均衡分布的统计量的估计不会被MCMC方法的样本之间的相关性所干扰。所以马尔可夫链的计算代价很高，主要源于达到均衡分布前需要磨合的时间以及在达到均衡分布之后从一个样本转移到另一个足够无关的样本所需要的时间。如果我们想要得到完全独立的样本，那么可以同时并行地运行多个马尔可夫链。这种方法使用了额外的并行计算来减少时延。使用一条马尔可夫链来生成所有样本的策略和（使用多条马尔可夫链）每条马尔可夫链只产生一个样本的策略是两种极端。深度学习的从业者们通常选取的马尔可夫链的数目和小批量中的样本数相近，然后从这些固定的马尔可夫链集合中抽取所需要的样本。马尔可夫链的数目通常选为100。
另一个难点是我们无法预先知道马尔可夫链需要运行多少步才能到达均衡分布。这段时间通常被称为混合时间（mixing time）。检测一个马尔可夫链是否达到平衡是很困难的。我们并没有足够完善的理论来解决这个问题。理论只能保证马尔可夫链会最终收敛，但是无法保证其他。如果我们从矩阵A作用在概率向量ν上的角度来分析马尔可夫链，那么可以发现当At除了单个1以外的特征值都趋于0时，马尔可夫链混合成功（收敛到了均衡分布）。这也意味着矩阵A的第二大特征值决定了马尔可夫链的混合时间。然而，在实践中，我们通常不能真的将马尔可夫链表示成矩阵的形式。我们的概率模型所能够达到的状态是变量数的指数级别，所以表达ν，A或者A的特征值是不现实的。由于以上在内的诸多阻碍，我们通常无法知道马尔可夫链是否已经混合成功。作为替代，我们只能运行一定量时间的马尔可夫链直到粗略估计这段时间是足够的，然后使用启发式的方法来判断马尔可夫链是否混合成功。这些启发性的算法包括手动检查样本或者衡量前后样本之间的相关性。