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

1. 前言

前面我们已经把Seq2Seq这条线接起来了：

• 编码器读入输入序列

• 解码器逐步生成输出序列

• 每一步都会给出对目标词表的概率分布

• 训练时通常用教师强制，让模型学习“下一个词该是什么”

但到了真正预测的时候，一个非常现实的问题就来了：

解码器每一步都给出很多候选词，那最终到底该怎么选，才能得到整句最优结果？

最朴素的办法当然是：

• 每一步都选当前概率最大的词

这叫贪心搜索（Greedy Search）。
它简单，但往往不够好。

于是，在序列生成任务中，一个非常经典的解码策略就出现了：

束搜索（Beam Search）

这一节的核心就是搞清楚：

• 为什么贪心搜索不够

• 什么是束搜索

• 束搜索是怎么一步步保留候选序列的

• 为什么它比贪心更合理

2. 为什么 Seq2Seq 生成时需要“搜索”

这点很重要。

在分类任务里，模型最后输出一个类别分布，
我们直接取最大值就行。

但在机器翻译、文本生成这种任务里，输出不是一个词，而是：

一整串词组成的序列

例如模型要生成一句话：

je suis étudiant

那就意味着：

• 第一步选一个词

• 第二步再选一个词

• 第三步继续选

• …

• 直到<eos>

所以生成不是一个单步决策，而是一个：

多步连续决策问题

而多步决策里，一个非常典型的难点就是：

当前这一步看起来最优，不一定能带来整句最优。

这就是为什么需要“搜索”。

3. 贪心搜索是什么

最直接的做法叫：

贪心搜索（Greedy Search）

它的规则非常简单：

在每一个时间步，都直接选当前概率最大的那个 token。

例如：

第一步

模型给出：

• je：0.45

• il：0.30

• tu：0.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 个。

例如：

• je：0.45

• il：0.30

于是当前 beam 里有 2 条路径：

• <bos> je

• <bos> 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>出发给出：

• A：0.5

• B：0.4

• C：0.1

保留前 2 个：

• <bos> A

• <bos> B

第二步展开

对<bos> A展开：

• A1：0.5 × 0.6 = 0.30

• A2：0.5 × 0.3 = 0.15

对<bos> B展开：

• B1：0.4 × 0.8 = 0.32

• B2：0.4 × 0.1 = 0.04

这时所有候选路径是：

• <bos> A A1：0.30

• <bos> A A2：0.15

• <bos> B B1：0.32

• <bos> B B2：0.04

再选前 2 个：

• <bos> B B1

• <bos> 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. 学习感悟

束搜索这一节很有意思，因为它提醒我们：

一个模型性能的好坏，不只取决于“学得怎么样”，也取决于“最后怎么用”。

前面我们花了很多力气学模型：

• RNN

• GRU

• LSTM

• Seq2Seq

但到了真正生成句子时，
如果解码策略太粗糙，模型学到的能力也可能发挥不出来。

所以束搜索其实是在告诉你：

模型之外，推理策略同样重要。

这也是为什么它虽然不是“网络结构”，却依然是序列生成里非常经典的一节。