[人工智能]再访word2vec

写在前面

以前学习的时候忽略了很多细节，也没有对照源码[1] [2]细细理解，忽略了很多有价值的内容，这里做一个记录，自己再学习word2vec的过程。

我们都知道word2vec的两种训练方法：CBOW模型和Skip-gram模型。CBOW利用中心词$w_t$的上下文来预测中心词；Skip-gram则相反，是利用中心词$w_t$预测上下文的词。这是模型的设计思路但是实际实现中有许多额外要考虑的东西，例如：词表很大时，模型的输出层预测就会占用比较大的开销。层次Softmax（Hierarchical Softmax）和负采样就是两种解决该问题的方法。

1. Hierarchical Softmax

CBOW模型最后输出是一个多分类，分类数是整个词表大小。这需要做vocab_size次sigmoid计算，对于动辄上万（[1] 中设定的词表大小为300万）的词表来说，最后一步的训练开销太大。

Hierarchical Softmax利用霍夫曼树来减少最后一步的计算开销。

实现

• 【预处理阶段】利用语料库的词频信息构造霍夫曼树，这也是计算压缩的关键。树的每一个叶子节点代表了词表中的一个单词，由此得到霍夫曼编码。（关于霍夫曼树/编码的知识点、特性可以参考资料[3]）

• 【训练阶段】由$w$的上下文单词$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}(w)$，经过网络得到输出层的输入$x_w$（这里得到$x_w$应用的是词向量相加取平均）。形象地讲，接下来要做的就是用$x_w$在霍夫曼树上进行逐层二分类，路径的最后就是预测的单词。理论的推导可以看[4] 。

  值得一提的是，word2vec采取的是直接将 $x_w$ 的更新量整个应用到每个上下文单词（$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}(w)$）的词向量上去。

2. 负采样

对于百万大小的词表来说，需要更多的文本实现模型的收敛，这既耗费计算资源，训练起来也很慢。这是因为除了目标词以外的其他所有词表理论上都是该样本句子的负样本单词（vocab_size-1）。

负采样的思想是：对于一条输入样本，只更新目标词（label=1）和若干负样本（label=0）的权重。

在论文中，作者指出指出对于小规模数据集，选择5-20个negative words会比较好，对于大规模数据集可以仅选择2-5个negative words。

负采样通过减少每轮更新的网络参数实现计算销量的提高。

而一个单词被选作negative sample的概率跟它出现的频次有关，出现频次越高的单词越容易被选作negative words。这里有些许矛盾的地方，为什么一个常见词反而是负样本呢？我的理解是：这是对于某一条输入句子（样本）而言的，在句子A中词常用词w虽然常见，但是和句子的句意不服，算作负样本。

在word2vec的C语言实现中，你可以看到对于这个概率的实现公式。每个单词被选为“negative words”的概率计算公式与其出现的频次有关。
$$P(w)=\frac{f(w{)}^{3/4}}{{\sum }_j^{n}f(w{)}^{3/4}}$$
其中$f(w)$代表单词的频次，这在Hierarchical Softmax已经做了处理。指数3/4是一个经验性的选择。

