Word2Vec原理之负采样算法

这篇主要根据前人的文章内容,整理了一遍skip-gram模型下negative-sampling的基本推导思路,只作学习之用,并不完整。公式也都是来自于已有论文。

分布式假设

Word2Vec虽然一直火热,也引发了各种词嵌入,但实际上不可否认依然是缺乏严谨的可解释性。所谓的分布式假设,就是处于相似上下文中的词具有相似的含义,一般认为这种相似包含了语义层面的相似,但却很难使用自然语言的词法、句法或语义的层面的现有知识来充分地解释。这可能也是词向量的一个缺陷,不过另一方面,这种分布式假设的概念可以应用到很多其他的领域的数据分析,比如广告分析、app点击数据分析等,毕竟只要能替代词和语料的关系,并且有上下文和中心词的类比关系,就可以一试,所以应用的广度可以说无法估计。

网络的分层

三层网络模型不再赘述,具体对于输入层和投影层,回顾CBOW模型,投影层是2c个输入词向量求和,即\(x_w=\sum_{i=1}^{2c}v(Context(w)_i)\in R^m\),最后输出为一颗huffman树。Skip-gram的输入层就是中心词\(w\)的向量,投影层是一个恒等投影,即\(v(w)\)。另,有的文献中沿用了一般神经网络的说法称投影层为隐含层。

Skip-gram模型

目标是要最大化概率:
\[
\arg\max_\theta \prod_{W\in Corpus} \prod_{c\in C(w)}p(c|w;\theta)
\]
\(C(w)\)是词\(w\)的上下文集合,因此可以简化为:
\[
\arg\max_\theta \prod_{(w,c)\in D}p(c|w;\theta)
\]
\((w,c)\)是目标词和上下文构成的pair。

求参的方法是使用softmax,其中\(v_c\)和\(v_w\in R^d\),分别是\(c\)和\(w\)的向量表示,\(C\)是所有上下文(contexts)的集合。参数\(\theta\)由\(v_{c_i}\)和\(v_{w_i}\)构成,其中\(w\in V\),\(c\in C\),\(i\in1,…,d\),参数的规模是\(|C|\times|V|\times d\)。
\[
p(c|w;\theta) = { e^{v_c \cdot v_w} \over \sum_{c’ \in C}e^{v’_c \cdot v_w}}
\]

用取log的方式:

\[\arg \max_\theta \sum_{(w,c)\in D}logp(c|w) = \sum_{(w,c)\in D}(loge^{v_c \cdot v_w}-log\sum_{c’}e^{v_{c’}\cdot v_w})\]

对嵌入过程的假设是:最大化上述目标函数可以得到好的嵌入\(v_w, \forall w \in V\),在这个意义上,相似的词会有相似的向量。

由于\(\sum_{c’ \in C}e^{v’_c \cdot v_w}\)的计算量太大,可以使用Hierarchical Softmax替代Softmax,这个在上一篇博客中已经提及。这里主要讨论Mikolov提出的Negative-Sampling方法.

值得一提的是,尽管不是所有版本的word2vec都实现了模型与算法的各种组合,但CBOW和Skip-gram两种模型,结合层次softmax和负采样两种算法,实际上可以有四种不同的组合。

Negative-Sampling

Negative-Sampling(NEG)基于skip-gram模型,但实际上是优化另一个目标函数,Mikolov说NEG是从NCE(Noise Contrastive Estimation)简化而来,用于提高训练速度,也可以改善词向量的质量。相比于分层Softmax,NEG使用的方式是随机负采样,而不是Huffman树。

我们的目标是找到合适的参数来最大化观测数据来源于语料库的概率:
\[\begin{align}
&\arg\max_\theta \prod_{(w,c)\in D}p(D=1|w,c;\theta) \\
= & \arg\max_\theta log \prod_{(w,c)\in D}p(D=1|w,c;\theta)\\
= & \arg\max_\theta \sum_{(w,c)\in D}logp(D=1|w,c;\theta)
\end{align}
\]

\(p(D=1|w,c;\theta)\)可以使用softmax来定义:
\[
p(D=1|w,c;\theta)={1 \over {1+e^{-v_c \cdot v_w}}}
\]

因此,目标函数变成:

\[
\begin{align}
\arg \max_\theta \sum_{(w,c)\in D}log{1 \over {1+e^{-v_c \cdot v_w}}}
\end{align}
\]

这个目标函数存在一个问题,如果我们设定\(\theta\)使得每一对\((w,c)\)的\(p(D=1|w,c;\theta)=1\),那这个目标函数就无意义了。而只要设置\(\theta\)对所有\(v_c\)和\(v_w\),使得\(v_c=v_w\)且\(v_c \cdot v_w=K\),而K是一个足够大的数字,则这种情况很容易出现(在Goldberg[1]的实验中当\(K\approx 40\)时,概率就为1了)。因为为了避免所有向量都是相同的值,可以去掉某些\((w,c)\)的组合,即可以随机选择\((w,c)\)对中的一部分作为负例。目标函数被改成:

\[
\begin{align}
& \arg\max_\theta \prod_{(w,c)\in D}p(D=1|c,w;\theta) \prod_{(w,c)\in D’}p(D=0|c,w;\theta) \\
= & \arg \max_\theta \prod_{(w,c)\in D}p(D=1|c,w;\theta) \prod_{(w,c)\in D’}(1-p(D=1|c,w;\theta)) \\
= & \arg \max_\theta \sum_{(w,c)\in D}logp(D=1|c,w;\theta) + \sum_{(w,c)\in D’}log(1-p(D=1|c,w;\theta)) \\
= & \arg \max_\theta \sum_{(w,c)\in D}log{1 \over {1+e^{-v_c \cdot v_w}}}+ \sum_{(w,c)\in D’}log(1-{1 \over {1+e^{-v_c \cdot v_w}}}) \\
= & \arg \max_\theta \sum_{(w,c)\in D}log{1 \over {1+e^{-v_c \cdot v_w}}}+ \sum_{(w,c)\in D’}log{1 \over {1+e^{v_c \cdot v_w}}}
\end{align}
\]

考虑sigmoid函数\(\sigma(x)={1\over {1+e^{-x}}}\),上述等式可以改写为:

\[
\begin{align}
& \arg \max_\theta \sum_{(w,c)\in D}log{1 \over {1+e^{-v_c \cdot v_w}}}+ \sum_{(w,c)\in D’}log{1 \over {1+e^{v_c \cdot v_w}}} \\
=& \arg \max_\theta \sum_{(w,c)\in D}log\sigma(v_c \cdot v_w)+ \sum_{(w,c)\in D’}log\sigma(-v_c \cdot v_w)
\end{align}
\]

这个目标函数表面的含义也可以理解为要尽量增大正例的\((v_c \cdot v_w)\)数据对,而尽量降低负例的\((v_c \cdot v_w)\)数据对。词与词之间,若其上下文很相近,则他们本身也很相似。

D’的选取与具体采样方法有关。在Mikolov的原文[2]中,考虑一个\((w,c)\in D\)的数据对样本,以及\(k\)个负样本\((w_j)\in D’, D’=W_{negative}\)。目标函数的写法是:

\[
log\sigma(v_c \cdot v_w) + \sum_{w_j\in W_{negative}}log\sigma(-v_{w_j} \cdot v_c)
\]

[1] Goldberg Y, Levy O. word2vec Explained: deriving Mikolov et al.’s negative-sampling word-embedding method[J]. arXiv preprint arXiv:1402.3722, 2014.
[2] Mikolov T, Dean J. Distributed representations of words and phrases and their compositionality[J]. Advances in neural information processing systems, 2013.