algorithm - 词预测算法

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)进行下一次扫描。现在，像在 1 中一样扫描 (2,3)，在最坏的情况下 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 次扫描 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

这是language modeling的问题.对于基线方法，您唯一需要的是一个哈希表，将固定长度的词链映射到最有可能的后续词。(*)

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

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-gram)只保留最常出现的第三个词。线性时间。

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

如果您想知道为什么应该只保留短子链而不是完整链，那么请查看 Markov windows 的理论.如果你的模型要记住它在输入中看到的所有单词链，那么它会很糟糕 overfit它的训练数据，并且只在预测时重现它的输入。严重程度取决于训练集(数据越多越好)，但对于 k>4 你真的需要 smoothing在你的模型中。

(*) 或概率分布，但这对于您的简单示例用例而言不是必需的。