吴恩达深度学习第5课 3.3：集束搜索

视频封面

视频元信息

课程来源：吴恩达（Andrew Ng）深度学习专项课程 · 序列模型（Sequence Models）第三周
本集主题：集束搜索（Beam Search）算法原理
时长：约 12 分钟

内容摘要（TL;DR）

本节课讲解机器翻译与语音识别中用于寻找最可能输出序列的集束搜索（Beam Search） 算法。以法译英为例，通过设置集束宽度 B（本例 B=3），在每一步保留概率最高的 B 个候选词，逐步扩展并筛选，最终输出最可能的完整句子。相比贪心搜索，集束搜索能在计算成本可控的前提下找到更优结果。

一、问题背景：为什么需要集束搜索 [00:04]

在机器翻译和语音识别任务中，给定输入（法语句子或音频片段），我们不希望输出随机的翻译或转录，而是希望输出最好、最可能的结果。

集束搜索（Beam Search）正是用于实现这一目标的最常用算法。

理解：这与之前学过的贪心搜索（Greedy Search）形成对比。贪心搜索每一步只选概率最高的一个词，容易陷入局部最优；集束搜索则同时保留多个候选，扩大了搜索空间。

二、运行示例与词表设定 [00:33]

以法语例句为例，目标是翻译成英语：

输入：Jane-Vizic-Lefriek on Sept. 10（法语）
期望输出：Jane visits Africa in September（英语）

词表设定：

词表大小约为 10,000 个词
为简化问题，忽略大小写，所有词以小写形式列出

考点：词表大小直接影响集束搜索每一步的计算量。 词表越大，候选组合越多，计算成本越高。

三、集束搜索第一步：选择第一个词 [01:00]

操作流程：

将输入法语句子通过编码网络（Encoder）
进入解码网络（Decoder） 的第一步
输出层是 softmax，覆盖全部 10,000 个词的概率
取概率最高的 B 个词 作为第一个词的候选

集束宽度参数 B（Beam Width）：

本例中设 B = 3
意味着每一步同时考虑 3 个候选
若 B = 10，则保留概率最高的 10 个候选

假设第一步评估后，最可能的三个词是：in、Jane、September

理解：贪心搜索只会选概率最高的那一个词然后继续；集束搜索则把这三个词都存入内存，分别尝试后续扩展。

四、集束搜索第二步：选择第二个词 [02:45]

对第一步保留的 3 个候选词，分别考虑第二个词的可能性。

具体做法：

以第一个词为 in 为例：
- 将解码器第一步的输出 ŷ<1> 硬连线（hardwire）为 in
- 反馈回网络，计算第二个词 ŷ<2> 的概率
- 对词表中全部 10,000 个词，计算 P(ŷ<2> | x, ŷ<1>=in)
对 Jane 和 September 重复同样操作

关键：评估的是词对的联合概率

根据条件概率规则：

$$P(y_1, y_2 \mid x) = P(y_1 \mid x) \times P(y_2 \mid x, y_1)$$

第一步已保存 P(y1 | x)
第二步计算 P(y2 | x, y1)
两者相乘得到词对的概率

易错点：第二步关注的不是第二个词单独的概率，而是第一个词和第二个词组成的词对的联合概率。 这是集束搜索的核心逻辑。

候选数量计算：

每个第一步候选对应 10,000 个第二步候选
总共考虑 3 × 10,000 = 30,000 种组合
从中选出概率最高的 3 个词对

假设最终选出的三个词对是：

in September
Jane is
Jane visits

思考：注意 September 作为第一个词的候选被淘汰了，因为以它开头的词对没有进入前三。这意味着第一个词的候选从 3 个减少到 2 个（in 和 Jane），但集束宽度仍为 3，跟踪的是 3 个词对。

五、网络副本与计算效率 [08:21]

重要实现细节：

由于 B = 3，每一步需要实例化 3 个网络副本
每个副本对应第一个词的不同选择
但这 3 个副本可以高效地并行评估所有 30,000 个选项

考点：不需要实例化 30,000 个网络副本，只需要 B 个（本例为 3 个）副本即可快速评估所有 10,000 个 softmax 输出。

理解：这是集束搜索高效的关键——通过少量网络副本并行处理大量候选组合。

六、集束搜索第三步及后续 [09:14]

第三步操作：

对已保留的三个词对（in September、Jane is、Jane visits），分别考虑第三个词
硬连线前两个词，计算第三个词的概率
同样评估所有 10,000 个词，选出概率最高的 3 个三元组

假设第三步选出的候选：

in September Jane
Jane is visiting
Jane visits Africa

持续迭代：

每一步增加一个词
直到遇到句末符号（End of Sentence Symbol, <EOS>）
最终输出最可能的完整句子：Jane visits Africa in September

七、集束搜索 vs 贪心搜索 [11:16]

对比项	贪心搜索（Greedy Search）	集束搜索（Beam Search）
每步候选数	1 个	B 个（如 3、10）
搜索范围	局部最优	更广的搜索空间
输出质量	通常较差	通常更好
计算成本	低	较高但可控