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

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

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

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

我的问题是,如何对这个图进行Beam Search以找到得分最高的句子。具体来说,如果Beam Search函数的输入是一个prefix_words字符串,一个beam_width整数和一个sen_length整数(句子的最大词长度),算法会是什么样的?在网上阅读了关于Beam Search算法的资料并观看了许多教程后,我不确定Beam Search函数在这种特定场景下如何真正工作。


回答:

假设graph_nodes是字典,每个句子必须以概率为1.0的<s>符号开始,并且所有句子必须以特殊符号</s>结束。为了避免对假设进行排序,我将它们保存在堆中,因此添加元素是常数时间操作。

import heapqbeam = [(1.0, ["<s>"])]for _ in range(sen_length):    new_beam = []    for score, hypothesis in beam:        hypothesis_end = hypothesis[-1]        # 完成的假设将返回到beam中并与新的假设竞争        if hypothesis_end == "</s>":            heapq.heappush(new_beam, (score, hypothesis))            if len(new_beam) > beam_width:                heapq.heappop(new_beam)        # 扩展未完成的假设        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

如果你的假设可以有不同的长度,你应该考虑一些长度归一化(例如,概率的几何平均)。此外,乘概率可能并不总是数值稳定的,因此你可能想要使用对数的和来代替。

Related Posts

使用LSTM在Python中预测未来值

这段代码可以预测指定股票的当前日期之前的值,但不能预测…

如何在gensim的word2vec模型中查找双词组的相似性

我有一个word2vec模型,假设我使用的是googl…

dask_xgboost.predict 可以工作但无法显示 – 数据必须是一维的

我试图使用 XGBoost 创建模型。 看起来我成功地…

ML Tuning – Cross Validation in Spark

我在https://spark.apache.org/…

如何在React JS中使用fetch从REST API获取预测

我正在开发一个应用程序,其中Flask REST AP…

如何分析ML.NET中多类分类预测得分数组?

我在ML.NET中创建了一个多类分类项目。该项目可以对…

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注