[论文笔记] [2013] [NIPS] Distributed Representations of Words and Phrases and their Compositionality

这篇论文的作者 Mikolov 基于他前面的工作——skip-gram model学习 word embedding，提出了几个提高词向量性能和训练速度的技巧，以及如何学习短语的表示。

这篇论文的主要贡献为：

1. 利用 subsampling 加速训练和提高词向量的质量；
2. 对 Noise Contrastive Estimation（NCE）做了一些简化，提出了 Negative sampling 来优化模型训练速度；
3. 尝试学习短语的表示。

The Skip-gram Model

Mikolov 之前的工作 skip-gram [1] 简单看来，就是给定一个中心词去预测周围词，训练的过程就是学习词向量的过程。模型的目标函数是：
$$\frac{1}{T}\sum _{t=1}^T\sum _{?c\le j\le c,j?=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}^{\prime T}{v}_{w_I})}{{\sum }_{w=1}^W\exp (v_w^{\prime T}{v}_{w_I})}$$
其中，$v_w$ 和 $v_w^{\prime }$ 分别为单词$w$的中心词词向量和周围词词向量（论文中称 “input” and “output” vector representations），$W$ 为词表的大小。采用 softmax 函数，在 inference的时候需要计算词表中每个词的概率，在一些W非常大的任务下，无疑计算量是很大的。另外，将上式预测一个词$w_O$的概率，代入到 cross-entropy loss中，可得（这里只是简化下，只计算一个词的loss）
$$J_{\theta }=?\log \frac{\exp (v_{w_O}^{\prime T}{v}_{w_I})}{{\sum }_{w=1}^W\exp (v_w^{\prime T}{v}_{w_I})}$$
通过化简，可以得到：
$$J_{\theta }=?v_{w_O}^{\prime T}{v}_{w_I}+\log \sum _{w=1}^W\exp (v_w^{\prime T}{v}_{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的梯度，可得到：
$${▽}_{\theta }{J}_{\theta }=?{▽}_{\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))}{▽}_{\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)$ 代替，可得下式：
$${▽}_{\theta }{J}_{\theta }=?{▽}_{\theta }(s(w_O,w_I))+\sum _{w=1}^{W}p(w|w_I){▽}_{\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 的基本思想是将复杂的归一化概率分解成一系列简单的条件概率乘积的形式。直观看来，Hierarchical Softmax 用一棵二叉树来表示输出层，而二叉树的叶子结点表示每个word的概率，而中间结点表示下一单词属于左子树的还是属于右子树的概率（就是一个二分类问题，所以这里使用sigmoid函数来计算概率）。从根节点出发，都存在一条路径到达叶子结点（word）。令 $n(w,j)$ 表示 从根节点到叶子结点单词 $w$ 路径上的第 $j$ 个结点，$L(w)$ 表示这个路径的长度。另外，对于中间结点，令 $ch(n)$ 表示 n 的右孩子，令当x为真时，$[x]$为1，反之为-1。这样，$p(w_O|w_I)$可由下式计算得到：
$$p(w|w_I)=\prod _{j=1}^{L(w)?1}\sigma \left([n(w,j+1)=ch(n(w,j))]?{v_{n(w,j)}^{\prime }}^T{v}_{w_I}\right)$$
以下图为例，我们需要预测 [“我们”, “周末”, “一起”, “去”] 这句话的下一个单词。值得注意的是，如果使用skip-gram模型，$v_{w_I}$ 便是中心词，而如果使用cbow模型，$v_{w_I}$ 便是周围词的 avg/sum。在 以hierarchical softmax为输出层的模型中，计算下一个词为"上课" $w_2$ 的概率。首先计算属于根节点的右子树的概率 $\sigma ({v_{n(w_2,1)}^{\prime }}^T{v}_{w_I})$，则属于左子树的概率为 $1?\sigma ({v_{n(w_2,1)}^{\prime }}^T{v}_{w_I})$，因为 $\sigma (?x)=1?\sigma (x)$，所以左子树的概率可以等于 $\sigma (?{v_{n(w_2,1)}^{\prime }}^T{v}_{w_I})$。而单词"上课"在根节点的左子树，所以上式的判断 $[n(w_I,2)=ch(n(w,1))]$ 为假，则$[?]=?1$，也就是得到 $\sigma (?{v_{n(w_2,1)}^{\prime }}^T{v}_{w_I})$，由此可推得 $p(w_2|w_I)=\sigma (?{v_{n(w_2,1)}^{\prime }}^T{v}_{w_I})\sigma ({v_{n(w_2,2)}^{\prime }}^T{v}_{w_I})\sigma (?{v_{n(w_3,2)}^{\prime }}^T{v}_{w_I})$。

可以简单计算下将上式概率计算代入到损失函数中，并求梯度，得到下式：
$${▽}_{\theta }{J}_{\theta }=?\sum _{j=1}^{L(w)?1}\sigma \left(c(w,j)?s(v_{n(w,j)}^{\prime },v_{w_I})\right)c(w,j){▽}_{\theta }(s(v_{n(w,j)}^{\prime },v_{w_I}))$$
其中，$c(w,j)=[n(w,j+1)=ch(n(w,j))]$。可以看出此时计算复杂度只与 $w_I$ 的深度 $L(w)$ 相关。而如果构建的树为 Huffman 树，其平均计算复杂度为 $\log W$。

Negative Sampling

作者提出的另外一个 trick，则是从目标函数下手。Negative Sampling 其实是作者对 Noise Contrastive Estimation（NCE）的简化，其思路是训练一个模型能够从样本中区分出负样本，这也就将softmax转换为了 logistic 回归。例如上面句子"我们周末一起去爬山"，"爬山"作为正样本，我们从词表中取出 k 个 词作为负样本，定义目标函数为：
$$\log \sigma ({v_{w_O}^{\prime }}^T{v}_{w_I})+\sum _{i=1}^k{\mathbb{E}}_{w_i{P}_n(w)}\left[\log \sigma (?{v_w^{\prime }}^T{v}_{w_I})\right]$$
上式的左边，其实就是正样本的概率， 而右边则是负样本的概率，而我们优化的目标就是希望增大正样本的概率，减小负样本的概率。此时对于每个词，总共要为 $K+1$ 个概率, $K?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$，可以发现上面的分布，减少了频率大的词的抽样概率，增大频率小的词的抽样概率，因为通常重要的词出现的概率会很低。所以，通过 Negative Sampling 的方式，不仅加快了训练的速度，也提高了模型的效果。

Subsampling of Frequent Words

通常在一个语料库中，像"the", “a” 这种词出现的频率是很高的，而它们所提供的信息往往是很少的，相反那些低频词往往能提供比较多的信息。出于这个考虑（上面negative sampling中采样分布的设置也是考虑到了这一点），作者采用了 subsampling 的方法来调整训练集。具体为，训练集中的词 $w_i$ 会以 $P(w_i)$ 的概率被删除，其中 $P(w_i)=1?\sqrt{\frac{t}{f(w_i)}}$，其中 $f(w_i)$ 为词 $w_i$ 在数据集中出现的频率。

从上面的概率计算可以看出，词频越大，$f(w_i)$ 越大，$P(w_i)$ 越大，那么词 $w_i$ 就有更大的概率被删除，反之亦然。如果词 $w_i$ 的词频小于等于 t，那么$w_i$ 则不会被删除。这样的做法，它一定程度加速了训练，并且能得到更好的词向量。

总结

这篇论文对Mikolov之前的工作做补充，完善了word2vec学习词向量的机制（2+2+1）。其中第一个"2" 为两种模型结构，虽然没有采用厉害的模型，但是这种极简的模型使得大型语料的学习成为可能，变相的提升了word embedding的质量；第二个"2" 为两种训练技巧，以及最后的"1" 为 subsampling。

另外，negative sampling和hierarchical softmax 也为那些有很多类别的分类任务提供一个优化思路。

参考文献

[1] Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space[J]. arXiv preprint arXiv:1301.3781, 2013.