搜出来的文本：从MCMC到模拟退火

©PaperWeekly 原创 · 作者｜苏剑林

单位｜追一科技

研究方向｜NLP、神经网络

在上一篇文章中，我们介绍了“受限文本生成”这个概念，指出可以通过量化目标并从中采样的方式来无监督地完成某些带条件的文本生成任务。同时，上一篇文章还介绍了“重要性采样”和“拒绝采样”两个方法，并且指出对于高维空间而言，它们所依赖的易于采样的分布往往难以设计，导致它们难以满足我们的采样需求。

此时，我们就需要引入采样界最重要的算法之一“Markov Chain Monte Carlo（MCMC）”方法了，它将马尔可夫链和蒙特卡洛方法结合起来，使得（至少理论上是这样）我们从很多高维分布中进行采样成为可能，也是后面我们介绍的受限文本生成应用的重要基础算法之一。本文试图对它做一个基本的介绍。

马尔可夫链

马尔可夫链实际上就是一种“无记忆”的随机游走过程，它以转移概率 为基础，从一个初始状态 出发，每一步均通过该转移概率随机选择下一个状态，从而构成随机状态列 ，我们希望考察对于足够大的步数 t， 所服从的分布，也就是该马尔可夫链的“平稳分布”。

假设 所服从的分布为 ，那么 所服从的分布就是：

如果已经达到平衡，那么应该有 ，所以如果 是平稳分布，那么它满足：

或者说，平稳分布就是上述关于 的方程的非零解。

那么，有一个需要回答的问题是：上述方程的非零解唯一吗？ 这个问题的答案关系到马尔可夫链的平稳分布是否依赖于初始状态 。很遗憾，答案是不一定。简单来说，非零解唯一的条件是该马尔可夫链的任意两个状态都是连通的，说具体点就是对于任意两个状态 ，存在状态链 ，使得：

说白了，就是从状态 跳转到 （不要求一步到位，可以多步）的概率大于 0。其实这个判据也不难理解，形象比喻就是指平稳分布唯一的条件是马尔可夫链不能存在“孤岛”，要不然如果 在孤岛内，那么就永远在孤岛内游走了，如果 在孤岛外，那么也就永远在孤岛外游走了，从而不同的初始状态导致了不同的平稳分布。

细致平稳

由于马尔可夫链存在一个平稳分布，而构建马尔可夫链则只需要一个转移矩阵，如果我们可以构建一个易于采样的转移矩阵，并且它的平稳分布就是我们要采样的分布 ，那么迭代足够多步后，不就相当于从 中采样了？这就是所有 MCMC 方法的思想。

当然，马尔可夫链往往需要迭代多步才能达到平稳，因此采样往往比较费时，但即便如此，终究能在有限成本内完成了采样过程，因此在很多情况下依然是实用的。

假设 MCMC 是可行的，那么很显然关键之处就是如何构造出一个转移概率 ，使得它的平稳分布是我们给定的分布 ，同时，根据上一篇文章的介绍，我们往往只知道跟 成正比的 ，而不知道归一化因子，因此构建 的过程中，不能依赖于 的归一化因子。

为此，我们需要用到一个“细致平稳条件”：

细致平稳条件： 如果分布 和转移概率 满足恒等式：

那么 就是 的平稳分布。

名字看上去高端，实际上它非常容易证明，只要两端对 求和，马上就得到式（2）了，满足式（2）就说明 是 的平稳分布。“细致平稳条件”是判断平稳分布的一个充分条件，但不是必要的，它的价值在于提供了一种比较方便的为任意分布构建转移概率的方式。

转移概率

给定平稳分布 以及任意的参考转移概率 ，如果它满足细致平稳条件，那么就万事大吉，直接用参考转移概率 作为最终的概率就好，如果它不满足，那么记 ，那么有下述显然成立的恒等式：

事实上，这个恒等式近乎废话，它相当于说“虽然 ，但 始终成立”。但就是这么个“废话”般的恒等式，给了我们启示：如果用 作为转移概率，那么对应的平稳分布不就是 了？

其实没那么简单，因为这样构造出来的 通常是没有归一化的，而没有归一化即意味着它本身就不是一个合理的转移概率，也就没有什么平稳分布之说了。注意，如果要进行采样，我们或许可以不需要知道归一化因子，但是理论分布的时候，我们是需要保证归一化成立的。

有的读者可能会想，那我手动除以个归一化因子行不？不行，因为除以归一化因子之后，细致平稳条件就未必成立了，甚至式（2）都可能不成立了。笔者查阅了很多介绍资料，都没有澄清这个问题，都是说直接用 作为转移概率的，困惑了很长时间。

