从 Embedding 到 Word2Vec

前言

Word Embedding 是将自然语言中的「单词」转换为「向量」或「矩阵」，使计算机更容易理解它们，你常常可以在自然语言处理的工作中见到这种方法。而 Word2Vec 正是 Word Embedding 的一种。

关于 Word Embedding 以及 Word2Vec，它们的基本思想我并不陌生，之前也有粗略地看过 NLP 相关的东西，最近接手毕业师兄的一些工作，想着也是要好好补一下 NLP 的这些东西了。

什么是 Embedding ?

在自然语言处理中，我们首先面对的是词语，而不是数字。以中译英翻译为例，我们有一系列的数据 (x, y)，其中 x，y 分别是中文和对应的英文单词，我们的任务是需要构建 f(x) -> y 的映射。

但是，我们遇到的第一个问题就是如何处理 x 也就是中文词语？我们的神经网络模型，只能接受数字的输入，而我们现有的词语则是符号形式的，人类的抽象总结，因此我们需要将它们转换为数字形式。

换句话说，利用词嵌入的方法通常是为一个特定的单词生成一个向量，然后训练它，用单词的上下文来表示这个单词。

我们希望，在经过充分训练后，两个向量之间的相对距离可以表示两个对应词的关系（相似性）。正如上图所展示的例子，猫和狗都是动物，因此 Cat 和 Dog 的 Embedding 更接近，类似的，Good 和 Nice 的 Embedding 也更接近。相反的，它们与 Table 的差距就非常大了，我们也可以猜测 Chair``、Tabulation 等单词的 Embedding 与 Table 的距离更近。

接下来我们要讨论的就是具体怎么做了，如何将词语转换为向量。

One-hot Encoding

首先来看一下 One-hot 编码，它将词语进行编码，本质上是用一个只含一个 1、其他都是 0 的向量来唯一表示词语。

举个例子，我们有一个字典 dict，字典中共有 N = 4 个词语 dict = {'Python', 'C++', 'Java', 'R'}，那么我们就可以这样进行编码：

词语	编码
`Python`	`1000`
`C++`	`0100`
`Java`	`0010`
`R`	`0001`

这样我们就可以用 N-1 个 0 和单个 1 组成的向量来表示每个类别。

One-hot 编码的问题

虽然 One-hot 编码能够通过一种非常简单的方式对词语进行编码，但它的缺点也非常明显。

众所周知，维数越少越好，但 One-hot 编码却增加了大量的维度。
数据稀疏。One-hot 编码实际上没有太多的信息，0 的数量远远超过 1。
映射之间完全独立。即并不能表示出不同类别之间的关系。

Word2Vec

首先我们需要了解一下 Word2Vec 的两个模型：CBOW 和 Skip-Gram。

还是来看个例子吧，可以很明显的看出两个模型的区别：

Continuous Bag-of-Word Model

CBOW 简单情形

CBOW 模型通过上下文来预测当前值，首先我们从简单的情形开始，即一对一的情况。

用当前词 x 预测它的下一个词 y

我们假设，词汇表大小为 $V$ ，隐藏层大小为 $N$ 。

模型的输入是经过 One-hot 编码的向量 $\mathbf{x} = \{x_1, \cdots, x_V\}$ ，正如我们前面提到的，这个向量中只有一个 1，其余都是 0。

输入层到隐藏层之间有一个 $V \times N$ 大小的权重矩阵 $W$ ，由此可以计算得到隐藏层：

$\mathbf{h} = W^T\mathbf{x}$

我们可以注意到，由于 $\mathbf{x}$ 是 One-hot 编码的向量，有且仅有 1 个值为 1，因此上面的计算结果本质就相当于选择了权重矩阵 $W$ 的某一行。那么能不能通过 $W$ 中的这某一行来作为这个单词的向量表示呢？

答案是肯定的，每个词语的 One-hot 编码里面 1 的位置是不同，因此对应的矩阵 $W$ 中的那一行向量也是不同的。因此，对于输入单词 $w_i$ ，我们可以使用 $\mathbf{v}_{w_i}$ 作为其向量表示，其中 $\mathbf{v}_{w_i}$ 是 $W$ 的第 $i$ 行。

同时，这也意味着隐藏层的激活函数其实是线性的。

另外一方面，从隐藏层到输出层还有一个 $N \times V$ 大小的权重矩阵 $W'$ ，类似的，输出层向量 $y$ 的每一个值，其实就是隐藏层的向量 $\mathbf{h}$ 点乘权重向量 $W'$ 的每一列:

