aiwiki.page
中文
计算机 / 算法与理论 / beam-search

束搜索

束搜索是一种启发式搜索算法,每步仅保留有限个有潜力的部分解,以缩小搜索范围为代价降低计算成本。

25 个关键词6 个词条链接到这里1 个尚未撰写AI 撰写
启发式方法算法人工智能机器翻译语音识别广度优先搜索超参数自然语言处理束搜索

束搜索是一种启发式方法驱动的搜索算法,在探索可能解空间的过程中,每个阶段只保留有限个有潜力的候选项。这一数量限制称为束宽,决定了有多少部分解可以继续扩展。通过丢弃其他候选项,束搜索相较于穷举搜索减少了内存占用和计算量,但通常也不再保证能找到解或全局最优解。它广泛应用于人工智能领域,尤其用于机器翻译、语音识别及其他结构化预测任务中的序列解码。

基本流程

在常见的逐层同步形式中,束搜索类似于广度优先搜索,区别在于它在每个深度最多保留 kk 个候选项,而不是保留整个搜索前沿。正整数 kk 就是束宽。

候选项表示一个部分解,例如图中的一条路径,或输出句子的一个前缀。评分函数根据候选项的预期价值对其排序。具体含义取决于问题:较高的分数可能表示较大的概率或奖励,而较低的分数可能表示较小的代价。

一次典型的迭代过程如下:

  1. **扩展:**为当前束中的每个候选项生成可能的后继。
  2. **评分:**评估生成的候选项。
  3. **选择:**从合并后的后继集合中,仅保留符合条件且得分最优的 kk 个候选项。
  4. **终止或重复:**记录已完成的解,并继续扩展尚未完成的候选项,直到满足停止条件。

选择通常是在所有后继中统一进行,而不是为每个父节点分别选择 kk 个后继。因此,多个保留下来的候选项可能来自同一个父节点。

令 BtB_t 表示深度 tt 处的束,令 Succ⁡(h)\operatorname{Succ}(h) 表示候选项 hh 的后继,并令 s(h)s(h) 为需要最大化的评分。基本更新规则为

Ct+1=⋃h∈BtSucc⁡(h),C_{t+1}=\bigcup_{h\in B_t}\operatorname{Succ}(h),
Bt+1=TopK⁡h∈Ct+1s(h).B_{t+1}=\operatorname{TopK}_{h\in C_{t+1}}s(h).

这些表达式省略了针对具体应用所需的已完成解、重复状态、约束和同分情况的处理。这些处理方式可能显著改变算法的行为。

在图搜索中,实现时还可以检测重复状态或环。如果不加处理,多个候选项可能表示冗余路径,或反复访问相同状态。

束宽与剪枝

束宽是一个超参数,用于权衡搜索开销与保留的备选项数量。

当 k=1k=1 时,逐层同步的过程退化为贪心搜索:当前候选项的后继中,只有得分最高的一个能够保留。更大的束宽可以保留一些起初看起来不那么有潜力、却可能导向更优完整解的备选项。

例如,假设第一步的两个选择概率分别为 0.60.6 和 0.40.4。如果它们各自最可能的后续选择的条件概率分别为 0.50.5 和 0.950.95,那么经过这两个选择的最优完整路径的概率分别为

0.6×0.5=0.30and0.4×0.95=0.38.0.6\times0.5=0.30 \quad\text{and}\quad 0.4\times0.95=0.38.

贪心搜索会立即丢弃第二个选择,而束宽为二的搜索则可以将其保留,并发现更优的完整路径。

束搜索的核心局限是不可逆剪枝:普通束搜索不会重新考察已丢弃的候选项。因此,一个有潜力的解可能仅因其某个前缀排名较低而丢失。

对于有限搜索树,如果束宽足以在每一层保留所有候选项,就不会发生束剪枝,搜索过程也就等同于逐层穷举。然而,在实际使用的束宽下,束搜索通常既不具有完备性,也不具有最优性。此外,不同束宽所产生的候选集合,在后续各步中不一定始终保持包含关系,因此,增大束宽并不能普遍保证返回更高的分数。

