自然语言处理

Word2Vec （google 2013）

Efficient Estimation of Word Representations in Vector Space。

开篇碎碎念

这次整的活是一篇自然语言处理(Natural Language Processing, NLP)相关的内容，为什么突然不介绍图和推荐跑来介绍这个呢，因为我想在后续内容里介绍DeepWalk和Node2Vec，然而这俩其实是基于Node2Vec来的，放一块怕太长，所以我单独整了一篇，OKK，废话不说了，开冲！

背景介绍

Word2Vec也是一种嵌入算法，而它的目标是单词。再NLP领域内，单词是文本内容划分之后的最细粒度，单词组成句子，句子再组成段落和文章。那怎么表示单词呢？一种最简单的方法就是用索引，每一个索引表示一个单词。但是呢，一般来说，对于一个长文本，单词的数量是非常非常非常非常多的，要用索引去表示会带来维度灾难。（设想一下，在一个总计有1万个单词的文本中，用One-Hot编码一个单词就需要1万维，那一万个单词就要1万x1万的空间，而且每一行里只有1位是有效的，其余9999位都是0，这种情况下去对这些向量进行运算，是不是想想就头皮发麻）。

那咋办呢？想法子把这个高维索引向量整到低维特征空间里呗，嗯？你说用啥整？找个映射函数。那么怎么找到一个合适的映射函数呢？先卖个关子，我先介绍一下一个语言模的概念:

和所有的监督模型一样，语言模型可以被抽象成 $f(x)\to{y}$ 语言模型针对的问题很多，我们这里简单的选取一种结合上面那个抽象公式进行介绍。上式中，x可以看作输入的一个句子中的一个单词，y则是输入的这个单词的上下文单词，那么这样来看，函数 $f$ 的作用就是依据输入的单词内容对上下文内容进行预测，并使其符合自然语言的规则。Word2Vec从某种角度来看，也是一种语言模型。

也许有小伙伴会问，这么来看，Word2Vec是种端到端的模型，输入单词输出单词，那词向量搁哪呢？确实，这个例子里，语言模型是一种端到端的模型，但Word2Vec其实和语言模型有一丝丝的差距（也就是我上面说的在某种角度来看),相对于语言模型，Word2Vec更关心中间过程而非最后的预测，对于W2v（打全程太费劲了，从这里开始我就只打个W2v代替了），下游的上下文预测任务实际上是为获取词向量服务的，算法需要最后的监督来帮助拉近相似词的嵌入向量。在语言模型中，要想实现下游任务，不可避免的要进行一个词嵌入任务，正如上面我们提到的，如果直接对单词做one-hot编码，会造成维度灾难，所以找到一个映射函数能把这个高维向量转到低维向量里就显得尤为关键了。看吧，我们绕回来了。那到底怎么获取这个映射函数呢？交给上帝神经网络吧，（如果你还记得我之前在ConvLSTM里提到的神经网络的哲学的话），我们找到了足够的数据和可行的监督，神经网络会给我们惊喜的。

模型模型模型！

W2V里一共包含两个模型：CBOW和Skip-Gram，直接拍图！

w2v

CBOW:
如上图左所示，CBOW是一个用上下文单词预测当前词的模型，相对于之前的语言模型，CBOW模型十分简单，中间的预测处理层没有非线性层，且对所有的单词都共享同一个预测层参数。接下来让我们更具体地了解一下CBOW是怎么获取词向量地：拍图x2!

cbow

