Beam Search学习

BackGround

在生成的时候，模型的输出是一个时间步一个时间步依次获得的，而且前面时间步的结果还会影响后面时间步的结果。也就是说，每一个时间步，模型给出的都是基于历史生成结果的条件概率。

• 为了生成完整的句子，需要一个称为解码的额外动作来融合模型多个时间步的输出，而且使得最终得到的序列的每一步条件概率连乘起来最大。

在文本生成任务中，每一个时间步可能的输出种类称为字典大小(vocabulary size，我们用V表示)，进行T步随机的生成可能获得的结果总共有$V^T$种。拿中文文本生成来说，V 的值大约是5000-6000，即常用汉字的个数。在如此大的基数下，遍历整个生成空间是不现实的。

贪心搜索

每一个时间步都取出一个条件概率最大的输出

Beam Search

思路也很简单，就是稍微放宽一些考察的范围。在每一个时间步，不再只保留当前分数最高的1个输出，而是保留num_beams个。当num_beams=1时集束搜索就退化成了贪心搜索。

• 实际上是堆树的思想

1. 在第一个时间步，A和C是最优的两个，因此得到了两个结果[A],[C]，其他三个就被抛弃了；
2. 第二步会基于这两个结果继续进行生成，在A这个分支可以得到5个候选人，[AA],[AB],[AC],[AD],[AE]，C也同理得到5个，此时会对这10个进行统一排名，再保留最优的两个，即图中的[AB]和[CE]；
3. 第三步同理，也会从新的10个候选人里再保留最好的两个，最后得到了[ABD],[CED]两个结果。 可以发现，beam search在每一步需要考察的候选人数量是贪心搜索的num_beams倍，因此是一种牺牲时间换性能的方法。

Beam Search例子

上面的贪心搜索只选择了概率最大的一个，而集束搜索则选择了概率最大的前k个。这个k值也叫做集束宽度（Beam Width）。

• k值等于2，则集束搜索的过程如下
  

• 得到第一个输出的概率分布[0.1,0.1,0.3,0.4,0.1][0.1,0.1,0.3,0.4,0.1]，选择概率最大的前两个，0.3和0.4，即Je和moi。

• 然后Je和moi分别作为Decoder的输入，得到两个概率分布，然后再选择概率和最大的前两个序列，0.3+0.8和0.4+0.6，即Je suis和moi suis。

以此类推，最终可以得到两个序列，即Je suis étudiant和moi suis étudiant，很明显前者的概率和最大，为2.2，所以这个序列是最终得到的结果。

缺点

Beam Search虽然比贪心强了不少，但还是会生成出空洞、重复、前后矛盾的文本。如果你有文本生成经验，一定对这些现象并不陌生。在语言模型还不像如今的BERT、GPT这么厉害的时候，这种现象更加明显。

• 可以发现即使是如今最顶级的语言模型加上足够长的引文输入，还是无法得到高质量的生成结果。

论文认为这种问题是由于这种试图最大化序列条件概率的解码策略从根上就有问题。

他们对比了给定同样引文的情况下人类续写和机器生成的词用语言模型计算出来的概率。
如下图所示，人类选择的词（橙线）并不是像机器选择的（蓝线）那样总是那些条件概率最大的词。从生成的结果也可以看出，机器生成的结果有大量重复。

改进方法

随机采样

第一种方法是用随机采样(sampling)代替取概率最大的词。采样的依据就是解码器输出的词典中每个词的概率分布。相比于按概率“掐尖”，这样会增大所选词的范围，引入更多的随机性。当时那篇论文的结论就是这种随机采样的方法远好于Beam Search。但这其实也是有条件的，随机采样容易产生前后不一致的问题。

• 而在开放闲聊领域，生成文本的长度都比较短，这种问题就被自然的淡化了。

temperature 随机采样

通过温度参数可以控制softmax函数产生的概率分布的平滑程度。温度参数（通常表示为T）是一个正数，用于调整指数运算的尺度。较高的温度会使得softmax函数的输出更加平滑，而较低的温度则会使得输出更加尖锐。

具体来说，给定输入向量 $x$，使用温度参数 $T$ 的softmax函数的计算公式如下：

$$y_i=\frac{e^{\frac{x_i}{T}}}{{\sum }_{j=1}^n{e}^{\frac{x_j}{T}}},\text{for}i=1,2,...,n$$

通过调整温度参数 $T$ 的值，可以改变输出向量 $y$ 中每个元素的相对大小。当温度参数 $T$ 较高时，指数运算的结果会变得更加平均，导致概率分布更加均匀，各个类别的概率差异较小。而当温度参数 $T$ 较低时，指数运算的结果会更加集中，导致概率分布更加尖锐，各个类别的概率差异较大。

需要注意的是，当温度参数 $T$ 趋近于无穷大时，softmax函数的输出将趋近于均匀分布，即每个类别的概率接近于 $\frac{1}{n}$，其中 $n$ 是类别的数量。而当温度参数 $T$ 趋近于零时，softmax函数的输出将趋近于一个独热编码，即只有最大值对应的类别的概率接近于1，其他类别的概率接近于0。

top-k采样

这个方法就是在采样前将输出的概率分布截断，取出概率最大的k个词构成一个集合，然后将这个子集词的概率再归一化，最后从新的概率分布中采样词汇。

• 这个办法据说可以获得比Beam Search好很多的效果，但也有一个问题，就是这个k不太好选。

因为这个概率分布变化比较大，有时候可能很均匀(flat)，有的时候比较集中(peaked)。对于集中的情况还好说，当分布均匀时，一个较小的k容易丢掉很多优质候选词。但如果k定的太大，这个方法又会退化回普通采样。

top-p采样

• 累加概率，前若干个词多概率进行累加一直到达到p的阈值，然后取出前面这若干个词，重新进行概率归一化，并把剩下词的概率设为0。

惩罚重复

为了解决重复问题，还可以通过惩罚因子将出现过词的概率变小或者强制不使用重复词来解决。惩罚因子来自于同样广为流传的《CTRL: A Conditional Transformer Language Model for Controllable Generation》[2]