3. 源码

    if (cbow) {  //train the cbow architecture
      // in -> hidden
      cw = 0;
      for (a = b; a < window * 2 + 1 - b; a++) if (a != window) {
        c = sentence_position - window + a;
        if (c < 0) continue;
        if (c >= sentence_length) continue;
        last_word = sen[c];
        if (last_word == -1) continue;
        for (c = 0; c < layer1_size; c++) neu1[c] += syn0[c + last_word * layer1_size];
        cw++;
      }
      if (cw) {
        for (c = 0; c < layer1_size; c++) neu1[c] /= cw;
        if (hs) for (d = 0; d < vocab[word].codelen; d++) {
          f = 0;
          l2 = vocab[word].point[d] * layer1_size;
          // Propagate hidden -> output
          for (c = 0; c < layer1_size; c++) f += neu1[c] * syn1[c + l2];
          if (f <= -MAX_EXP) continue;
          else if (f >= MAX_EXP) continue;
          else f = expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];
          // 'g' is the gradient multiplied by the learning rate
          g = (1 - vocab[word].code[d] - f) * alpha;
          // Propagate errors output -> hidden
          for (c = 0; c < layer1_size; c++) neu1e[c] += g * syn1[c + l2];
          // Learn weights hidden -> output
          for (c = 0; c < layer1_size; c++) syn1[c + l2] += g * neu1[c];
        }
        // NEGATIVE SAMPLING
          if (negative > 0) for (d = 0; d < negative + 1; d++) {
          if (d == 0) {
            target = word;
            label = 1;
          } else {
            next_random = next_random * (unsigned long long)25214903917 + 11;
            target = table[(next_random >> 16) % table_size];
            if (target == 0) target = next_random % (vocab_size - 1) + 1;
            if (target == word) continue;
            label = 0;
          }
          l2 = target * layer1_size;
          f = 0;
          for (c = 0; c < layer1_size; c++) f += neu1[c] * syn1neg[c + l2];
          if (f > MAX_EXP) g = (label - 1) * alpha;
          else if (f < -MAX_EXP) g = (label - 0) * alpha;
          else g = (label - expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))]) * alpha;
          for (c = 0; c < layer1_size; c++) neu1e[c] += g * syn1neg[c + l2];
          for (c = 0; c < layer1_size; c++) syn1neg[c + l2] += g * neu1[c];
        }
        // hidden -> in
        for (a = b; a < window * 2 + 1 - b; a++) if (a != window) {
          c = sentence_position - window + a;
          if (c < 0) continue;
          if (c >= sentence_length) continue;
          last_word = sen[c];
          if (last_word == -1) continue;
          for (c = 0; c < layer1_size; c++) syn0[c + last_word * layer1_size] += neu1e[c];
        }
      }
    } else {  //train skip-gram
      for (a = b; a < window * 2 + 1 - b; a++) if (a != window) {
        c = sentence_position - window + a;
        if (c < 0) continue;
        if (c >= sentence_length) continue;
        last_word = sen[c];
        if (last_word == -1) continue;
        l1 = last_word * layer1_size;
        for (c = 0; c < layer1_size; c++) neu1e[c] = 0;
        // HIERARCHICAL SOFTMAX
        if (hs) for (d = 0; d < vocab[word].codelen; d++) {
          f = 0;
          l2 = vocab[word].point[d] * layer1_size;
          // Propagate hidden -> output
          for (c = 0; c < layer1_size; c++) f += syn0[c + l1] * syn1[c + l2];
          if (f <= -MAX_EXP) continue;
          else if (f >= MAX_EXP) continue;
          else f = expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];
          // 'g' is the gradient multiplied by the learning rate
          g = (1 - vocab[word].code[d] - f) * alpha;
          // Propagate errors output -> hidden
          for (c = 0; c < layer1_size; c++) neu1e[c] += g * syn1[c + l2];
          // Learn weights hidden -> output
          for (c = 0; c < layer1_size; c++) syn1[c + l2] += g * syn0[c + l1];
        }
        // NEGATIVE SAMPLING
        if (negative > 0) for (d = 0; d < negative + 1; d++) {
          if (d == 0) {
            target = word;
            label = 1;
          } else {
            next_random = next_random * (unsigned long long)25214903917 + 11;
            target = table[(next_random >> 16) % table_size];
            if (target == 0) target = next_random % (vocab_size - 1) + 1;
            if (target == word) continue;
            label = 0;
          }
          l2 = target * layer1_size;
          f = 0;
          for (c = 0; c < layer1_size; c++) f += syn0[c + l1] * syn1neg[c + l2];
          if (f > MAX_EXP) g = (label - 1) * alpha;
          else if (f < -MAX_EXP) g = (label - 0) * alpha;
          else g = (label - expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))]) * alpha;
          for (c = 0; c < layer1_size; c++) neu1e[c] += g * syn1neg[c + l2];
          for (c = 0; c < layer1_size; c++) syn1neg[c + l2] += g * syn0[c + l1];
        }
        // Learn weights input -> hidden
        for (c = 0; c < layer1_size; c++) syn0[c + l1] += neu1e[c];
      }
    }

从word2vec的C语言实现中可以看到，CBOW和Skip-gram两种算法都用到了Hierarchical Softmax和负采样。两个模型的区别就只有选词（相应的权重更新方式），和循环顺序的区别。

参考资料

[1] Google Code Archive - Long-term storage for Google Code Project Hosting.

[2] dav/word2vec: This tool provides an efficient implementation of the continuous bag-of-words and skip-gram architectures for computing vector representations of words. These representations can be subsequently used in many natural language processing applications and for further research. (github.com)

[3] 数据结构和算法——Huffman树和Huffman编码_null的专栏-CSDN博客_huffman树编码

[4] Hierarchical Softmax（层次Softmax） - 知乎 (zhihu.com)

[5] 源码解析——word2vec源码解析 - 知乎 (zhihu.com)

创建日期：2022年1月3日