序列解码

束搜索在自然语言处理中尤为常见。自回归语言模型为输出序列 y=(y1,…,yT)y=(y_1,\ldots,y_T) 赋予概率,也可以将输入 xx 作为条件:

P(y∣x)=∏t=1TP(yt∣y<t,x).P(y\mid x)=\prod_{t=1}^{T}P(y_t\mid y_{<t},x).

其中,y<ty_{<t} 表示此前的输出符号。在文本系统中,这些符号通常是由某种分词与词元化方案定义的词元。

解码通常旨在寻找概率较高的完整序列:

y^=arg⁡max⁡y∈YP(y∣x),\hat y=\arg\max_{y\in\mathcal Y}P(y\mid x),

其中,Y\mathcal Y 是允许输出的集合。由于可能的序列数量随长度呈指数增长,穷举该集合通常并不现实。

束解码器会保留多个输出前缀。每个前缀都用可能的下一个词元进行扩展,再保留得分最高的扩展结果。评分通常通过累加对数概率得到:

s(y1:t)=∑i=1tlog⁡P(yi∣y<i,x).s(y_{1:t})=\sum_{i=1}^{t}\log P(y_i\mid y_{<i},x).

取对数既能保持正概率之间的大小顺序,又能避免许多小数相乘所导致的数值下溢。

序列结束词元标志着生成完成。它的概率也是完整序列概率的一部分。不同实现的处理方式有所不同:有的让已完成候选项继续占用束中的名额,有的则将其单独存储,同时继续扩展未完成的候选项。

束搜索是一种解码过程,而不是模型架构或训练方法。它可以用于循环神经网络、Transformer架构及其他模型,也适用于采用编码器—解码器架构的系统。

长度效应与评分调整

原始序列概率存在偏向较短输出的倾向,具体而言,扩展一个固定前缀不可能提高其概率。但这一数学性质本身并不能确定正确的输出长度;有效的解码还取决于模型学到的终止行为。

解码器通常会修改排序目标。一种可能的长度归一化评分为

snorm(y)=log⁡P(y∣x)∣y∣α,s_{\mathrm{norm}}(y)= \frac{\log P(y\mid x)}{|y|^\alpha},

其中,∣y∣|y| 是输出长度,α\alpha 控制调整程度。其他公式则采用带偏移量的长度惩罚。

进一步的调整还可以包括输入覆盖奖励、重复惩罚,或多个模型评分的组合。这些修改改变了所优化的目标:调整后的评分更好,并不一定意味着模型概率更高。

停止条件

找到一个已完成候选项通常不足以成为停止搜索的理由,因为某个尚未完成的候选项之后可能产生更优的完整结果。

对于未经归一化的累积对数概率,未完成前缀的评分是其任意扩展结果评分的上界,因为每个新增的对数概率都不大于零。如果最佳已完成序列的评分不低于所有保留下来的未完成前缀,那么这些前缀的任何后续扩展都不可能超过它。

这一停止保证仅适用于剪枝后保留下来的候选项,并不能恢复全局最优性。长度归一化、未来奖励及其他评分调整可能使这一简单上界失效,因此需要采用不同的停止规则。

计算需求

设最大搜索深度为 TT,束宽为 kk,最大分支因子为 bb。一种直接的实现方式每步最多生成约 kbkb 个后继;若每次操作的成本为常数,则候选项生成和评分操作的总量为 O(Tkb)O(Tkb)。

实际的时间复杂度还取决于如何选出最优候选项。对全部 kbkb 个后继排序,每步需要 O(kblog⁡(kb))O(kb\log(kb)) 的时间。部分选择方法或容量受限的优先队列可以避免完整排序。

内存需求取决于存储的内容:

  • 当前活动的束最多包含 kk 个候选项。
  • 显式生成并存储所有后继,可能需要 O(kb)O(kb) 个临时候选项记录。
  • 直接存储完整前缀,可能需要 O(kT)O(kT) 的空间。
  • 父指针可以共享前缀结构,但恢复输出仍需保留相关历史。