$u_j = {\mathbf{v}'_{w_j}}^T\mathbf{h}$

其中， $\mathbf{v}'_{w_j}$ 是 $W'$ 的第 $j$ 列。最后是 softmax:

$p(w_j \vert w_i) = y_i = \frac{\exp (u_j)}{\sum^V_{j'=1} \exp (u_{j'})}$

其中 $y_j$ 是输出层的第 $j$ 个单元。综合上面两个式子，可以得到：

$p(w_j \vert w_i) = y_i = \frac{\exp ({\mathbf{v}'_{w_j}}^T\mathbf{v}_{w_i})}{\sum^V_{j'=1} \exp ({\mathbf{v}'_{w_{j'}}}^T\mathbf{v}_{w_i})}$

$\mathbf{v}_w$ 和 $\mathbf{v}'_w$ 是单词 $w$ 的两种表示，分别为「输入向量」和「输出向量」。

举个例子， $V=6, N=4$ ，我们来看一下具体的计算过程：

损失函数

在了解了模型的框架之后，我们更进一步，考虑损失函数的部分。

$\begin{aligned} \max p(w_o \vert w_i) &= \max y_{j^{*}}\\ &= \max \log y_{j^{*}} \\ &= u_{j^{*}} - \log \sum^V_{j'=1} \exp (u_{j'}) := -E \\ \end{aligned}$

其中， $E = -\log p(w_o \vert w_i)$ 就是损失函数。

当我们通过从训练语料库中产生的上下文-目标词对来迭代更新模型参数时，对向量的影响将不断累积。我们可以想象，一个词 $w$ 的输出向量被其上下文不断影响。同样地，一个输入向量也可以被认为是被许多输出向量所拖动。经过多次迭代，输入和输出向量的相对位置最终会稳定下来。

你可以在这个可视化网站中进一步了解其原理 wevi: word embedding visual inspector

具体的反向传播过程这里就不进行说明了，你可以在参考资料 1中找到完整的计算过程。

更一般的形式

正如我们之前提到的，CBOW 模型通过上下文来预测当前值，那么我们就需要把简单的一对一的模型改造成多个输入的模型：

在计算隐藏层输出时，CBOW 模型不是直接取输入上下文词的输入向量，而是取输入上下文词向量的平均值。

$\begin{aligned} \mathbf{h} &=\frac{1}{C} W^T (\mathbf{x}_1 + \mathbf{x}_2 + \cdots + \mathbf{x}_C) \\ &=\frac{1}{C} (\mathbf{v}_{w_1} + \mathbf{v}_{w_2} + \cdots + \mathbf{v}_{w_C})^T \end{aligned}$

其中 $C$ 是上下文的单词数， $w_1, w_2, \cdots , w_C$ 是上下文单词， $\mathbf{v}_w$ 是单词 $w$ 的输入向量。损失函数：

$\begin{aligned} E &= -\log p(w_o \vert w_{i,1}, \cdots, w_{i,C}) \\ &= -u_{j^{*}} + \log \sum^V_{j'=1} \exp (u_{j'}) \\ &= -{\mathbf{v}'_{w_o}}^T \cdot \mathbf{h} + \log \sum^V_{j'=1} \exp ({\mathbf{v}'_{w_{j}}}^T \mathbf{h}) \\ \end{aligned}$

Skip-Gram Model

Skip-Gram 模型通过当前值来预测上下文，我们首先来看看模型的结构，很显然，它正好与 CBOW 模型相反，目标字现在在输入层上，而上下文在输出层上。

类似的，计算隐藏层向量 $\mathbf{h}$ ：

$\mathbf{h} = W^T_{k,\cdot} := \mathbf{v}^T_{w_i}$

Skip-Gram 通过输入一个词去预测多个词的概率。输入层到隐藏层的原理和 simple CBOW 一样，不同的是隐藏层到输出层，损失函数变成了 $C$ 个词损失函数的总和，权重矩阵 $W'$ 还是共享的。

隐藏层 $\rightarrow$ 输出层：

$p(w_{c,j} = w_{o,c}|w_i) = y_{c,j} = \frac{\exp (u_{c,j})}{\sum^V_{j'=1} \exp (u_{j'})}$

损失函数:

$\begin{aligned} E &= - \log p(w_{o,1}, w_{o,2}, \cdots, w_{o,C} \vert w_i) \\ &= - \log \prod^{C}_{c=1} \frac{\exp (u_{c, j^{*}_{c}})}{\sum^{V}_{j'=1} \exp (u_{j'})} \\ &= - \sum^C_{c=1} u_{j^{*}_c} + C \log \sum^{V}_{j'=1} \exp (u_{j'}) \\ \end{aligned}$

