[论文笔记] [2013] [NIPS] Distributed Representations of Words and Phrases and their Compositionality
该论文的主要作者 Mikolov 在其先前的研究——skip-gram模型的基础上学习 word embedding技术，并提出了若干提升词向量性能与训练效率的技术手段。同时探讨了对短语进行表示的方法。
这篇论文的主要贡献为：
- 通过 subsampling 加速训练，并在提高词向量质量的同时加快了整体效率；
- 一方面简化了Noise Contrastive Estimation（NCE）的方法，在此基础上提出了Negative sampling技术来进一步提升模型训练速度；
- 探索短语的表征方法。
The Skip-gram Model
Mikolov 之前的工作 skip-gram [1] 简单看来，就是给定一个中心词去预测周围词，训练的过程就是学习词向量的过程。模型的目标函数是：
\frac{1}{T} \sum_{t=1}^T{\sum_{-c \leq j \leq c, j \neq 0}{\log{p(w_{t+j}|w_t)}}}
其中 c 为上下文词的范围。c 越大，需要的训练样本更大，训练的时间更久，但模型的效果会更好。 p(w_{t+j}|w_t) 的计算则是通过 softmax函数做概率的归一化：
p(w_O|w_I) = \frac{\exp(v_{w_O}'^Tv_{w_{I}})}{\sum_{w=1}^W\exp(v_w'^Tv_{w_I})}
其中，v_w 和 v_w' 分别为单词w的中心词词向量和周围词词向量（论文中称 “input” and “output” vector representations），W 为词表的大小。采用 softmax 函数，在 inference的时候需要计算词表中每个词的概率，在一些W非常大的任务下，无疑计算量是很大的。另外，将上式预测一个词w_O的概率，代入到 cross-entropy loss中，可得（这里只是简化下，只计算一个词的loss）
J_{\theta} = - \log{ \frac{\exp(v_{w_O}'^Tv_{w_{I}})}{\sum_{w=1}^W\exp(v_w'^Tv_{w_I})}}
通过化简，可以得到：
J_{\theta} = -v_{w_O}'^Tv_{w_I} + \log{\sum_{w=1}^W\exp(v_w'^Tv_{w_I})}
这里定义一个 score function s，其作用是将 (word, context) 映射为实值score（上式中，是采用内积的方式 ，有点计算相似度那味儿），另外简化 v_w 为 w，这样得到下式：
J(\theta) = -s(w_O,w_I) + \log{\sum_{w=1}^W\exp(s(w,w_I))}
将上式loss function中的参数用 \theta 表示, 求上面loss的梯度，可得到：
\bigtriangledown_\theta J_\theta = - \bigtriangledown_\theta(s(w_O, w_I)) + \sum_{w=1}^W{\frac{\exp(s(w,w_I))}{\sum_{w=1}^W\exp(s(w,w_I))}} \bigtriangledown_\theta(s(w,w_I))
注意到，上式中的 \frac{\exp(s(w,w_I))}{\sum_{w=1}^W\exp(s(w,w_I))} 就是 softmax 函数计算单词 w 的概率，将其用 p(w|w_I) 代替，可得下式：
\bigtriangledown_\theta J_\theta = - \bigtriangledown_\theta(s(w_O, w_I)) + \sum_{w=1}^W{p(w|w_I)} \bigtriangledown_\theta(s(w,w_I))
通过上式可以发现，在模型训练计算梯度时，后半部分的计算量非常大，于是也就有了一些工作尝试去简化后半部分的计算。本文作者提出的两个trick，一个Hierarchical softmax是基于softmax层进行改进（softmax-based approaches ），而negative sampling属于基于采样的方法（sampling-based approaches ），在计算目标函数时（或者其梯度时），它完全摒弃了 softmax函数，而是采用更方便计算的损失值来逼近softmax的分母项。另外值得注意的是，基于采样的方法只能用于训练阶段的优化（优化目标函数），在 inference 时依旧要计算 full softmax。
Hierarchical Softmax
Hierarchical Softmax的核心概念在于将复杂的归一化概率分解为一系列简单的条件概率乘积的形式。其基本原理是通过构建一棵二叉树来表示输出层结构，在此树中叶子节点对应每个word的概率分布而中间节点则代表下一词属于左子树还是右子树的概率（即一种二元分类问题）。具体而言，在从根节点出发的过程中每一条路径都能到达对应的叶子节点（即特定word）。在这里我们定义n(w,j)作为从根节点到该单词w路径上的第j个节点其中j=1,2,...,L(w)-1；而L(w)则表示该路径的总长度值ch(n)则表示n节点的右孩子定义[x]为1当且仅当x成立的情况下σ([x])即等于σ(x)而σ(¬x)=1−σ(x)这一特性使得我们可以将中间节点的概率计算转化为对应的sigmoid函数形式从而简化整个过程
可以考虑将上式的概率计算直接纳入损失函数，并对参数θ求梯度运算，从而得到以下表达式：
\bigtriangledown_\theta{J_\theta} = - \sum_{j=1}^{L(w)-1} {\sigma \left(c(w,j) \cdot s({v'_{n(w,j)}}, v_{w_I})\right) c(w,j) \bigtriangledown_\theta(s({v'_{n(w,j)}}, v_{w_I}))}
其中定义c(w,j)为指示变量n(w,j+1)=ch(n(w,j))的存在性指标变量。由此可知，当前的计算复杂度仅取决于词I的深度L(w)。而如果构建的树为 Huffman 树，则平均计算复杂度降为\log{W}。
Negative Sampling
作者提出的另外一个 trick，则是从目标函数下手。Negative Sampling 其实是作者对 Noise Contrastive Estimation（NCE）的简化，其思路是训练一个模型能够从样本中区分出负样本，这也就将softmax转换为了 logistic 回归。例如上面句子"我们周末一起去爬山 "，"爬山"作为正样本，我们从词表中取出 k 个 词作为负样本，定义目标函数为：
\log{\sigma({v'_{w_O}}^Tv_{w_I})}+\sum_{i=1}^k{\mathbb{E}_{w_i ~ P_n(w)}\left[ \log{\sigma(-{v'_w}^Tv_{w_I})} \right]}
上式的左边，其实就是正样本的概率， 而右边则是负样本的概率，而我们优化的目标就是希望增大正样本的概率，减小负样本的概率。此时对于每个词，总共要为 K+1 个概率, K \ll V。而上式负样本遵循的分布为 U(w)^{3/4}/Z，这里的 U(w) 为 ngram分布（也就是词 w 在数据集中出现的概率），Z 为归一化的参数，使得求解之后的概率和依旧为1。
在这里采用 3/4 次幂对词表进行处理后的影响是什么？例如，在一个词表中存在两个单词a和b的情况下，假设单词a的概率为 U(a) = 0.01 而单词b的概率为 U(b)=0.99 ，那么根据负采样方法计算得出它们的采样概率分别为：P(a) = \frac{0.01^{0.75}}{0.01^{0.75}+0.99^{0.75}}=0.03 ，P(b) = \frac{0.99^{0.75}}{0.01^{0.75}+0.99^{0.75}}=0.97 。由此可见，在这种处理方式下频率较高的词（如b）被赋予较低的抽样概率而频率较低的词（如a）则获得了较高的抽样概率。因此通过负采样的手段不仅显著提高了训练效率而且有效提升了模型性能。
Subsampling of Frequent Words
通常在一个语料库中，“the”, “a”这类常见词汇的分布情况会非常密集（即出现频率很高），但它们往往只提供有限的信息量；相比之下，“low-frequency words”（低频词）却能提供更为丰富的语义信息。基于此考虑（即在negative sampling的过程中采样分布的设置也是基于这一规律），研究者采用了sub-sampling的方法来优化训练数据集的质量和效率。具体而言，在训练集中某个词w_i被删除的概率P(w_i)会根据其在整个数据集中出现的频率f(w_i)进行计算：P(w_i) = 1 - \sqrt{\frac{t}{f(w_i)}}（其中t表示阈值）。此外，在这一过程中还需要考虑到每个词语的具体语义贡献度等多方面因素的影响
通过概率计算的结果来看，在文本中出现频率越高的单词 w_i ，其对应的f(w_i) 和 P(w_i) 也会越大。也就是说，在这种情况下（即当f(w_i) > t），单词 w_i 会有更高的概率会被移除。相反地，在f(w_i) \leqslant t 的情况下，则不会有这样的移除操作发生。这种处理方法在一定程度上加速了训练过程，并且能够生成更加优质的词向量。
总结
这篇论文对Mikolov先前的研究进行了补充，并优化了word2vec算法用于学习词向量机制（2+2+1）。其中第一个数字代表两种模型架构，在未采用复杂模型的情况下实现了大规模语料的有效学习；第二个数字对应两种训练方法；最后一个数字对应sub采样技术。
此外，在多类别分类问题中使用negative sampling和hierarchical softmax是一种有效的策略。
参考文献
Effective learning of word embeddings within a vector space framework was introduced by Mikolov et al., who presented an efficient method for estimating these representations in their seminal work [1].