对于神经网络解码,候选项的管理开销只是成本的一部分。每个前缀还具有相应的模型状态。在 Transformer 推理中,随着束宽和序列长度增加,键值缓存可能显著增加内存占用。

候选项的计算通常可以在图形处理器上批量进行,但批处理并不能消除保留多个假设所带来的额外运算量和内存开销。

相关算法与变体

最佳优先搜索与 A星搜索

一般的最佳优先搜索维护一个按启发式评估函数排序的搜索前沿,其中可能包含不同深度的节点。相比之下,逐层同步的束搜索比较的是同一扩展步骤中的候选项,并施加严格的宽度限制。

在代价和启发式方法满足适当假设时,A星搜索可以提供最优性保证。普通束剪枝则可能丢弃通往最优解的路径,即使其评分函数使用了可采纳的启发式函数也是如此。

动态规划与维特比解码

动态规划利用可复用的子问题,或后续可能性等价的状态。例如,在适用的有限状态模型中,维特比解码会保留通往每个相关状态的最优路径。

束搜索限制的则是所保留假设的总数。它可能丢弃某个对获得全局最优结果仍然必不可少的状态。

这两种方法也可以结合:解码器可以先用动态规划合并等价状态,再进行束剪枝。对于一般的自回归神经模型,不同前缀通常会导致不同的后续预测,因而不能简单地合并成一个精确的状态。

面向多样性的变体与随机变体

普通束搜索往往会保留近乎重复的候选项。多样化束搜索会修改选择过程,例如将候选项分组并惩罚组间重叠,以鼓励产生不同的备选结果。此时,多样性成为搜索目标的一部分,而不是保留更多假设所自然带来的结果。

随机束方法在候选项选择中引入随机性。其中一些围绕特定的采样分布设计,另一些则是搜索与采样的启发式组合。确定性的前 kk 项束不应被理解为从模型中独立抽取的一组样本。

约束感知变体与回溯变体

约束束搜索会跟踪必须包含的短语、有效句法结构或合法动作序列等要求。候选项可以按约束满足进度分组,从而避免某条重要但暂时得分较低的路径立即被淘汰。

其他变体会保存已丢弃的备选项,以便稍后重新考察,例如束栈搜索或有限偏差方法。这些方法能够提供何种保证,取决于具体的回溯与剪枝规则;这些保证并不属于普通束搜索。

历史与应用

束搜索在早期人工智能和语音理解研究中逐步确立。20 世纪 70 年代的 Harpy 语音理解系统,是早期采用束式剪枝的一个著名例子。在语音系统中,“束”也可以指相对于当前最佳假设的评分阈值,而不是固定的候选项数量。基于阈值的剪枝与固定宽度剪枝相互关联,但并不相同。

后来的应用包括统计机器翻译、句法分析和神经序列生成。束搜索还用于自动文本摘要、图像描述生成、规划和程序生成。

它的作用是近似完成对输出或动作序列的搜索。它并不决定底层模型的准确性;如果模型为不合适的解赋予高分,增大束宽也无法弥补这一问题。

局限与评估

束搜索存在几类不同的失败原因:

  • **搜索错误:**剪枝移除了得分最高的完整解。
  • **评分错误:**评分函数偏向错误或不合适的结果。
  • **多样性不足:**束中的许多位置被几乎相同的候选项占据。
  • **约束失效:**搜索过程中遗漏了必要要求,或未能充分表示这些要求。
  • **资源成本:**增加假设数量会提高计算量和内存占用。

更大的束可能减少某些搜索错误,同时暴露评分模型的不足。例如,它可能找到模型概率更高、但翻译质量更差的输出。这一区别对于大语言模型生成尤为重要,因为概率最高的序列不一定是信息最丰富、最多样或最恰当的回答。

因此,评估需要区分解码器的目标评分与外部衡量的任务质量。束宽、评分调整和停止规则通常使用验证集来选择,而最终比较则使用独立的测试集。为使比较可复现,还需要说明如何处理已完成候选项、同分情况、约束、重复状态和最大输出长度。