小结

好了，到了这里就已经基本讲完 Word2Vec 的两个模型以及其实现原理了，接下来我们来看看针对模型的优化问题。如果你只是想了解 Word2Vec 的大致原理，那么你也可以跳过优化计算部分。

优化计算效率

Word2vec 本质上是一个语言模型，它的输出节点数是 $V$ 个，对应了 $V$ 个词语，本质上是一个多分类问题，但实际当中，词语的个数非常非常多，会给计算造成很大困难，所以需要用技巧来加速训练。

为了解决这个问题，作者提出了两个解决方案，hierarchical softmax 和 negative sampling。

Hierarchical Softmax

层次 softmax 使用二叉树来表示词汇表中的所有单词，其中每个单词均是叶子结点。对于每个叶子结点，存在一条从根到叶子结点的唯一路径；而这条路径被用来估计叶子结点所代表的词的概率。

在层次 softmax 模型中，我们使用这样的一棵 Huffman 数来替代输出层，因此对于单词 $w$ ，模型中就不存在其「输出向量」表示。取而代之的是， $V-1$ 个非叶子结点中都存在输出向量 $\mathbf{v}'_{n(w,j)}$ ，一个词成为输出词的概率被定义为：

$p(w = w_o) = \prod^{L(w)-1}_{j=1} \sigma \left( \llbracket n(w,j+1) = \ch (n(w,j)) \rrbracket \cdot {v'_{n(w,j)}}^T \mathbf{h} \right)$

其中 $\ch(n)$ 代表第 $n$ 个节点的左孩子； $\mathbf{v}'_{n(w,j)}$ 是节点 $n(w,j)$ 向量表示（输出向量）； $\mathbf{h}$ 为隐藏层向量：

$\mathbf{h} = \begin{cases} \frac 1 C \sum^C_{c=1} \mathbf{v}_{w_c} & \text{in CBOW} \\ \mathbf{v}_{w_i} & \text{in Skip-Gram} \end{cases}$

$\llbracket x \rrbracket = \begin{cases} 1 & \text{if } x \text{ is true} \\ -1 & \text{otherwise} \end{cases}$

以上面的图为例，我们来尝试理解这一大串式子的含义

假设我们现在想计算输出是 $w_2$ 的概率，那么其实我们可以把这个问题看成从根节点出发到叶子节点的随机游走的概率，对于一个非叶子结点 $n$ 来说，向左走的概率为:

$p(n,left) = \sigma ({\mathbf{v}'_{n}}^T \cdot \mathbf{h})$

其中 ${\mathbf{v}'_{n}}^T \cdot \mathbf{h}$ 与我们之前在 CBOW 中讨论的相同，也就是说，向左走的概率由非叶子结点的向量 $\mathbf{v}'_{n}$ 和隐藏向量 $\mathbf{h}$ 决定。同理，我们计算向右走的概率：

$p(n,right) = 1 - \sigma ({\mathbf{v}'_{n}}^T \cdot \mathbf{h}) = \sigma (-{\mathbf{v}'_{n}}^T \cdot \mathbf{h})$

得到了向左走和向右走的概率，我们就可以计算从根节点到 $w_2$ 的概率：

$\begin{aligned} p(w_2 = w_o) &= p(n(w_2,1),left) \cdot p(n(w_2,2),left) \cdot p(n(w_2,3),right) \\ &= \sigma \left( {\mathbf{v}'_{n(w_2,1)}}^T \cdot \mathbf{h} \right) \cdot \left( {\mathbf{v}'_{n(w_2,2)}}^T \cdot \mathbf{h} \right) \cdot \left( -{\mathbf{v}'_{n(w_2,3)}}^T \cdot \mathbf{h} \right) \end{aligned}$

这其实也就是下面的式子：

$p(w = w_o) = \prod^{L(w)-1}_{j=1} \sigma \left( \llbracket n(w,j+1) = \ch (n(w,j)) \rrbracket \cdot {v'_{n(w,j)}}^T \mathbf{h} \right)$

明白了上面式子的含义，也不难看出:

$\sum^{V}_{i=1} p(w_i = w_o) = 1$

现在我们还是来看看损失函数，为了简单起见，我们考虑 simple CBOW，即一对一模型：

$\begin{aligned} E &= - \log p(w = w_o \vert w_i) \\ &= -\sum^{L(w)-1}_{j=1} \log \sigma \left( \llbracket n(w,j+1) = \ch (n(w,j)) \rrbracket \cdot {v'_{n(w,j)}}^T \mathbf{h} \right) \end{aligned}$