束搜索是一种启发式方法驱动的搜索算法,在探索可能解空间的过程中,每个阶段只保留有限个有潜力的候选项。这一数量限制称为束宽,决定了有多少部分解可以继续扩展。通过丢弃其他候选项,束搜索相较于穷举搜索减少了内存占用和计算量,但通常也不再保证能找到解或全局最优解。它广泛应用于人工智能领域,尤其用于机器翻译、语音识别及其他结构化预测任务中的序列解码。
基本流程
在常见的逐层同步形式中,束搜索类似于广度优先搜索,区别在于它在每个深度最多保留 个候选项,而不是保留整个搜索前沿。正整数 就是束宽。
候选项表示一个部分解,例如图中的一条路径,或输出句子的一个前缀。评分函数根据候选项的预期价值对其排序。具体含义取决于问题:较高的分数可能表示较大的概率或奖励,而较低的分数可能表示较小的代价。
一次典型的迭代过程如下:
- **扩展:**为当前束中的每个候选项生成可能的后继。
- **评分:**评估生成的候选项。
- **选择:**从合并后的后继集合中,仅保留符合条件且得分最优的 个候选项。
- **终止或重复:**记录已完成的解,并继续扩展尚未完成的候选项,直到满足停止条件。
选择通常是在所有后继中统一进行,而不是为每个父节点分别选择 个后继。因此,多个保留下来的候选项可能来自同一个父节点。
令 表示深度 处的束,令 表示候选项 的后继,并令 为需要最大化的评分。基本更新规则为
这些表达式省略了针对具体应用所需的已完成解、重复状态、约束和同分情况的处理。这些处理方式可能显著改变算法的行为。
在图搜索中,实现时还可以检测重复状态或环。如果不加处理,多个候选项可能表示冗余路径,或反复访问相同状态。
束宽与剪枝
束宽是一个超参数,用于权衡搜索开销与保留的备选项数量。
当 时,逐层同步的过程退化为贪心搜索:当前候选项的后继中,只有得分最高的一个能够保留。更大的束宽可以保留一些起初看起来不那么有潜力、却可能导向更优完整解的备选项。
例如,假设第一步的两个选择概率分别为 和 。如果它们各自最可能的后续选择的条件概率分别为 和 ,那么经过这两个选择的最优完整路径的概率分别为
贪心搜索会立即丢弃第二个选择,而束宽为二的搜索则可以将其保留,并发现更优的完整路径。
束搜索的核心局限是不可逆剪枝:普通束搜索不会重新考察已丢弃的候选项。因此,一个有潜力的解可能仅因其某个前缀排名较低而丢失。
对于有限搜索树,如果束宽足以在每一层保留所有候选项,就不会发生束剪枝,搜索过程也就等同于逐层穷举。然而,在实际使用的束宽下,束搜索通常既不具有完备性,也不具有最优性。此外,不同束宽所产生的候选集合,在后续各步中不一定始终保持包含关系,因此,增大束宽并不能普遍保证返回更高的分数。
序列解码
束搜索在自然语言处理中尤为常见。自回归语言模型为输出序列 赋予概率,也可以将输入 作为条件:
其中, 表示此前的输出符号。在文本系统中,这些符号通常是由某种分词与词元化方案定义的词元。
解码通常旨在寻找概率较高的完整序列:
其中, 是允许输出的集合。由于可能的序列数量随长度呈指数增长,穷举该集合通常并不现实。
束解码器会保留多个输出前缀。每个前缀都用可能的下一个词元进行扩展,再保留得分最高的扩展结果。评分通常通过累加对数概率得到:
取对数既能保持正概率之间的大小顺序,又能避免许多小数相乘所导致的数值下溢。
序列结束词元标志着生成完成。它的概率也是完整序列概率的一部分。不同实现的处理方式有所不同:有的让已完成候选项继续占用束中的名额,有的则将其单独存储,同时继续扩展未完成的候选项。
束搜索是一种解码过程,而不是模型架构或训练方法。它可以用于循环神经网络、Transformer架构及其他模型,也适用于采用编码器—解码器架构的系统。
长度效应与评分调整
原始序列概率存在偏向较短输出的倾向,具体而言,扩展一个固定前缀不可能提高其概率。但这一数学性质本身并不能确定正确的输出长度;有效的解码还取决于模型学到的终止行为。
解码器通常会修改排序目标。一种可能的长度归一化评分为
其中, 是输出长度, 控制调整程度。其他公式则采用带偏移量的长度惩罚。
进一步的调整还可以包括输入覆盖奖励、重复惩罚,或多个模型评分的组合。这些修改改变了所优化的目标:调整后的评分更好,并不一定意味着模型概率更高。
停止条件
找到一个已完成候选项通常不足以成为停止搜索的理由,因为某个尚未完成的候选项之后可能产生更优的完整结果。
对于未经归一化的累积对数概率,未完成前缀的评分是其任意扩展结果评分的上界,因为每个新增的对数概率都不大于零。如果最佳已完成序列的评分不低于所有保留下来的未完成前缀,那么这些前缀的任何后续扩展都不可能超过它。
这一停止保证仅适用于剪枝后保留下来的候选项,并不能恢复全局最优性。长度归一化、未来奖励及其他评分调整可能使这一简单上界失效,因此需要采用不同的停止规则。
计算需求
设最大搜索深度为 ,束宽为 ,最大分支因子为 。一种直接的实现方式每步最多生成约 个后继;若每次操作的成本为常数,则候选项生成和评分操作的总量为 。
实际的时间复杂度还取决于如何选出最优候选项。对全部 个后继排序,每步需要 的时间。部分选择方法或容量受限的优先队列可以避免完整排序。
内存需求取决于存储的内容:
- 当前活动的束最多包含 个候选项。
- 显式生成并存储所有后继,可能需要 个临时候选项记录。
- 直接存储完整前缀,可能需要 的空间。
- 父指针可以共享前缀结构,但恢复输出仍需保留相关历史。
对于神经网络解码,候选项的管理开销只是成本的一部分。每个前缀还具有相应的模型状态。在 Transformer 推理中,随着束宽和序列长度增加,键值缓存可能显著增加内存占用。
候选项的计算通常可以在图形处理器上批量进行,但批处理并不能消除保留多个假设所带来的额外运算量和内存开销。
相关算法与变体
最佳优先搜索与 A星搜索
一般的最佳优先搜索维护一个按启发式评估函数排序的搜索前沿,其中可能包含不同深度的节点。相比之下,逐层同步的束搜索比较的是同一扩展步骤中的候选项,并施加严格的宽度限制。
在代价和启发式方法满足适当假设时,A星搜索可以提供最优性保证。普通束剪枝则可能丢弃通往最优解的路径,即使其评分函数使用了可采纳的启发式函数也是如此。
动态规划与维特比解码
动态规划利用可复用的子问题,或后续可能性等价的状态。例如,在适用的有限状态模型中,维特比解码会保留通往每个相关状态的最优路径。
束搜索限制的则是所保留假设的总数。它可能丢弃某个对获得全局最优结果仍然必不可少的状态。
这两种方法也可以结合:解码器可以先用动态规划合并等价状态,再进行束剪枝。对于一般的自回归神经模型,不同前缀通常会导致不同的后续预测,因而不能简单地合并成一个精确的状态。
面向多样性的变体与随机变体
普通束搜索往往会保留近乎重复的候选项。多样化束搜索会修改选择过程,例如将候选项分组并惩罚组间重叠,以鼓励产生不同的备选结果。此时,多样性成为搜索目标的一部分,而不是保留更多假设所自然带来的结果。
随机束方法在候选项选择中引入随机性。其中一些围绕特定的采样分布设计,另一些则是搜索与采样的启发式组合。确定性的前 项束不应被理解为从模型中独立抽取的一组样本。
约束感知变体与回溯变体
约束束搜索会跟踪必须包含的短语、有效句法结构或合法动作序列等要求。候选项可以按约束满足进度分组,从而避免某条重要但暂时得分较低的路径立即被淘汰。
其他变体会保存已丢弃的备选项,以便稍后重新考察,例如束栈搜索或有限偏差方法。这些方法能够提供何种保证,取决于具体的回溯与剪枝规则;这些保证并不属于普通束搜索。
历史与应用
束搜索在早期人工智能和语音理解研究中逐步确立。20 世纪 70 年代的 Harpy 语音理解系统,是早期采用束式剪枝的一个著名例子。在语音系统中,“束”也可以指相对于当前最佳假设的评分阈值,而不是固定的候选项数量。基于阈值的剪枝与固定宽度剪枝相互关联,但并不相同。
后来的应用包括统计机器翻译、句法分析和神经序列生成。束搜索还用于自动文本摘要、图像描述生成、规划和程序生成。
它的作用是近似完成对输出或动作序列的搜索。它并不决定底层模型的准确性;如果模型为不合适的解赋予高分,增大束宽也无法弥补这一问题。
局限与评估
束搜索存在几类不同的失败原因:
- **搜索错误:**剪枝移除了得分最高的完整解。
- **评分错误:**评分函数偏向错误或不合适的结果。
- **多样性不足:**束中的许多位置被几乎相同的候选项占据。
- **约束失效:**搜索过程中遗漏了必要要求,或未能充分表示这些要求。
- **资源成本:**增加假设数量会提高计算量和内存占用。
更大的束可能减少某些搜索错误,同时暴露评分模型的不足。例如,它可能找到模型概率更高、但翻译质量更差的输出。这一区别对于大语言模型生成尤为重要,因为概率最高的序列不一定是信息最丰富、最多样或最恰当的回答。
因此,评估需要区分解码器的目标评分与外部衡量的任务质量。束宽、评分调整和停止规则通常使用验证集来选择,而最终比较则使用独立的测试集。为使比较可复现,还需要说明如何处理已完成候选项、同分情况、约束、重复状态和最大输出长度。