首先，让我们先了解CBOW模型的输入，对于单词这类非数值型且数量众多的值，我们通常使用one-hot编码对其进行表示。One-hot编码通过N位寄存器对N种状态进行编码，每个状态由一位寄存器独立表示，且任何状态下只有一位有效。我们假设当前问题下共有V种单词，所以对于其中的每一种单词，其one-hot编码表征为V维。从图中可以看到，对于所有上下文单词的one-hot编码表征，CBOW模型设定了一个共享的权重参数 $W_{V\times{N}}$ ，所有上下文单词表征与该权重相乘相加获得了一个N维的中间向量。之后，CBOW模型又设定了一个权重参数 $W_{V\times{N}}^{'}$ ，通过中间向量与之相乘获得一个V维的输出向量，再利用
$Softmax(x_i)=\frac{e^{x_i}}{\sum_{j=1}^{V}{x^{x_j}}}, i=1,2,...,V$
计算出最有可能的当前单词的对应位置，完成预测。而要训练这个神经网络，只需要利用反向传播算法即可，反向传播算法我这里也不展开了嗷，之后别地章节里铁会有写的！。(~~Flag!!!~~)
Skip-gram:
Skip-gram在输入层、预测层与输出层的维度与CBOW模型类似，唯一不同点在于CBOW通过上下文单词预测当前词，而Skip-gram通过当前词预测上下文单词，不展开了嗷。
下面主要关注两个能加速计算的技巧 层次Softmax、负采样:
层次Softmax(Hierarchical Softmax)：
在传统的word2vec的训练和预测阶段，需要利用一个 $N\times{V}$ 的权重参数将N维的中间向量再转回一个V维的向量(这个输出向量中的每一位表示预测为这一位单词的概率)，再通过Softmax归一化概率后进行损失计算和预测。传统的Softmax方法在处理大数据的时候会有速度过慢的问题，因此，Word2vec引入了层次Softmax来帮助加速计算。

来，康康原理：

层次Softmax使用二叉树表示词库中的所有单词，在一颗已经构成的二叉树中，一定有V个叶子节点表示词库中的V个单词，同时，由于这是一颗二叉树，我们很容易能得知其中有V-1个内部节点。对二叉树中的每一个叶子节点，都有一条唯一的从根节点到其的路径，在层次Softmax 中，我们利用这条路径估计当前预测值是否为该叶子节点表示的单词的概率。

为了追求最快的训练速度，Word2Vec模型使用了霍夫曼树进行层次Softmax（其中霍夫曼树中各叶子节点的权重为该叶子节点表示的单词的出现频率），所以下图给出了一副基于霍夫曼树的层次Softmax示例，然后就按着这个来进行介绍了：（拍图x3！）

hierachical

与传统的Softmax不同，层次Softmax不再需要预测层的权重

W_{N\times{V}}

,所以它的输出也不会是一个V维的向量，取而代之的是二叉树中的一系列可学习的内在节点上的向量

v_{n(w,j)}^{'}

,而计算当前值为某一节点

W_2

代表的单词的概率则由以下公式进行计算：

P(w=w_0)=\prod_{j=1}^{L(w)-1}{\sigma([n(w,j+1)=ch(n(w,j))]\cdot{{v_{n(w,j)}^{'}}^Th})}

看起来是不是有点恐怖。一点一点来叭，这其中，

ch(n)

表示节点n的左孩子节点，

n(w,j)

表示从根节点到叶子节点w路径上的第j个节点,

v_{n(w,j)}^{'}

表示内部节点

n(w,j)

的可学习向量，h是预测层输出的中间向量（在Skip-gram中是当前单词的向量表征

h=v_{w_{I}}

;在CBOW中是上下文单词向量表征的均值

h=\frac{1}{h}\sum_{c=1}^{C}{v_{w_c}}

[x]

被定义为一个指示函数，其功能为：

[x]=\left\{ \begin{aligned} 1&\qquad if\ x\ is\ true\\ -1&\qquad otherwise \end{aligned} \right.

为了方便理解哈，我们拿图上的那个

w_3

为例来算一波概率：首先再强调一波，在层次Softmax中，我们可以将预测为某一个单词的概率视作是从根节点开始随机游走到这个单词对应的叶子节点的概率。于是我们定义对于每一个内部节点想左孩子节点游走的概率为：

p(n,left)=\sigma{({v_n^{'}}^T\cdot{h})}

从上式中不难发现，是否向左孩子节点游走取决于预测层的中间向量与当前节点的可学习向量（值得注意的是，在层次Softmax方法中，通过Sigmoid函数将概率归一化）。那么向右游走的概率显然是：

p(n,right)=1-p(n,left)=1-\sigma({v_{n}^{'}}^T\cdot{h})=\sigma({-v_{n}^{'}}^T\cdot{h})

那么从根节点游走到叶子节点

w_3

的概率即为：

P(w_3=w_O)\\ \begin{aligned} &=p(n(w_3,1),left)\cdot{p(n(w_3,2),left)}\cdot{p(n(w_3,3),right)}\\ &=\sigma({v_{n(w_3,1)}^{'}}^T\cdot{h})\cdot{\sigma({v_{n(w_3,2)}^{'}}^T\cdot{h})}\cdot{\sigma({-v_{n(w_3,3)}^{'}}^T\cdot{h})} \end{aligned}

然后我们就可以得到上面的那个hin长的公式了。并且我们从中可以看出，对于所有的叶子节点，由：

\sum_{i=1}^{V}{p(w_i=w_O)}=1

再然后，我们来推一下层次Softmax中参数更新的方法。首先，对于层次Softmax，我们可以将损失函数定义为：

E = -log\,p(w=w_O|W_I)=-\sum_{j=1}^{L(w)-1}{log\sigma{([\cdot]{v_{n_{w,j}^{'}}}^T\cdot{h}})}

该损失函数的目的即为最大化预测正确的概率，这个里面有一串很长的

{v_{n_{w,j}^{'}}}^T

和

[n(w,j+1)=ch(n(w,j))]

,之后我就简化成

{v_{j}^{'}}^T

和

[\cdot]

(~~虽然复制粘贴hin快，但架不住我懒~~)，然后我们来对E求

{v_{n_{w,j}^{'}}}^T\cdot{h}

的导数，如下：

\frac{\partial{E}}{\partial{{v_{n_{w,j}^{'}}}^T\cdot{h}}}\\ \begin{aligned} =&(\sigma([\cdot]v_{n_{w,j}^{'}}^T\cdot{h}))\\ =&\left\{ \begin{aligned} \sigma(v_{n_{w,j}^{'}}^T\cdot{h})-1,&\qquad ([\cdot]=1)\\ \sigma(v_{n_{w,j}^{'}}^T\cdot{h})&\qquad ([\cdot]=-1) \end{aligned} \right.\\ =&\sigma(v_{n_{w,j}^{'}}^T\cdot{h})-t_j \end{aligned}

其中，当

[\cdot]=1

时，

t_j=1

，否则

t_j=0

。
拿到这个之后，我们就可以对E求

v_{n_{w,j}^{'}}^T

的导数了：

\frac{\partial{E}}{\partial{v_{n_{w,j}^{'}}^T}}=\frac{\partial{E}}{\partial{v_{n_{w,j}^{'}}^T}\cdot{h}}\cdot{\frac{\partial{v_{n_{w,j}^{'}}^T}\cdot{h}}{\partial{v_{n_{w,j}^{'}}^T}}}=(\sigma(v_{n_{w,j}^{'}}^T\cdot{h})-t_j)\cdot{h}

然后捏，然后我们就可以得到新参数的迭代公式了：

{v_{j}^{'}}^{(new)}={v_{j}^{'}}^{(old)}-\eta((\sigma(v_{n_{w,j}^{'}}^T\cdot{h})-t_j)\cdot{h}),for i=1,2,...,L(w)-1

再然后，为了让这边的损失值能通过反向传播传递至模型的左半边（这里我们把预测这一块看作有半边嗷），就对损失函数E求关于隐藏层输出的偏导:

\frac{\partial{E}}{\partial{h}}=\sum_{j=1}^{L(w)-1}{\frac{\partial{E}}{\partial{v_{n_{w,j}^{'}}^T\cdot{h}}}\cdot\frac{\partial{v_{n_{w,j}^{'}}^T\cdot{h}}}{\partial{h}}}=(\sigma(v_{n_{w,j}^{'}}^T\cdot{h})-t_j)\cdot{v_j^{'}}

在CBOW模型中，该值可以直接传递以更新模型从输入到中间向量的权重；而对于Skip-gram模型，需要计算所有上下文单词的偏导数值，并将总和传递以更新权重。

负采样策略（Negative Sampling）：
负采样策略主要是为了解决在每轮中需要更新大量输出向量而导致速度受限的问题。为此，负采样策略选择留下正样本及部分采样得到的负样本，并通过这些留下的数量更小的样本集进行模型参数更新。整一个小例子嗷，假设有1万个词汇需要被训练，我们输入单词“fox“进入word2vec时，希望最后的输出结果只在fox对应的那一位为1，其余9999位都为0，如果按照传统的训练方式，这里所有的输出向量对应的权重参数都需要更新，而负采样的对象就是这9999位，负采样策略从中选择一小部分的negative word，并用这小部分负样本进行权重更新。
于是，在负采样策略中，损失函数变为：
$E=-log\,\sigma({v_{w_O}^{'}}^Th)-\sum_{w_j\in{W_{neg}}}{log\,(\sigma{-{v_{w_j}^{'}}^T\cdot{h}})}$
其中呢， $w_O$ 是正样本， $v_{w_O}^{'}$ 是其输出向量，h是预测层输出的中间向量， $W_{neg}$ 是采样得到的负样本合集， $v_{w_j}^{'}$ 是其输出向量。之后的参数更新、损失传递与之前的推导类似，这里不再展开。需要强调的是，与原始的Word2Vec模型相比，参与更新的只有正样本和采样得到的负样本的输出向量，相当于只在一个子集上进行了更新。

总结总结总结

fufufu，终于写完了，这篇篇幅应该是目前最长的一篇了，因为这是一篇非常非常非常非常经典的工作，我希望能尽可能介绍的细一点，另外很多后续工作例如DeepWalk啊，Node2Vec啊，GATNE啊，啥的都会基于这个，之后我们也会慢慢接受，OK，收！

【NLP】词嵌入算法—Word2vec