Word2Vec数学原理初探

前言

论文：https://arxiv.org/pdf/1301.3781.pdf

符号约定如下：

1. $\textrm{context(w)}$：表示词的上下文，即w前window个词和后window个词，但不包括词w
2. C：表示整个有效的词样本空间(即语料库中所有词的集合去掉低频词后的词语集合)
3. $\textrm{Neg}(w)$：w的负样本空间，不包括w。

sigmoid函数

定义为：

$$\sigma(x) = \frac{1}{1+e^{-x}}$$

导数为:

$$\sigma^{'}(x)=\sigma{x}(1-\sigma(x))$$

函数$\log \sigma(x)$的导数为:

$$[\log \sigma(x)]^{'} = 1-\sigma(x)$$

函数$\log(1- \sigma(x))$的导数为:

$$[\log(1-\sigma(x))]^{'} = -\sigma(x)$$

Hierarchical Softmax

huffman树结构及其表示

如上图所示，黄色为叶子节点用于表示字典中的单词，白色为非叶子结点为辅助节点。除了根节点外，其余节点会标识0或者1，左边为1，右边为0。

关于数学符号的相关约定如下：

1. 令$P^w$表示从根节点到达w对应叶子结点的路径。以上图为例$w_2$的路径$P^{w2}$ 为$P_1^{w_2},P_2^{w_2},P_3^{w_2},w_2$

2. 令$\mathcal{l}^w$表示路径$P^{w}$包含结点的个数

3. 令$P_j^w$表示词w的路径$P^w$上第j个节点
4. 令$d_j^w \in \{0,1\}$表示对于词w，在路径$P^w$的第j个节点$P_j^w$的编码；比如，词$w_2$在$P_2^w$节点上的编码为1
5. 令$\theta_j^w \in R$表示词w在路径$P^w$上第j个节点的参数(向量)

从根节点开始，在每个非叶子结点上，都有两个选择，要么编码为1，要么编码为0，这正好对应到二值分类器。在w2v的实现中，将huffman编码为0对应到正类，编码为1对应到负类。所使用的二分类器为逻辑回归分类器。

在上图的huffman树中，逻辑回归二分类器的正类概率表示为:

$$\sigma(X^{\top}\theta) = \frac{1}{1+e^{-X^{\top}\theta}} \tag{1-1}$$

负类概率表示为：

$$1-\sigma(X^{\top}\theta) \tag{1-2}$$

那么对于节点$P_j^w$的编码可表示成:

$$\textrm{label}(P_j^w) = 1-d_j^w \tag{1-3}$$

使用huffman树求词的概率

以w2为例$\mathcal{P}_{w_2}=P_1,P_2,P_3,w_2$，处理过程如下：

1. 在$P_1$处向左转移，概率为:$P(d_2^{w_2}=1|X_{w_2}^{\top},\theta_1^{w_2}) = 1-\sigma(X_{w_2}^{\top}\theta_1^{w_2})$
2. 在$P_2$处向右转移，概率为:$P(d_3^{w_2}=0|X_{w_2}^{\top},\theta_2^{w_2})=\sigma(X_{w_2}^{\top}\theta_2^{w_2})$
3. 在$P_3$处向左转移，概率为:$P(d_4^{w_2}=1|X_{w_2}^{\top},\theta_3^{w_2})=1-\sigma(X_{w_2}^{\top}\theta_3^{w_2})$

以w2的概率为例，其概率可以写成如下形式:

$$\begin{aligned} P(w_2) &= \prod_{j=1}^{\mathcal{l}^{w_2}-1}P(d_{j+1}^{w_2}|X_{w_2}^{\top},\theta_j^{w_2})\\ &= \prod_{j=1}^{\mathcal{l}^{w_2}-1} \{[1-\sigma(X_{w_2}^{\top}\theta_j^{w_2})]^{d_{j+1}^{w_2}}[\sigma(X_{w_2}^{\top}\theta_j^{w_2})]^{1-d_{j+1}^{w_2}}\} \end{aligned} \tag{1-4}$$

推广到一半情况，即为:

$$\begin{aligned} P(w) &= \prod_{j=1}^{\mathcal{l}^{w}-1}P(d_{j+1}^{w}|X_{w}^{\top},\theta_j^{w})\\ &= \prod_{j=1}^{\mathcal{l}^{w}-1} \{[1-\sigma(X_{w}^{\top}\theta_j^{w})]^{d_{j+1}^{w}}[\sigma(X_{w}^{\top}\theta_j^{w})]^{1-d_{j+1}^{w}}\} \end{aligned} \tag{1-5}$$

CBOW连续词袋模型

如上图所示，cbow有三层结构，分别为:

1. 输入层：$V_{u}$,其中$u\in \textrm{context}(w)$，$\textrm{context}(w) \subset C$
2. 投影层：$\textrm{sum}(V_u)=\sum_{u\in \textrm{context(w)}} V_u$
3. 输出层：输出层对应一棵huffman树

目标函数

$$\varGamma = \sum_{w\in C} \log P(w|\textrm{context(w)}) \tag{1-6}$$

由于cbow有投影层，则令$X_w = \sum V_u ,u\in \textrm{context}(w)$

基于Hierarchical Softmax

根据公式(1-5)可把式(1-6)写成：

$$\begin{aligned} \varGamma &= \sum_{w\in C} \log \left[ \prod_{j=1}^{\mathcal{l}^{w}-1} \{[1-\sigma(X_{w}^{\top}\theta_j^{w})]^{d_{j+1}^{w}}[\sigma(X_{w}^{\top}\theta_j^{w})]^{1-d_{j+1}^{w}}\}\right]\\ &= \sum_{w\in C}\sum_{j=1}^{\mathcal{l^w}-1} \log\{[1-\sigma(X_{w}^{\top}\theta_j^{w})]^{d_{j+1}^{w}}[\sigma(X_{w}^{\top}\theta_j^{w})]^{1-d_{j+1}^{w}}\} \end{aligned}\tag{1-7}$$

令

$$\begin{aligned} \mathcal{L}(w,j) &=\log\{ [1-\sigma(X_{w}^{\top}\theta_j^{w})]^{d_{j+1}^{w}}[\sigma(X_{w}^{\top}\theta_j^{w})]^{1-d_{j+1}^{w}}\}\\ &=d_{j+1}^w \log[1-\sigma(X_{w}^{\top}\theta_j^{w})]+(1-d_{j+1}^w)\log[\sigma(X_{w}^{\top}\theta_j^{w})] \end{aligned} \tag{1-8}$$

对$\theta_j^w$求导，(参考前面《sigmoid函数》小节):

$$\begin{aligned} \frac{\partial{\mathcal{L}(w,j)}}{\partial{\theta_j^w}} &= \frac{\partial}{\partial{\theta_j^w}} \{d_{j+1}^w \log[1-\sigma(X_{w}^{\top}\theta_j^{w})]+(1-d_{j+1}^w)\log[\sigma(X_{w}^{\top}\theta_j^{w})]\} \\ &= -d_{j+1}^w \sigma(X_w^{\top}\theta_j^w)X_w+(1-d_{j+1})(1-\sigma(X_w^{\top}\theta_j^w))X_w\\ &= [1-d_{j+1}^w-\sigma(X_w^{\top}\theta_j^w)]X_w \end{aligned} \tag{1-9}$$

令学习速率为$\alpha$，则梯度更新公式可写成:

$$\begin{aligned} \theta_{j} &:= \theta_j + \alpha\frac{\partial{\mathcal{L}(w,j)}}{\partial{\theta_j}}\\ &:= \theta_j+\alpha [1-d_{j+1}^w-\sigma(X_w^{\top}\theta_j^w)]X_w \end{aligned}\tag{1-10}$$

由于$X_w$与$\theta_j$对称，则对于$X_w$的求导：

$$\begin{aligned} \frac{\partial{\mathcal{L}(w,j)}}{\partial{X_w}} &= \frac{\partial}{\partial{X_w}}\{d_{j+1}^w \log[1-\sigma(X_{w}^{\top}\theta_j^{w})]+(1-d_{j+1}^w)\log[\sigma(X_{w}^{\top}\theta_j^{w})]\}\\ &= [1-d_{j+1}^w-\sigma(X_w^{\top}\theta_j^w)]\theta_j \end{aligned}\tag{1-11}$$

对于$V_u$参数的梯度更新公式可写成:

$$V_u = V_u +\alpha \sum_{j=1}^{\mathcal{l}^w-1} \frac{\partial{\mathcal{L}(w,j)}}{\partial{X_w}},u\in \textrm{context}(w) \tag{1-12}$$

参数学习过程伪代码

1. e=0
2. $$X_w=\sum_{u\in\textrm{context}(w)}V_u$$
3. for j=1 ->$\mathcal{l}^w$-1:
   1. q = $\sigma(X^{\top}_w\theta_j^w)$
   2. g = $\alpha[1-d_{j+1}^w-q]$
   3. e = e+g$\theta_j^w$
   4. $$\theta_j^w = \theta_j^w+gX_w$$
4. for $u \in \textrm{context}(w)$:
   1. $$V_u = V_u+e$$

基于Negative Sampling

相当于小型的softmax，把维数从字典词语个数V降低到到|Neg(w)|+1。

正样本：词z=w

负样本：词z!=w

令

$$Y_z = \left\{\begin{aligned}1,z=w \\ 0,z\ne w \end{aligned}\right.\tag{1-13}$$

基于Negative Sampling的P(context(w))表示为:

$$P(w) = \prod_{z\in \{\{w\} \cup\textrm{Neg}(w)\}} P(z|\textrm{context}(w)) \tag{1-14}$$ $$P(z|\textrm{context}(w)) = [\sigma(X_w^{\top}\theta^z)]^{Y_z}[1-\sigma(X^{\top}_w\theta^z)]^{1-Y_z} \tag{1-15}$$

此处的$X_w$ 仍然表示各词的词向量之和。

那么目标函数式(1-6)可写成:

$$\begin{aligned} \varGamma &= \sum_{w\in C} \log P(w) \\ &= \sum_{w \in C} \sum_{z\in \{\{w\} \cup\textrm{Neg}(w)\}} \log P(z|\textrm{context}(w))\\ &= \sum_{w \in C} \sum_{z\in \{\{w\} \cup\textrm{Neg}(w)\}}\{\log[\sigma(X_w^{\top}\theta^z)]^{Y_z}[1-\sigma(X^{\top}_w\theta^z)]^{1-Y_z} \}\\ &= \sum_{w \in C} \sum_{z\in \{\{w\} \cup\textrm{Neg}(w)\}}\{(Y_z)\log[\sigma(X_w^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(X^{\top}_w\theta^z)] \}\\ &= \sum_{w\in C}\{\log[\sigma(X_w^{\top}\theta^z)]+\sum_{z\in \textrm{Neg}(w)}\log[1-\sigma(X^{\top}_w\theta^z)]\} \\ \end{aligned} \tag{1-16}$$

令

$$\mathcal{L}(w,z) = (Y_z)\log[\sigma(X_w^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(X^{\top}_w\theta^z)] \tag{1-17}$$

对$\theta^z$求导：

$$\begin{aligned} \frac{\partial{\mathcal{L}(w,z)}}{\partial{\theta^z}} &= \frac{\partial}{\partial{\theta^z}}\{(Y_z)\log[\sigma(X_w^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(X^{\top}_w\theta^z)]\}\\ &= Y_z[1-\sigma(X^{\top}_w\theta^z)]X_w-(1-Y_z)\sigma(X^{\top}_w\theta^z)X_w\\ &= [Y_z-\sigma(X^{\top}_w\theta^z)]X_w \end{aligned}\tag{1-18}$$

对$\theta^z$的梯度更新为：

$$\begin{aligned} \theta^{z} &:= \theta^z +\alpha \frac{\partial{\mathcal{L}(w,z)}}{\partial{\theta^z}} \\ &:= \theta^z + \alpha[Y_z-\sigma(W^{\top}_w\theta^z)]W_w \end{aligned}$$

对$X_w$求导:

$$\frac{\partial{\mathcal{L}(w,z)}}{\partial{X_w}} = [Y_z-\sigma(X_w^{\top}\theta^z)]\theta^z \tag{1-19}$$

对$V_u$的梯度更新公式可写为:

$$V_u = V_u + \alpha \sum_{z\in \{\{w\} \cup\textrm{Neg}(w)\}} \frac{\partial{\mathcal{L}(w,z)}}{\partial{X_w}} ,u \in \textrm{context(w)} \tag{1-20}$$

参数学习过程伪代码

1. e=0
2. $$X_w=\sum_{u \in\textrm{context}(w)}V_u$$
3. For z in {w}$\cup$Neg(w):
   1. q = $\sigma(X^{\top}_w\theta^z)$
   2. g = $\sigma[Y_z-q]$
   3. e = e+g$\theta^z$
   4. $$\theta^z = \theta^z+gX_w$$
4. For u in context(w):
   1. $$V_u=V_u+e$$

skip-gram 模型

对于skip-gram模型而言，已知当前w,求上下文context(w)的概率。

目标函数

$$\varGamma = \sum_{w\in C} \log P(\textrm{context(w)}|w) \tag{1-21}$$ $$P(\textrm{context(w)}|w) = \prod_{u \in \textrm{context}(w)} P(u|w) \tag{1-22}$$

基于层次softmax

$$P(u|w) = \prod_{j=1}^{\mathcal{l}^u-1} P(d_{j+1}^u|V_w,\theta_j^u) \tag{1-23}$$

根据式(1-5)，目标函数可写成：

$$\varGamma = \sum_{w\in C} \sum_{u\in \textrm{context}(w)} \sum_{j=1}^{\mathcal{l^u}-1} \log\{[1-\sigma(V_w^{\top}\theta_j^{u})]^{d_{j+1}^{u}}[\sigma(V_{w}^{\top}\theta_j^{u})]^{1-d_{j+1}^{u}}\} \tag{1-24}$$

令

$$\begin{aligned} \mathcal{L}(w,u,j) &= \log\{[1-\sigma(V_w^{\top}\theta_j^{u})]^{d_{j+1}^{u}}[\sigma(V_{w}^{\top}\theta_j^{u})]^{1-d_{j+1}^{u}}\}\\ &=d_{j+1}^u\log[1-\sigma(V_w^{\top}\theta_j^u)]+(1-d_{j+1}^u)\log[\sigma(V_w^{\top}\theta_j^u)] \end{aligned}\tag{1-25}$$

对$\theta_j^u$求导，

$$\begin{aligned} \frac{\partial{\mathcal{L}(w,u,j)}}{\partial{\theta_{j}^u}} &= \frac{\partial}{\partial{\theta_j^u}}\{d_{j+1}^u\log[1-\sigma(V_w^{\top}\theta_j^u)]+(1-d_{j+1}^u)\log[\sigma(V_w^{\top}\theta_j^u)]\}\\ &= -d_{j+1}^u \sigma(V_w^{\top}\theta^u_j)V_w+(1-d_{j+1}^u)(1-\sigma(V_w^{\top}\theta_j^u))V_w \\ &= [1-d_{j+1}^u-\sigma(V_w^{\top}\theta_{j}^u)]V_w \end{aligned} \tag{1-26}$$

则$\theta_j^u$ 的梯度更新公式表示为:

$$\theta^u_j := \theta^u_j + \alpha[1-d_{j+1}^u-\sigma(V_w^{\top}\theta_j^u)]V_w \tag{1-27}$$

对$V_w$求导，

$$\frac{\partial{\mathcal{L}(w,u,j)}}{\partial{V_w}} = [1-d_{j+1}^u-\sigma(V_w^{\top}\theta_j^u)]\theta_j^u \tag{1-28}$$

则$V_w$的更新公式表示为:

$$V_w:=V_w+\alpha \sum_{u\in \textrm{context}(w)} \sum_{j=1}^{\mathcal{l}^u-1} \frac{\partial{\mathcal{L}(w,u,j)}}{\partial{V_w}} \tag{1-29}$$

参数学习过程伪代码

1. 版本1

   1. e=0

   2. For $u \in \textrm{context}(w)$ :

      1. for j=1 ->$\mathcal{l}^u$-1:
         1. q = $\sigma(V_w^{\top}\theta_j^u)$
         2. g = $\alpha(1-d_{j+1}^u-q)$
         3. e = e+g$\theta_j^u$
         4. $$\theta_j^u = \theta_j^u+gV_w$$
   3. $$V_w = V_w+e$$

1. 版本2(word2vec 源码中的更新规则)

   1. For $u \in \textrm{context}(w)$ :

      1. e=0

      2. for j=1 ->$\mathcal{l}^u$-1:

         1. q = $\sigma(V_w^{\top}\theta_j^u)$
         2. g = $\alpha(1-d_{j+1}^u-q)$
         3. e = e+g$\theta_j^u$
         4. $$\theta_j^u = \theta_j^u+gV_w$$
      3. $$V_w=V_w+e$$

基于Negative Sampling

对于Negative Sampling，式(1-22)可写成：

$$P(u|w) = \prod_{z \in \{u\}\cup\textrm{Neg}(u)} P(z|w) \tag{1-30}$$

根据式(1-13)以及逻辑斯蒂回归二分类器，$P(z|w)$可表示为：

$$P(z|w) = [\sigma(V_w^{\top}\theta^z)]^{Y_z}[1-\sigma(V_w^{\top}\theta^z)]^{1-Y_z} \tag{1-31}$$

根据式(1-21),式(1-22),式(1-30),式(1-31)，最终目标函数表示为:

$$\begin{aligned} \varGamma &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{u\}\cup\textrm{Neg}(u)} \log{P(z|w)}\\ &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{u\}\cup\textrm{Neg}(u)} \log \left\{[\sigma(V_w^{\top}\theta^z)]^{Y_z}[1-\sigma(V_w^{\top}\theta^z)]^{1-Y_z}\right\} \\ &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{u\}\cup\textrm{Neg}(u)}\left\{Y_z\log[\sigma(V_w^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(V_w^{\top}\theta^z)]\right\} \end{aligned} \tag{1-32}$$

式(1-32)表示，对于每一个w的上下文词语u，都进行一次负采样。而在w2v源码中只针对w进行了|context(w)|次负采样。令

$$\begin{aligned} \varGamma &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{u\}\cup\textrm{Neg}(u)} \log{P(z|w)}\\ &= \sum_{w\in C} g(w) \end{aligned}$$

则对于w2v源码中的g(w)与式(1-32)有所不同，其表示为(版本2):

$$g(w) = \sum_{u\in \textrm{context}(w)} \sum_{z\in\{w\}\cup\textrm{Neg}(w)} \log{P(z|u)} \tag{1-33}$$

式(1-33)本质上还是cbow，只是把context(w)拆分，与目标词w组成pair(u,w)。即把式(1-14)写成式(1-33)的形式。

根据式(1-15)，P(z|u)可表示为:

$$P(z|u) = [\sigma(V_u^{\top}\theta^z)]^{Y_z}[1-\sigma(V^{\top}_u\theta^z)]^{1-Y_z} \tag{1-34}$$

结合式(1-33)、式(1-34)，目标函数可写成:

$$\begin{aligned} \varGamma &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{w\}\cup\textrm{Neg}(w)} \log{P(z|u)} \\ &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{w\}\cup\textrm{Neg}(w)}\log \left\{[\sigma(V_u^{\top}\theta^z)]^{Y_z}[1-\sigma(V^{\top}_u\theta^z)]^{1-Y_z}\right\}\\ &= \sum_{w\in C}\sum_{u\in \textrm{context}(w)} \sum_{z\in\{w\}\cup\textrm{Neg}(w)}\left\{(Y_z)\log[\sigma(V_u^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(V_u^{\top}\theta^z)]\right\}\\ \end{aligned}$$

令

$$\mathcal{L}(w,u,z) =(Y_z)\log[\sigma(V_u^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(V_u^{\top}\theta^z)] \tag{1-35}$$

关于$\theta^z$的梯度计算：

$$\begin{aligned} \frac{\partial{\mathcal{L}}}{\partial{\theta^z}} &= \frac{\partial}{\partial{\theta^z}}\{(Y_z)\log[\sigma(V_u^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(V_u^{\top}\theta^z)]\}\\ &= [Y_z-\sigma(V_u^{\top}\theta^z)]V_u \end{aligned}\tag{1-36}$$

于是$\theta^z$的更新公式可写成:

$$\theta^z := \theta^z + \alpha [Y_z-\sigma(V_u^{\top}\theta^z)]V_u \tag{1-37}$$

关于$V_u$的梯度计算：

$$\begin{aligned} \frac{\partial{\mathcal{L}}}{\partial{V_u}} &= \frac{\partial}{\partial{V_u}}\{(Y_z)\log[\sigma(V_u^{\top}\theta^z)]+(1-Y_z)\log[1-\sigma(V_u^{\top}\theta^z)]\}\\ &= [Y_z-\sigma(V_u^{\top}\theta^z)]\theta^z \end{aligned} \tag{1-38}$$

于是$V_u$的更新公式为:

$$V_u := V_u + \alpha \sum_{z\in\{w\}\cup\textrm{Neg}(w)}\frac{\partial{\mathcal{L}}}{\partial{V_u}}$$

参数学习伪代码

• 版本1

  略

• 版本2

  1. For u in context(w) :

     1. e = 0

     2. For z in {w}$\cup$Neg(w):

        1. q = $\sigma(V_u^{\top}\theta^u)$
        2. g = $\alpha(Y_z-q)$
        3. e = e+g$\theta^z$
        4. $$\theta^z =\theta^z+gV_u$$
     3. $$V_u=V_u+e$$

参考资料

• word2vec 中的数学原理详解（一）目录和前言
• word2vec 中的数学原理详解（二）预备知识
• word2vec 中的数学原理详解（三）背景知识
• word2vec 中的数学原理详解（四）基于 Hierarchical Softmax 的模型
• word2vec 中的数学原理详解（五）基于 Negative Sampling 的模型
• word2vec 中的数学原理详解（六）若干源码细节
• word2vec Explained: Deriving Negative-Sampling Word-Embedding Method