Beam Search Decoding

Beam Search 寻找概率最大的序列的过程，可以分为以下几个步骤，这些步骤包括初始化、逐步扩展、得分排序和剪枝、终止条件等。接下来，详细解释如何通过 Beam Search 找到概率最大的序列。

1. 初始化

• 初始状态：解码器的初始状态通常是某个起始标志（例如 <s> 或 <start>）。

• 候选序列集合：开始时，候选序列集合只包含初始状态。

• 束宽度（Beam Width）：设定一个预定的束宽度 ( B )，例如 3。这意味着在每一步中最多保留 3 个最高得分的候选序列。

2. 逐步扩展

• 在每一步，针对每个候选序列，使用解码器生成所有可能的下一个词（或其他单位），并计算其联合概率。

• 对于每个候选序列 ( c_i )，它扩展后的每个新候选序列将是 ( c_i ) 加上一个新词，例如 ( c_i , w_j )，并计算其联合概率 ( P(c_i , w_j) )。

3. 计算得分并排序

• 计算每个新扩展候选序列的得分，通常是对数形式的联合概率以避免下溢，例如 ( \log P(c_i , w_j) )。

• 将所有新扩展的候选序列根据其得分进行排序，选择得分最高的 ( B ) 个序列。

4. 剪枝

• 在排序后，只保留得分最高的 ( B ) 个候选序列，其余的序列会被剪掉。

• 这一步骤确保了搜索空间的大小是可控的，而不会爆炸性增加。

5. 终止条件

• 上述过程持续进行，直到达到某个终止条件。常见的终止条件包括：

  • 生成的候选序列中包含某个终止标志（例如 <eos>）。

  • 达到最大生成长度。

6. 选择最优序列

• 当搜索过程结束时，从剩下的候选序列中选择得分最高的一个序列作为最终输出。

示例来解释这个过程：

假设我们有一个简化版的解码任务，当前候选序列为：

• 初始状态：<start>

假设束宽度 ( B = 2 )。

第一步：

• 初始状态扩展生成候选序列：

  • <start> A ( \log P(A) = -0.5 )

  • <start> B ( \log P(B) = -0.3 )

  • <start> C ( \log P(C) = -0.4 )

  排名前 ( B = 2 ) 的候选序列为：

  • <start> B ( \log P(B) = -0.3 )

  • <start> A ( \log P(A) = -0.5 )

第二步：

• 对 <start> B 进行扩展：

  • <start> B D ( \log P(B D) = -0.3 + (-0.6) = -0.9 )

  • <start> B E ( \log P(B E) = -0.3 + (-0.5) = -0.8 )

• 对 <start> A 进行扩展：

  • <start> A D ( \log P(A D) = -0.5 + (-0.4) = -0.9 )

  • <start> A E ( \log P(A E) = -0.5 + (-0.3) = -0.8 )

  全部新候选序列及其得分：

  • <start> B E ( \log P(B E) = -0.8 )

  • <start> A E ( \log P(A E) = -0.8 )

  • <start> B D ( \log P(B D) = -0.9 )

  • <start> A D ( \log P(A D) = -0.9 )

  排名前 ( B = 2 ) 的候选序列为：

  • <start> B E ( \log P(B E) = -0.8 )

  • <start> A E ( \log P(A E) = -0.8 )

依此类推，继续扩展、剪枝，直到满足终止条件。最终，从保留下来的候选序列中选择得分最高的序列作为输出。

通过这种逐步扩展与剪枝的过程，Beam Search 能够有效找到概率最大的序列，同时控制计算复杂度。