Word2vec 数学原理详解

Word2vec 数学原理详解

引言

词向量可看做基于深度学习的自然语言处理的一个里程碑。从2003年最初的神经语言模型的副产物,到后面的Word2vec, glove, fastext, 及其近两年流行的ELMO, GPT, BERT, 可以说,预训练词向量是伴随着自然语言处理一起发展的。

这篇博客主要想介绍下Word2vec的相关知识,特别是word2vec的数学原理部分,已达到对其有个知其然且知其所以然的目的。Word2vec 最初由Mikolov2013年在《Efficient Estimation of Word Representations in Vector Space》中提出,但文中对其细节并未涉及太多。本文主要基于2016年Xin Rong的一篇论文,《word2vec Parameter Learning Explained》。

1 神经语言模型

神经语言模型是对一个句子出现的概率进行建模。直白点的说法就是,什么样的句子更像是人话。假设一个句子有m个单词,$ [w_1, w_2, …, w_m] $,那么这个句子出现的概率就是这m个单词的共现概率:

$$
P(sent=[w_1, w_2, …, w_m])=P(w_1, w_2, …, w_m)=P(w_1)P(w_2|w_1)P(w_3|w_2, w_1)…P(w_m|w_{m-1}…w_1)
$$
我们希望概率$P$能取到最大值,从而得到一句比较靠谱的话,其实就是希望上式中的条件概率$P(w_m|w_{m-1}…w_1)$最大,即在给定$[w_1, w_2, …, w_{m-1}]$的情况下, 下个词是$w_m$的概率最大。实际情况中,往往假设下个词出现的概率只与距离他比较近的N个词相关(一般N<5),这就是N-gram语言模型了,它是语言模型的一个近似。这时, 上式退化成:

$$
P(sent=[w_1, w_2, …, w_m])=P(w_1, w_2, …, w_m)=P(w_1)P(w_2|w_1)P(w_3|w_2w_1)…P(w_m|w_{m-1}…w_{w-n})
$$
2003年,Bengio在《A neural probabilistic language model》中提出了非常经典的神经语言模型,word2vec就是由此简化而来。Bengio利用一个简单的三层(实际上是四层,第一层是查表)神经网络来计算条件概率$P(w_m|w_{m-1…w_{m-n}} )$,如下图所示(这里并没有采用论文原图,而是用了一个更加详细的前馈神经网络,标注更加详细):

从下往上看,首先, C是一个维度(V, D) 的矩阵, 存储着所有词的词向量,其中D为词向量的维度, V为词典大小, C一般是随机初始化的。用前n个词的索引到C中去取对应的词向量, 拼接到一起,得到一个(1, ND)的向量,然后经过线性运算W(维度为(ND, H)映射到隐藏层(维度为1, H),在与$W’$(维度为(H, V))线性运算,经过激活函数,输出一个(1, V)的矩阵。由于我们希望遍历所有词汇找到概率最大的那个词, 因此,最终的输出概率应该是所有词的概率, 为(1, V)维。

这个模型训练起来会非常耗时。原因将在下面说明。

2 One word model

下面结合图2来说明类CBOW的前向和反向传播过程。为简单起见,我们只考虑上文为1的情况,即输入是一个词, N=1。

CBOW相比于神经语言模型,在网络结构上有个两个主要的改变:

  • 没有激活函数
  • 只有三层,上面我们提到过,神经语言模型实际上有四层,第一层是查表操作。CBOW实际上是省略了神经语言模型中的隐藏层。

在输入层,单词$w_I$是用one-hot矩阵来表示的,维度为(1, V), 即除了$x_k$为1, 其他全部为0, k为该单词在词汇表中的下标。该向量与词向量矩阵(维度为(V,D))相乘,实际上是做行的选取, 取除了第k个单词对应的词向量矩阵的第k行,得到一个(1, D)的向量, 记为$X$,事实上这就是这个单词的词向量表示。

先来看下前向传播,从第一层到第二层:

$$h=W_T \cdot X=v^T_{w_I}$$

第二层到第三层(输出层):

$$u=W’^T \cdot h$$

各层维度变化依次为:
$$
(1, V)(V, D)\rightarrow(1, D)(D, V)\rightarrow(1, V)
$$
最后用softmax将输出层做一个归一化,得到每个候选词$w_j$的概率:

$$P(w_j|w_I)=y_j=\frac{exp(u_j)}{\Sigma_{k\in V}exp(u_k)}$$

这里面$W$和$W’$是要学习的参数, 其中W就是词向量。这里其实出现一个问题了,为什么用W而不用W’作为词向量的表示呢?下面从反向传播出发给出解释。

首先,一个训练样本为$(w_I, w_o)$, 输入词是一个one-hot表示的维度为V的向量X,真实值为$w_O$, 也可以将其表示为one-hot编码,而我们模型的输出是维度为V的概率,因此可以用交叉熵作为损失函数。

上面我们得到了每个候选词的概率表示,那么,利用最大对数似然函数,可以得到:

$$max P(w_O|w_I) = max \frac{exp(u_j)}{\Sigma_{k\in V}exp(u_k)}=max(u_j-\Sigma^V_{k=1}exp(u_k))=-E$$

取对数,可得到:

$$max Obj=u_{j^*}-\Sigma^V_{k=1}exp(u_k))$$

