Word2vec(CBOW,skip-gram,负采样,分层softmax)

CS224N:Natural Language Processing with Deep Learning

Word2vec

Word2vec是一个软件包，包括:

两个算法：

• continuous bag-of-words (CBOW) 连续词袋模型
• skip-gram 跳字模型

两个训练方法：

• 负采样 negative sampling
• 分层 hierarchical softmax

上下文context:
一个单词的上下文是m个周围单词的集合。例如，句子“the quick brown fox jumping over the lazy dog”中单词“fox”的m = 2上下文是{“quick”，“brown”，“jumping”，“over”}。
这个模型依赖于语言学中一个非常重要的假设，即分布相似性distributional similarity，即相似的单词具有相似的上下文。

语言模型 Language Models

任意给定n个tokens序列的概率:

$$P\left(w_1, w_2, \cdots, w_n\right)$$

看一个例句：
“The cat jumped over the puddle.”

Unigram model（一元模型）：

$$P\left(w_1, w_2, \cdots, w_n\right)=\prod_{i=1}^n P\left(w_i\right)$$

Bigram model（二元模型）:

$$P\left(w_{1}, w_{2}, \cdots, w_{n}\right)=\prod_{i=2}^{n} P\left(w_{i} \mid w_{i-1}\right)$$

Continuous Bag of Words Model (CBOW)

从中心词周围的上下文预测中心词，对每一个word，我们学习两个向量

• $v$输入向量，当这个词在context中
• $u$输出向量，当这个词是中心词

CBOW模型记号：

• $w_i$ 词汇表V中的第i个单词
• $\mathcal{V} \in \mathbb{R}^{n \times|V|}$ Input word matrix，嵌入矩阵
• $v_i$ $\mathcal{V}$的第i列，$w_i$的输入向量表式
• $\mathcal{U} \in \mathbb{R}^{|V| \times n}$ Output word matrix
• $u_i$ $\mathcal{U}$的第i行，$w_i$的输出向量表式

我们创建两个矩阵$\mathcal{V} \in \mathbb{R}^{n \times|V|}$ $\mathcal{U} \in \mathbb{R}^{|V| \times n}$。n可以是任意大小，定义了嵌入空间embedding space的大小。

步骤：

• 1.生成大小为m窗口内的context所有word的one-hot vector：$\left(x^{(c-m)}, \ldots, x^{(c-1)}, x^{(c+1)}, \ldots, x^{(c+m)} \in \mathbb{R}^{|V|}\right)$
• 2.得出context所有word的嵌入词向量:$v{c-m} = \mathcal{V} x^{(c-m)}, v{c-m+1}=\mathcal{V} x^{(c-m+1)}, \ldots, v_{c+m}=\mathcal{V} x^{(c+m)} \in \mathbb{R}^{n}$
• 3.把上一步得到的嵌入词向量取平均$\hat{v}=\frac{v{c-m}+v{c-m+1}+\ldots+v_{c+m}}{2 m} \in \mathbb{R}^n$，$\hat{v}$代表context的平均。
• 4.生成得分向量$z=\mathcal{U} \hat{v} \in \mathbb{R}^{|V|}$
• 5.$\hat{y}=\operatorname{softmax}(z) \in \mathbb{R}^{|V|}$
• 6.比较我们生成的概率$\hat{y} \in \mathbb{R}^{|V|}$和真实概率$y \in \mathbb{R}^{|V|}$

用交叉熵损失函数计算两个分布之间的距离

loss function:

$$H(\hat{y}, y)=-\sum_{j=1}^{|V|} y_j \log \left(\hat{y}_j\right)=-y_i \log \left(\hat{y}_i\right)$$

优化目标函数：

$$\begin{aligned} \operatorname{minimize} J & =-\log P\left(w_c \mid w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m}\right) \\ & =-\log P\left(u_c \mid \hat{v}\right) \\ & =-\log \frac{\exp \left(u_c^T \hat{v}\right)}{\sum_{j=1}^{|V|} \exp \left(u_j^T \hat{v}\right)} \\ & =-u_c^T \hat{v}+\log \sum_{j=1}^{|V|} \exp \left(u_j^T \hat{v}\right) \end{aligned}$$

我们用随机梯度下降来更新所有相关的词向量$u_c$和$v_j$

Skip-Gram Model

根据中心词预测上下文

Skip-Gram模型的记号：

