在图上使用 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 heapq

beam = [(1.0, ["<s>"])]

for _ in range(sen_length):

    new_beam = []

    for score, hypothesis in beam:

        hypothesis_end = hypothesis[-1]

        # finished hypothesis will return to the beam and compete with new ones

        if hypothesis_end == "</s>":

            heapq.heappush(new_beam, (score, hypothesis))

            if len(new_beam) > beam_width:

                heapq.heappop(new_beam)

        # expand unfinished hypothesis

        for possible_continuation in graph_nodes[hypothesis_end]:

            continuation_score = score * get_prob(hypothesis_end, possible_continuation)

            heapq.heappush(

                new_beam, (continuation_score, hypothesis + [possible_continuation])

            if len(new_beam) > beam_width:

                heapq.heappop(new_beam)

    beam = new_beam

如果您的假设可以有不同的长度，您应该考虑一些长度归一化（例如，概率的几何平均值）。此外，乘法概率在数值上可能并不总是稳定的，因此您可能希望使用对数和。