事实上，MCMC方法根本就没有去归一化 ，而是将剩余部分的概率概率全部转移到自身去了。用数学的话来说，就是它最后使用的转移概率实际上是：

其中 ，代表了只能转移到自身（即“永远不变”）的转移概率。所以， 的定义其实就是把多出来的概率统统叠加到“不变”这一操作上，所以它显然满足归一化，至于细致平稳条件可以代入检验，同样是满足的，其中主要是因为对于任意的 和 ，下式总是恒成立的。

所以 才是我们所要寻求的真正的转移概率。如果状态空间有限的话，那么转移概率就对应一个有限的矩阵，上述结果其实就是说“通过调整转移矩阵的对角线元素可以完成归一化，并且不影响细致平稳条件的成立”。

MCMC方法

怎么实现从上述 从采样呢？很简单，先实现从 采样，然后如果不满足从 采样的条件，那么就保持不变；而 ，我们假定从 中采样是容易的，那么回忆上一篇文章介绍的拒绝采样，我们可以通过进一步采样一个 ，通过 来决定是否接受采样出来的 。综上所述，我们就得到了如下的 MCMC 采样流程：

Metropolis采样：

初始状态为 ，t 时刻状态为 。

通过如下流程采样出 ：

1. 采样 ；  

2. 采样 ；  

3. 计算 ；  

4. 如果 ，那么 ，否则 。

这就是由 Metropolis 在 1953 年提出来的采样算法，一般称为 Metropolis 算法，或者干脆称为 MCMC 方法。它需要知道 的精确表达式，并且需要知道一个易于采样的转移概率 ，然后根据上述流程迭代采样足够多步后，所得的 我们就可以认为是从 中采样出来的。这里的足够多步取决于 和 的具体选择，一般来说只能根据实验结果确定，没有统一的标准。

可能有读者觉得，这不就是一个普通的拒绝采样吗？刚才说的“把多出来的概率统统叠加到‘不变’这一操作上”体现在哪？事实上，跟普通的拒绝采样还是有点不一样的，在普通的拒绝采样中，如果 ，那就重复 1、2、3 步采样过程，直到采样出 为止，然后让 。

而上述采样过程中，如果 ，那么直接让 了，再下一步采样出来的就是 了。假如我们认为从 T 时刻开始，分布就平稳了，那么 都是 中采样出来的样本（同分布但不独立），显然两种不同的拒绝方式，会影响 最终的分布情况。

此外，值得指出的是，尽管本系列文章中，我们所处理的 是离散对象，但事实上同样的结论也适用于连续型对象的采样，只需要在前面的推导过程中，将求和改为对概率密度的积分就行了，没有实质的区别。

MH采样

上述 Metropolis 采样在很多场景下已经可用了，但它还不是特别完美。首先，刚才说了，Metropolis 采样需要知道 的精确表达式，这在不少任务下是难以做到的；其次，接受率 往往过小，导致长时间“原地踏步”，从而达到平稳状态的时间过长。幸运的是，有一个简单的技巧可以同时解决这两个问题。

该技巧就是使用如下式子作为接受率：

该接受率其实也是源于恒等式（5），对于接受率而言，我们唯一的要求就是它在 0～1 之间，此外是越接近于 1 越好，为此，我们可以让恒等式（5）两边的接受率都除以 ，这样一来，它们俩其中一个就变成了 1，另一个也不大于 1，并且得到了放大，化简之后就得到了 。而且相当巧妙的是，此时 只依赖于 的相对值，所以我们可以不用算出它的归一化因子了。

这样一来，我们就得到了改进版的 Metropolis 采样算法，这就是大名鼎鼎的Metropolis-Hastings Sampling（MH 采样）：

Metropolis-Hastings采样：

初始状态为 ，t 时刻状态为 。

通过如下流程采样出 ：

1. 采样 ；  

2. 采样 ；  

3. 计算 ；  

4. 如果 ，那么 ，否则 。

分析思考

上一篇文章中，我们指出直接从 中采样是很困难的，就算是拒绝采样，如果 的维度过高，那么从近似分布 采样后其接受率通常也会很低，导致拒绝采样的效率极低而无法使用。那么很自然的一个问题是：

在 MCMC 方法中，同样要从转移概率 中采样，同样有接受概率 ，那为什么 MCMC 就是实用的，而普通的拒绝采样就是不实用的？

其实，对于直接拒绝采样来说，它要从近似分布 中直接采样的是整个高维序列，如果 与精确的 差得比较大，那么接受概率往往是指数衰减的，因此接受概率极低；而对于 MCMC 方法来说，我们对 的形式没有过多的限制，那么我们可以适当地设计 ，使得概率分布只集中在跟 相似的那些 中。

