波束搜索是一种在计算机科学中使用的启发式搜索算法，用于通过扩展有限集合中最有希望的节点来探索图。它是最佳优先搜索的一种修改，通过仅保留预定数量的最佳部分解作为候选来减少内存需求，使其成为一种贪心算法。该算法广泛应用于序列解码任务，如机器翻译和语音识别，在这些任务中它在输出质量与计算可行性之间取得平衡。
波束搜索的核心思想是维护一组最有希望的部分解，称为波束，并在每一步仅扩展这些解。这种方法与考虑所有可能路径的穷举搜索方法形成对比，后者对于大型搜索空间而言在计算上可能令人望而却步。通过剪枝掉希望较小的候选，波束搜索实现了效率，但牺牲了完备性和最优性的保证。
算法细节
波束搜索使用广度优先搜索策略来构建其搜索树。在树的每一层，它生成当前层所有状态的后继，并按启发式成本的递增顺序对其进行排序。然而，它仅存储预定数量的最佳状态，记为β（波束宽度），在每一层。只有这些状态会在下一步被扩展，其余的被丢弃。
波束宽度β是一个关键参数，控制着搜索质量与资源使用之间的权衡。较大的波束宽度保留更多状态，减少被剪枝的候选数量，并可能提高解的质量，但同时也增加了内存和计算需求。当波束宽度为无穷大时，没有状态会被剪枝，波束搜索就变得与最佳优先搜索相同。相反，波束宽度为1时对应于爬山算法，它仅贪婪地跟随单条最佳路径。
波束宽度限制了执行搜索所需的内存，使其适用于内存有限的大型系统。然而，由于目标状态可能被剪枝，波束搜索牺牲了完备性，，即算法在存在解时保证以解终止的特性。此外，波束搜索不是最优的，这意味着它不保证能找到最佳可能的解
##历史发展
波束搜索首次使用是在Harpy语音识别系统中，该系统在1976年的一篇论文中提出。该过程最初被称为“轨迹模型搜索”，但“波束搜索”一词在1977年已在使用。Harpy是在卡内基梅隆大学开发的，代表了语音识别技术的重大进步，展示了启发式搜索在实际应用中的实用性
波束搜索的发展是20世纪70年代人工智能系统高效搜索算法更广泛趋势的一部分。研究人员认识到，对于复杂问题，穷举搜索方法往往不切实际，这促使了能够快速找到良好解的启发式方法的发展。Harpy系统的成功帮助确立了波束搜索作为该领域基本技术的地位
##在机器翻译中的应用
波束搜索在机器翻译系统中得到了最突出的应用，在这些系统中它帮助在许多可能的候选翻译中选择最佳翻译。在传统统计机器翻译中，句子的每个部分都会被处理，并生成单词的多种不同翻译方式。波束搜索根据句子结构保留最佳翻译，丢弃其余部分，然后根据给定标准评估剩余翻译，以选择最符合目标的那个
在现代神经机器翻译中，主要使用大型语言模型和变换器架构，波束搜索仍然是关键的解码策略之一。在生成过程中，模型在每一步产生一个关于可能的下一个标记的概率分布。波束搜索维护多个部分序列，根据其累积概率扩展最有希望的序列。这种方法产生的翻译质量高于贪心解码，后者在每一步仅选择单个最可能的标记
波束搜索在机器翻译中的应用已被广泛研究，研究人员探索了各种修改以提高性能。例如，通常应用长度归一化以避免偏向较短的序列，并开发了多样波束搜索技术以鼓励候选序列之间的多样性
##变体与扩展
已经开发了几种波束搜索的变体来解决其局限性，特别是其缺乏完备性和最优性的问题。一种方法将波束搜索与深度优先搜索相结合，产生了波束栈搜索和深度优先波束搜索等算法。这些算法是任意时间算法，能像波束搜索一样快速找到良好但可能次优的解，然后回溯并继续寻找改进的解，直到收敛到最优解
另一种变体，使用有限差异回溯的波束搜索（BULB），将波束搜索与有限差异搜索相结合。这种方法也产生任意时间算法，可以随时间改进解。在局部搜索的背景下，局部波束搜索是一种特定算法，它首先选择β个随机生成的状态，然后对于搜索树的每一层，在当前状态的所有可能后继中考虑β个新状态，直到达到目标
由于局部波束搜索常常会陷入局部最大值，一个常见解决方案是以随机方式选择下一个β个状态，概率取决于状态的启发式评估。这种搜索称为随机波束搜索。其他变体包括灵活波束搜索和恢复波束搜索，它们动态调整波束宽度或允许从较差的剪枝决策中恢复
##在现代AI系统中的作用
波束搜索在现代人工智能系统中扮演着关键角色，特别是在生成式AI应用中。在深度学习模型中，尤其是基于变换器架构的模型，波束搜索在推理期间用于生成序列，如文本、代码或语音。像OpenAI、Anthropic和Google DeepMind这样的公司在其语言模型中使用波束搜索，以产生连贯且上下文适当的输出
该技术也用于其他序列生成任务，如图像描述、语音识别和蛋白质结构预测。在这些应用中，波束搜索有助于在生成输出的质量与所需计算资源之间取得平衡。波束宽度可以根据任务的具体要求进行调整，较大的宽度以增加计算为代价提供更好的质量
##理论性质
波束搜索的理论性质已在启发式搜索的背景下进行了分析。作为一种贪心算法，它在每一步做出局部最优选择，这可能导致全局次优解。算法的性能在很大程度上取决于用于评估状态的启发式函数的质量。设计良好的启发式可以引导搜索走向良好解，而较差的启发式可能导致算法错过最优路径
波束宽度与解质量之间的权衡是实际应用中的核心考虑因素。研究表明，增加波束宽度通常会提高解质量，但收益递减。在某些情况下，过大的波束宽度可能导致过度生成和增加计算成本，而没有显著的质量提升。相反，过小的波束宽度可能因过度剪枝而导致较差的解
##计算考虑因素
波束搜索的计算复杂度主要由波束宽度和搜索空间的分支因子决定。在每一层，算法为波束中的所有状态生成后继，这需要β × b次操作，其中b是分支因子。对这些后继进行排序在每层增加了log(β × b)的额外因子。因此，总复杂度为O(β × b × L × log(β × b)，其中L是搜索的最大深度
内存使用受波束宽度限制，因为每层仅存储β个状态。这使得波束搜索特别适合内存有限的应用，如嵌入式系统或实时处理。算法在内存使用与解质量之间取得平衡的能力，促成了其在学术研究和工业应用中的持久流行
##与其他搜索方法的比较
波束搜索常与其他搜索算法进行比较，如贪心搜索、最佳优先搜索和基于机器学习的解码方法。贪心搜索，对应于波束宽度为1的波束搜索，计算效率高，但通常产生较低质量的结果。最佳优先搜索，考虑所有部分解，可以找到最优解，但需要与整个搜索空间成比例的内存
在神经序列生成的背景下，波束搜索有时与基于采样的方法形成对比，后者根据概率分布随机选择标记。采样可以产生更多样化的输出，但可能牺牲连贯性，而波束搜索倾向于产生更确定性和更高质量的结果。最近的研究探索了将波束搜索与采样相结合的混合方法，以在质量与多样性之间取得平衡
##未来方向
截至21世纪20年代初，波束搜索仍然是活跃的研究领域，特别是在大型语言模型的背景下。研究人员正在探索自适应波束宽度策略，根据模型预测的置信度进行调整，以及将外部约束纳入波束搜索过程的方法。来自NVIDIA和AMD等公司的更高效硬件的发展，如专用AI加速器，使得在实时应用中能够使用更大的波束宽度和更复杂的搜索策略
波束搜索与其他AI技术的整合，如强化学习和神经网络，也是持续研究的领域。这些努力旨在提高序列生成在广泛应用中的效率和有效性，从自然语言处理到科学发现