python - 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 模式下运行时间更长。