• $w_i$ 词汇表V中的第i个单词
• $\mathcal{V} \in \mathbb{R}^{n \times|V|}$ Input word matrix，嵌入矩阵
• $v_i$ $\mathcal{V}$的第i列，$w_i$的输入向量表式
• $\mathcal{U} \in \mathbb{R}^{|V| \times n}$ Output word matrix
• $u_i$ $\mathcal{U}$的第i行，$w_i$的输出向量表式

步骤：

• 1.生成中心单词的one-hot向量$x \in \mathbb{R}^{|V|}$
• 2.得到中心单词的词嵌入: $v_c=\mathcal{V} x \in \mathbb{R}^n$
• 3.生成得分向量$z=\mathcal{U} v_c \in \mathbb{R}^{|V|}$
• 4.把得分转换为概率$\hat{y}=\operatorname{softmax}(z) \in \mathbb{R}^{|V|}$，注意到$\hat{y}{c-m}, \ldots, \hat{y}{c-1}, \hat{y}{c+1}, \ldots, \hat{y}{c+m}$为观测到每个上下文单词的概率。

• 5.我们希望我们生成的概率和真实概率$y^{(c-m)}, \ldots, y^{(c-1)}, y^{(c+1)}, \ldots, y^{(c+m)}$（one-hot形式）比较接近。

  下面第一步到第二步使用了朴素贝叶斯假设（条件独立）：

  $$\begin{aligned} \text { minimize } J & =-\log P\left(w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m} \mid w_c\right) \\ & =-\log \prod_{j=0, j \neq m}^{2 m} P\left(w_{c-m+j} \mid w_c\right) \\ & =-\log \prod_{j=0, j \neq m}^{2 m} P\left(u_{c-m+j} \mid v_c\right) \\ & =-\log \prod_{j=0, j \neq m}^{2 m} \frac{\exp \left(u_{c-m+j}^T v_c\right)}{\sum_{k=1}^{|V|} \exp \left(u_k^T v_c\right)} \\ & =-\sum_{j=0, j \neq m}^{2 m} u_{c-m+j}^T v_c+2 m \log \sum_{k=1}^{|V|} \exp \left(u_k^T v_c\right) \end{aligned}$$

  

负采样 negative sampling

Distributed Representations of Words and Phrases and their Compositionality

观察CBOW和skip-gram算法的objective function，其中求和部分计算量太大，$|V|$是百万级的。负采样的思路就是估计这个值，而不是每次做更新或者评估objective function都去做完整的计算。

训练过程每次循环迭代，我们不要计算完整的对$|V|$的求和，我们可以从分布$P_n(w)$中采样几个负样本。为了引入负采样，我们需要改变

• objective function
• 梯度
• 更新规则

考虑$(w,c)$是一个词和它的上下文，$P(D=1|w,c)$是$(w,c)$属于语料库的概率，$P(D=0|w,c)$是$(w,c)$不属于语料库的概率。我们用sigmoid函数表示这个概率

$$P(D=1 \mid w, c, \theta)=\sigma\left(u_c^T v_w\right)=\frac{1}{1+e^{\left(-u_c^T v_w\right)}}$$

接下来，我们创建一个新的objective function，最大化这个似然，（$\theta$是模型参数，在这里是$\mathcal{V}$和$\mathcal{U}$）

$$\begin{aligned} \theta & =\underset{\theta}{\operatorname{argmax}} \prod_{(w, c) \in D} P(D=1 \mid w, c, \theta) \prod_{(w, c) \in \tilde{D}} P(D=0 \mid w, c, \theta) \\ & =\underset{\theta}{\operatorname{argmax}} \prod_{(w, c) \in D} P(D=1 \mid w, c, \theta) \prod_{(w, c) \in \tilde{D}}(1-P(D=1 \mid w, c, \theta)) \\ & =\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log P(D=1 \mid w, c, \theta)+\sum_{(w, c) \in \tilde{D}} \log (1-P(D=1 \mid w, c, \theta)) \\ & =\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log \frac{1}{1+\exp \left(-u_w^T v_c\right)}+\sum_{(w, c) \in \tilde{D}} \log \left(1-\frac{1}{1+\exp \left(-u_w^T v_c\right)}\right) \\ & =\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log \frac{1}{1+\exp \left(-u_w^T v_c\right)}+\sum_{(w, c) \in \tilde{D}} \log \left(\frac{1}{1+\exp \left(u_w^T v_c\right)}\right) \end{aligned}$$

上式等价于最小化