换句话说，只有当 与 很相似时， 才不为 0，否则就为 0。这样一来，从 采样的结果跟输入 只有小的差别，变化不大的情况下，接受率往往更高些，所以使得拒绝采样成为可能。

所以，说白了，MCMC 方法就是将“直接生成 ”，转换为了“从 出发，反复对它微调、润色，直到生成符合条件的 ”这么一个渐进式过程，从而使得它行之有效，这跟上一篇文章提到的“一步步来”的思想是一致的。

接下来，我们将介绍两个 MH 采样的例子：Gibbs 采样和模拟退火，它们都体现了 MCMC 的这种微调、渐进的思想。

Gibbs采样

假设 是一个长度为 l 的序列，Gibbs 采样每次只调整其中一个元素。具体来说，Gibbs 采样将参考转移概率定义为：

其中 是将 的第 i 个位置替换为 y 后的序列。这也就是说，它根据待采样分布 自身来构建 作为转移概率，每次先从 中随机选择一个位置 i，然后将位置 i 的元素替换成从分布 采样出来的结果。更妙的是，我们可以证明这种情况下接受概率恒为 1：

由此，我们可以构建如下的 Gibbs 采样过程：

Gibbs采样：

初始状态为 ，t 时刻状态为 。

通过如下流程采样出 ：

1. 均匀地从 中采样一个 i；  

2. 计算 ；  

3. 采样 ；  

4. （即将 的第 i 个位置替换为 y 作为 ）。

模拟退火

另一个例子是模拟退火（Simulated Annealing） 算法。前一篇文章中，我们提到了最大化一个目标，其实也可以看成是从这个目标中进行随机采样，其结果便对应着模拟退火算法。

首先，设我们要最大化的函数是 ，并且假设存在某个常数 T > 0，使得对于任意 ，都有：

这里的 的物理意义就是温度。这个假设看起来是额外的约束，但事实上模拟退火也就只适用于满足这个条件的场景。由于满足该条件，那么我们就可以构造分布：

假设最大值点是唯一的，那么当 时， 就会退化为 one hot 分布，也就是只有最大值点的概率为 1，如果从 中采样，那么采样结果就是最大值点了。即使 ，那么依然是最大值点的概率最大，所以从 中采样，也会有趋于最大值点的趋势。

所以，我们可以先固定温度 ，构造一个从 进行 MH 采样的随机过程，然后再慢慢让 下降，那么最终的收敛结果就是最大值点附近了，这就是所谓的“模拟退火”了。

为了进行 MH 采样，我们需要构建转移矩阵，模拟退火的选择比较简单，就是根据当前状态 设计固定数目的 作为新的 的候选值（这步通常称为“变异”，往往只是对 进行简单修改来得到 ，然后 就是从候选中均允随机地选一个。既然是均匀的，那么 就是一个常数，并且 ，因此就有：

所以，模拟退火就是一种搜索策略，如果 ，那么就更新 ，就算不是，那么还有一定的概率更新 。在整个搜索过程中，我们慢慢进行退火（ 慢慢趋于 0），在适当的退火策略下，模拟退火几乎总是能找到最大值点的。当然，如何根据具体问题制定“适当的”退火策略，那又是一个值得思考的问题了。

模拟退火：

初始状态为 ，初始温度为 ，温度按照事先制定的策略下降，t 时刻状态为 ，温度为 。

通过如下流程采样出 ：

1. 采样 ；  

2. 采样 ；  

3. 计算 ；  

4. 如果 ，那么 ，否则 。

如果简单修改一下，将接受策略改为“如果 则接受，否则就拒绝”，那么就变成了更朴素的“爬山法（Hill Climbing）”了。显然，爬山法目标更明确，前期可能收敛更快，但是一旦陷入了局部最大值后，通常就跳不出来了，最终的收敛结果没有模拟退火那么好。

当然，也可以通过选择不同的初始值来重复实验，提升爬山法的效果。具体选择什么算法，那就看具体问题而定了。

本文小结

本文依然介绍“受限文本生成”所需要的基础采样算法——MCMC 方法。经过反复修改，本文总算写出了笔者觉得比较满意的 MCMC 方法介绍，其中主要的区别是回答了一些常见的 MCMC 方法教程中没有提及到的细节问题。

对于基础算法的介绍，到此就告一段落。从下一篇文章开始，我们将逐步介绍如何将这些看似枯燥的采样算法应用到生动、具体的文本生成任务中去。

更多阅读

#投 稿 通 道#

 让你的论文被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。

📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志

📬 投稿邮箱：

• 投稿邮箱：hr@paperweekly.site 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。