Loading... <div class="tip inlineBlock share"> 转载自: https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html </br> B站链接: https://www.bilibili.com/video/BV1B44y1C7m1 </div> ## 前言 在 [9.7节](https://zh.d2l.ai/chapter_recurrent-modern/seq2seq.html#sec-seq2seq)中,我们逐个预测输出序列(token), 直到预测序列中出现特定的序列结束词元`<eos>`。这里将首先介绍*贪心搜索*(greedy search)策略, 并探讨其存在的问题,然后对比其他替代策略: *穷举搜索*(exhaustive search)和*束搜索*(beam search)。 在正式介绍贪心搜索之前,我们使用与 [9.7节](https://zh.d2l.ai/chapter_recurrent-modern/seq2seq.html#sec-seq2seq)中 相同的数学符号定义搜索问题。 在任意时间步$t^\prime$,解码器输出$y_{t^\prime}$的概率取决于 时间步$t^\prime$之前的输出子序列$y_1, ...,y_{t^\prime - 1}$ 和对输入序列的信息进行编码得到的上下文变量$c$。 为了量化计算代价,用$Y$表示词表的大小(目标词汇表长度)。 我们还将输出序列的最大词元数(目标句子长度)指定为$T^\prime$。 因此,我们的目标是从所有$O(|Y|^{T^\prime})$个 可能的输出序列中寻找理想的输出。 当然,对于所有输出序列,在`<eos>`之后的部分(非本句) 将在实际输出中丢弃。 ## 1.贪心搜索 首先,让我们看看一个简单的策略:*贪心搜索*, 该策略已用于 [9.7节](https://zh.d2l.ai/chapter_recurrent-modern/seq2seq.html#sec-seq2seq)的序列预测。 对于输出序列的每一时间步$t^\prime$, 我们都将基于贪心搜索从$Y$中找到具有最高条件概率的词元,即: $$ y_{t^\prime} = \mathop{argmax}\limits_{y \in Y } P(y|y_1, .... y_{t^\prime-1}, c) $$ 一旦输出序列包含了“`<eos>`”或者达到其最大长度$T^\prime$,则输出完成。 ![贪心](https://zoe.red/usr/uploads/2024/04/194629314.png) **图1** **在每个时间步,贪心搜索选择具有最高条件概率的词元** 如 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)中, 假设输出中有四个词元“A”“B”“C”和“`<eos>`”。 每个时间步下的四个数字分别表示在该时间步 生成“A”“B”“C”和“`<eos>`”的条件概率。 在每个时间步,贪心搜索选择具有最高条件概率的词元。 因此,将在 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)中 预测输出序列“A”“B”“C”和“`<eos>`”。 这个输出序列的条件概率是 0.5×0.4×0.4×0.6=0.048。 那么贪心搜索存在的问题是什么呢? 现实中,*最优序列*(optimal sequence)应该是最大化 $\prod_{t^\prime=1}^{T^\prime} P(y_{t^\prime}| y_1, ...,y_{t^\prime-1, c})$ 值(累积结果)的输出序列,这是基于输入序列生成输出序列的条件概率。 然而,贪心搜索无法保证得到最优序列。 ![image.png](https://zoe.red/usr/uploads/2024/04/3583098713.png) **图2** **在时间步2,选择具有第二高条件概率的词元“C”(而非最高条件概率的词元)** [图2](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob2)中的另一个例子阐述了这个问题。 与 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)不同,在时间步2中, 我们选择 [图2](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob2)中的词元“C”, 它具有*第二*高的条件概率。 由于时间步3所基于的时间步1和2处的输出子序列已从 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)中的“A”和“B”改变为 [图2](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob2)中的“A”和“C”, 因此时间步3处的每个词元的条件概率也在 [图2](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob2)中改变。 假设我们在时间步3选择词元“B”, 于是当前的时间步4基于前三个时间步的输出子序列“A”“C”和“B”为条件, 这与 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)中的“A”“B”和“C”不同。 因此,在 [图2](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob2)中的时间步4生成 每个词元的条件概率也不同于 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)中的条件概率。 结果, [图2](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob2)中的输出序列 “A”“C”“B”和“`<eos>`”的条件概率为 0.5×0.3×0.6×0.6=0.054, 这大于 [图1](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-s2s-prob1)中的贪心搜索的条件概率。 这个例子说明:贪心搜索获得的输出序列 “A”“B”“C”和“`<eos>`” 不一定是最佳序列。 --- ## 2.穷举搜索 如果目标是获得最优序列, 我们可以考虑使用*穷举搜索*(exhaustive search): 穷举地列举所有可能的输出序列及其条件概率, 然后计算输出条件概率最高的一个。 虽然我们可以使用穷举搜索来获得最优序列, 但其计算量$O(|Y|^{T^\prime})$可能高的惊人。 例如,当`目标词汇表长度`$|Y|=10000$和`目标句子长度`$T^\prime=10$时, 我们需要评估$10000^{10}=10^{40}$序列, 这是一个极大的数,现有的计算机几乎不可能计算它。 然而,贪心搜索的计算量$O(|Y|\times T^\prime)$要显著地小于穷举搜索。 例如,当$|Y|=10000$和$T^\prime=10$时, 我们只需要评估$10000×10=10^5$个序列。 --- ## 3. 束搜索 那么该选取哪种序列搜索策略呢? 如果精度最重要,则显然是穷举搜索。 如果计算成本最重要,则显然是贪心搜索。 而束搜索的实际应用则介于这两个极端之间。 *束搜索*(beam search)是贪心搜索的一个改进版本。 它有一个超参数,名为*束宽*(beam size)$k$。 在时间步1,我们选择具有最高条件概率的$k$个词元。 这$k$个词元将分别是$k$个候选输出序列的第一个词元。 在随后的每个时间步,基于上一时间步的$k$个候选输出序列, 我们将继续从$k \times |Y|$个可能的选择中 挑出具有最高条件概率的$k$个候选输出序列。 ![image.png](https://zoe.red/usr/uploads/2024/04/2395828598.png) **图3** **束搜索过程(束宽:2,输出序列的最大长度:3)。候选输出序列分别是**A**、**C**、**AB**、**CE**、**ABD**和**CED** [图3](https://zh.d2l.ai/chapter_recurrent-modern/beam-search.html#fig-beam-search)演示了束搜索的过程。 假设输出的词表只包含五个元素: $Y=\{A,B,C,D,E\}$, 其中有一个是“`<eos>`”。 设置束宽$k=2$,输出序列的最大长度$T^\prime=3$。 在时间步1,假设具有最高条件概率 $P(y_1, c)$的词元是"A"和"C"。 在时间步2,我们计算所有$y_2 \in Y$为: $$ \begin{equation} \begin{aligned} P(A, y_2 | c) = P(A|c) \times P(y_2| A, c) \\ P(C, y_2 | c) = P(C|c) \times P(y_2| C, c) \end{aligned} \end{equation} $$ 从这十个值(k:2xY:5=10)中选择最大的两个, 比如$P(A,B|c)$和$P(C,E|c)$。 然后在时间步3,我们计算所有$y_3 \in Y$为: $$ \begin{equation} \begin{aligned} P(A,B, y_3 | c) = P(A, B|c) \times P(y_3| A, B,c) \\ P(C,E, y_3 | c) = P(C, E|c) \times P(y_3| C, E,c) \end{aligned} \end{equation} $$ 从这十个值中选择最大的两个, 即$P(A,B,D|c)$和P(C,E,D|c), 我们会得到六个候选输出序列: (1)A;(2)C;(3)AB;(4)CE;(5)ABD;(6)CED。 最后,基于这六个序列(例如,丢弃包括“`<eos>`”和之后的部分), 我们获得最终候选输出序列集合。 然后我们选择其中条件概率乘积最高的序列作为输出序列: $$ \frac{1}{L^\alpha}logP(y_1, ..., Y_L|c) = \frac{1}{L^\alpha}\sum\limits_{t^\prime=1}^{L}logP(y_{t^\prime} | y_1, ..., y_{t^\prime-1}, c) $$ 其中$L$是最终候选序列的长度, $\alpha$通常设置为0.75。 因为一个较长的序列在上面公式的求和中会有更多的对数项, 因此分母中的$L^\alpha$用于惩罚长序列。 束搜索的计算量为$O(k \times |Y| \times T^\prime)$,这个结果介于贪心搜索和穷举搜索之间。 实际上,贪心搜索可以看作一种束宽为1的特殊类型的束搜索。 通过灵活地选择束宽,束搜索可以在正确率和计算代价之间进行权衡。 补充: 代码实现& 问题分析与进一步改进工作 * https://juejin.cn/post/7069650062305361957 * https://www.cnblogs.com/nickchen121/p/15499576.html * https://cloud.tencent.com/developer/article/1675791 ## 小结 * 序列搜索策略包括贪心搜索、穷举搜索和束搜索。 * 贪心搜索所选取序列的计算量最小,但精度相对较低。 * 穷举搜索所选取序列的精度最高,但计算量最大。 * 束搜索通过灵活选择束宽,在正确率和计算代价之间进行权衡。 THE END 本文作者:将夜 本文链接:https://zoe.red/2024/433.html 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。 最后修改:2024 年 04 月 06 日 © 转载自他站 赞 如果觉得我的文章对你有用,请随意赞赏