时间戳

首页 > 解决方案 > Word2Vec 时间复杂度

python - Word2Vec 时间复杂度

问题描述

我已经用谷歌搜索了这个问题，但我找不到任何可靠的解决方案（一些来源给 log(V) 一些 log(V/2)。但是具有以下参数的 word2vec 模型的时间复杂度是多少：

Word2Vec(corpus, size=4000, window=30, min_count=1, workers=50, iter=100, alpha=0.0001)

我的词汇量等于 10000 个单词（唯一单词）。

标签： pythontime-complexitybig-ogensimword2vec

解决方案

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

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

O(N * log(V))
  • 其中 N 是总语料库大小，
  • V 是唯一词词汇量。

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

所以使用默认值：

  • 如果一个语料库的长度是另一个语料库的两倍，那么在更大的语料库上训练模型需要大约两倍的时间。
  • 但是，如果一个语料库与另一个语料库的字数相同，但词汇量是另一个语料库的两倍，那么您可能不会注意到运行时有太大变化。

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

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

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

推荐阅读