原标题:教程 怎么样去使用贪婪搜索和束搜索解码算法进行自然语言处理 选自MachineLearnin
本文介绍了贪婪搜索解码算法和束搜索解码算法的定义及其 Python 实现。
自然语言处理任务如图像描述生成和机器翻译，涉及生成一系列的单词。通常，针对这样一些问题开发的模型的工作方式是生成在输出词汇表上的概率分布，并通过解码算法对概率分布进行采样以生成可能性最大的单词序列。在本教程中，你将学习可用于文本生成问题的贪婪搜索和束搜索解码算法。
在自然语言处理任务中，如图像描述生成、文本摘要和机器翻译等，需要预测的是一连串的单词。通常，针对此类问题开发的模型会输出每个单词在对应的输出序列词汇表上的概率分布，然后解码器将其转化为最终的单词序列。
当你使用循环神经网络解决以文本作为输出的 NLP 任务时，你很可能会遇到这一种情况。神经网络模型的最后一层对输出词汇表中的每个单词都有对应的一个神经元，同时 softmax 激活函数被用来输出词汇表中每个单词成为序列中下一个单词的可能性。
解码最大有可能的输出序列包括根据它们的可能性搜索所有可能的输出序列。词汇表中通常含有成千上万个单词，甚至上百万个单词。因此，搜索问题依据输出序列的长度呈指数级变化，并且很难做到完全搜索（NP-complete）。
实际上，对于给定的预测，可以用启发式搜索方法返回一或多个逼近或「足够好」的解码输出序列。
由于搜索图的范围是根据源语句长度呈指数级的，所以我们一定要使用近似来有效地找到解决方案。
候选单词序列的分数是根据它们的可能性评定的。通常，使用贪婪搜索或束搜索定位文本的候选序列。本文将研究这两种解码算法。
每个单独的预测都有一个关联的分数（或概率），我们对最大分数（或最大概率）的输出序列感兴趣。一种流行的近似方法是使用贪婪预测，即在每个阶段采用得分最高的项。虽然这种方法通常是有效的，但显然不是最佳的。实际上，用束搜索作为近似搜索通常比用贪婪搜索要好得多。
一个简单的近似方法是使用贪婪搜索，即在输出序列的每一步中选择最大有可能的单词。该方法的优点是非常快，但最终输出序列的质量可能远非最佳。
我们可以用 Python 中的一个小例子来展示贪婪搜索的解码方式。我们从一个包含 10 个单词的序列的预测问题开始。每个单词的预测是其在五个单词组成的词汇表上的概率分布。
我们假定单词是整数编码的，这样，列索引就可拿来查找词汇表中的相关单词。因此，解码任务就变成从概率分布中选择整数序列的任务。argmax() 数学函数可用于选择具有最大值的数组的索引。我们大家可以用该函数选择在序列每个步骤中最大有可能的单词索引。这个函数是直接在 numpy 中提供的。
另一种流行的启发式算法是在贪婪搜索的基础扩展而来的束搜索，它返回的是可能性最大的输出序列列表。相对于在构建序列时就贪婪地选择最大有可能的下一步，束搜索选择扩展所有可能的下一步，并保持 k 是最大有可能的，k 是用户指定的参数，它通过一系列概率控制束或并行搜索的数量。
本地束搜索算法跟踪 k 个状态，而不仅仅只跟踪一个。它从 k 个随机生成的状态开始，在每一步中都生成所有 k 个状态的所有后继者。如果这其中的任何一个后继者是目标，那么算法就会停止。否则，它将从完整列表中选择k个最佳后继者并不断重复。
我们不需要从随机状态开始；相反 ，我们以k个最可能的单词开始，作为序列的第一步。对于贪婪搜索，常见的束宽度值为 1，对于机器翻译中常见的基准问题，它的值为 5 或 10。由于多个候选序列增加了更好地匹配目标序列的可能性，所以较大的束宽度会使模型性能提高。性能的提高会导致解码速度降低。
在 NMT 中，新的句子通过一个简单的束搜索解码器被翻译，该解码器能够找到一个近似最大化已训练 NMT 模型的条件概率的译文。束搜索从左到右逐词完成翻译，同时在每一步中都保持固定数目（束）的活跃候选者。增大束尺寸能大大的提升翻译性能，但代价是解码器的速度显著降低。
搜索过程能够最终靠达到最大长度、到达序列结束标记或到达阈值可能性来分别停止每个候选项。
我们可以定义一个函数来执行给定序列概率和束宽度参数k的束搜索。在每一步中，每个候选序列都被扩展为所有可能的后续步骤。每个候选步骤的分数通过概率相乘得到。选择具有最大概率的k个序列，并删去其他候选项。然后重复该过程直到序列结束。
概率是很小的数，而把小的数相乘就会得到更小的数。为了尽最大可能避免浮点数的下溢，可将概率的自然对数相乘，这样使得到的数字更大、更易于管理。此外，通过最小化分数来进行搜索也是很常见的，因此，可以将概率的负对数相乘。这个最后的调整使我们也可以按照分数对所有候选序列进行升序排序，并选择前k个序列作为可能性最大的候选序列。
我们可以将它与上一节的样本数据结合在一起，这次返回的是 3 个可能性最大的序列。
