NLP

Word2Vec之 基于Negative Sampling的模型

本篇介绍基于 Negative Sampling 的 CBOW和 Skip-gram模型.Negative Sampling(简称为 NEG)是 NCE(Noise Contrastive Estimation)的一个简化版本，目的是用来提高训练速度并改善所得词向量的质量.与 Hierarchical Softmax 相比，NEG 不再使用(复杂的)Huffman树，而是利用(相对简单的)随机负采样，能大幅度提高性能，因而可作为 Hierarchical Softmax 的一种替代.

CBOW 模型

在 CBOW 模型中，已知词 $\omega$ 的上下文 $Context(\omega)$ ，需要预测 $\omega$，因此，对于给定的 $Context(\omega)$，词 $\omega$ 就是一个正样本，其它词就是负样本.负样本那么多，该如何选取呢?

假定现在已经选好了一个关于 $\omega$ 的负样本子集 $NEG(\omega) \neq \emptyset$.且对 $\forall \widetilde{\omega} \in D$，定义

$$L^{\omega}(\widetilde{\omega}) = \begin{cases} 1, \widetilde{\omega} = \omega; \\ 0, \widetilde{\omega} \neq \omega; \end{cases}$$ 表示词 $\widetilde{\omega}$ 的标签，即正样本的标签为 1，负样本的标签为 0.

---

对于一个给定的正样本 $(Context(\omega),\omega)$，我们希望最大化

$$g(\omega) = \prod_{\mu \in \{ \omega \} \cup NEG(\omega) } p(\mu | Context(\omega))$$ 其中 $$p(\mu | Context(\omega)) = \begin{cases} \sigma \left( X_{\omega}^T \theta^{\mu} \right) , & L^{\omega}(\mu) = 1; \\ 1 - \sigma \left( X_{\omega}^T \theta^{\mu} \right), & L^{\omega}(\mu) = 0; \end{cases}$$ 或者写成整体表达式 $$p(\mu | Context(\omega)) = \left[ \sigma \left( X_{\omega}^T \theta^{\mu} \right) \right]^{L^{\omega}(\mu)} \cdot \left[ 1 - \sigma \left( X_{\omega}^T \theta^{\mu} \right) \right]^{1 - L^{\omega}(\mu)}$$ ，这里 $X_{\omega}$ 任然表示 $Context(\omega)$ 中各词的词向量之和，而 $\theta^{\mu} \in R^m$ 表示词 $\mu$ 对应的 一个辅助向量，为待训练参数.

---

为什么要最大化 $g(\omega)$ 呢？让我们先来看看 $g(\omega)$ 的表达式，由上面两式得:

$$g(\omega) = \sigma \left( X_{\omega}^T \theta^{\omega} \right) \prod_{\mu \in NEG(\omega)}{\left[ 1 - \sigma \left( X_{\omega}^T \theta^{\mu} \right) \right]}$$
其中 $\sigma \left( X_{\omega}^T \theta^{\omega} \right)$ 表示当上下文为 $Context(\omega)$ 时，预测中心词为 $\omega$ 的概率，而 $\sigma \left( X_{\omega}^T \theta^{\mu} \right),\mu \in NEG(\omega)$ 则表示当上下文为 $Context(\omega)$ 时，预测中心词为 $\mu$ 的概率(这里可看成一个二分类问题).从形式上看，最大化 $g(\omega)$，相当于最大化 $\sigma \left( X_{\omega}^T \theta^{\omega} \right)$，同时最小化所有的 $\sigma \left( X_{\omega}^T \theta^{\mu} \right),\mu \in NEG(\omega)$.这不正是我们希望的吗？增大正样本的概率同时降低负样本的概率.于是，对于一个给定的语料库 $C$，函数 $$G = \prod_{\omega \in C} g(\omega)$$ 就可以作为整体优化的目标.当然，为计算方便，对 $G$ 取对数，最终的目标函数就是 $$L = log G = \sum_{\omega \in C} log g(\omega) \\= \sum_{\omega \in C} log{\prod_{\mu \in \{\omega\} \cup NEG(\omega)} \left\{ \sigma \left( X_{\omega}^T \theta^{\mu} \right)^{L^{\omega}(\mu)} \left[ 1 - \sigma \left( X_{\omega}^T \theta^{\mu} \right) \right]^{1 - L^{\omega}(\mu)} \right\}} \\= \sum_{\omega \in C} \sum_{\mu \in \{ \omega \} \cup NEG(\omega)} \left\{ L^{\omega}(\mu) \cdot log[\sigma(X_{\omega}^T \theta^{\mu})] + [1 - L^{\omega}(\mu)] \cdot log[1 - \sigma(X_{\omega}^T \theta^{\mu})] \right\}$$