结合以上两式,可得:

$$E=u_{j^*}-\Sigma^V_{k=1}exp(u_k))$$

接下来就可以利用E进行反向传播了。

首先第三层到第二层的向量矩阵W’的梯度:

$$\frac{\partial E}{\partial W’_{ij}}=\frac{\partial E}{\partial u_j}\frac{\partial u_j}{\partial W’_{ij}}=(y_j-t_j)h_i$$

这样就能得到W‘更新方式了:

$$
W’^{(new)}{ij}=W’^{(old)}{ij}-\eta \cdot(y_j-t_j)h_i
$$
上式是W’一个元素的更新方式,我们将他整合成向量的形式:

$$v’^{(new)}_{w_j}=v’^{(old)}_{w_j}-\eta \cdot(y_j-t_j) \cdot h$$ $$for j=1, 2, …, V$$

其中,$\eta$是学习率。我们具体看下更新过程。我们的目标$t=[0, 0, 0,…,1,0, 0, 0]_{1V}$。只有一个词为1, 剩下的都为0。而模型的预测为$y=[x_1, x_2, …, x_V]$. 更新的目的就是为了是y逼近t。这就是说,对于每个j,W‘的第j列向量都要如上式的方式更新。W’的更新需要对所有的V列个向量进行更新,即DV个参数。

接着看第二层到第一层的更新方式,即参数矩阵W的更新,其实就是h的更新,因为h是W的一行。

$$\frac {\partial E}{\partial W}=\frac {\partial E}{\partial h} \frac{\partial h}{\partial W}$$

由于h是(1, D)为向量,且$u_j = w_{ij} \cdot h_i$,我们先考察每个元素$h_i$的更新方式:

$$\frac {\partial E}{\partial h_i}=\frac {\partial E}{\partial u} \frac {\partial u}{\partial h_i}= \Sigma^V_{j=1}(y_j-t_j)w’_{ij}=W’_i \bigodot P$$

这里求和的原因与上面类似。这样就能得到:

$$\frac {\partial E}{\partial h}=W’ \bigodot P$$

这里其实就是$W_i$的更新了。

由于$x$中仅一个元素不为0, 所以W只需要更新第i行就行了。

CBOW model

模型如下图所示:

跟one word model唯一不同的是,输入不再是一个单词,而是C个单词,每个单词都采用one hot编码。这时候第二层的计算与之前就有些不同了。之前是直接取出W的第i行作为h的值,现在则是取出W中所有C个单词的词向量,共C行,然后直接取平均:

$$h=\frac {1}{C}W^T(x_1+x_2+…+x_C)=\frac {1}{C}(v_{w_1}+v_{w_2}+…+v_{w_C})T$$

后面的前向传播就和one-word-model 没什么不同了。

再来看反向传播。第三层到第二层,与one word model 完全相同。$\frac {\partial E}{\partial h}$也不变, 再写一遍:

$$\frac {\partial E}{\partial h}=W’ \bigodot P$$

但是这时候W的更新稍有不同了,因为h是由多个行做平均的,这里采取的策略是将h的梯度平均分配到每个单词上,每次反向传播时会更新W中的c行。

$$v^{T(new)}_{w_{I,c}}=v^{T(old)}_{w_{I,c}}-\frac {1}{C} \eta W’\bigodot P$$ $c=1, 2, …, C$

