word2vec之Negative Sampling理解

word2vec之Negative Sampling理解

本文章将介绍基于Negative Sampling的CBOW和Skip-Gram模型。与Hierarchical Softmax相比，Negative Sampling不需要构建复杂的Huffman树，以及进行多次二分类，而是利用简单的随机负采样，能大幅度提高性能。因而可以说Negative Sampling是Hierarchical Softmax的一种改进。

1 CBOW模型

在cbow模型中，已知的是上下文 context(w) $context(w)$，需要去预测词语 w $w$。所以可以换种说法，对于特定的 context(w) $context(w)$，词语 w $w$是其正样本，其他词语就是其负样本。但是负样本那么多，我们如何高效的去选择负样本，这就牵涉到Negative Sampling算法。首先，我们假设已经采样到一个负样本集合 NEG(w)≠ϕ $NEG(w)\ne \varphi$。对于一个 w˜ $\tilde{w}$，定义一个标签：
ι(w˜)=1 $\iota (\tilde{w})=1$ 当 w˜=w $\tilde{w}=w$
ι(w˜)=0 $\iota (\tilde{w})=0$ 当 w˜≠w $\tilde{w}\ne w$
所以类似逻辑回归，我们定义了一个如下的公式：
p(u|context(w)))=δ(xTwθu) $p(u|context(w)))=\delta (x_w^T{\theta }^u)$ 当 ι(w˜)=1 $\iota (\tilde{w})=1$
p(u|context(w)))=1−δ(xTwθu) $p(u|context(w)))=1-\delta (x_w^T{\theta }^u)$ 当 ι(w˜)=0 $\iota (\tilde{w})=0$
将其写成一个正式为：

p(u|context(w)))=δ(xTwθu)ιw(u)(1−δ(xTwθu))1−ιw(u) $$p(u|context(w)))=\delta (x_w^T{\theta }^u{)}^{{\iota }^w(u)}(1-\delta (x_w^T{\theta }^u){)}^{1-{\iota }^w(u)}$$

假设词语之间相互独立，我们希望最大化的是：

g(w)=∏uϵw⋃NEGwp(u|context(w))=∏uϵw⋃NEGwδ(xTwθu)ιw(u)(1−δ(xTwθu))1−ιw(u) $$g(w)=\underset{uϵw\bigcup NEGw}{\prod }p(u|context(w))=\underset{uϵw\bigcup NEGw}{\prod }\delta (x_w^T{\theta }^u{)}^{{\iota }^w(u)}(1-\delta (x_w^T{\theta }^u){)}^{1-{\iota }^w(u)}$$

对于一个给定的语料库 C $C$ ，假设其中各词语相互独立，所以整体函数为:

G=∏wϵCg(w) $$G=\underset{wϵC}{\prod }g(w)$$

为了求得 g(w) $g(w)$ 的最大值，我们对上式进行最大似然估计：

ι=log(G)=log(∏wϵCg(w)) $$\iota =log(G)=log(\underset{wϵC}{\prod }g(w))$$

=∑wϵClog(g(w)) $$=\underset{wϵC}{\sum }log(g(w))$$

=∑wϵClog(∏uϵw⋃NEGwp(u|context(w))) $$=\underset{wϵC}{\sum }log(\underset{uϵw\bigcup NEGw}{\prod }p(u|context(w)))$$

=∑wϵC∑uϵw⋃NEGwlog(p(u|context(w))) $$=\underset{wϵC}{\sum }\underset{uϵw\bigcup NEGw}{\sum }log(p(u|context(w)))$$

=∑wϵC∑uϵw⋃NEGwlog(δ(xTwθu)ιw(u)(1−δ(xTwθu))1−ιw(u))) $$=\underset{wϵC}{\sum }\underset{uϵw\bigcup NEGw}{\sum }log(\delta (x_w^T{\theta }^u{)}^{{\iota }^w(u)}(1-\delta (x_w^T{\theta }^u){)}^{1-{\iota }^w(u)}))$$