为了下面梯度推导方便起见，将上式花括号里的内容简记为 $L(\omega,\mu)$，即

$$L(\omega,\mu) = L^{\omega}(\mu) \cdot log[\sigma(X_{\omega}^T \theta^{\mu})] + [1 - L^{\omega}(\mu)] \cdot log[1 - \sigma(X_{\omega}^T \theta^{\mu})]$$
接下来利用随机梯度上升法对上式进行优化，关键是要给出 $L$ 的两类梯度.首先要考虑 $L(\omega,\mu)$ 关于 $\theta^{\mu}$ 的梯度计算: $$\frac{\partial L(\omega,\mu)}{\partial \theta^{\mu}} = \frac{\partial}{\partial \theta^{\mu}} \left\{ L^{\omega}(\mu) \cdot log[\sigma(X_{\omega}^T \theta^{\mu})] + [1 - L^{\omega} (\mu)] \cdot log[1 - \sigma(X_{\omega}^T \theta^{\mu})] \right\} \\ = L^{\omega}(\mu) [1 - \sigma(X_{\omega}^T \theta^{\mu})] X_{\omega} - [1 - L^{\omega}(\mu)] \sigma(X_{\omega}^T \theta^{\mu}) X_{\omega} \\ = \left\{ L^{\omega} (\mu) [1 - \sigma(X_{\omega}^T \theta^{\mu})] - [1 - L^{\omega} (\mu)] \sigma(X_{\omega}^T \theta^{\mu}) \right\} X_{\omega} \\ = [L^{\omega}(\mu) - \sigma(X_{\omega}^T \theta^{\mu}) ] X_{\omega}$$
于是，$\theta^{\mu}$ 的更新公式可写为 $$\theta^{\mu} := \theta^{\mu} + \eta [L^{\omega}(\mu) - \sigma(X_{\omega}^T \theta^{\mu})] X_{\omega}$$

---

接下来考虑 $L(\omega,\mu)$ 关于 $X_{\omega}$ 的梯度，同样利用 $L(\omega,\mu)$ 中 $X_{\omega}$ 和 $\theta^{\mu}$ 的对称性，有

$$\frac{\partial L(\omega,\mu)}{\partial X_{\omega}} = \left[ L^{\omega}(\mu) - \sigma(X_{\omega}^T \theta^{\mu}) \right] \theta^{\mu}$$ 于是，利用 $\frac{\partial L(\omega,\mu)}{\partial X_{\omega}}$，可得 $V(\widetilde{\omega}),\widetilde{\omega} \in Context(\omega)$ 的更新公式为: $$V(\widetilde{\omega}) = := V(\widetilde{\omega}) + \eta \sum_{\mu \in \{ \omega \} \cup NEG(\omega)} \frac{\partial L(\omega,\mu)}{\partial X_{\omega}} , \widetilde{\omega} \in Context(\omega)$$

---

下面以样本 $(Context(\omega), \omega)$ 为例，给出基于 Negative Sampling 的 CBOW 模型中采用随机梯度上升法更新各参数的伪代码.

