Deep Learning Note: 5-7 学习 Word Embedding
1. 学习 Word Embedding
学习 Word Embedding 的一个方法是训练一个语言模型。例如训练一个网络来预测句子中的下一个单词，如图 1 所示。
图 1
图 1 中单词下的数字为单词在词汇表中的索引，假设词汇表中有 10000 个单词。对于第一个词 $I$，其独热编码为 $O_{4343}$，使用一个 Embedding 矩阵 $E$ 与其相乘，得到 $I$ 的一个新的编码 $E_{4343}$。假设 $E$ 的大小为 $600 \times 10000$，则 $E_{4343}$ 是一个 $600 \times 1$ 的向量。对于句子中的每一个单词，使用同一个 Embedding 矩阵 $E$ 重复以上步骤，将得到的这些新的编码输入一个神经网络，这个神经网络输出 10000 个激活值，输出数量与词汇表的单词数量相同，由一个 Softmax 节点进行预测，如图 2 所示。
图 2
通过训练图 2 所示的网络，就可以得到一个能预测句子的下一个词的网络。需要训练的参数包括 Embedding 矩阵 $E$，以及网络本身的权重和偏置参数等，最终得到的 Embedding 矩阵即可用于单词编码。这一算法能够有效地学习 Word Embedding，在训练过程中，网络倾向于调整 $E$ 使得相似的单词具有相似的编码，以更好地拟合训练集。如网络可能会经常看到 orange juice 和 apple juice，通过调整 $E$ 使得 orange 和 apple 具有相似的编码，网络可以更好地拟合 orange _ 和 apple _ 的情况。
图 2 的网络使用了 6 个词作为输入，每个输入单词是一个 $300 \times 1$ 的向量。这里网络输入的单词数量是一个超参数，表示要使用前面多少个单词来预测下一个单词，通常是一个固定值，以便处理任意长度的句子。
以上算法是较早出现的一个能够很好地学习 Word Embedding 的算法，在 A Neural Probabilistic Language Model 一文中有详细论述。
上面的问题可以推广为让算法根据一定的上下文（Context）预测句子中的目标（Target）词，这里的上下文可以有不同的选择。
I want a glass of orange juice to go along with my cereal.
例如对于上面这句话，目标词是 juice，如果想要构建语言模型，通常会选择目标词前的几个单词作为上下文，比如使用目标词之前的 4 个单词作为上下文，即预测 “a glass of orange _”。
反之，如果只是想要学习 Embedding，则可以选择其他形式的上下文：如选择目标单词之前和之后的各 4 个单词作为上下文，即预测 “a glass of orange _ to go along with”；更简单地，甚至可以只使用目标词之前的 1 个词作为上下文，即预测 “orange _”；此外，还可以使用目标词附近的 1 个词作为上下文，如使用 glass，即预测 “glass * * _”，这称为 Skip-Gram 模型，具有很好的性能。
2. Word2Vec
Word2Vec 是一种更简单且有效的学习 Embedding 的算法，前面提到的 Skip-Gram 模型就是其中之一。对于 Skip-Gram 模型并不使用目标词之前且相邻的一个或多个词作为上下文。举例来说，对于下面这句话：
I want a glass of orange juice to go along with my cereal.
Skip-Gram 模型随机地选择一个词作为上下文，例如选择了 orange；然后在这个词附近的一个窗口内（如 10 个单词内）选择一个词作为目标词，例如选择了orange 后面的第 1 个词 juice，或者选择了 orange 之前的第 2 个词 glass，又或者选择了 orange 之后的第 6 个词 my。由此就得到了一系列上下文和目标词的组合，如表 1 所示。
表 1
| Context | Target |
|---|---|
| orange | juice |
| orange | glass |
| orange | my |
由此就可以建立一个监督学习问题，学习从上下文 $c$ 到目标词 $t$ 的映射关系：对于上下文 $c$，首先获得其独热编码 $O_c$；然后使用一个 Embedding 矩阵 $E$ 与之相乘，得到一个新的编码 $e_c = Eo_c$；接着将 $e_c$ 输入一个 Softmax 单元，得到对目标词的预测 $\hat{y}$。
这里的 Softmax 单元计算的是在给定上下文 $c$ 时，目标词为 $t$ 的概率，即：
\begin{equation}
p(t|c) = \frac{e^{\theta_t^Te_c}}{\sum_{j=1}^{n_v}e^{\theta_j^Te_c}} \tag{1}
\end{equation}
式 (1) 中，$n_v$ 为词汇表中单词的数量，$\theta_t$ 是与输出 $t$ 相关的一个参数。
使用交叉熵作为损失函数：
\begin{equation}
L(\hat{y}, y) = -\sum_{i=1}^{n_v}y_i\log\hat{y_i} \tag{2}
\end{equation}
式 (2) 中，$y$ 是目标词 $t$ 的独热编码，是一个 $n_v \times 1$ 的向量，Softmax 单元输出的 $\hat{y}$ 也是一个 $n_v \times 1$ 的向量。
在这个模型中，参数包括 Embedding 矩阵 $E$ 以及 Softmax 单元中的参数 $\theta_t$。通过在式 (2) 所示的代价函数上优化这些参数，可以得到一系列非常好的 Embedding 向量。
以上 Skip-Gram 模型出自 Efficient Estimation of Word Representations in Vector Space 这篇论文。
使用 Skip-Gram 的一个主要问题是计算速度较慢，式 (2) 分母上对词汇表中的每个词进行了计算并求和，如果词汇表中包含数十万甚至上百万个单词，每次预测都要花费大量的时间。这个问题的也有一些解决办法，论文中使用了 Hierarchical Softmax 分类器来降低计算量，即使用一系列二元分类器构成一个查找树，来定位最终要输出的预测结果，在构建查找树时，通常使常见的词出现在数的上层，使其能够更快地被查找到。关于 Hierarchical Softmax 的详细内容可以参考上面的论文，以及 Hierarchical Probabilistic Neural Network Language Model 和 word2vec Parameter Learning Explained（3.1 节）两篇论文。
最后的一个问题是，如何选择上下文 $c$。一种方法是在训练语料中均匀地随机采样，但这样采样会得到很多诸如 the、of、a、an、and 的单词，因为这些单词出现的频率很高，而一些出现频率较低的单词则很难被采样到。所以实际中使用的采样概率并不是完全平均分布的，使得少见的词也能被采样到。
在 Efficient Estimation of Word Representations in Vector Space 这篇论文中，作者还给出了另一种 Word2Vec 算法，称为 CBOW，即 Continuous Bag of Words，它使用目标词前后的内容作为上下文，来预测中间的目标词。
3. 负采样
Distributed Representations of Words and Phrases and their Compositionality 一文提出的负采样（Negative Sampling）可以解决 Skip-Gram 模型计算量大的问题。
I want a glass of orange juice to go along with my cereal.
仍以上面的句子为例，现在的问题是，给出两个单词，预测这两个单词之间是否存在 Context 到 Target 的关系。例如 orange 和 juice 两个词之间具有 Context 到 Target 的关系，而 orange 和 king 两个词之间没有 Context 到 Target 的关系。
在构造训练集时，可以使用前面 Skip-Gram 的方法，采样得到一个 (Context, Target) 的单词对，例如 (orange, juice)，如表 2 所示。
表 2
| Context | Word | Target? |
|---|---|---|
| orange | juice | 1 |
然后从词汇表中随机抽取 $K$ 个词，与上一步采样的 Context 组成单词对，从词汇表中随机抽取的词都不是 Target，如表 3 所示。
表 3
| Context | Word | Target? |
|---|---|---|
| orange | king | 0 |
| orange | book | 0 |
| orange | the | 0 |
| orange | of | 0 |
注意表 3 中最后一条的单词 of 其实出现在了原句中，但这里的 of 是从词汇表中随机抽取的，它出现在原句中只是一个巧合，这里不认为 of 是 Target。在每次迭代中，都使用以上方式，为每个 (Context, Target) 的单词对生成 $K$ 个 (Context, 非 Target) 的单词对。对于 $K$ 的选择，原论文作者建议对于较小的数据集，$K$ 的取值范围为 5 到 20；对于较大的数据值，$K$ 可以取较小的值，如 2 到 5。
通过以上方法就可以构造出训练集的数据，特征 $x$ 是 Context（以下简称 $c$）和 Word（以下简称 $t$）的单词对，标签 $y$ 为这个单词对的 Word 是否为 Target。由此可以构造一个逻辑回归模型，预测给定 $c$ 和 $t$ 时，$y = 1$ 的概率，即：
\begin{equation}
P(y = 1|c, t) = \sigma(\theta_t^Te_c) \tag{3}
\end{equation}
式 (3) 中，$\theta_t$ 与一个与 $t$ 相关的参数；$e_c$ 为 $c$ 的 Embedding 向量，由 Embedding 矩阵 $E$ 与 $c$ 的独热编码 $o_c$ 相乘得到，即 $e_c = Eo_c$。
假设词汇表中有 10000 个单词，对于 $c = orange$，orange 在词汇表中的位置为 6257，其独热编码为 $o_{6257}$，Embedding 向量 $e_{6257} = Eo_{6257}$。对于 $e_{6257}$，要计算它与词汇表中每个词具有 Context 到 Traget 关系的概率，就需要计算 10000 个如式 (3) 表述的二分类问题。而在每次迭代中，我们只从词汇表中抽取了 $K$ 个单词，计算 $e_{6257}$ 与 $K + 1$ 个单词（1 个真实 Traget 和 $K$ 个从词汇表中抽取的词）具有 Context 到 Traget 关系的概率，每次迭代的计算量大大降低。
以上就是负采样算法，其称为“负采样”的原因是，对于每个 (Context, Target) 单词对，如表 2 中的 (orange, juice)，我们使用该 Context 在词汇表中采样了 $K$ 不具有 Context 到 Target 关系的负（Negative）样本，如表 3 中的 (oragne, king)、(oragne, book) 等等。注意在每次迭代中，都要为每个 (Context, Target) 样本生成不同的 $K$ 个负样本。
在词汇表中采样负样本时，一种方法是按照单词在语料中出现的经验频率进行采样，即多采样在语料中出现频繁的单词，但这样做会导致经常采样到如 the、of、and 这类出现非常频繁单词。另一种极端的方法是在词汇表中均匀地随机采样，但这样做就无法表现单词在语料中的实际分布情况。原论文的作者提出使用如下的经验概率进行采样可以得到最好的效果：
\begin{equation}
P(w_i) = \frac{f(w_i)^{\frac{3}{4}}}{\sum_{i=1}^{n_v}f(w_j)^{\frac{3}{4}}} \tag{4}
\end{equation}
式 (4) 中，$n_v$ 是词汇表中单词的数量，$f(w_i)$ 为单词 $w_i$ 在语料中出现的频率，通过取其 $\frac{3}{4}$ 次方，平衡了按经验频率采样和平均采样两种方式。
4. GloVe 单词向量
GloVe 即 Global Vectors for Word Representation，由 GloVe: Global Vectors for Word Representation 一文提出。
GloVe 没有像前面 Skip-Gram 和负采样模型那样显式地定义 (Context, Traget) 单词对，而是使用 $X_{ij}$ 表示单词 $i$ 以 单词 $j$ 为上下文的次数，单词 $i$ 为 Target，单词 $j$ 为 Context。
GloVe 算法定义 Context 和 Taget 为距离接近的两个词，例如定义 Context 和 Taget 为出现在 10 个单词距离之内的两个词，此时则 $i$ 和 $j$ 的关系是对称的，有 $X_{ij}$ = $X_{ji}$。
GloVe 算法的优化目标是最小化 $\theta_i^Te_j$ 和 $\log X_{ij}$ 之间的差距，即使得 $\theta_i^Te_j$ 能够体现 $i$ 和 $j$ 两个词一起出现的频率。具体来说，优化目标是最小化：
\begin{equation}
\sum_{i=1}^{n_v}\sum_{j=1}^{n_v} f(X_{ij})(\theta_i^Te_j + b_i + b_j’ – \log X_{ij})\tag{5}
\end{equation}
式 (5) 中，$n_v$ 是词汇表中单词的数量。$f(X_{ij})$ 是一个权重函数，当 $X_{ij} = 0$ 时，$f(X_{ij}) = 0$，避免计算 0 的对数。另外，对于如 this、is、of、a 这类出现非常频繁的单词，$f(X_{ij})$ 会保证其权重不会太大；而对于如 durian 之类很少见的词，$f(X_{ij})$ 会保证其权重不会太小。$f(X_{ij})$ 的具体设计方法可以参考上面给出的原论文。
由于在 GloVe 算法中 $i$ 和 $j$ 的关系是对称的，故式 (5) 中 $\theta_i$ 和 $e_j$ 也是对称的，将 $i$ 和 $j$ 的位置互换并不会改变优化目标。训练算法时，可以均匀地随机初始化 $\theta_i$ 和 $e_j$，然后使用梯度下降最小化式 (5)，对于单词 $w$，可以对 $e_w$ 和 $\theta_w$ 求平均，得到 $w$ 最终的 Embedding 向量，即：
\begin{equation}
e_w^{final} = \frac{e_w + \theta_w}{2}
\end{equation}
GloVe 算法是在之前语言模型、Word2Vec Skip-Gram 模型等基础的之上进行简化而来的，算法本身非常简单，而且确实能有效地学习 Word Embedding。
最后，需要注意的是，前文在引入 Word Embedding 时的例子中，使用了一系列特征来对单词进行评估，如 Gender、Royal、Age、Food 等。而对于通过本文介绍的算法所实际习得的 Word Embedding，其中的每一个成分并不一定完全表现为如 Gender 或 Royal 等特定的具体特征，因为对于一个可逆矩阵 $A$，式 (5) 中的计算 $\theta_i^Te_j$ 可以表示成 $(A\theta_i)^T(A^{-T}e_j)$ 的形式（有 $(A\theta_i)^T(A^{-T}e_j) = \theta_i^TA^TA^{-T}e_j = \theta_i^Te_j$）。
图 3
如图 3 所示，e 是实际习得的 Word Embedding 中的一个成分，它综合了 Gender 和 Royal 两个特征，在人看来，很难理解 e 到底体现了什么特征，但相似单词的 Embedding 仍具有如前文图 3 所示的平行关系。
