词预测算法

Question

我确定有一个帖子,但我找不到一个问这个确切的问题.考虑以下:

1. 我们有一个单词字典
2. 我们给了很多段的单词,我希望能够根据这个输入预测句子中的下一个单词.

假设我们有一些句子,例如"你好我的名字是汤姆","他的名字是杰里","他去没有水的地方".如果单词存在,我们检查哈希表.如果没有,我们为它分配一个唯一的id并将其放在哈希表中.这样,我们可以只有一个uniqueID列表,而不是将一串"单词"存储为一串字符串.

在上面,我们将具有例如(0,1,2,3,4),(5,2,3,6)和(7,8,9,10,3,11,12).请注意,3是"is",我们在发现新单词时添加了新的唯一ID.所以说我们得到一个句子"她的名字是",这将是(13,2,3).在这个背景下,我们想知道下一个词应该是什么.这是我想到的算法,但我认为它没有效率:

1. 我们有一个N链(观察到的句子)列表,其中一个链可能是ex.3,6,2,7,8.
2. 每条链的平均大小为M,其中M是平均句子长度
3. 我们给了一个大小为S的新链,例如.13,2,3,我们希望知道最有可能的下一个词是什么？

算法:

1. 首先扫描包含完整S输入的链的整个链表(在本例中为13,2,3).由于我们必须扫描N个链,每个长度为M,并且每次比较S个字母,其O(N*M*S).

2. 如果我们的扫描中没有链条具有完整的S,则通过删除最不重要的单词(即第一个单词,然后删除13)进行下一次扫描.现在,扫描(2,3),如在最坏情况下为1(O*N*M*S),这实际上是S-1.

3. 继续扫描,直到我们得到结果> 0(如果有的话).

4. 记下我们收集的所有剩余链中的下一个词.我们可以使用哈希表,每次添加时都会对其进行计数,并跟踪最多添加的单词.O(N)最坏情况构建,O(1)找到最大字.

5. 找到的最大单词是最有可能的,所以返回它.

每次扫描都采用O(M*N*S)最差情况.这是因为有N个链,每个链都有M个数字,我们必须检查S个数字以覆盖匹配.我们扫描最坏情况的S次(13,2,3,然后是2,3,然后3次扫描= S).因此,总复杂度为O(S ^ 2*M*N).

因此,如果我们有100,000个链并且平均句子长度为10个单词,我们会查看1,000,000*S ^ 2以获得最佳单词.显然,N >> M,因为句子长度一般不随着观察句子的数量而缩放,所以M可以是常数.然后我们可以将复杂度降低到O(S ^ 2*N).然而,O(S ^ 2*M*N)可能对分析更有帮助,因为M可以是相当大的"常数".

对于这类问题,这可能是完全错误的方法,但我想分享我的想法而不是公然要求协助.我扫描我的方式的原因是因为我只想尽可能多地扫描.如果没有完整的S,只需保持修剪S直到某些链匹配.如果他们永远不匹配,我们不知道下一个词会预测什么!关于更少时间/空间复杂解决方案的任何建议？谢谢!

Answer 1

这是语言建模的问题.对于基线方法,您唯一需要的是一个哈希表,它将固定长度的单词链(例如长度为k)映射到最可能的后续单词.(*)

在训练时,您使用滑动窗口将输入分解为(k +1) - 图表.所以,如果你遇到

The wrath sing, goddess, of Peleus' son, Achilles

你为k = 2 生成

START START the
START the wrath
the wrath sing
wrath sing goddess
goddess of peleus
of peleus son
peleus son achilles

这可以在线性时间内完成.对于每个3-gram,计数(在哈希表中)第三个单词跟随前两个单词的频率.

最后,循环遍历哈希表,并为每个键(2克)保留最常出现的第三个单词.线性时间.

在预测时,仅查看k(2)个最后一个单词并预测下一个单词.这只需要一个恒定的时间,因为它只是一个哈希表查找.

如果你想知道为什么你应该只保留短链而不是全链,那么请研究马尔可夫窗口的理论.如果你的模型要记住它在输入中看到的所有单词链,那么它会严重过度训练数据,并且只能在预测时重现其输入.多么严重依赖于训练集(更多数据更好),但是对于k > 4,你真的需要在你的模型中进行平滑.

(*)或概率分布,但您的简单示例用例不需要这样做.

Answer 2

Yeh Whye Teh最近也做了一些有趣的工作来解决这个问题。“序列记忆器”扩展了传统的按部分匹配的预测方案，以考虑任意长的历史。

这是原始论文的链接：http : //www.stats.ox.ac.uk/~teh/research/compling/WooGasArc2011a.pdf

还值得阅读一些背景工作，这些工作可以在论文“内插Kneser-Ney的贝叶斯解释”中找到。