Approximate Training

跳元模型的主要思想是使用softmax运算来计算基于给定的中心词$w_c$生成上下文字$w_0$的条件概率。

• 由于softmax操作的性质，上下文词可以是词表$V$中的任意项，这个包含与整个词表大小一样多的项的求和。因此，在跳元模型的梯度计算和连续词袋模型的梯度计算都包含求和。

• 不幸的是，在一个词典上（通常有几十万或数百万个单词）求和的梯度的计算成本是巨大的！

为了降低上述计算复杂度，本节将介绍两种近似训练方法：负采样和分层softmax。由于跳元模型和连续词袋模型的相似性，我们将以跳元模型为例来描述这两种近似训练方法。

Negative Sampling

负采样修改了原目标函数。给定中心词$w_c$的上下文窗口，任意上下文词$w_o$来自该上下文窗口的被认为是由下式建模概率的事件：

$P(D = 1 \mid w_c, w_o) = \sigma(\mathbf{u}_o^\top \mathbf{v}_c),$

其中$\sigma$使用了sigmoid激活函数的定义：

$\sigma(x) = \frac{1}{1 + \exp(-x)}.$

让我们从最大化文本序列中所有这些事件的联合概率开始训练词嵌入。具体而言，给定长度为$T$的文本序列，以$w^{(t)}$表示同步$t$的词，并使上下文窗口为$m$，考虑最大化联合概率：

$\prod_{t=1}^{T} \prod_{-m \leq j \leq m, j \neq 0} P(D = 1 \mid w^{(t)}, w^{(t+j)}).$

然而，只考虑那些正样本的事件。仅当所有词向量都等于无穷大时，这其中的联合概率才最大化为1。当然，这样的结果毫无意义。为了使目标函数更有意义，负采样添加从预定分布中采样的负样本。

用$S$表示上下文词$w_o$来自中心词$w_c$的上下文窗口的事件。对于这个涉及$w_o$的事件，从预定义分布$P(w)$中采样$K$个不是来自这个上下文窗口噪声词。

用$N_k$表示噪声词$w_k$（$k=1,\dots,K$）不是来自$w_o$的上下文窗口的事件。假设正例和负例$S, N_1,\dots,N_K$的这些事件是相互独立的。

负采样将(14.2.3)中的联合概率（仅涉及正例）重写为:

$\prod_{t=1}^{T} \prod_{-m \leq j \leq m, j \neq 0} P(w^{(t+j)} \mid w^{(t)}),$

通过事件$S, N_1,\dots,N_K$近似条件概率：

$P(w^{(t+j)} \mid w^{(t)}) = P(D = 1 \mid w^{(t)}, w^{(t+j)}) \prod_{k=1, w_k \sim P(w)}^{K} P(D = 0 \mid w^{(t)}, w_k).$

分别用$i_t$和$h_k$表示词$w^{(t)}$和噪声词$w_k$在文本序列中的同步处的索引。(14.2.5)中关于条件概率的对数损失为：

$-\log P(w^{(t+j)} \mid w^{(t)}) = -\log P(D = 1 \mid w^{(t)}, w^{(t+j)}) - \sum_{k=1, w_k \sim P(w)}^{K} \log P(D = 0 \mid w^{(t)}, w_k)$

$= -\log \sigma(\mathbf{u}{t+j}^\top \mathbf{v}{i_t}) - \sum_{k=1, w_k \sim P(w)}^{K} \log \left( 1 - \sigma(\mathbf{u}{h_k}^\top \mathbf{v}{i_t}) \right)$

$= -\log \sigma(\mathbf{u}{t+j}^\top \mathbf{v}{i_t}) - \sum_{k=1, w_k \sim P(w)}^{K} \log \sigma(-\mathbf{u}{h_k}^\top \mathbf{v}{i_t}).$

我们可以看到，现在每个训练步的梯度计算成本与词表大小无关，而是线性依赖于$K$。当将超参数$K$设置为较小的值时，在负采样的每个训练步处的梯度的计算成本较小。

Hierarchical Softmax

作为另一种近似训练方法，层序Softmax（hierarchical softmax）使用二叉树（图14.2.1中说明的数据结构），其中树的每个叶节点表示词表$V$中的一个词。

用$L(w)$表示二叉树中表示字$w$的从根节点到叶节点的路径上的节点数（包括两端）。设$n(w, j)$为该路径上的第$j$th节点，其上下文字向量为$\mathbf{u}_{n(w,j)}$。例如，图14.2.1中的$L(w_3) = 4$。分层softmax将(14.1.4)中的条件概率近似为

$P(w_o \mid w_c) = \prod_{j=1}^{L(w_o)-1} \sigma\left(\left[n(w_o, j+1) = \text{leftChild}(n(w_o,j))\right] \cdot \mathbf{u}_{n(w_o,j)}^\top \mathbf{v}_c\right),$

其中函数$\sigma$在(14.2.2)中定义，$\text{leftChild}(n)$是节点$n$的左子节点：如果$x$为真，$\llbracket x \rrbracket = 1$；否则$\llbracket x \rrbracket = -1$。

为了说明，让我们计算图14.2.1中给定词$w_3$生成词$w_3$的条件概率。这需要$w_c$的词向量$\mathbf{v}_c$和从根到$w_3$的路径（图14.2.1中加粗的路径）上的非叶节点向量之间的点积，该路径依次向左、向右和向左遍历：

$P(w_3 \mid w_c) = \sigma(\mathbf{u}_{n(w_3,1)}^\top \mathbf{v}c) \cdot \sigma(-\mathbf{u}_{n(w_3,2)}^\top \mathbf{v}c) \cdot \sigma(\mathbf{u}_{n(w_3,3)}^\top \mathbf{v}_c).$

由于$\sigma(x) + \sigma(-x) = 1$，它认为基于任意词$w_c$生成词表$V$中所有词的条件概率总和为1：

$\sum_{w \in V} P(w \mid w_c) = 1.$

幸运的是，由于二叉树结构，$L(w_o) - 1$大约与$O(\log_2 |V|)$是一个数量级。当词表大小$|V|$很大时，与没有近似训练的相比，使用分层softmax的每个训练步的计算代价显著降低。

下采样

文本数据通常有“the”“a”和“in”等高频词：它们在非常大的语料库中甚至可能出现数十亿次。然而，这些词经常在上下文窗口中与许多不同的词共同出现，提供的有用信息很少。

例如，考虑上下文窗口中的词“chip”：直观地说，它与低频单词“intel”的共现比与高频单词“a”的共现在训练中更有用。

此外，大量（高频）单词的训练速度很慢。因此，当训练词嵌入模型时，可以对高频单词进行下采样 (Mikolov et al., 2013)。具体地说，数据集中每个词$w_i$将有概率地被丢弃：

$P(w_i) = \max \left( 1 - \sqrt{\frac{t}{f(w_i)}}, 0 \right),$

其中$f(w_i)$是$w_i$的词数与数据集中的总词数的比率，常量$t$是超参数（在实验中为$10^{-4}$）。我们可以看到，只有当相对比率$f(w_i) > t$时，（高频）词$w_i$才能被丢弃，且该词的相对比率越高，被丢弃的概率就越大。