Beam Search

Beam Search并不是很陌生的算法，它和深度优先算法、广度优先算法一样都曾被使用于树结构的搜索。本文重提Beam Search主要是因为在智能对话生成式模型中，Beam Search被应用在解码过程。而对话系统的生成式模型，本公众号也曾经进行过介绍。

本文主要解决如下三个问题：

Q1： 在生成式对话系统中，为什么会使用Beam Search算法？

Q2： Beam Search的具体原理是什么？

Q3： 对话系统中，为生成更好的回复，对Beam Search可以做什么改进？

对于Q1，首先就要回顾一下生成式模型了，简单的理解为给定一句话X=[x1,x2,x3,...,xn]，需要生成对应的回复Y=[y1,y2,...,ym]，何为生成式模型，其实就和机器学习中的生成模型一样（机器学习中的模型一般分为判别模型和生成模型），也就是按照条件概率P(Y|X)去生成答案。首先对X进行建模（一般使用RNN模型），然后得到X的编码之后，解码生成回复Y中的每个词语（同样使用RNN模型）。那Beam Search是用在哪呢？就是解码过程，使用RNN只能得到一个序列的隐层输出，如何由隐层状态得到对应的词语，就需要计算概率了，而这个概率一般是通过softmax函数得到。最早的解码过程中，t时刻的词语是通过计算概率P(yt | y1,y2,...yt-1,X)得到，然后在词典中采样得到，但是这种结果没考虑前后词语，容易出现叠词或无意义的助词，例如“你好啊啊啊啊啊”，这样出现多个“啊”。使用Beam Search的原因，不是保证每个时刻得到单个词的概率最大，而是要保证y1,y2,...ym这个序列的联合概率最大。

对于Q2，这里主要从解码过程进行介绍Beam Search的基本原理。之前也说过，解码的模型是使得P(Y|X)最大。Beam Search简单地可以理解为包搜索，就是每次算法会维持一个Beam，Beam里就是已经解码出来的Top K个候选，K表示Beam Size大小，Top K的计算就是按概率的大小排序。例如在t-1时刻，我们得到了K个候选，每个候选的得分可以表示为：

在t时刻，每个候选需要保存前K个词语，此时得到的y1,y2...,yt-1, yt的序列个数为K*K个，再将这K*K个候选重新按照上述得分计算公式排序，选取Top K作为下一时刻的候选。以此循环，如下所示。

需要解释的是，为啥下一时刻的score是上一时刻的score加上此时刻的概率。主要在于对概率取log对数，其实相当于p(y1)*p(y2)*...*p(yt)，是概率乘积，对应于独立事件的概率计算。

对于Q3，由于上述的Beam Search容易陷入局部最优，或者说容易让某个Beam起到主导作用，这时解码产生的回复，Beam中的候选很相似，让回复比较单一。目前为使得回复比较有意义，而不是通用的一些回复类似“好的”、“是的”、“嗯”这样的，有大量工作对Beam Search进行改进，其中一个就是针对Beam中候选集排序加入惩罚项，具体如下所示：

加入惩罚项的原因在于，避免一个Beam中Top 1得分很高时，对应的Top 2,3,4,...等得分都很高，这样导致最后得到的回复非常相似。例如“你好”，“你好啊”，“你好呢”，“你好吗”等。

（欢迎关注公众号，一起学习探讨）