在图上使用 Beam Search 生成得分最高的句子

Question

我正在处理从一篇长文章中提取的图表。有向加权图实际上只不过是一个字典，它包含作为顶点的头部单词，这些顶点通过边连接到文章中该单词之后的每个单词（尾部单词）。因此，如果“yellow”一词在文章中出现 3 次，并且后面跟着“brick”、“brick”和“submarine”，那么“yellow”条目将在图中表示如下：

{"yellow": ["brick", "brick", "submarine"]}

这个图是使用我编写的一个 python 类生成的ExtractedGraph，除了一个__init__生成图的方法之外，还有一个getProb(self, head_word, tail_word)方法可以将头词和尾词作为输入并输出头词将遵循的概率尾词，即连接头词节点和尾词节点的边的权重。因此，如果我们输入“yellow”和“brick”，输出将是 2/3。

我的问题是，如何对该图进行波束搜索以找到得分最高的句子。具体来说，如果束搜索函数的输入是一个prefix_words字符串、一个beam_widthint 和一个sen_lengthint（一个句子的最大字长）怎么办。算法看起来如何？在在线阅读了 Beam Search 算法并观看了大量教程之后，我不确定 Beam Search 功能在这种特定情况下如何真正发挥作用。

Answer 1

假设graph_nodes是字典，每个句子必须以概率 1.0 的符号开头，<s>所有句子都必须以特殊符号结尾</s>。为了避免对假设进行排序，我将它们放在堆中，因此添加元素是恒定的。import heapqbeam = [(1.0, ["<s>"])]for _ in range(sen_length):&nbsp; &nbsp; new_beam = []&nbsp; &nbsp; for score, hypothesis in beam:&nbsp; &nbsp; &nbsp; &nbsp; hypothesis_end = hypothesis[-1]&nbsp; &nbsp; &nbsp; &nbsp; # finished hypothesis will return to the beam and compete with new ones&nbsp; &nbsp; &nbsp; &nbsp; if hypothesis_end == "</s>":&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heapq.heappush(new_beam, (score, hypothesis))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if len(new_beam) > beam_width:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heapq.heappop(new_beam)&nbsp; &nbsp; &nbsp; &nbsp; # expand unfinished hypothesis&nbsp; &nbsp; &nbsp; &nbsp; for possible_continuation in graph_nodes[hypothesis_end]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continuation_score = score * get_prob(hypothesis_end, possible_continuation)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heapq.heappush(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_beam, (continuation_score, hypothesis + [possible_continuation])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if len(new_beam) > beam_width:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heapq.heappop(new_beam)&nbsp; &nbsp; beam = new_beam如果您的假设可以有不同的长度，您应该考虑一些长度归一化（例如，概率的几何平均值）。此外，乘法概率在数值上可能并不总是稳定的，因此您可能希望使用对数和。