束搜索

type

status

date

slug

summary

category

icon

password

Property

🐬

贪心搜索穷举搜索束搜索

在seq2seq中，逐个预测输出序列，直到预测序列中出现特定的序列结束词元“<eos>”。这里将首先介绍贪心搜索（greedy search）策略，并探讨其存在的问题，然后对比其他替代策略： 穷举搜索（exhaustive search）和束搜索（beam search）。

在任意时间步，解码器输出的概率取决于时间步之前的输出子序列和对输入序列的信息进行编码得到的上下文变量。为了量化计算代价，用表示输出词表，其中包含“<eos>”，所以这个词汇集合的基数就是词表的大小。我们还将输出序列的最大词元数指定为。因此，我们的目标是从所有个可能的输出序列中寻找理想的输出。当然，对于所有输出序列，在“<eos>”之后的部分（非本句）将在实际输出中丢弃。

贪心搜索所选取序列的计算量最小，但精度相对较低

穷举搜索所选取序列的精度最高，但计算量最大

束搜索通过灵活选择束宽，在正确率和计算代价之间进行权衡

贪心搜索

该策略已用于seq2seq的序列预测。对于输出序列的每一时间步，都将基于贪心搜索从中找到具有最高条件概率的词元，即：

一旦输出序列包含了“<eos>”或者达到其最大长度，则输出完成。

如图中，假设输出中有四个词元“A”、“B”、“C”和“<eos>”。每个时间步下的四个数字分别表示在该时间步生成“A”、“B”、“C”和“<eos>”的条件概率。在每个时间步，贪心搜索选择具有最高条件概率的词元。因此，将在图中预测输出序列“A”、“B”、“C”和“<eos>”。这个输出序列的条件概率是。

那么贪心搜索存在的问题是什么呢？现实中，最优序列（optimal sequence）应该是最大化值的输出序列，这是基于输入序列生成输出序列的条件概率。然而，贪心搜索无法保证得到最优序列。

另一个例子阐述了这个问题。在时间步中，我们选择图中的词元“C”，它具有第二高的条件概率。由于时间步所基于的时间步和处的输出子序列已从“A”和“B”改变为“A”和“C”，因此时间步处的每个词元的条件概率也在改变。假设我们在时间步选择词元“B”，于是当前的时间步基于前三个时间步的输出子序列“A”、“C”和“B”为条件，这与之前的“A”、“B”和“C”不同。因此，在时间步生成每个词元的条件概率也不同于之前图中的条件概率。结果输出序列 “A”、“C”、“B”和“<eos>”的条件概率为，这大于贪心搜索的条件概率。这个例子说明：贪心搜索获得的输出序列 “A”、“B”、“C”和“<eos>” 不一定是最佳序列。

穷举搜索

如果目标是获得最优序列，我们可以考虑使用穷举搜索（exhaustive search）：穷举地列举所有可能的输出序列及其条件概率，然后计算输出条件概率最高的一个。

虽然我们可以使用穷举搜索来获得最优序列，但其计算量可能高的惊人。例如，当和时，我们需要评估序列，这是一个极大的数，现有的计算机几乎不可能计算它。然而，贪心搜索的计算量通它要显著地小于穷举搜索。例如，当和时，只需要评估个序列。

那么该选取哪种序列搜索策略呢？如果精度最重要，则显然是穷举搜索。如果计算成本最重要，则显然是贪心搜索。而束搜索的实际应用则介于这两个极端之间。

束搜索（beam search）是贪心搜索的一个改进版本。它有一个超参数，名为束宽（beam size） 。在时间步，选择具有最高条件概率的个词元。这个词元将分别是个候选输出序列的第一个词元。在随后的每个时间步，基于上一时间步的个候选输出序列，我继续从个可能的选择中挑出具有最高条件概率的个候选输出序列。

上图演示了束搜索的过程。假设输出的词表只包含五个元素：，其中有一个是“<eos>”。设置束宽为，输出序列的最大长度为。在时间步，假设具有最高条件概率的词元是和。在时间步，我们计算所有为：

从这十个值中选择最大的两个，比如和。然后在时间步，计算所有为：

从这十个值中选择最大的两个，即和，我们会得到六个候选输出序列：（1）；（2）；（3）；（4）；（5）；（6）。

最后，基于这六个序列（例如，丢弃包括“<eos>”和之后的部分），获得最终候选输出序列集合。然后选择其中条件概率乘积最高的序列作为输出序列：

其中是最终候选序列的长度，通常设置为。因为一个较长的序列在求和中会有更多的对数项，因此分母中的用于惩罚长序列。

束搜索的计算量为，这个结果介于贪心搜索和穷举搜索之间。实际上，贪心搜索可以看作是一种束宽为的特殊类型的束搜索。通过灵活地选择束宽，束搜索可以在正确率和计算代价之间进行权衡。