=∑wϵC∑uϵw⋃NEGwιw(u)log(δ(xTwθu))+(1−ιw(u))log(1−δ(xTwθu)) $$=\underset{wϵC}{\sum }\underset{uϵw\bigcup NEGw}{\sum }{\iota }^w(u)log(\delta (x_w^T{\theta }^u))+(1-{\iota }^w(u))log(1-\delta (x_w^T{\theta }^u))$$

=∑wϵClog(δ(xTwθu))+∑uϵNEG(w)log(1−δ(xTwθu)) $$=\underset{wϵC}{\sum }log(\delta (x_w^T{\theta }^u))+\underset{uϵNEG(w)}{\sum }log(1-\delta (x_w^T{\theta }^u))$$

=∑wϵClog(δ(xTwθw))+∑uϵNEG(w)log(−δ(xTwθu) $$=\underset{wϵC}{\sum }log(\delta (x_w^T{\theta }^w))+\underset{uϵNEG(w)}{\sum }log(-\delta (x_w^T{\theta }^u)$$

为了求导方便，我们将后面的部分记为：

L(w,u)=ιw(u)log(δ(xTwθu))+(1−ιw(u))log(1−δ(xTwθu)) $$L(w,u)={\iota }^w(u)log(\delta (x_w^T{\theta }^u))+(1-{\iota }^w(u))log(1-\delta (x_w^T{\theta }^u))$$

接下来利用梯度下降算法对其进行优化：

αL(w,u)αθu=αιw(u)log(δ(xTwθu))+(1−ιw(u))log(1−δ(xTwθu))αθu $$\frac{\alpha L(w,u)}{\alpha {\theta }^u}=\frac{\alpha {\iota }^w(u)log(\delta (x_w^T{\theta }^u))+(1-{\iota }^w(u))log(1-\delta (x_w^T{\theta }^u))}{\alpha {\theta }^u}$$

=[L(w,u)−δ(xTwθu)]xTw $$=[L(w,u)-\delta (x_w^T{\theta }^u)]x_w^T$$

所以 θu ${\theta }^u$ 的更新方程为：

θu+=η[L(w,u)−δ(xTwθu)]xTw $${\theta }^u+=\eta [L(w,u)-\delta (x_w^T{\theta }^u)]x_w^T$$

由于 θu ${\theta }^u$ 和 xTw $x_w^T$ 相对称，所以对 xTw $x_w^T$ 求导得

αL(w,u)αxTw=[L(w,u)−δ(xTwθu)]θu $$\frac{\alpha L(w,u)}{\alpha x_w^T}=[L(w,u)-\delta (x_w^T{\theta }^u)]{\theta }^u$$

所以 xTw $x_w^T$ 的更新增量为：

e=η∑uϵw⋃NEGw[L(w,u)−δ(xTwθu)]θu $$e=\eta \underset{uϵw\bigcup NEGw}{\sum }[L(w,u)-\delta (x_w^T{\theta }^u)]{\theta }^u$$

由于 xTw $x_w^T$ 为 context(w) $context(w)$ 中各词的词向量之和，所以可以将该增量平均到 context(w) $context(w)$ 各词中，即：
v(u)+=e $v(u)+=e$ ，其中 uϵcontext(w) $uϵcontext(w)$

2、Skip-Gram模型

本小节介绍基于Negative Sampling的Skip-Gram模型。和基于Hierarchical Softmax模型的Skip-Gram模型相类似，我们可以将目标方程定义为：

G=∏wϵC∏uϵcontext(w)g(u) $$G=\underset{wϵC}{\prod }\underset{uϵcontext(w)}{\prod }g(u)$$

，其中 g(u) $g(u)$ 和CBOW模型中定义相似

g(w)=∏uϵw⋃NEGwp(u|w)=∏uϵw⋃NEGwδ(xTwθu)ιw(u)(1−δ(xTwθu))1−ιw(u) $$g(w)=\underset{uϵw\bigcup NEGw}{\prod }p(u|w)=\underset{uϵw\bigcup NEGw}{\prod }\delta (x_w^T{\theta }^u{)}^{{\iota }^w(u)}(1-\delta (x_w^T{\theta }^u){)}^{1-{\iota }^w(u)}$$

于是我们对 G $G$ ,去对数似然函数：

ι=log(G)=log(∏wϵC∏uϵcontext(w)∏uϵw⋃NEGwp(u|w)) $$\iota =log(G)=log(\underset{wϵC}{\prod }\underset{uϵcontext(w)}{\prod }\underset{uϵw\bigcup NEGw}{\prod }p(u|w))$$

=∑wϵC∑uϵcontext(w)∑uϵw⋃NEGwlog(p(u|w)) $$=\underset{wϵC}{\sum }\underset{uϵcontext(w)}{\sum }\underset{uϵw\bigcup NEGw}{\sum }log(p(u|w))$$

=∑wϵC∑uϵcontext(w)∑uϵw⋃NEGwlog(δ(xTwθu)ιw(u)(1−δ(xTwθu))1−ιw(u)) $$=\underset{wϵC}{\sum }\underset{uϵcontext(w)}{\sum }\underset{uϵw\bigcup NEGw}{\sum }log(\delta (x_w^T{\theta }^u{)}^{{\iota }^w(u)}(1-\delta (x_w^T{\theta }^u){)}^{1-{\iota }^w(u)})$$

=∑wϵC∑uϵcontext(w)∑uϵw⋃NEGwιw(u)log(δ(xTwθu)+(1−ιw(u))log(1−δ(xTwθu)) $$=\underset{wϵC}{\sum }\underset{uϵcontext(w)}{\sum }\underset{uϵw\bigcup NEGw}{\sum }{\iota }^w(u)log(\delta (x_w^T{\theta }^u)+(1-{\iota }^w(u))log(1-\delta (x_w^T{\theta }^u))$$

具体的推导过程和CBOW相类似，就不一一推导了。

3、Negative Sampling

由上面两节可知，采样的好坏则直接决定了最后模型的性能，那么对于一个词语 w $w$，如何快速有效的生成 NEG(w) $NEG(w)$呢？
词典 D $D$中的词在语料 C $C$中，出现的次数有高有低，对于采样有个通用的准则：高频的词语，被选择为负样本的概率应该较高，低频词语被选择为负样本的概率较低。这其实就是一个带权重采样问题，相关的算法比较多。下面借助一篇博客中的介绍解释一种带权重采样的问题。

那么word2vec怎么去实现这个带权采样问题了？
记 l0=0 $l_0=0$， lk=∑kj=1len(wj) $l_k=\underset{j=1}{\overset{k}{\sum }}len(w_j)$, k=1,2,3...,N $k=1,2,\mathrm{3...},N$。这里 wj $w_j$表示词典 D $D$中第 j $j$个词。则以 (lj)Nj=0 $(l_j{)}_{j=0}^N$会在长度 [0,1] $[0,1]$中划分N个非等分区间。记： Ii=(li−1,li] $I_i=(l_{i-1},l_i]$， i=1,2,3...N $i=1,2,\mathrm{3...}N$为其N个非等分区间。进一步引入区间 [0,1] $[0,1]$上的一个等分区间，部分节点记为 (mj)Mj=0 $(m_j{)}_{j=0}^M$，其中 M≫N $M\gg N$

有了这个刻度表后，我们可以进行一个建立一个映射关系：

Table(i)=wj $$Table(i)=w_j$$

有了这个映射后，采用就非常简单了。首先我们在[1,M-1]中随机选取一个整数 r $r$ ，然后通过映射 Table(r) $Table(r)$ ，就可以获取一个样本 w $w$ 。那么，如果碰巧选到自己怎么办？直接跳过就行了。

需要注意的是，word2vec中 len(w) $len(w)$的计算，有稍许不同，其对频率 count(w) $count(w)$作了 α $\alpha$次幂。在算法中 α $\alpha$选择为3/4,所以 len(w) $len(w)$的计算公式变为了：

len(w)=count(w)34∑uεDcount(u)34 $$len(w)=\frac{count(w{)}^{\frac{3}{4}}}{\underset{u\epsilon D}{\sum }count(u{)}^{\frac{3}{4}}}$$

M $M$ 则选择为 108 ${10}^8$