SkipGram Model

skipGram是通过单词预测上下文,这个模型与one word model不同之处在于,SG的输出有多个词,而one word model的输出只有一个词。此时,输出层就不是一个多项式分布了,而是C个多项分布,模型如下图所示。

先来看下前向传播,第一层到第二层与one word model相同:

$$h=W^T \cdot X=v^T_{w_I}$$

在输出层,有C个词,意味着有C个独立的多项式分布:$y_1, y_2, …y_C$, 对于第c个词,输出层预测的概率与one word model相同:

$$P(w_{c, j}|w_I)=y_{c, j}=\frac {exp(u_{c,j})}{\Sigma^V_{k=1}exp(u_{c, k})}$$

至于从第二层到第三层,从图中可以看出,连接第二层与c个输出层的参数矩阵W‘是共享的,即$u_{c,j}=u_j=v’^T_{wj} \cdot h$, 这里$v’^T_{wj}$与one word model中一样,表示W’的第J列,同时也是词汇表中第j个单词的一种词向量表示。

对于SG模型,损失函数和前面两个模型稍有不同,这里需要最大化的是C个词的概率,而这C个词是独立的,因此他们的联合概率只需将每个词的概率相乘即可,其对数最大似然函数如下:

$$E=-\Sigma^C_{c=1}u_{j^*c}+Clog\Sigma^V_{k=1}exp(u_k)$$

这里:

$$\frac {\partial E}{\partial u_{c,j}}=y_{c, j}-t_{c, j}$$

下面来看下W‘的梯度。由于W’是C个单词共享的,因此其梯度更新受C个单词影响,实际上也是平摊的思想,只不过反过来了。先来看下W‘中一个元素的梯度:

$$
\frac {\partial E}{\partial w’{ij}}=\Sigma^C{c=1}\frac {\partial E}{\partial u_{c,j}}\frac{\partial u_{c,j}}{\partial w’{ij}}=\Sigma^C{c=1}(y_{c,j}-t_{c,j})h_i=Q_jh_i
$$
与one word model相比,这里就多了一个求和项而已。W’的更新也类似。

再来看第二层到第一层,首先考虑对$h_i$的梯度:

$$
\frac {\partial E}{\partial h_i}=\Sigma^C_{c=1}\Sigma^V_{j=1}\frac{\partial E}{\partial u_{c,j}}\frac{\partial u_{c,j}}{\partial h_i}=\Sigma^C_{c=1}\Sigma^V_{j=1}(y_{c,j}-t_{c,j})w’{ij}=\Sigma^V{j=1}Q_jw’_{ij}=W’_i \bigodot Q
$$
向量形式为:

$$\frac {\partial E}{\partial h}=W’ \bigodot Q$$

h同样是W的一行。

至此,CBOW和SKIP的前向和反向传播就介绍完了。这两个都可以看做one word model的变种,CBOW是第一层到第二层变了,而SG是第二层到第三层变了,所以先理解one word model很重要。

从反向传播的推导可以看出,对于CBOW和SKIP模型,W‘每次需要更行所有的参数,而W每次只需更行部分行。W’的参数个数为(D,V),其中,D为词向量维度,一般在50-300之间,V为词典大小,对于大规模语料,可能达到十万百万量级,因此,这一层的参数量在千万亿量级,规模巨大。因此,人们提出一些策略来优化,word2vec采用了层次化softmax和负采样两种方法来优化,这两种方法的目的是一致的,就是在训练时,一次反向传播的只需更新W‘的部分参数,也就是说W’并不是实际中存在的,这也是为什么不用它作为词向量表示的原因。上述过程训练过程复杂度高的原因在于,每次都要更新V列个列向量,这两种方法都是用来减小这个数目。

Hierarchical softmax (层次化softmax)

回想下上面三个模型的输出层,我们的目的是对给定的输入,找到概率最大的候选词作为输出。HS主要基于哈弗曼树,他将计算量大的部分变成了二分类问题。下图所示是一颗哈弗曼树(二叉树),其叶子节点为所有的V个词。根节点与第二层的h相连。

