Word2Vec 时间复杂度

Question

我在谷歌上搜索了这个问题，但我找不到任何可靠的解决方案（一些来源给出了 log(V) 一些 log(V/2)。但是具有以下参数的 word2vec 模型的时间复杂度是多少：Word2Vec(corpus, size=4000, window=30, min_count=1, workers=50, iter=100, alpha=0.0001)我有一个等于 10000 个单词（唯一单词）的词汇表。

Answer 1

在没有正式分析/证明的情况下，在实践中和默认的“负采样”情况下，执行时间主要由语料库的大小决定，并且随着语料库的大小大致线性增长。唯一词的数量（词汇量 V）不是主要因素。

Gensim 的实现使用对词汇表大小的数组进行二分搜索来实现反例的采样，因此从技术上讲，它的时间复杂度可能是：

O(N * log(V))

• 其中 N 是总语料库大小和

• V 是唯一词词汇量。

但这种特殊的O(log(V))操作在实践中通常比原始 Google/Mikolov word2vec.c 使用的内存饥饿 O(1) 采样查找更快——可能是由于提高了 CPU 缓存效率。

所以使用默认值：

• 如果一个语料库的长度是另一个语料库的两倍，那么在更大的语料库上训练模型大约需要两倍的时间。

• 但是，如果一个语料库的大小与另一个语料库的大小相同，但词汇量是另一个语料库的两倍，那么您可能不会注意到运行时有太大变化。

在非默认hierarchical softmax情况下 – hs=1, negative=0– 单词的编码方式不同，并且随着词汇量的增加具有更长的编码，这会增加每个语料库单词的平均训练操作数 – 以log(V)为因子，我相信，所以我们再次在技术上有一个 * O(N * log(V))时间复杂度。

但是，在实践中，这种由词汇驱动的增加往往比负采样的基于二分搜索的采样中的增加更显着。

因此，如果您有两个长度相同的语料库，但其中一个的唯一词数量是其两倍，您很可能会注意到在分层 softmax 模式下的运行时间更长。