本文共分为三节，由若干文章拼接而成。第一节具体推导word2vec参数的更新规则，第二节介绍在词表比较大时对softmax做近似的方法，第三部分介绍如何生成好的词向量
Word2vec的参数学习
本节内容完全来自于[rong2014]
连续词袋模型（CBOW）
上下文仅有一个单词的情况
上下文只有一个单词时，网络做的事情其实类似于二元语法模型。假设词表大小为\(V\)，隐藏层大小为\(N\)，输入层到隐藏层及隐藏层到输出层都是全连接，输入为独热编码向量，那么网络的示意图如下图所示 
从图中可知，输入层和隐藏层之间的权重可以使用\(V \times N\)的矩阵\(\boldsymbol{W}\)表示。假设输入的语境单词为词表中的第\(k\)个单词，则输入向量\(\boldsymbol{x}\)满足\(x_k = 1\)且\(\forall k' \not= k \rightarrow x_{k'} = 0\)，因此有 \[ \boldsymbol{h} = \boldsymbol{W}^\mathsf{T}\boldsymbol{x} = \boldsymbol{w}_{(k, \cdot)}^\mathsf{T} := \boldsymbol{v}_{w_I}^\mathsf{T} \] 即\(\boldsymbol{W}\)的第k行行向量实际上就是词表中第k个单词词向量的转置，记输入单词词向量为\(\boldsymbol{v}_{w_I}\)
假设最后得到的得分向量为\(\boldsymbol{u}\)，则从隐藏层到输出层有 \[ \boldsymbol{u} = \boldsymbol{W}'^\mathsf{T}\boldsymbol{h} \tag{1} \] 其中\(\boldsymbol{u}\)的第\(j\)行元素\(u_j\)为 \[ u_j = \boldsymbol{w}_{(\cdot, j)}'^\mathsf{T}\boldsymbol{h} \tag{2} \] 这里\(\boldsymbol{w}_{(\cdot, j)}'\)是\(\boldsymbol{W}'\)的第\(j\)列。记\(\boldsymbol{w}_{(\cdot, j)}'\)为\(\boldsymbol{v}'_{w_O}\)
得到\(\boldsymbol{u}\)以后，可以使用softmax来得到单词的后验分布：给定上文单词为\(w_I\)的情况下，出现单词\(w_O\)的概率为 \[ P(w_O|w_I) = y_j = \frac{\exp(u_j)}{\sum_{j'=1}^V \exp(u_{j'})} \tag{3} \] 将式(1)和(2)代入(3)可得 \[ P(w_O|w_I) = \frac{\exp\left(\boldsymbol{v}_{w_O}'^\mathsf{T}\boldsymbol{v}_{w_I}\right)}{\sum_{j'=1}^V \exp\left(\boldsymbol{v}_{w_j'}'^\mathsf{T}\boldsymbol{v}_{w_I}\right)} \tag{4} \]
可见对同一个单词\(w\)来说，会有两个嵌入表示\(\boldsymbol{v}_{w}\)和\(\boldsymbol{v}_{w}'\)，前者是\(\boldsymbol{W}\)的第\(i\)行行向量，后者是\(\boldsymbol{W}'\)的第\(i\)列列向量。在后续的分析中，称前者为单词\(w\)的输入向量，后者为单词\(w\)的输出向量
隐藏层到输出层权重的更新
假设给定单词\(w_k\)，期望输出是单词\(w_{j^\ast}\)，那么模型优化的目标是要最大化正确单词对应的概率\(y_{j^\ast}\)，有 \[ \begin{align*} \mathop{ {\rm \arg}\max}_{\boldsymbol{W}'} p(w_O|w_I) &= \mathop{ {\rm \arg}\max}_{\boldsymbol{W}'} y_{j^\ast} \\ &= \mathop{ {\rm \arg}\max}_{\boldsymbol{W}'} \log y_{j^\ast} \\ &= \mathop{ {\rm \arg}\max}_{\boldsymbol{W}'} \left(u_{j^\ast} - \log \sum_{j'=1}^V \exp(u_{j'})\right) \end{align*} \] 记\(E = -\log p(w_O|w_I)\) 为学习的目标函数，那么学习的目的就是最小化\(E\)。可知 \[ \frac{\partial E}{\partial u_j} = y_j - t_j := e_j \] 其中\(t_j = \mathbb{1}(j = j^\ast)\)。或者可以写为 \[ \frac{\partial E}{\partial u_j} = \begin{cases}y_j - 1 & j = j^\ast \\ y_j & {\rm elsewhere}\end{cases} \] 接着可以求出\(E\)对\(\boldsymbol{W}'\)中每个元素\(w_{ij}'\)的偏导数 \[ \frac{\partial E}{\partial w_{ij}'} = \frac{\partial E}{\partial u_j}\cdot \frac{\partial u_j}{\partial w_{ij}'} = e_j \cdot h_i \] 因此梯度下降的更新方法为 \[ w_{ij}'^{(\rm new)} = w_{ij}'^{(\rm old)} - \eta \cdot e_j\cdot h_i \] 向量化的形式为 \[ \boldsymbol{v}_{w_j}'^{(\rm new)} = \boldsymbol{v}_{w_j}'^{(\rm old)} - \eta \cdot e_j \cdot \boldsymbol{h} \] 这意味着，当\(y_j > t_j\)时，\(e_j\)为正值，\(\boldsymbol{v}_{w_j}'\)会变小。由于\(t_j\)只能为0或1，因此这说明给定输入单词为\(w_I\)时，对不是期望单词序号\(j^\ast\)的\(j\)，\(w_j\)的输出向量会变小，反之相反
输入层到隐藏层权重的更新
首先计算目标函数\(E\)对隐藏层每个输出元素\(h_i\)的偏导数。由于隐藏层到输出层是全连接的，因此\(h_i\)对每个\(u_j\)都有贡献，使用全微分公式有 \[ \frac{\partial E}{\partial h_i} = \sum_{j=1}^V \frac{\partial E}{\partial u_j} \cdot \frac{\partial u_j}{\partial h_i} = \sum_{j=1}^V e_j \cdot w_{ij}' := e'_i \] 其中\(e'_i\)是\(N\)维向量\(\boldsymbol{e}'\)的第\(i\)个元素。由于输入层到隐藏层也是一个全连接，因此有 \[ h_i = \sum_{k=1}^V x_k \cdot w_{ki} \] 所以对\(\boldsymbol{W}\)的每个元素\(w_{ki}\)，有 \[ \frac{\partial E}{\partial w_{ki}} = \frac{\partial E}{\partial h_i}\cdot \frac{\partial h_i}{\partial w_{ki}} = e'_i \cdot x_k \] 写成向量（矩阵）形式，为 \[ \frac{\partial E}{\partial \boldsymbol{W}} = \boldsymbol{x} \otimes \boldsymbol{e}' = \boldsymbol{x}\boldsymbol{e}'^\mathsf{T} \] 由于\(\boldsymbol{x}\)是独热向量，因此\(\partial E/\partial \boldsymbol{W} = \boldsymbol{e}'^\mathsf{T}\)，即 \[ \boldsymbol{v}_{w_I}^{(\rm new)} = \boldsymbol{v}_{w_I}^{(\rm old)} - \eta \boldsymbol{e}'^\mathsf{T} \] 这意味着本次更新只有输入单词对应的那一行参数会受到影响
从前面的推导中可以看出，\(\boldsymbol{e}'\)实际上是\(V\)个输出向量\(\boldsymbol{v}_j'\)的加权求和，权重是每个单词\(j\)的损失值\(e_j = y_j - t_j\)。因此如果在输出层中，单词\(w_j\)成为输出单词的概率被高估了，梯度下降会把输入向量\(w_I\)拉得离\(w_j\)的输出向量远一些，反之相反
综上所述，整个参数更新的过程实际上就是输出词的输出向量被输入词（邻居）的输入向量来回拉扯的过程，对输入词的输入向量也是如此。两个词的共现次数越多，对应向量之间的拉力就越强，最后整个系统在经历足够多的迭代以后，会稳定下来
上下文有多个单词的情况
当上下文有多个单词时（假设有\(C\)个），隐藏层会对输入向量做平均 \[
\begin{align*}
\boldsymbol{h} &= \frac{1}{C}\boldsymbol{W}^\mathsf{T}(\boldsymbol{x}_1 + \boldsymbol{x}_2 + \cdots + \boldsymbol{x}_C) \\
&= \frac{1}{C}(\boldsymbol{v}_{w_1} + \boldsymbol{v}_{w_2} + \cdots + \boldsymbol{v}_{w_C})^\mathsf{T}
\end{align*}
\] 模型的损失函数并没有变化，结构变为如下形式 
输出向量的更新方法也没有变化，唯一变化是输入向量的更新量是之前的\(C\)分之一 \[ \boldsymbol{v}_{w_{I, c}}^{(\rm new)} = \boldsymbol{v}_{w_{I, c}}^{(\rm old)} - \frac{1}{C}\cdot\eta \boldsymbol{e}'^\mathsf{T} \]
SkipGram模型
CBOW模型是用多个词做上下文，预测的是中心词；而跳表模型是用一个词做上下文，预测的是周围词。因此，对跳表模型，隐藏层输入向量与单个单词做上下文的CBOW模型没有区别 \[ \boldsymbol{h} = \boldsymbol{w}_{(k, \cdot)}^\mathsf{T} := \boldsymbol{v}_{w_I}^\mathsf{T} \] 由于是预测周围\(C\)个词，因此输出层要输出\(C\)个多项分布，输出之间共享隐藏层到输出层的矩阵\(\boldsymbol{W'}\)。有
\[ p(w_{c,j} = w_{O, c}|w_I) = y_{c,j} = \frac{\exp(u_{c, j})}{\sum_{j'=1}^V \exp(u_{j'})} \] 其中\(w_{c,j}\)是输出层中第\(c\)个位置上的第\(j\)个单词，\(w_{O, c}\)是输出单词序列中的第\(c\)个单词（第\(c\)个位置上的实际单词），\(w_I\)是唯一的那个输入单词，\(y_{c,j}\)是模型算出第\(c\)个位置上是第\(j\)个单词的概率。由于输出层各个位置共享权重，因此 \[ u_{c,j} = u_j = \boldsymbol{v}_{w_j}'^\mathsf{T} \cdot \boldsymbol{h},\ \ {\rm for\ }c =1,2,\cdots, C \] 其中\(\boldsymbol{v}_{w_j}'\)仍然是第\(j\)个单词的输出向量，也是\(\boldsymbol{W}_j'\)的第\(j\)列。跳表模型的示意图如下
由于是预测多个输出单词，因此需要对\(C\)个输出概率连乘。损失函数变为 \[ \begin{align*} E &= -\log p(w_{O,1}, w_{O, 2}, \cdots, w_{O, C}|w_I) \\ &= -\log \prod_{c=1}^C \frac{\exp (u_{c, j_c^\ast})}{\sum_{j'=1}^V \exp(u_{j'})} \\ &= -\sum_{c=1}^C u_{j_{c}^\ast} + C \cdot \log\sum_{j'=1}^V \exp(u_{j'}) \end{align*} \] 对输出的每个位置\(c\)，\(\partial E / \partial u_{c,j}\)的计算方法与之前差别不大 \[ \frac{\partial E}{\partial u_{c,j}} = y_{c,j} - t_{c,j} := e_{c,j} \] 定义\(e_j\)为每个位置\(c\)上模型都预测为\(w_j\)时，模型的损失值总和 \[ e_j = \sum_{c=1}^C e_{c,j} \] 这样，跳表模型的\(\partial E /\partial w_{ij}'\)、\(e_i'\)和权重更新公式就和前面单个上下文CBOW模型的公式形式一样了
优化计算效率
前面提到无论是CBOW还是SkipGram算法，对每个单词都会计算出一个输入向量\(\boldsymbol{v}_w\)和一个输出向量\(\boldsymbol{v}_w'\)。为了计算输出向量，对每条训练数据都要迭代词表中的每个单词\(w_j\)，计算原始得分\(u_j\)、概率\(p_j\)（对SkipGram是\(p_{c, j}\)）、误差\(e_j\)然后才能更新\(\boldsymbol{v}_j'\)。这些计算代价太高，因此对大型训练语料或者大词表使用原始做法比较难，因此人们想出了分层softmax和负采样两种做法
分层softmax
分层softmax的做法是建立一棵二叉树（更确切地说，为了快速训练，是一颗Huffman树）表达此表中的所有单词，其中所有单词对应的节点都是叶子节点，因此树一共有\(V\)个叶子节点，相应地有\(V-1\)个内部节点。而且由树的性质，从树根到每个单词的路径是唯一的，这条路径也就可以用来估计叶子节点对应单词的概率。对单词\(w\)，记从根节点到其对应叶子节点路径上的第\(j\)个节点为\(n(w,j)\)
在该模型中，单词不再有对应的输出向量表示，而是每个内部节点都有一个输出向量\(\boldsymbol{v}'_{n(w,j)}\)。令\(L(w)\)是路径的长度（即路径上有几个节点，因此\(n(w, 1) = {\rm root}\)，\(n(w, L(w)) = w\)）。对所有内部节点\(n\)，令\({\rm ch}(n)\)为其左孩子（Mikolov的原始论文里其实无此限制），并令\([\![x]\!]\)在\(x\)为真时为1否则为-1，\(\sigma(x)\)是sigmoid函数，则一个单词是输出单词的概率是 \[ p(w=w_O) = \prod_{j=1}^{L(w)-1}\sigma\left([\![n(w, j+1) = {\rm ch}(n(w, j))]\!] \cdot {\boldsymbol{v}_{n(w,j)}'}^\mathsf{T}\boldsymbol{h}\right) \]
上图给出了分层softmax的一个示例。假设要计算输出单词为\(w_2\)的概率，这实际上是计算从根开始随机游走，有多大概率会走到\(w_2\)对应的叶子节点。我们先定义在每个内部节点向左走的概率为 \[ p(n, {\rm left}) = \sigma\left(\boldsymbol{v}_n'^\mathsf{T}\cdot \boldsymbol{h}\right) \] 由于二叉树是Huffman树，每个内部节点有且仅有两个分支，因此显然\(p(n, {\rm right}) = 1 - p(n, {\rm left})\)。由sigmoid函数的性质，有 \[ p(n, {\rm right}) = \sigma\left(-\boldsymbol{v}_n'^\mathsf{T}\cdot \boldsymbol{h}\right) \] 所以有 \[ \begin{align*} p(w_2=w_O) &= p(n(w_2, 1), {\rm left}) \cdot p(n(w_2, 2), {\rm left}) \cdot p(n(w_2, 3), {\rm right})\\ &= \sigma\left(\boldsymbol{v}_{n(w_2,1)}'^\mathsf{T}\cdot \boldsymbol{h}\right) \cdot \sigma\left(\boldsymbol{v}_{n(w_2,2)}'^\mathsf{T}\cdot \boldsymbol{h}\right) \cdot \sigma\left(-\boldsymbol{v}_{n(w_2,3)}'^\mathsf{T}\cdot \boldsymbol{h}\right) \end{align*} \] 显然有 \[ \sum_{i=1}^V p(w_i = w_O) = 1 \] 接下来来看一下分层softmax算法如何更新权重。为了简单起见，不失准确性地，可以记 \[ \begin{align*} [\![\cdot]\!] &:= [\![n(w, j+1) = {\rm ch}(n(w, j))]\!] \\ \boldsymbol{v}'_j &:= \boldsymbol{v}'_{n_{(w, j)}} \end{align*} \]
因此损失函数为 \[ E = -\log p(w=w_O|w_I) = -\sum_{j=1}^{L(w)-1}\log \sigma\left([\![\cdot]\!]\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\right) \]
先计算\(\partial E/\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\)。考虑到\(\sigma'(x) = \sigma(x)(1-\sigma(x))\)和\(\sigma(-x) = 1-\sigma(x)\)，有 \[ \begin{align*} \frac{\partial E}{\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}} &= \left(\sigma\left( [\![\cdot]\!] \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\right)-1\right)[\![\cdot]\!] \\ &= \begin{cases}\sigma\left(\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\right) - 1 & ([\![\cdot]\!] = 1)\\ \sigma\left(\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\right) & ([\![\cdot]\!] = -1) \end{cases} \\ &= \sigma\left(\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\right) - t_j \end{align*} \] 其中 \[ \begin{align*} t_j = \begin{cases}1 & {\rm if\ }[\![\cdot]\!]=1 \\ 0 & {\rm elsewhere}\end{cases} \end{align*} \]
有了\(\partial E/\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}\)以后，计算\(\partial E / \partial \boldsymbol{v}'\)就容易许多： \[ \frac{\partial E}{\partial \boldsymbol{v}_j'} = \frac{\partial E}{\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}} \cdot \frac{\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}}{\partial \boldsymbol{v}_j'} = \left(\sigma(\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h})-t_j\right) \cdot \boldsymbol{h} \] 所以对\(j = 1, 2, \cdots, L(w)-1\)，有内部节点输出向量的更新公式 \[ \boldsymbol{v}_j'^{(\rm new)} = \boldsymbol{v}_j'^{\rm (old)} - \eta \left(\sigma(\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h})-t_j\right) \cdot \boldsymbol{h} \]
该公式对CBOW和skip-gram模型都适用。对于后者，需要对\(C\)个输出单词重复走一遍这个过程
为了学习输入层到隐藏层的权重，需要计算\(\partial E/\partial \boldsymbol{h}\)： \[ \begin{align*} \frac{\partial E}{\partial \boldsymbol{h}} &= \sum_{j=1}^{L(w)-1}\frac{\partial E}{\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}} \cdot \frac{\partial \boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h}}{\partial \boldsymbol{h}} \\ &= \sum_{j=1}^{L(w)-1} \left(\sigma(\boldsymbol{v}_j'^\mathsf{T}\boldsymbol{h})-t_j\right) \cdot \boldsymbol{v}_j' \\ &:= \boldsymbol{e}' \end{align*} \]
就可以继续用之前推导过的公式来更新权重
可以看出，使用分层softmax以后，参数数量没有变化（\(V-1\)个输出向量，\(V\)个输入向量），但是每个训练单词的计算复杂度从\(O(V)\)削减到了\(O(\log(V))\)
负采样
负采样的思想是，由于每次迭代要花时间更新太多输出向量，不如采样少量几个单词，把它们当做负样本。采样负样本只需要设计一个合理的概率分布就可以，这里称其为“噪声分布”，记为\(P_n(w)\)。原文的噪声分布参见词向量的介绍。目标函数为 \[ E = -\log \sigma(\boldsymbol{v}_{w_O}'^\mathsf{T}\boldsymbol{h}) - \sum_{w_j \in \mathcal{W}_{\rm neg}} \log \sigma(-\boldsymbol{v}_{w_j}'^\mathsf{T}\boldsymbol{h}) \] 其中
- \(w_O\)是输出单词（正样本）
- \(\boldsymbol{v}_{w_O}'\)是正样本的输出向量
- 对CBOW模型，\(\boldsymbol{h}\)为\(\frac{1}{C}\sum_{c=1}^C \boldsymbol{v}_{w_c}\)；对skip-gram模型，\(\boldsymbol{h}=\boldsymbol{v}_{w_I}\)
- \(\mathcal{W}_{\rm neg} = \{w_j|j=1,\cdots, K\}\)是使用分布\(P_n(w)\)获得的一些单词（负样本）
类似地，可以先计算出损失函数对原始得分的偏导数 \[ \begin{align*} \frac{\partial E}{\partial \boldsymbol{v}_{w_j}'^\mathsf{T}\boldsymbol{h}} &= \begin{cases}\sigma\left(\boldsymbol{v}_{w_j}'^\mathsf{T}\boldsymbol{h}\right) - 1 & {\rm if\ } w_j = w_O \\ \sigma\left(\boldsymbol{v}_{w_j}'^\mathsf{T}\boldsymbol{h}\right) & {\rm if\ }w_j\in \mathcal{W}_{\rm neg}\end{cases} \\ &= \sigma\left(\boldsymbol{v}_{w_j}'^\mathsf{T}\boldsymbol{h}\right)-t_j \end{align*} \]
其中\(t_j\)意义明显，不再进一步解释。接下来的参数更新方式和\(\partial E/\partial \boldsymbol{h}\)的计算也与前面分层softmax部分的推导类似，不再赘述
Softmax的近似方法
本节主要来自于Ruder的博客文章[ruder2016a]
如本文和前面若干文章所讨论过的，softmax的最大问题是要对每个词都计算得分，因此当词表非常大时，算法的时间复杂度非常高。为了不让这个步骤成为影响效率的主要瓶颈，人们提出了很多种方法。其中softmax扩展法仍然保留了softmax的基本思想，不过对体系结构做出了修改；而采样法则是去掉了softmax层，通过修改损失函数做softmax的近似。word2vec的两个改进方案里，分层Softmax（以下简称HSM）属于第一种方法，而负采样属于第二种
（本节写作的初衷是，直觉上感觉TensorFlow不太好实现HSM，想看看有没有写得比较漂亮的代码，然后发现好像真的没有。接着，在OpenNMT-py，也就是OpenNMT的PyTorch版，的一个issue里，看到他们没有实现HSM的原因是PyTorch实现了一个更高效的方法，称为适应softmax（adaptive softmax，简称ASM）。因此勾起了我的好奇心，想看看有没有其它类似比较高效的，适用于大规模词表的softmax方法，于是就找到了Ruder的这篇文章。但是此文成文之时并没有介绍ASM，因此本节会同时覆盖两者，并把ASM作为重点。其它方法基本都会简略带过）
Softmax扩展法
除去HSM和ASM，[ruder2016a]还介绍了两种扩展方法
- 差分softmax（[chen2016]，differentiated softmax，DSM）认为不同单词需要的参数数量不一样。少部分常见词可能需要很多参数来描述，而大部分罕见词其向量维度可以少一点。因此DSM使用了一个很大的稀疏矩阵，将其分为若干块。假设矩阵分为两块，那么左上角的子矩阵列数会多一些，行数少一些，用来刻画常见词；而右下角的子矩阵则是列数少，行数多，用来刻画罕见词。稀疏矩阵的右上角和左下角都是0。该方法的问题是对罕见词的建模能力比较弱
- CNN-softmax [jozefowicz2016]对输出层也使用了一个字符级别的CNN（charCNN）。不过实验显示对拼写相近而意思差别很大的两个单词，charCNN的效果不太好。文章的对策是为每个单词加一个修正向量。这种做法的好处是对集外词比较鲁棒
本小节主要介绍的工作是FAIR在2016年发表的工作ASM[grave2017]（2016年首发于arxiv），这项工作的最大特点是其目的是要有效利用GPU，比起普通softmax有2倍到10倍性能提升。其核心思想是将单词聚类，然后做分层softmax
假设训练时每批量数据大小为\(B\)，隐藏单元数量为\(d\)，词表大小为\(k\)，大小为\(B\times d\)的隐层矩阵与大小为\(d \times k\)的输出层矩阵相乘的计算时间为\(g(k, B)\)。实验表明，当固定\(B\)大小不变时，存在一个阈值\(k_0\)，使得\(k \le k_0\)时\(g(k)\)的时间为常量，\(k > k_0\)时\(g(k)\)与\(k\)呈线性关系，对\(B\)也存在一个类似的\(B_0\)。因此有 \[ g(k,B) = \max(c+\lambda k_0B_0, c+\lambda kB) \] 即当矩阵相乘时，如果某个维度比较小，则相乘效率会降低。所以使用Huffman编码的效率不是最优的，原因是会导致每个内部结点下面只有两个叶子节点，节点数太少；或者如果某个内部节点下面的叶子节点都是罕见词，概率\(p\)都很小，也会导致\(pB\)变小，不划算
由于自然语言中存在Zipf现象（直观例子是87%的文档由20%单词覆盖），因此直观地说可以把词典\(\mathcal{V}\)划分成两个簇\(\mathcal{V}_{\rm h}\)和\(\mathcal{V}_{\rm t}\)，其中\(\mathcal{V}_{\rm h}\)是分布的头部（头簇），只包含最常见的单词；\(\mathcal{V}_{\rm t}\)是分布的尾部（尾簇），包含大量罕见词。划分应该满足\(|\mathcal{V}_{\rm h}| \ll |\mathcal{V}_{\rm t}|\)且\(p_{\rm h} := \sum_{w \in \mathcal{V_{\rm h}}}p_i \gg p_{\rm t} := \sum_{w \in \mathcal{V_{\rm t}}}p_i\)。如果使用short-list实现方式（根节点里包含一个列表，列表中存储头簇），且记\(k_{\rm h} = |\mathcal{V}_{\rm h}|\)，则总的计算时间为 \[ C = g(k_{\rm h}+1, B) + g(k_{\rm t}, p_{\rm t}B) \] 文章使用了一个投影矩阵来把尾簇的维度降低到\(d/4\)，因为罕见词不太容易被学习，使用高维空间比较浪费
类似的思想可以很容易扩展到多维划分的情况，此时词典\(\mathcal{V}\)被分为\(\mathcal{V}= \mathcal{V}_{\rm h} \cup \mathcal{V}_1 \cup \ldots \cup \mathcal{V}_J\)，\(\mathcal{V}_i \cap \mathcal{V}_j = \varnothing\)。此时比较好的策略是将所有词按出现频率降序排列，词频高的词分到比较小的簇，簇的大小依次增大（小簇里是词频高的词，大簇里是罕见词）。实验指出簇数在10到15达到最优，但是超过5以后模型ppl（perplexity，困惑度）变化不是很大，因此常用2到5个簇。确定簇数后，每个簇分配多少个单词就可以用动态规划求解
自适应softmax的TF实现可以参考这里
采样法
Softmax可以看做是将各个得分归一化的手段，采样法实际上是对归一化时的分母做近似，使用一些其它更容易计算的损失函数。采样法只在训练时可用，推断时仍然需要计算完整的softmax
为了说明上面加粗部分的结论，来看一下损失函数\(J_\theta\)对参数\(\theta\)的梯度。通常来讲，多元分类使用交叉熵作为损失函数，即 \[ H(p, q) = -\sum_x p(x)\log q(x) \] 这里\(p(x)\)为真实概率分布，\(q(x)\)为近似的概率分布。对于使用softmax获得各单词概率的模型来说，\(p(x)\)就是一个独热向量，该向量中对应应该出现的单词的ID那一行元素为1，其余元素为0；\(q(x)\)是一个概率分布，由softmax得出。因此假设目标单词为\(w\)，则损失函数为 \[ \begin{align*} J_\theta &= -\log \frac{\exp(\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h})}{\sum_{w_i \in V}\exp(\boldsymbol{v}_{w_i}'^\mathsf{T}\boldsymbol{h})}\\ &= -\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h} + \log \sum_{w_i\in V} \exp(\boldsymbol{v}_{w_i}'^\mathsf{T}\boldsymbol{h}) \end{align*} \] 记\(-\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h}\)为\(\mathcal{E}(w)\)，则上式可以重写为 \[ J_\theta = \mathcal{E}(w) + \log \sum_{w_i \in V}\exp(-\mathcal{E}(w_i)) \] 求\(J_\theta\)对\(\theta\)的偏导，有 \[ \begin{align*} \nabla_\theta J_\theta &= \nabla_\theta\mathcal{E}(w) + \nabla_\theta\log\sum_{w_i \in V}\exp(-\mathcal{E}(w_i))\\ &= \nabla_\theta\mathcal{E}(w) + \frac{1}{\sum_{w_i \in V}\exp(-\mathcal{E}(w_i))}\sum_{w_i\in V}\exp(-\mathcal{E}(w_i))\nabla_\theta(-\mathcal{E}(w_i)) \\ &= \nabla_\theta\mathcal{E}(w) + \sum_{w_i \in V}\frac{\exp(-\mathcal{E}(w_i))}{\sum_{w_j \in V}\exp(-\mathcal{E}(w_j))}\nabla_\theta(-\mathcal{E}(w_i)) \end{align*} \] 注意到求和项内部梯度的系数其实就是\(w_i\)的softmax概率，因此将其写作\(P(w_i)\)，有 \[ \begin{align*} \nabla_\theta J_\theta &= \nabla_\theta \mathcal{E}(w) + \sum_{w_i \in V}P(w_i)\nabla_\theta (-\mathcal{E}(w_i)) \\ &= \nabla_\theta \mathcal{E}(w) - \sum_{w_i \in V}P(w_i)\nabla_\theta \mathcal{E}(w_i) \end{align*} \] 因此梯度可以分为两部分，第一部分是增强目标单词\(w\)，第二部分是削弱非目标单词\(w_i\)。后者又可以写作 \[ \sum_{w_i \in V}P(w_i)\nabla_\theta\mathcal{E}(w_i) = \mathbb{E}_{w_i \sim P}[\nabla_\theta\mathcal{E}(w_i)] \] 因此所有的抽样法实际上都是在求上项的近似值，以避免算\(V\)中所有单词\(w_i\)的概率
[ruder2016a]调研了若干种基于采样法的工作，本文主要介绍两项：重要性采样法（Importance Sampling，简称IS）和噪声对比估计（Noice Contrastive Estimation，简称NCE）。另一个重要的方法是负采样，在本系列博客中已经提到很多次，这里就不赘述了。不过需要注意的是，负采样可以看作是NCE的一个简化版本
IS
如果知道前面提到的单词分布\(P\)，那么就可以从该分布中抽样\(m\)个单词，计算近似期望（蒙特卡罗法） \[ \mathbb{E}_{w_i \sim P}[\nabla_\theta\mathcal{E}(w_i)] \approx \frac{1}{m}\sum_{i=1}^m\nabla_\theta\mathcal{E}(w_i) \] 但是根据前面的分析，要避免计算每个单词的softmax分布，所以退而求其次，需要找到一个替代的分布\(Q\)，使得该分布容易获得，而且最好接近\(P\)。常用的分布\(Q\)是训练集中的单词词频。进一步，还可以用另一个近似来避免对抽样到的\(w\)计算\(P(w)\)。此时，计算\(1/R \cdot r(w_i)\)来避免计算\(P(w_i)\)，其中 \[ \begin{align*} r(w) &= \frac{\exp(-\mathcal{E}(w))}{Q(w)};\ \ \ R = \sum_{j=1}^m r(w_j) \end{align*} \] 综上，有 \[ \mathbb{E}_{w_i \sim P}[\nabla_\theta\mathcal{E}(w_i)] \approx \frac{1}{R}\sum_{r=1}^mr(w_i)\nabla_\theta\mathcal{E}(w_i) \] 需要注意的是，样本数越少，近似效果越差
关于IS法的详细内容，可以参考[bengio2003]
NCE
IS法的一个潜在风险是近似分布\(Q\)有可能偏离真实分布\(P\)，而NCE[gutmann2010] [mnih2012]则不再直接估计某个词的概率，而是使用了另一种损失函数做辅助。其核心思想是将目标单词从噪声中区分开，因此模型训练过程变成了求解一个二元分类问题。假设每个目标单词\(w_i\)的语境\(c_i\)由\(n\)个上文单词\(w_{t-1}, \ldots, w_{t-n+1}\)组成（注意原始NCE论文没有考虑单词下文），\(k\)个噪声单词\(\tilde{w}_{ik}\)来自于噪声分布\(Q\)（这里也使用一元词频），则类别\(y=1\)说明给定\(c_i\)得到\(w_i\)，类别\(y=0\)说明给定\(c_i\)得到\(\tilde{w}_{ik}\)。损失函数为 \[ J_\theta = -\sum_{w_i \in V}\left(\log P(y=1|w_i, c_i) + k\mathbb{E}_{\tilde{w}_{ik}\sim Q}[\log P(y=0|\tilde{w}_{ij}, c_j)]\right) \] 使用蒙特卡洛模拟来计算期望，上式可化为 \[ \begin{align*} J_\theta &= -\sum_{w_i \in V}\left(\log P(y=1|w_i, c_i) + k\sum_{j=1}^k\frac{1}{k}\log P(y=0|\tilde{w}_{ij}, c_j)\right) \\ &= -\sum_{w_i \in V}\left(\log P(y=1|w_i, c_i) + \sum_{j=1}^k\log P(y=0|\tilde{w}_{ij}, c_j)\right) \end{align*} \] 由于正确单词是从训练集的经验分布\(P_{\rm train}\)中取得且依赖于语境\(c\)，噪声来自于分布\(Q\)，因此给定语境\(c\)，取样到一个单词的概率为 \[ P(y,w|c) = \frac{1}{k+1}P_{\rm train}(w|c) + \frac{k}{k+1}Q(w) \] 若某个单词被抽中，则其为正确样本的条件概率为 \[ \begin{align*} P(y=1|w, c) &= \frac{\frac{1}{k+1}P_{\rm train}(w|c) }{\frac{1}{k+1}P_{\rm train}(w|c) + \frac{k}{k+1}Q(w)} \\ &= \frac{P_{\rm train}(w|c)}{P_{\rm train}(w|c) + kQ(w)} \end{align*} \] 由于\(P_{\rm train}(w|c)\)为未知量，可以将其替为模型概率\(P(w|c)\)，而显然 \[ P(w|c) = \frac{\exp(\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h})}{\sum_{w_i \in V}\exp(\boldsymbol{v}_{w_i}'^\mathsf{T}\boldsymbol{h})} \] 似乎又回到了原来的老问题，但是NCE直接将分母置为1！（更保守的做法是将分母设为一个可学习的参数，但是有研究发现学到的分母通常也都接近于1，而且方差不大）。这样，就可以直接说\(P(w|c) = \exp(\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h})\)，所以 \[ P(y=1|w,c) = \frac{\exp(\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h})}{\exp(\boldsymbol{v}_w'^\mathsf{T}\boldsymbol{h}) + kQ(w)} \] 由于要求解的是一个二分类问题，因此\(P(y=0|w, c) = 1-P(y=1|w,c)\)。将上述结论代入\(J_\theta\)，可得到最终的NCE损失函数 \[ J_\theta= -\sum_{w_i \in V}\left[\log \frac{\exp(\boldsymbol{v}_{w_i}'^\mathsf{T}\boldsymbol{h})}{\exp(\boldsymbol{v}_{w_i}'^\mathsf{T}\boldsymbol{h})+kQ(w_i)} + \sum_{j=1}^k\log\left(1-\frac{\exp\left(\boldsymbol{v}_{\tilde{w}_{ij}}'^\mathsf{T}\boldsymbol{h}\right)}{\exp\left(\boldsymbol{v}_{\tilde{w}_{ij}}'^\mathsf{T}\boldsymbol{h}\right) + kQ(\tilde{w}_{ij})}\right)\right] \] 有理论证明，当NCE中噪声样本数量\(k\)变大时，NCE损失函数的梯度会逼近于softmax函数的梯度
NCE与其它采样法的关系
[jozefowicz2016]论证了IS实际上是优化一个多类别分类问题（NCE是二分类），因此更适合于语言建模。当NCE使用的\(k=|V|\)且\(Q\)为均匀分布时（此时\(kQ(w) = 1\)），NCE退化成负采样
（原计划在本文里还跟进Ruder词向量系列博客的第三部：On word embeddings - Part 3: The secret ingredients of word2vec，该文章讨论了一些词向量的理论解释，但是比较抽象，数学内容更多，因此暂时就不介绍了。有兴趣的可以移步上面的链接阅读原文，或者参考[levy2015] [levy2014]）
如何生成好的词向量
[lai2016]讨论了一些训练词向量的细节，包括模型搭建、训练语料、参数设计等方面。文章调查的工作包括
- Neural Network Language Model (NNLM, [bengio2003])
- Log-Bilinear Language Model (LBL, [mnih2007])
- C&W [collobert2008]
- CBOW & Skip-gram [mikolov2013]
- Order：文章提出的虚拟模型，将上下文单词词向量连接起来
- Global Vectors model (GloVe, [pennington2014])
所有训练词向量的方法基本都依赖于一条分布式假设：出现在相似上下文的单词有相同意思。因此，文章调研的建模方法实际上都是在对目标单词\(w\)和上下文\(c\)之间的关系建模，不同模型的区别主要体现在 (1) 如何建模目标单词和上下文之间的关系 (2) 如何表示上下文。对于前者，大部分模型都是用给定上下文预测中心词（注意，从这个角度看，skipgram也可以看作是用上下文预测中心词，只不过此时“中心词”是滑动的），而C&W是建模\((c, w)\)的分数。对于后者，word2vec没有考虑上下文的词序，而其它工作均将上下文单词词向量按序拼接，有的还加入了隐藏层来获取更强的建模能力
文章使用了三类共八项任务来评估词向量模型，包括
- 词向量的语义属性，使用了WordSim353数据集（判断单词相似性，代号ws）、TOEFL数据集（四个选项选择同义词，代号tfl）、类比数据集（检查词向量是否能表示woman = queen - king + man的关系，代号sem & syn）
- 将词向量作为下游任务的特征。包括
- 使用IMDB数据集做文本分类（代号avg），此时模型特征是词向量的加权平均，权重是TF（term frequency）
- 命名实体识别（NER）（代号ner），测试集是CoNLL03 shared task数据集
- 使用词向量初始化神经网络，包括使用CNN做情感分类（代号cnn）、使用神经网络做词性标注（代号pos）等
最后得到如下结论
对于模型来说，从目标单词与上下文之间关系的角度看，训练时只建模\((c, w)\)分数的C&W不太容易捕捉词义相加和相减的关系，因此使用上下文预测目标单词的模型效果更好。从上下文表示的角度看，数据量小时，简单的模型效果更好（例如CBOW在训练语料单词量级为千万或亿时效果很好），但是语料量更大时，复杂的模型更好 如果要用词向量初始化其他任务需要的网络，或者作为特征，结论是不同词向量模型影响不是很大，此时简单的模型就足够了
对于训练语料来说，同领域下，语料量越大，得到的词向量效果越好。不同领域下语料训练出的词向量变化会非常大，例如IMDB语料训出的词向量里，与"movie"相近的词包括了"this"、"it"等，说明在这个语料里movie这个词相当于是一个停用词 文章做了一个比较有趣的实验：对于avg任务，使用纯IMDB语料训练词向量，加权作为特征，然后向训练词向量用的语料里逐渐加入wiki与纽约时报的语料，重新训练词向量，观察新特征对模型的影响。实验表明，混杂的语料总是不如纯净的IMDB语料，因此语料领域比语料数量影响大得多
训练词向量应该训练多少轮？实验表明使用训练词向量时对应的验证集意义不大，最好的选择是用一个简单的任务（例如前面介绍的tfl任务）来做验证。如果训练词向量是为了一个特定的任务，那么应该使用该任务对应的验证集来验证词向量效果，不过这个过程可能比较费时间。此外，对于NLP任务，50维的词向量就可以达到不错的效果
参考文献
[rong2014] Rong, X. (2014). word2vec parameter learning explained. arXiv preprint arXiv:1411.2738.
[ruder2016a] Ruder, S. (2016). On Word Embeddinngs - Part 2: Approximating the Softmax
[chen2016] Chen, W., Grangier, D., & Auli, M. (2016). Strategies for Training Large Vocabulary Neural Language Models. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (ACL2016) (Vol. 1, pp. 1975-1985).
[jozefowicz2016] Jozefowicz, R., Vinyals, O., Schuster, M., Shazeer, N., & Wu, Y. (2016). Exploring the limits of language modeling. arXiv preprint arXiv:1602.02410.
[grave2017] Grave, E., Joulin, A., Cissé, M., & Jégou, H. (2017, August). Efficient softmax approximation for GPUs. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 (ICML 2017) (pp. 1302-1310).
[bengio2003] Bengio, Y., & Senécal, J. S. (2003, January). Quick Training of Probabilistic Neural Nets by Importance Sampling. In AISTATS (pp. 1-9).
[gutmann2010] Gutmann, M., & Hyvärinen, A. (2010, March). Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (pp. 297-304).
[mnih2012] Mnih, A., & Teh, Y. W. (2012). A fast and simple algorithm for training neural probabilistic language models. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 (Vol. 2, pp. 1751-1758).
[levy2015] Levy, O., Goldberg, Y., & Dagan, I. (2015). Improving distributional similarity with lessons learned from word embeddings. Transactions of the Association for Computational Linguistics, 3, 211-225.
[levy2014] Levy, O., & Goldberg, Y. (2014). Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems, NeurIPS 2014 (pp. 2177-2185).
[lai2016] Lai, S., Liu, K., He, S., & Zhao, J. (2016). How to generate a good word embedding. IEEE Intelligent Systems, 31(6), 5-14.
[bengio2003] Bengio, Y., Ducharme, R., Vincent, P., & Jauvin, C. (2003). A neural probabilistic language model. Journal of machine learning research, 3(Feb), (JMLR) (pp. 1137-1155).
[mnih2007] Mnih, A., & Hinton, G. (2007, June). Three new graphical models for statistical language modelling. In Proceedings of the 24th international conference on Machine learning, ICML 2007 (pp. 641-648). ACM.
[collobert2008] Collobert, R., & Weston, J. (2008, July). A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th international conference on Machine learning, ICML 2008 (pp. 160-167). ACM.
[mikolov2013] Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013). Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781.
[pennington2014] Pennington, J., Socher, R., & Manning, C. (2014). Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing ,EMNLP 2014 (pp. 1532-1543).