从根节点到每个叶子节点,都有一条唯一的路径。比如说,$w_2$是真实值,那我们的目的就是使得加粗的这条路径的概率最大。从根节点到叶子节点,经过每个内部节点时,都有两种选择,即向左还是向右,不同的选择对应不同的路径。这里用到类似逻辑回归的思想。用$n(w,j)$表示到叶子节点$w$的路径上第j个非叶子节点,我们假设每个非叶子节点都对应一个向量$v’_{n(w,j)}$, 维度与h相同,为(1, D)。可以证明,一共有V-1个这样的内部节点。在每个内部节点,我们将该节点的向量与h做内积,然后做sigmoid变换,得到一个概率值,通过概率来指示向左还是向右。第j个节点向左和向右的概率定义为:

$$P(j, left)=\sigma(v’^T_w \cdot h)$$

$$P(j, right)=1-\sigma(v’^T_w \cdot h)=\sigma(-v’^T_w \cdot h)$$

这样,就可以定义整条路径上,输入输出的概率了:

$$P(w=w_O|w_I)=\Pi^{L_{(w)-1}}_{j=1}P(I(n(w,j+1==left)v’^T_w \cdot h))$$

其中,$I()$为指示函数,当下个节点是left,为1, 否则为-1, $L_{(w)}$表示整条路径的长度。

下面给出对数似然函数:

$$-E=-logP(w=w_O|w_I)=-\Sigma^{L_{(w)-1}}_{j=1}log(\sigma([I]v’^T_j \cdot h))$$

接着就可以求梯度了(这里省略了log,具体推导可见论文):

$$\frac {\partial E}{\partial v’^T_j}=\frac {\partial E}{\partial v’^T_j \cdot h}\frac{\partial v’^T_j \cdot h}{\partial v’^T_j}=(\sigma(v’^T_jh)-t_j)h$$

$v’^T_j$的更新方式为:

$$v’^{(new)}_j=v’^{(old)}_j-\eta((\sigma(v’^T_jh)-t_j)h$$ $j=1, 2, 3,…,L_{w}-1$

这就是说,对于一个样本,只需要更新$L_w-1$个向量就行了,而未优化版本需要更新V个,相当于时间复杂度从$O(V)$变成了$O(log(V))$, 而向量的个数没变,都是V个向量,即空间复杂度相同。而且,一般构建哈弗曼树时,高频词会离根节点越近,也就是说高频词的路径更短, 复杂度低于$O(log(V))$

隐藏层的梯度也很容易求得:

$$\frac {\partial E}{\partial h}=\frac {\partial E}{\partial v’^T_j \cdot h}\frac{\partial v’^T_j \cdot h}{\partial h}=\Sigma^{L_{(w)-1}}_{j=1}(\sigma(v’^T_jh)-t_j)v’_j$$

Negative Sampling 负采样

负采样比层次化softmax更简单粗暴了,每次训练,我们这样构造样本,首先正确的候选词只有一个,为正例,负例呢,在剩余的词中按照一定分布采样N个, N<<V。如何采样呢?在word2vec中,作者直接基于词频的权重分布:

$$len(w)=\frac {count(w)^{3/4}}{\Sigma_{u\in vocab} count(u)^{3/4}}$$

采样前,我们将长度为1的线段划分成M等份,M>>N, 这M份中的每一份都对应某个词对应的线段上。采样的时候只需要从M个位置中采样出neg位置就可以了,每个位置所属的词就是负例词。

这样,每次优化时,使正例的概率越大越好,负例的概率越小越好,这实际上是二元逻辑回归来解决多分类问题。正例和负例的概率分别为:

$$P_+=\sigma(v’^T_w \cdot h)$$

$$P_-=1-\sigma(v’^T_w \cdot h)=\sigma(-v’^T_w \cdot h)$$

那么,正例和负例的最大似然函数为:

$$maxObj=maxP_+ \cdot \Pi^N_1P_-$$

对数似然函数为:

$$E = -log(P_+)-\Sigma^N_1log(P_-)$$

其中,N为负采样的个数。

剩下部分的推导就和HS一样了,这里就不再赘述。

总结

  • Word2vec 是神经语言模型的优化版本,CBOW是用周围的词预测中心词;SKIP-Gram中心词预测上下文
  • 层级softmax和负采样技术是两种优化技术,其核心思想是每次训练时,不用更新第二层到输出层矩阵的所有参数,只需更新部分参数即可,大大降低了计算复杂度。