$$J=-\sum_{(w, c) \in D} \log \frac{1}{1+\exp \left(-u_w^T v_c\right)}-\sum_{(w, c) \in \tilde{D}} \log \left(\frac{1}{1+\exp \left(u_w^T v_c\right)}\right)$$

$\tilde{D}$是”false” or “negative” corpus

利用上述思想，在CBOW模型中，给定上下文$\hat{v}=\frac{v{c-m}+v{c-m+1}+\ldots+v_{c+m}}{2 m}$，观测到中心词$u_v$，目标函数为

$$-\log \sigma\left(u_c^T \cdot \hat{v}\right)-\sum_{k=1}^K \log \sigma\left(-\tilde{u}_k^T \cdot \hat{v}\right)$$

作为对比，CBOW没有负采样，原始常规softmax损失为

$$-u_c^T \hat{v}+\log \sum_{j=1}^{|V|} \exp \left(u_j^T \hat{v}\right)$$

在skip-gram模型中，给定中心词c，观测到上下文单词c-m+j目标函数为

$$-\log \sigma\left(u_{c-m+j}^T \cdot v_c\right)-\sum_{k=1}^K \log \sigma\left(-\tilde{u}_k^T \cdot v_c\right)$$

作为对比，skip-gram没有负采样，原始常规softmax损失为

$$-u_{c-m+j}^T v_c+\log \sum_{k=1}^{|V|} \exp \left(u_k^T v_c\right)$$

补充：在上述讨论中，$\left{\tilde{u}_k \mid k=1 \ldots K\right}$从分布$P_n(w)$中采样。$P_n(w)$为一元模型的3/4次方。在一元模型中，我们假设

$$P\left(w_1, w_2, \cdots, w_n\right)=\prod_{i=1}^n P\left(w_i\right)$$

hierarchical(分层) softmax

这个算法主要优势：计算复杂度从$O(|V|)$降低到$O(\log (|V|))$
hierarchical softmax的符号表示
$L(w)$：从根节点到达$w$所在的叶节点的路径上的节点数量（不包括叶子结点)
$n(w, i)$为路径上第i个节点，$v_{n(w, i)}$为这个节点对应的向量
$\operatorname{ch}(n)$:任意选择内部节点n的子节点

$$P\left(w \mid w_i\right)=\prod_{j=1}^{L(w)-1} \sigma\left([n(w, j+1)=\operatorname{ch}(n(w, j))] \cdot v_{n(w, j)}^T v_{w_i}\right)$$ $$[x]=\left\{\begin{array}{l} 1 \text { if } x \text { is true } \\ -1 \text { otherwise } \end{array}\right.$$

与negative sampling的“采样”思想不同，hierarchical softmax用一棵二叉树来表示整个词表，其中，每个叶结点都代表一个单词，每个内部节点上都有一个向量，这些向量构成了整个二叉树的参数。与原始softmax计算输出词的概率分布时要遍历整个词表不同，我们将“某个单词是输出单词的概率”定义为从根到该单词的叶子的随机漫步（random walk）的概率。所以，我们只需要在二叉树中找到从根结点到输出词所在的叶子结点之间的path，然后根据输入词向量和path中包含的各个内部节点上的向量来计算该输出词的概率。

在这个模型中，没有输出词的向量表示，也就是没有$\mathcal{U}$矩阵。要学习的参数包括两方面：一是输入词矩阵（即$\mathcal{V}$），二是整个树的内部结点上的向量。

无论是negative sampling还是hierarchical softmax，它们都是在对原始的softmax计算做简化近似，只是采取的角度和使用的方法不同而以。在实际使用中，对于低频词，hierarchical softmax的效果会略优于negative sampling，而negative sampling则在高频词和低维向量的情况下效果较好。

References

[Bengio et al., 2003] Bengio, Y., Ducharme, R., Vincent, P., and Janvin, C. (2003). A neural probabilistic language model. J. Mach. Learn. Res., 3:1137–1155.
[Collobert et al., 2011] Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., and Kuksa, P. P. (2011). Natural language processing (almost) from scratch. CoRR, abs/1103.0398.
[Mikolov et al., 2013] Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013). Efficient estimation of word representations in vector space. CoRR, abs/1301.3781.
[Rong, 2014] Rong, X. (2014). word2vec parameter learning explained. CoRR, abs/1411.2738.
[Rumelhart et al., 1988] Rumelhart, D. E., Hinton, G. E., and Williams, R. J. (1988). Neurocomputing: Foundations of research. chapter Learning Representations by Back-propagating Errors, pages 696–699. MIT Press, Cambridge, MA, USA.