在讲基于Negative Sampling的word2vec模型前，我们先看看Hierarchical Softmax的的缺点。的确，使用霍夫曼树来代替传统的神经网络，可以提高模型训练的效率。但是如果我们的训练样本里的中心词w是一个很生僻的词，那么就得在霍夫曼树中辛苦的向下走很久了。能不能不用搞这么复杂的一颗霍夫曼树，将模型变的更加简单呢？
Negative Sampling就是这么一种求解word2vec模型的方法，它摒弃了霍夫曼树，采用了Negative Sampling（负采样）的方法来求解。

负采样算法

在CBOW模型中，已知词$w$w的上下文$context(w)$context(w)需要预测$w$w。因此，对于给定的$context(w)$context(w)，词$w$w就是一个正样本，其它词就是负样本了。在Skip-gram中同样也存在正负样本问题。负样本那么多，该如何选取呢？这就是Negative Sampling（负采样）问题。也就是对于给定的词，如何生成其负样本子集$NEG(w)$NEG(w)？

采用的基本要求是：词典$D$D中的词在语料$C$C中出现的次数有高有低，对于那些高频词，被选为负样本的概率就应该比较大，反之，对于那些低频词，其被选中的概率就应该比较小。本质上就是一个带权采样问题。

word2vec采用的负采样方法如下：

（1）首先将一段长度为1的线段分成长度不相等的$V$V份($V$V是词汇表的大小)，每份对应词汇表的一个词。高频词对应长线段，低频词对应短线段。每个词的线段长度由下式决定：
$len(w) = \frac{count(w)}{\sum\limits_{u \in D} count(u)}$len(w)=u∈D∑​count(u)count(w)​
在word2vec中，分子和分母都取了3/4次幂如下：
$len(w) = \frac{count(w)^{3/4}}{\sum\limits_{u \in D} count(u)^{3/4}}$len(w)=u∈D∑​count(u)3/4count(w)3/4​
（2）在引入一个长度为1的线段进行等距划分成$M$M份，其中$M>>N$M>>N，如下图所示：

如图所示，M份中的每一份都会落在某一个词对应的线段上。

（3）采样时，先从M个位置中采出neg个位置，再匹配到这neg个位置对应的词就是负词。如假设我们先采出$m_3$m3​，对应$I_2$I2​，$I_2$I2​对应的词就是负词。

注：在word2vec中，M取值默认为$10^8$108。

CBOW模型

