03 集束搜索（Beam Search）
这一节在讲什么
这一节正式讲 Beam Search。它解决的问题是：
不可能把所有翻译句子都试一遍，那就只保留“目前最有希望”的少数候选。
先说核心思想
束搜索不是每一步只留 1 条路，而是留 $B$ 条路。
这里的 $B$ 叫做束宽（beam width）。
- 如果 $B=1$，那就退化成贪心搜索
- 如果 $B=3$，每一步保留 3 个最有希望的部分句子
- 如果 $B$ 更大，通常结果更好，但更慢
第 1 步怎么做
课程里的例子还是：
\[\text{Jane visite l'Afrique en septembre.}\]先让解码器预测第一个输出词的分布：
\[P(y^{\langle 1 \rangle} \mid x)\]假设词表有 10000 个词，模型会给 10000 个概率。
如果束宽 $B=3$，就只留下概率最高的 3 个词。
课程里举的候选示意有：
injaneseptember
注意，这不是说它们就是正确答案，而是说“先留下最可能的 3 个起点”。
第 2 步怎么做
对每个保留下来的第一个词，再去扩展第二个词。
如果束宽是 3，词表是 10000，那么第二步会有：
\[3 \times 10000 = 30000\]个二词候选。
比如：
in ain septemberjane isjane visitsseptember ...
然后对每个二词候选算概率：
\[P(y^{\langle 1 \rangle}, y^{\langle 2 \rangle} \mid x)\]根据链式法则：
\[P(y^{\langle 1 \rangle}, y^{\langle 2 \rangle} \mid x) = P(y^{\langle 1 \rangle} \mid x) P(y^{\langle 2 \rangle} \mid x, y^{\langle 1 \rangle})\]再从这 30000 个里保留最好的 3 个。
第 3 步及后面
之后就重复同样逻辑：
- 先拿当前保留的 3 个部分句子
- 每个都再扩展一个新词
- 对所有扩展后的候选打分
- 只保留前 3 名
直到某条句子生成 <EOS> 结束符。
为什么它比贪心更好
贪心每一步只留 1 个候选，所以一旦第一步走偏，后面全错。
束搜索会多保留几条路，相当于说：
“我先别太早下结论，我留几个备选，后面再看谁更像正确答案。”
这就是它通常优于贪心搜索的原因。
用课程里的句子体会一下
课程里展示的搜索路径里，可能会出现：
in septemberjane isjane visits
虽然 in 作为第一个词单看很奇怪，但束搜索允许它先活着；
后面随着完整句子越来越长，真正好的路径会慢慢脱颖而出。
最终更可能找到像这样的句子：
\[\text{Jane visits Africa in September}\]或者更自然的变体。
小白最容易卡住的点
1. 它不是把所有路径都存下来
它只存前 $B$ 名。
2. 它不是每一步找“最好的下一个词”
它找的是“目前整体上最好的部分句子”。
3. 它不是保证全局最优
它只是一个近似搜索算法。
所以它通常更好，但不保证一定找到真正的全局最优句子。
这一节最该记住的公式
目标
\[\hat y = \arg\max_y P(y\mid x)\]二词候选的分数
\[P(y^{\langle 1 \rangle}, y^{\langle 2 \rangle} \mid x) = P(y^{\langle 1 \rangle} \mid x) P(y^{\langle 2 \rangle} \mid x, y^{\langle 1 \rangle})\]更一般地
\[P(y \mid x)=\prod_{t=1}^{T_y} P(y^{\langle t \rangle} \mid x, y^{\langle 1:t-1 \rangle})\]这一节最该记住的要点
要点 1：束搜索保留多个候选，而不是一个
这就是它和贪心搜索最根本的区别。
要点 2：每一步都扩展，再截断到前 $B$ 个
它不断“扩展候选 -> 打分 -> 裁剪候选”。
要点 3：它在效果和速度之间折中
- $B$ 小：快，但可能差
- $B$ 大：更好，但更慢
要点 4：$B=1$ 就是贪心搜索
所以束搜索可以看成贪心搜索的推广版。
这一节一句话总结
束搜索通过在每一步保留前 $B$ 个最有希望的部分句子，避免了贪心搜索“一步走错全盘皆输”的问题，是 seq2seq 生成任务中最常用的近似搜索方法。