logo标签列表

词语预测算法

algorithmmachine-learning
21
我确定这个问题已经有人发过帖子了，但我没有找到一个提出这个确切问题的帖子。考虑以下问题：
  1. 我们有一个可用的单词字典
  2. 我们会得到许多段落的单词，我希望能够根据这些输入预测句子中的下一个单词。
假设我们有一些句子，如“你好，我的名字是汤姆”，“他的名字是杰里”，“他去了没有水的地方”。我们检查哈希表中是否存在某个单词。如果不存在，则为其分配一个唯一的ID并将其放入哈希表中。这样，我们不必将一堆字符串作为“链”存储，而只需拥有一系列唯一ID。
以上述方式，我们将得到(0, 1, 2, 3, 4)、(5, 2, 3, 6)和(7, 8, 9, 10, 3, 11, 12)等结果。请注意，3是“is”，我们在发现新单词时添加了新的唯一ID。因此，假设我们获得了一个句子“她的名字是”，那么它将变成(13, 2, 3)。我们想知道，在给定这个上下文的情况下，下一个单词应该是什么。这是我想到的算法，但我认为它不够高效：
  1. 我们有一个N个链条（观察到的句子）的列表，其中一个链可能是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)。
如果我们的扫描中没有包含完整S的链，则通过删除最不显著的单词（即第一个单词，因此删除13）进行下一次扫描。现在，像1中一样扫描(2,3)，最坏情况下为O(N*M*S)，这实际上是S-1。
按照这种方式继续扫描，直到我们得到的结果>0（如果有的话）。
计算我们收集到的所有剩余链中的下一个单词。我们可以使用哈希表进行计数，每次添加时都会保持跟踪最多的添加单词。最坏情况下建立为O(N)，查找最大单词为O(1)。
找到的最大单词是最有可能的，所以返回它。
每次扫描最坏情况下需要O(M*N*S)。这是因为有N个链，每个链有M个数字，并且我们必须检查S个数字是否匹配。最坏情况下扫描S次（从13、2、3开始，然后是2、3，然后是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直到某些链匹配即可。如果它们永远不匹配，我们就不知道要预测下一个单词！有关减少时间/空间复杂性的建议吗？谢谢！
读完您的问题后，我想到的是短语/段落的基于单词的后缀数组。请参见http://projectile.sv.cmu.edu/research/public/tools/salm/tutorial.pdf以获取示例。 - hatchet - done with SOverflow
我没有直接的解决方案，但这里有一些很好的阅读材料：http://en.wikipedia.org/wiki/N-gram http://www.codeproject.com/Articles/20423/N-gram-and-Fast-Pattern-Extraction-Algorithm http://aclweb.org/anthology-new/Q/Q13/Q13-1010.pdf - Arjun Sol
2个回答
21
这是语言模型的问题。基线方法只需要一个哈希表，将长度为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

这可以在线性时间内完成。对于每个三元组，计算第三个单词跟随前两个单词的频率（在哈希表中）。
最后，循环遍历哈希表，并仅保留出现最频繁的第三个单词作为每个键（2-元组）。线性时间。
在预测时，仅查看最后k（2）个单词并预测下一个单词。这只需要常数时间，因为它只是一个哈希表查找。
如果你想知道为什么应该仅保留短的子链而不是完整的链，请参考Markov windows的理论。如果你的模型要记住它在输入中看到的所有单词链，那么它会严重overfit其训练数据，并且在预测时只会复制其输入。有多少依赖于训练集（更多数据更好），但对于k>4，你确实需要smoothing在你的模型中。
(*) 或者转换为概率分布，但这对于你的简单示例用例不是必需的。
啊，是的，我会过度训练得很厉害。所以重申一下你说的，以3克为单位训练输入，并找到最常见的下一个单词。对于我们发现的每个键（其中键是2-gram），将最常见的第三个单词存储为哈希值。对于连续训练来说，将遇到的所有单词都保存在存储器中是否有好处？然后，每个2-gram可以保存一个列表，例如，在2-gram之后的前T个单词中选择最佳的单词。我只是试图想出一种方法，不必重新训练已经看到的输入，并记住2-gram之后我们看到了多少个先前的单词。我想这是一个问题。 - user2045279
训练时间与您想要使用的存储量成正比。例如，假设您观察到“名字是约翰”10次，“名字是彼得”9次。如果您再用两个句子训练“彼得”，那么现在彼得应该是最常见的。但是，除非我们再次对整个集合进行训练，否则我们将不知道这一点，因为我们只存储了最常见的内容。您有什么想法？ - user2045279
@user2045279：对于在线培训，你确实需要保留更多的信息，因此需要列出所有可能的结果及其频率，而不仅仅是最常见的一个。 - Fred Foo
谢谢，Lars，你帮了我很大的忙。我会接受这个答案并尝试在这个阶段实现它。 - user2045279
你是什么意思？“在预测时，只看最后的k（2）个单词并预测下一个单词。”当我们基于最后一个单词时，我们将如何预测下一个单词？ - Tom
这里有一个问题：我们能否使用下一个单词的单字概率作为排名相等的n-gram的一种方式？例如，如果“the wrath sing”和“the wrath of”在“the wrath”后面出现相同的次数，我们应该选择哪一个？我倾向于说我们应该根据哪个单词出现更多来选择（是“sing”还是“of”）。 - Nate Reed
6
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接