假设已经采样一个关于$w$w的负样本子集$NEG(w) \ne \emptyset$NEG(w)​=∅ ，且对于 $\tilde w \in D$w~∈D，定义：
$L^w(\tilde w ) = \begin{cases} 1, \quad \tilde w = w \\ 0, \quad \tilde w \ne w \end{cases}$Lw(w~)={1,w~=w0,w~​=w​
表示词$\tilde w$w~的标签。即正样本的标签为1，负样本的标签为0。

对于一个给定的正样本$(context(w),w)$(context(w),w)，希望最大化：
$g(w) = \prod_{u \in {w} \cup NEG(w) }P(u|context(w))$g(w)=u∈w∪NEG(w)∏​P(u∣context(w))
其中：
$P(u|context(w)) = \begin{cases} \sigma(\mathbf x_w^T\theta^u) \qquad L^w( u )=1 \\ 1-\sigma(\mathbf x_w^T\theta^u) \quad L^w( u )=0 \end{cases}$P(u∣context(w))={σ(xwT​θu)Lw(u)=11−σ(xwT​θu)Lw(u)=0​
写成整体表达式：
$P(u|context(w)) = [\sigma(\mathbf x_w^T\theta^u)]^{L^w( u )} \cdot [1-\sigma(\mathbf x_w^T\theta^u)]^{1- L^w( u )}$P(u∣context(w))=[σ(xwT​θu)]Lw(u)⋅[1−σ(xwT​θu)]1−Lw(u)
这里的$\mathbf x_w$xw​是各词向量之和。$\theta^u$θu表示词对应的一个向量，是个待训练参数。

所以，最终$g(w)$g(w)的表达式如下：
$g(w) = \sigma(\mathbf x_w^T\theta^w) \prod_{u \in NEG(w) } [1-\sigma(\mathbf x_w^T\theta^u) ]$g(w)=σ(xwT​θw)u∈NEG(w)∏​[1−σ(xwT​θu)]
其中$\sigma(\mathbf x_w^T\theta^w)$σ(xwT​θw) 表示当上下文为$contecxt(w)$contecxt(w) 时，预测中心词为w的概率；而$\sigma(\mathbf x_w^T\theta^u) u∈NEG(w)$σ(xwT​θu)u∈NEG(w)，预测中心词为u的概率。从形式上看，最大化$g(w)$g(w), 相当于：增大正样本的概率同时降低负样本的概率。所以，给定预料库$C$C，函数：
$G= \prod_{w \in C} g(w)$G=w∈C∏​g(w)
可以作为整体的优化目标。为了计算方便可以对G 取对数。所以：
$\begin{aligned} \mathcal L &= \log G = \log \prod_{w \in C} g(w) = \sum_{w \in C} \log g(w) \\ &=\sum_{w \in C} \log \prod_{u \in {w} \cup NEG(w) } \left\{ [\sigma(\mathbf x_w^T\theta^u)]^{L^w( u )} \cdot [1-\sigma(\mathbf x_w^T\theta^u)]^{1- L^w( u )} \right\} \\ & = \sum_{w \in C} \sum_{u \in {w} \cup NEG(w) } \left\{ {L^w( u )} \log [\sigma(\mathbf x_w^T\theta^u)]+ (1- L^w( u ))\log [1-\sigma(\mathbf x_w^T\theta^u)] \right\} \\ &= \sum_{w \in C} \sum_{u \in {w} \cup NEG(w) } \mathcal L(w,u) \end{aligned}$L​=logG=logw∈C∏​g(w)=w∈C∑​logg(w)=w∈C∑​logu∈w∪NEG(w)∏​{[σ(xwT​θu)]Lw(u)⋅[1−σ(xwT​θu)]1−Lw(u)}=w∈C∑​u∈w∪NEG(w)∑​{Lw(u)log[σ(xwT​θu)]+(1−Lw(u))log[1−σ(xwT​θu)]}=w∈C∑​u∈w∪NEG(w)∑​L(w,u)​
接下来利用随机梯度上升对参数进行优化。

（1）更新$\theta^u$θu：

因为：
$\begin{aligned}\frac{\partial \mathcal L(w,u)}{\partial \theta^u} &= \frac{\partial \{ L^w( u ) \log [\sigma(\mathbf x_w^T\theta^u)]+ [1- L^w( u )]\log [1-\sigma(\mathbf x_w^T\theta^u)]\} }{\partial \theta^u} \\&= L^w( u ) [1-\sigma(\mathbf x_w^T\theta^u)]\mathbf x_w - [1- L^w( u )] \sigma(\mathbf x_w^T\theta^u) \mathbf x_w \\ &=[L^w( u )-\sigma(\mathbf x_w^T\theta^u)] \mathbf x_w \end{aligned}$∂θu∂L(w,u)​​=∂θu∂{Lw(u)log[σ(xwT​θu)]+[1−Lw(u)]log[1−σ(xwT​θu)]}​=Lw(u)[1−σ(xwT​θu)]xw​−[1−Lw(u)]σ(xwT​θu)xw​=[Lw(u)−σ(xwT​θu)]xw​​
所以 $\theta^u$θu 更新公式为：
$\theta^u:=\theta^u + \eta [L^w( u )-\sigma(\mathbf x_w^T\theta^u)] \mathbf x_w$θu:=θu+η[Lw(u)−σ(xwT​θu)]xw​
其中$\eta$η为学习率。

（2）更新$\mathbf x_w$xw​

因为$\mathcal L(w,u)$L(w,u) 关于变量$\mathbf x_w$xw​和$\theta^w$θw 是对称的。所以：
$\begin{aligned} \frac{\partial \mathcal L(w,u)}{\partial \mathbf x_w} = [L^w( u )-\sigma(\mathbf x_w^T\theta^u)] \theta^u \end{aligned}$∂xw​∂L(w,u)​=[Lw(u)−σ(xwT​θu)]θu​
所以：
$\mathbf v( \tilde w) := \mathbf v( \tilde w) + \eta \sum_{u \in {w} \cup NEG(w) } \frac{\partial \mathcal L(w,u)}{\partial \mathbf x(w)},\quad \tilde w \in context(w)$v(w~):=v(w~)+ηu∈w∪NEG(w)∑​∂x(w)∂L(w,u)​,w~∈context(w)
以下是伪代码：

Skip-gram模型

Skip-gram模型与CBOW模型的负采样模型推到过程相似。具体过程可以参考word2vec中的数学原理详解

下面简单的给出随机梯度上升更新参数的伪代码：