1. $\boldsymbol{e} = 0$
2. $X_{\omega} = \sum_{\mu \in Context(\omega)} V(\mu)$
3. $for \ \ \mu = \{ \omega \} \cup NEG(\omega) \ \ do$
4. $\{$
5. $\ \ \ \ q = \sigma(X_{\omega}^T \theta^{\mu})$
6. $\ \ \ \ g = \eta ( L^{\omega}(\mu) - q )$
7. $\ \ \ \ \boldsymbol{e} := \boldsymbol{e} + g \theta^{\mu}$
8. $\ \ \ \ \theta^{\mu} := \theta^{\mu} + g X_{\omega}$
9. $\}$
10. $for \ \ \mu \in Context(\omega) \ \ do$
11. $\{$
12. $\ \ \ \ V(\mu) := V(\mu) + \boldsymbol{e}$
13. $\}$

注意，步 7 和步 8 不能交换次序，即 $\theta^{\mu}$ 要等贡献到 $\boldsymbol{e}$ 后才更新.

---

Skip-gram 模型

有了 Hierarchical Softmax 框架下由 CBOW 模型过渡到 Skip-gram 模型的推导经验，这里，我们任然可以这样做.首先，将优化目标函数由原来的

$$G = \prod_{\omega \in C} g(\omega)$$ 改写为 $$G = \prod_{\omega \in C} \prod_{\mu \in Context(\omega)} g(\mu)$$ 这里，$\prod_{\mu \in Context(\omega)} g(\mu)$ 表示对于一个给定的样本 $(\omega,Context(\omega))$ ，我们希望最大化的量，$g(\mu)$ 类似于上一节的 $g(\omega)$，定义为: $$g(\mu) = \prod_{z \in \{ \mu \} \cup NEG(\mu)} p(z | \omega)$$ 其中 $NEG(\mu)$ 表示处理词 $\mu$ 时生成的负样本子集，条件概率 $$p(z | \omega) = \begin{cases} \sigma (v(\omega)^T \theta^z), & L^{\mu}(z) == 1; \\ 1 - \sigma (v(\omega)^T \theta^z),& L^{\mu}(z) == 0; \end{cases}$$ 或者写成整体表达式: $$p(z | \omega) = \left[ \sigma (v(\omega)^T \theta^z) \right]^{L^{\mu}(z)} \cdot \left[ 1 - \sigma (v(\omega)^T \theta^z) \right]^{1 - L^{\mu}(z)}$$ 同样，我们取 $G$ 的对数，最终的目标函数就是 $$L = log G = log \prod_{\omega \in C} \prod_{\mu \in Context(\omega)} g(\mu) = \sum_{\omega \in C} \sum_{\mu \in Context(\omega)} log g(\mu) \\ = \sum_{\omega \in C} \sum_{\mu \in Context(\omega)} log \prod_{z \in \{ \mu \} \cup NEG(\mu)} p(z | \omega) \\ = \sum_{\omega \in C} \sum_{\mu \in Context(\omega)} \sum_{z \in \{ z \} \cup NEG(\mu)} log( p(z | \omega)) \\ = \sum_{\omega \in C} \sum_{\mu \in Context(\omega)} \sum_{z \in \{ z \} \cup NEG(\mu)} log \left\{ \left[ \sigma (v(\omega)^T \theta^z) \right]^{L^{\mu}(z)} \cdot \left[ 1 - \sigma (v(\omega)^T \theta^z) \right]^{1 - L^{\mu}(z)} \right\} \\ = \sum_{\omega \in C} \sum_{\mu \in Context(\omega)} \sum_{z \in \{ z \} \cup NEG(\mu)} \left\{ L^{\mu}(z) \cdot log[\sigma (v(\omega)^T \theta^z)] + [1 - L^{\mu}(z)] \cdot log[1 - \sigma (v(\omega)^T \theta^z)] \right\}$$ 后面就是对中间花括号里的内容进行求偏导然后对 $\theta^{z}$进行梯度更新了.

---

下面以样本 $(\omega,Context(\omega))$ 为例，给出基于 Negative Sampling 的 Skip-gram 模型中采用随机梯度上升法更新各参数的伪代码:

1. $for \ \ \widetilde{\omega} = Context(\omega) \ \ do$
2. $\{$
3. $\ \ \ \ \boldsymbol{e} = 0$
4. $\ \ \ \ for \ \ \mu = \{ \omega \} \cup NEG^{\widetilde{\omega}}(\omega) \ \ do$
5. $\ \ \ \ \{$
6. $\ \ \ \ \ \ \ \ q = \sigma(V(\widetilde{\omega})^T \theta^{\mu})$
7. $\ \ \ \ \ \ \ \ g = \eta (L^{\omega}(\mu) - q )$
8. $\ \ \ \ \ \ \ \ \boldsymbol{e} := \boldsymbol{e} + g \theta^{\mu}$
9. $\ \ \ \ \ \ \ \ \theta^{\mu} := \theta^{\mu} + g V(\widetilde{\omega})$
10. $\ \ \ \ \}$
11. $\ \ \ \ V(\widetilde{\omega}) := V(\widetilde{\omega}) + \boldsymbol{e}$
12. $\}$

---

负采样算法

顾名思义，在基于 Negative Sampling 的 CBOW 和 Skip-gram 模型中，负采样是个很重要的环节，对于一个给定的词 $\omega$，如何生成 $NEG(\omega)$呢？

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

---

下面先用一段通俗的描述来帮助读者理解带权采样的机理.

设词典 $D$ 中的每一个词 $\omega$ 对应一个线段 $l(\omega)$，长度为

$$len(\omega) = \frac{counter(\omega)}{\sum_{\mu \in D} counter(\mu)}$$ 这里 $counter(\cdot)$ 表示一个词在语料 $C$ 中出现的次数(分母中的求和项用来做归一化).现在将这些线段首尾相连拼接在一起，形成一个长度为 $1$ 的单位线段.如果随机地往这个单位线段上打点，则其中长度越长的线段(对应高频词)被打中的概率就越大.

---

接下来谈谈 word2vec 中的具体做法: 记 $l_0 = 0, l_k = \sum_{j=1}^k len(\omega_j),k = 1,2,\cdots,N$，这里 $\omega_j$ 表示词典 $D$ 中第 $j$ 个词，则以 $\{ l_j \}_{j=0}^N$ 为剖分节点可得到区间 $[0,1]$上的一个非等距剖分，$I_i = (l_{i-1},l_i],i = 1,2,\cdots,N$为其 $N$ 个剖分区间.进一步引入区间 $[0,1]$ 上的一个等距离剖分，剖分节点为 $\{ m_j \}_{j=0}^M$，其中 $M >> N$，具体如下图所示:

将内部剖分节点 $\{ m_j \}_{j=1}^{M-1}$ 投影到非等距剖分上，可建立 $\{ m_j \}_{j=1}^{M-1}$ 与区间 $\{ I_j \}_{j=1}^N$ (或者说 $\{ \omega_j \}_{j=1}^N$ ) 的映射关系

$$Table(i) = \omega_k, where \ \ \ \ m_i \in I_k,i = 1,2,\cdots, M - 1$$
有了这个映射，采样就简单了：每次生成一个 $[1, M - 1]$ 间的随机整数 $r$，$Table(r)$ 就是一个样本.当然，这里还有一个细节，当对 $\omega_i$ 进行负采样时，如果碰巧选到 $\omega_i$ 自己怎么办？那就跳过去呗:-)，代码中也是这么处理的.

指得一提的是，word2vec 源码中为词典 $D$ 中的词设置权值时，不是直接用 $counter(\omega)$，而是对其作了 $\alpha$ 次幂，其中 $\alpha = \frac{3}{4}$，即变成了

$$len(\omega) = \frac{counter(\omega)^{\frac{3}{4}}}{\sum_{\mu \in D} [counter(\mu)]^{\frac{3}{4}}}$$ 此外，代码中取 $M = 10^8$ (对应源码中变量 table_size)，而yingshe映射则是通过一个名为 InitUnigramTable的函数来完成。