动手学深度学习——束搜索

1. 前言前面我们已经把Seq2Seq这条线接起来了编码器读入输入序列解码器逐步生成输出序列每一步都会给出对目标词表的概率分布训练时通常用教师强制让模型学习“下一个词该是什么”但到了真正预测的时候一个非常现实的问题就来了解码器每一步都给出很多候选词那最终到底该怎么选才能得到整句最优结果最朴素的办法当然是每一步都选当前概率最大的词这叫贪心搜索Greedy Search。它简单但往往不够好。于是在序列生成任务中一个非常经典的解码策略就出现了束搜索Beam Search这一节的核心就是搞清楚为什么贪心搜索不够什么是束搜索束搜索是怎么一步步保留候选序列的为什么它比贪心更合理2. 为什么 Seq2Seq 生成时需要“搜索”这点很重要。在分类任务里模型最后输出一个类别分布我们直接取最大值就行。但在机器翻译、文本生成这种任务里输出不是一个词而是一整串词组成的序列例如模型要生成一句话je suis étudiant那就意味着第一步选一个词第二步再选一个词第三步继续选…直到eos所以生成不是一个单步决策而是一个多步连续决策问题而多步决策里一个非常典型的难点就是当前这一步看起来最优不一定能带来整句最优。这就是为什么需要“搜索”。3. 贪心搜索是什么最直接的做法叫贪心搜索Greedy Search它的规则非常简单在每一个时间步都直接选当前概率最大的那个 token。例如第一步模型给出je0.45il0.30tu0.10其他更低那贪心就选je。第二步接着在前缀je条件下再选当前概率最大的词。如此一直往后。所以贪心搜索的特点是简单快每一步都只保留一个候选序列4. 贪心搜索为什么可能出错问题就在于局部最优不等于全局最优。举个直觉例子。假设第一步候选 A 概率更高候选 B 概率略低贪心一定选 A。但如果后续继续展开你可能会发现以 A 开头的后续句子整体概率很差以 B 开头的后续句子整体概率反而更高也就是说第一步稍微“吃点亏”后面可能换来更好的整句结果。所以贪心的问题在于它看得太短只顾眼前。5. 机器翻译里为什么特别容易出现这种问题因为语言是有强上下文依赖的。例如一句翻译里第一个词选错后面很多结构都可能跟着别扭前面稍微不那么优的词可能让后面整个句法更顺某些词的搭配要看整句而不是只看当前一步所以在机器翻译中真正想找到好的翻译结果通常要比较整句路径的联合概率而不是只看每一步单独最大的词。这就引出了束搜索。6. 什么是束搜索束搜索英文叫Beam Search它可以理解为每一步不只保留一个候选序列而是保留前 k 个最有希望的候选序列。这里的k就叫束宽beam size也就是说贪心搜索相当于k 1束搜索则是k 1束搜索的核心改进就在于不把所有希望都压在一个当前最优路径上而是同时跟踪多个高分候选。这样模型就更有机会避免“早早走错路”。7. 束搜索最核心的思想是什么如果一句话概括就是宁可多留几条看起来不错的路后面再比较也不要太早把其他可能性全砍掉。所以束搜索本质上是在做有限宽度的路径搜索用更多候选换更好的全局结果它不是穷举因为穷举太贵它也不是贪心因为贪心太短视。它是一种折中在计算成本和生成质量之间做平衡。8. 束搜索是怎么一步步进行的假设束宽为k 2那么生成流程可以这样理解。第一步从bos开始模型给出一堆候选词。我们不只选概率最大的 1 个而是保留前 2 个。例如je0.45il0.30于是当前 beam 里有 2 条路径bos jebos il第二步对这 2 条路径分别继续展开。假设bos je可以继续生成若干候选bos il也可以继续生成若干候选于是会产生更多新路径。然后我们再从这些所有新路径中选出总分最高的前 2 条继续保留。后续步骤重复这个过程直到达到最大长度或者所有路径都生成eos这就是束搜索的基本流程。9. 为什么要比较“路径总分”而不是当前步概率因为我们真正关心的是整条序列的概率而不是某一步单独的好坏。假设一个序列y1, y2, ..., yT它的总概率通常写成P(y1, y2, ..., yT) P(y1) P(y2|y1) ... P(yT|y1,...,yT-1)也就是说整句概率是每一步条件概率的连乘。在实际计算中为了避免数值下溢通常会取对数log P(y1, ..., yT) log P(y1) log P(y2|y1) ... log P(yT|...)所以束搜索在比较候选路径时通常比较的是累计对数概率而不是最后一步单独概率。10. 为什么通常用对数概率因为直接连乘很多小于 1 的概率会变得非常非常小容易造成数值下溢。例如0.4 × 0.3 × 0.2 × 0.1 …很快就接近 0而取对数以后连乘变成连加数值更稳定比较大小也更方便所以在束搜索里候选路径分数通常是累计 log probability这是很标准的做法。11. 一个最简单的束搜索例子假设束宽k 2。第一步候选模型从bos出发给出A0.5B0.4C0.1保留前 2 个bos Abos B第二步展开对bos A展开A10.5 × 0.6 0.30A20.5 × 0.3 0.15对bos B展开B10.4 × 0.8 0.32B20.4 × 0.1 0.04这时所有候选路径是bos A A10.30bos A A20.15bos B B10.32bos B B20.04再选前 2 个bos B B1bos A A1你会发现虽然第一步A比B更大但第二步后B B1反而成了最优路径。这就是束搜索优于贪心的直观例子。12. 束宽k越大越好吗不一定但通常会更接近全局最优。束宽小例如k 1其实就是贪心搜索快但容易错过好路径束宽大会保留更多候选更有机会找到更好的整句结果但计算更慢、显存更大束宽极大如果大到接近穷举理论上会更全面但实际上代价太高不现实。所以束宽是一个典型的工程折中参数。13. 为什么束搜索不是“最优搜索”虽然束搜索比贪心强但它仍然不是严格全局最优。原因在于它每一步只保留前 k 个候选其他路径仍然会被剪掉。如果某条真正最优的路径在前几步分数不突出它仍然可能提前被束搜索淘汰。所以束搜索本质上是一种启发式近似搜索它通常足够好、足够实用但不能保证一定找到绝对全局最优序列。14. 束搜索为什么在机器翻译里这么常见因为它刚好特别适合翻译这种逐步生成任务。机器翻译里解码器每一步都会输出整个目标词表的概率分布最终目标是一整句翻译质量尽可能高只靠贪心往往太短视完全穷举又太昂贵所以束搜索成了一个很自然的选择比贪心更稳比穷举更省。因此在很多 Seq2Seq、注意力模型、甚至早期 Transformer 解码中束搜索都是标准组件之一。15. 束搜索和训练有什么关系这点要分清。训练时通常还是用教师强制交叉熵损失不会真的跑束搜索来训练推理/预测时才会用贪心搜索束搜索采样等策略所以束搜索属于推理阶段的解码策略它不是模型参数学习的一部分而是模型“怎么输出结果”的一部分。16. 为什么束搜索结果有时会偏向短句这是束搜索里的一个经典问题。因为序列总概率是很多小概率连乘句子越长乘的项越多整体概率往往越小。这意味着模型可能会偏向提前输出eos生成较短句子因为短句累计概率可能更大。所以实际中常常会加入一些长度归一化或长度惩罚策略避免模型总是偏爱过短结果。这也是束搜索在工程上常见的一个修正点。17. 为什么长度归一化很重要如果只看原始累计 log probability长句往往天然吃亏。例如两句都很合理长句只因为词更多就累积了更多负对数最后分数反而更差所以实际常用做法是对分数做长度归一化例如总分除以序列长度的某种函数这样可以让比较更公平不至于让搜索策略总偏向短句。这一点在机器翻译里尤其常见。18. 束搜索和采样有什么区别虽然这一节主讲束搜索但顺手区分一下很有帮助。束搜索目标是尽量找到高概率序列它偏“确定性优化”。采样目标是按概率分布随机抽样生成它偏“多样性生成”。所以翻译这类任务更常用束搜索创意文本生成有时会更偏向采样因为翻译更强调“准确最优”而创意生成更强调“多样自然”。19. 李沐这一节最想让你理解什么这一节最关键的不是让你背复杂公式而是让你抓住这条主线第一序列生成不是单步分类它是多步决策问题。第二贪心搜索容易陷入局部最优因为它每一步只看眼前最大概率。第三束搜索保留多个候选路径这样更有机会找到更好的整句结果。第四束搜索是一种推理阶段的解码策略它不改变模型参数只改变模型如何生成输出。所以这一节本质上是在告诉你模型学会了概率分布之后怎么把这些概率真正变成一句更好的输出。20. 本节总结这一节我们学习了束搜索核心内容可以总结为以下几点。20.1 束搜索是一种序列生成时的解码策略常用于机器翻译、Seq2Seq 等任务。20.2 它的核心是每一步保留前 k 个候选序列而不是像贪心搜索那样只保留一个。20.3 候选路径比较通常依据累计对数概率而不是单步概率。20.4 束搜索比贪心更容易找到更好的整句结果但仍然不是严格全局最优。20.5 实际中常结合长度归一化等技巧使用以避免过度偏向短句。21. 学习感悟束搜索这一节很有意思因为它提醒我们一个模型性能的好坏不只取决于“学得怎么样”也取决于“最后怎么用”。前面我们花了很多力气学模型RNNGRULSTMSeq2Seq但到了真正生成句子时如果解码策略太粗糙模型学到的能力也可能发挥不出来。所以束搜索其实是在告诉你模型之外推理策略同样重要。这也是为什么它虽然不是“网络结构”却依然是序列生成里非常经典的一节。