21

我确定有一篇关于此的帖子，但我找不到有人问这个确切的问题。考虑以下：

  1. 我们有一个可用的字典
  2. 我们得到了很多单词段落，我希望能够在给定这个输入的情况下预测句子中的下一个单词。

假设我们有几句话，例如“你好，我叫汤姆”、“他叫杰瑞”、“他去没有水的地方”。如果一个单词存在，我们检查一个哈希表。如果没有，我们为其分配一个唯一的 id 并将其放入哈希表中。这样，我们可以只拥有一个 uniqueID 列表，而不是将单词“链”存储为一堆字符串。

在上面，我们将有例如 (0, 1, 2, 3, 4), (5, 2, 3, 6) 和 (7, 8, 9, 10, 3, 11, 12)。请注意，3 是“是”，我们在发现新单词时添加了新的唯一 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，直到某些链匹配。如果它们永远不匹配，我们不知道下一个词要预测什么！关于时间/空间复杂度较低的解决方案有什么建议吗？谢谢！

4

2 回答 2

21

这就是语言建模的问题。对于基线方法，您唯一需要的是将固定长度的单词链（例如长度k）映射到最可能的后续单词的哈希表。（*）

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

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) 个最后的单词并预测下一个单词。这只需要恒定的时间，因为它只是一个哈希表查找。

如果您想知道为什么应该只保留短子链而不是完整链，请查看马尔可夫窗口理论。如果您的模型要记住它在输入中看到的所有单词链，那么它将严重过度拟合其训练数据，并且仅在预测时重现其输入。严重程度取决于训练集（数据越多越好），但是对于k > 4，您确实需要在模型中进行平滑处理。

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

于 2013-09-10T20:45:54.833 回答
6

Yeh Whye Teh also has some recent interesting work that addresses this problem. The "Sequence Memoizer" extends the traditional prediction-by-partial-matching scheme to take into account arbitrarily long histories.

Here is a link the original paper: http://www.stats.ox.ac.uk/~teh/research/compling/WooGasArc2011a.pdf

It is also worth reading some of the background work, which can be found in the paper "A Bayesian Interpretation of Interpolated Kneser-Ney"

于 2013-09-13T14:41:55.910 回答