许多 NLP 应用程序（例如机器翻译、聊天机器人、文本摘要和语言模型）都会生成一些文本作为输出。此外，图像字幕或自动语音识别（即语音转文本）等应用程序也会输出文本，尽管它们可能不被视为纯 NLP 应用程序。

所有这些应用程序都使用了一些常用的算法作为其产生最终输出的最后一步。

在本文中，我将探讨 Beam Search，并解释其用途和工作原理。我们将简要介绍贪婪搜索，以便我们了解 Beam Search 如何对其进行改进。

我们首先了解一下 NLP 模型如何生成其输出，以便我们能够理解 Beam Search（和 Greedy Search）的适用范围。

注意：根据要解决的问题，NLP 模型可以生成字符或单词的输出。与 Beam Search 相关的所有概念都同样适用于这两种情况，因此在本文中我将交替使用这两个术语。

NLP 模型如何生成输出

我们以序列到序列模型为例。这些模型经常用于机器翻译等应用。

例如，如果该模型用于从英语翻译成西班牙语，它会将源语言中的句子（例如英语中的“You are welcome”）作为输入，并输出目标语言中的等效句子（例如西班牙语中的“De nada”）。

文本是单词（或字符）的序列，NLP 模型构建由源语言和目标语言的整个单词集组成的词汇表。

该模型将源句作为输入，并将其传递至嵌入层和编码器。然后，编码器输出一个编码表示，该表示紧凑地捕获输入的基本特征。

然后，该表示与“<START>”标记一起被输入到解码器中，作为其输出的种子。解码器使用这些来生成自己的输出，即目标语言中句子的编码表示。

然后将其传递到输出层，该输出层可能由一些线性层和 Softmax 组成。线性层输出词汇表中每个单词在输出序列中每个位置出现的可能性的分数。然后 Softmax 将这些分数转换为概率。

当然，我们的最终目标不是这些概率，而是最终的目标句子。为了得到这个目标句子，模型必须决定它应该为目标序列中的每个位置预测哪个单词。

它是怎样做到的？

贪婪搜索

一种相当明显的方法是简单地取每个位置上概率最高的单词并进行预测。这种方法计算速度快，易于理解，而且通常能产生正确的结果。

事实上，贪婪搜索很容易理解，我们不需要花更多时间来解释它。但我们能做得更好吗？

啊哈，终于让我们进入真正的主题了！

束搜索 (Beam Search) 对贪婪搜索 (Greedy Search) 做了两点改进。

使用贪婪搜索时，我们只选取每个位置上最好的一个单词。相比之下，定向搜索会扩展这一范围，并选取最好的“N”个单词。
使用贪婪搜索时，我们会单独考虑每个位置。一旦我们确定了该位置的最佳单词，我们就不会检查它之前（即前一个位置）或之后的单词。相比之下，定向搜索会挑选迄今为止的“N”个最佳序列，并考虑所有前面的单词与当前位置的单词的组合概率。

换句话说，它投射的“搜索光束”比贪婪搜索更宽一些，这就是它的名字的由来。超参数“N”称为光束宽度。

直观地看，这比贪婪搜索能给我们带来更好的结果。因为我们真正感兴趣的是最佳的完整句子，如果我们在每个位置只挑选最佳的单个单词，我们可能会错过它。

让我们举一个简单的例子，其中 Beam 宽度为 2，并且使用字符来保持简单。

当涉及到第二个位置时，它会重新运行模型两次，通过固定第一个位置的可能字符来生成概率。换句话说，它将第一个位置的字符限制为“A”或“C”，并生成两个具有两组概率的分支。具有第一组概率的分支对应于位置 1 中的“A”，而具有第二组概率的分支对应于位置 1 中的“C”。
现在，它会根据前两个字符的组合概率从两组概率中挑选出总体上最好的两个字符对。因此，它不会只从第一组中挑选出一个最佳字符对，也不会从第二组中挑选出一个最佳字符对。例如“AB”和“AE”