NLP算法（一）- Word2Vec_nlp识别pdf中标题

1 背景

1.1 算法提出

词向量的概念提出之前，将语料库中的单词映射到向量空间的方式是one-hot编码。但one-hot编码的缺陷在于：

1. 无效编码过多，空间利用率极低，后续使用中极大占用内存。
2. 单词之间均为正交关系，与单词在实际使用过程中的规律相背。

因此，我们希望找到某种方法，将单词映射到向量空间中。且希望语义相近的单词对应向量相似度更高，语义无关的单词对应向量相似度更低。
在这一背景下，Word2Vec和Glove两种算法相继被提出，本文将讨论Word2Vec的实现。

1.2 数学基础

适用于解决二分类问题的Sigmoid函数
$$\sigma (x)=\frac{1}{1+e^{-x}}$$

该函数具有如下几个性质
1 − σ ( x ) = σ ( − x ) ( 1.1 ) l o g ′ [ σ ( x ) ] = 1 − σ ( x ) ( 1.2 ) l o g ′ [ 1 − σ ( x ) ] = − σ ( x ) ( 1.3 )

$$\begin{aligned} &1-\sigma(x) = \sigma(-x) \quad &(1.1) \\ &log^{'}[\sigma(x)] = 1-\sigma(x) \quad &(1.2) \\ &log^{'}[1-\sigma(x)] = -\sigma(x) \quad &(1.3) \end{aligned}$$ ​1−σ(x)=σ(−x)log′[σ(x)]=1−σ(x)log′[1−σ(x)]=−σ(x)​(1.1)(1.2)(1.3)​

2 模型

Word2Vec的想法是，认为一篇文档中，在一定范围内位置相邻的单词具有某种关联性。且语义相近的不同单词，其上下文的内容也相近。
因此，

• 通过一单词的上下文预测该中心词可建立模型，即为CBOW。
• 通过一单词预测其上下文可建立模型，即为SkipGram。

2.1 CBOW模型

CBOW(continuous bag-of-words)模型结构如下所示。

用符号 $C$ 表示包含所有文档的语料库，$w$ 表示中心词，$context(w)$表示中心词 $w$ 的上下文，该模型希望最大化
L = ∏ w ∈ C p ( w ∣ c o n t e x t ( w ) ) = ∏ w ∈ C e x p [ p ( w ∣ c o n t e x t ( w ) ] ∑ z ∈ V e x p [ p ( z ∣ c o n t e x t ( w ) ]

$$\begin{aligned} L &= \prod_{w\in{C}} {p(w|context(w))} &= \prod_{w\in{C}} \frac{exp[p(w|context(w)]}{\sum_{z\in{V}}exp[p(z|context(w)]} \end{aligned}$$ L​=w∈C∏​p(w∣context(w))​=w∈C∏​∑z∈V​exp[p(z∣context(w)]exp[p(w∣context(w)]​​

2.1 SkipGram模型

SkipGram模型结构如下所示。

用符号 $C$ 表示包含所有文档的语料库，$w$ 表示中心词，$context(w)$表示中心词 $w$ 的上下文，该模型希望最大化
L = ∏ w ∈ C p ( c o n t e x t ( w ) ∣ w ) = ∏ w ∈ C ∏ u ∈ c o n t e x t ( w ) p ( u ∣ w ) = ∏ w ∈ C ∏ u ∈ c o n t e x t ( w ) e x p [ p ( u ∣ w ) ] ∑ z ∈ V e x p [ p ( z ∣ w ) ]

$$\begin{aligned} L &= \prod_{w\in{C}} {p(context(w)|w)} = \prod_{w\in{C}} \prod_{u\in{context(w)}} p(u|w) \\ &= \prod_{w\in{C}} \prod_{u\in{context(w)}} \frac{exp[p(u|w)]}{\sum_{z\in{V}}exp[p(z|w)]} \end{aligned}$$ L​=w∈C∏​p(context(w)∣w)=w∈C∏​u∈context(w)∏​p(u∣w)=w∈C∏​u∈context(w)∏​∑z∈V​exp[p(z∣w)]exp[p(u∣w)]​​

2.3 算法优化

在模型实际计算中，由于词表往往很大，输出层在计算 ${\sum }_{z\in V}exp[p(z|context(w)]$ 或 ${\sum }_{z\in V}exp[p(z|w)]$ 时，把词表中所有单词的相应概率计算一遍代价过高。因此，需要通过优化提升计算效率。

3 Hierachical霍夫曼编码

通过语料库构建词表，根据各单词词频，可将所有单词通过霍夫曼编码表示，其中每个叶子节点对应词表中的各单词。

3.1 CBOW

CBOW结合霍夫曼树改动后的模型如下所示

在具体介绍该模型算法时，先引入相关记号：

1. $p^w$：从根节点出发，到达w对应叶子节点的路径。
2. $l^w$：路径 $p^w$ 包含节点的个数。
3. $p_{l^0}^w,p_{l^1}^w,\dots ,p_{l^w-1}^w$：路径 $p^w$ 中各节点。其中 $p_{l^0}^w$ 表示根节点，$p_{l^w-1}^w$ 表示单词 $w$ 对应的叶子节点。
4. d 1 w , d 2 w , … , d l w − 1 w ∈ { 0 , 1 } d^w_{1},d^w_{2},\dots,d^w_{l^w-1} \in{\{0,1\}} d1w​,d2w​,…,dlw−1w​∈{0,1}：单词 $w$ 的霍夫曼编码，共 $l^w-1$ 位。$d_j^w$ 表示第 $j$ 位对应编码，树的根节点没有编码。
5. ${\theta }_1^w,{\theta }_2^w,\dots ,{\theta }_{l^w-1}^w$：路径 $p^w$ 中非叶子节点对应向量，${\theta }_{l^w-1}^w$ 即为我们最终需要获得的词向量。

假设 $context(w)$ 对应的词向量为 $x_w$, $p(w|context(w)=f(x_w,{\theta }_j^w)$。
根据霍夫曼树的性质，每个单词 $w$ 必存在唯一一条路径 $p^w$。该路径上存在 $l^w-1$ 个分支，可以将其看成做了 $l^w-1$ 次二分类，每次分类产生一个概率，这些概率的累乘即为最终的 $p(w|context(w)$。

也即
$$p(w|context(w)=\prod _{j=1}^{l^w-1}p(d_j^w|x_w,{\theta }_j^w)$$

利用Sigmoid函数，做出如下假设
p ( d j w ∣ x w , θ j w ) = { σ ( x w T θ j w ) ( d j w = 0 ) 1 − σ ( x w T θ j w ) ( d j w = 1 )

$$\begin{aligned} p(d_j^w|x_w,\theta^w_j) = \left\{ \begin{matrix} &\sigma(x_w^T\theta^w_j) \quad &(d^w_j=0) \\ &1-\sigma(x_w^T\theta^w_j) \quad &(d^w_j=1) \\ \end{matrix} \right. \end{aligned}$$ p(djw​∣xw​,θjw​)={​σ(xwT​θjw​)1−σ(xwT​θjw​)​(djw​=0)(djw​=1)​​

因此，模型的损失函数可写为
L = l o g ∏ w ∈ C ∏ j = 1 l w − 1 [ σ ( x w T θ j w ) ] 1 − d j w ∗ [ 1 − σ ( x w T θ j w ) ] d j w = ∑ w ∈ C ∑ j = 1 l w − 1 ( 1 − d j w ) l o g [ σ ( x w T θ j w ) ] + d j w l o g [ 1 − σ ( x w T θ j w ) ]

$$\begin{aligned} L &= log \prod_{w\in{C}} \prod_{j=1}^{l^w-1} {[\sigma(x_w^T\theta^w_j)]^{1-d^w_j}*[1-\sigma(x_w^T\theta^w_j)]^{d^w_j}} \\ &= \sum_{w\in{C}} \sum_{j=1}^{l^w-1} {(1-d^w_j)log[\sigma(x_w^T\theta^w_j)] + d^w_jlog[1-\sigma(x_w^T\theta^w_j)]} \end{aligned}$$ L​=logw∈C∏​j=1∏lw−1​[σ(xwT​θjw​)]1−djw​∗[1−σ(xwT​θjw​)]djw​=w∈C∑​j=1∑lw−1​(1−djw​)log[σ(xwT​θjw​)]+djw​log[1−σ(xwT​θjw​)]​

上式中各变量均相互独立，记
$$L(x_w,{\theta }_j^w)=(1-d_j^w)log[\sigma (x_w^T{\theta }_j^w)]+d_j^{w}log[1-\sigma (x_w^T{\theta }_j^w)]$$

分别对 $x_w,{\theta }_j^w$ 求导，并利用Sigmoid函数求导时的性质
∇ θ j w L ( x w , θ j w ) = ( 1 − d j w ) [ 1 − σ ( x w T θ j w ) ] x w − d j w σ ( x w T θ j w ) x w = [ 1 − d j w − σ ( x w T θ j w ) ] x w

$$\begin{aligned} \nabla_{\theta^w_j}L(x_w,\theta^w_j) &= (1-d^w_j)[1-\sigma(x_w^T\theta^w_j)]x_w - d^w_j\sigma(x_w^T\theta^w_j)x_w \\ &= [1-d^w_j-\sigma(x_w^T\theta^w_j)]x_w \end{aligned}$$ ∇θjw​​L(xw​,θjw​)​=(1−djw​)[1−σ(xwT​θjw​)]xw​−djw​σ(xwT​θjw​)xw​=[1−djw​−σ(xwT​θjw​)]xw​​

∇ x w L ( x w , θ j w ) = ( 1 − d j w ) [ 1 − σ ( x w T θ j w ) ] θ j w − d j w σ ( x w T θ j w ) θ j w = [ 1 − d j w − σ ( x w T θ j w ) ] θ j w

$$\begin{aligned} \nabla_{x_w}L(x_w,\theta^w_j) &= (1-d^w_j)[1-\sigma(x_w^T\theta^w_j)]\theta^w_j - d^w_j\sigma(x_w^T\theta^w_j)\theta^w_j \\ &= [1-d^w_j-\sigma(x_w^T\theta^w_j)]\theta^w_j \end{aligned}$$ ∇xw​​L(xw​,θjw​)​=(1−djw​)[1−σ(xwT​θjw​)]θjw​−djw​σ(xwT​θjw​)θjw​=[1−djw​−σ(xwT​θjw​)]θjw​​

之后通过梯度上升法更新相应参数即可， ${\theta }_{l^w-1}^w$ 即为最终需要获得的词向量。

3.2 SkipGram

SkipGram结合霍夫曼树改动后的模型如下所示

该方法的思路与CBOW完全一样，只因模型结构略有不同，通过霍夫曼树表示的概率变为 $p(u|w)$。
其计算方法与之前类似，将路径上各节点的概率累乘
p ( u ∣ w ) = ∏ j = 1 l u − 1 p ( d j u ∣ v ( w ) , θ j u ) = ∏ j = 1 l u − 1 [ σ ( v ( w ) T θ j u ) ] 1 − d j u ∗ [ 1 − σ ( v ( w ) T θ j u ) ] d j u

$$\begin{aligned} p(u|w) &= \prod_{j=1}^{l^u-1} {p(d^u_j|v(w),\theta^u_j)} \\ &= \prod_{j=1}^{l^u-1} {[\sigma(v(w)^T\theta^u_j)]^{1-d^u_j}*[1-\sigma(v(w)^T\theta^u_j)]^{d^u_j}} \end{aligned}$$ p(u∣w)​=j=1∏lu−1​p(dju​∣v(w),θju​)=j=1∏lu−1​[σ(v(w)Tθju​)]1−dju​∗[1−σ(v(w)Tθju​)]dju​​

模型损失函数可写为
L = l o g ∏ w ∈ C ∏ u ∈ c o n t e x t ( w ) ∏ j = 1 l u − 1 [ σ ( v ( w ) T θ j u ) ] 1 − d j u ∗ [ 1 − σ ( v ( w ) T θ j u ) ] d j u = ∑ w ∈ C ∑ u ∈ c o n t e x t ( w ) ∑ j = 1 l u − 1 ( 1 − d j u ) l o g [ σ ( v ( w ) T θ j u ) ] + d j u l o g [ 1 − σ ( v ( w ) T θ j u ) ]

$$\begin{aligned} L &= log \prod_{w\in{C}} \prod_{u\in{context(w)}} \prod_{j=1}^{l^u-1} {[\sigma(v(w)^T\theta^u_j)]^{1-d^u_j}*[1-\sigma(v(w)^T\theta^u_j)]^{d^u_j}} \\ &= \sum_{w\in{C}} \sum_{u\in{context(w)}} \sum_{j=1}^{l^u-1} {(1-d^u_j)log[\sigma(v(w)^T\theta^u_j)] + d^u_jlog[1-\sigma(v(w)^T\theta^u_j)]} \end{aligned}$$ L​=logw∈C∏​u∈context(w)∏​j=1∏lu−1​[σ(v(w)Tθju​)]1−dju​∗[1−σ(v(w)Tθju​)]dju​=w∈C∑​u∈context(w)∑​j=1∑lu−1​(1−dju​)log[σ(v(w)Tθju​)]+dju​log[1−σ(v(w)Tθju​)]​

记
$$L(v(w),{\theta }_j^u)=(1-d_j^u)log[\sigma (v(w{)}^T{\theta }_j^u)]+d_j^{u}log[1-\sigma (v(w{)}^T{\theta }_j^u)]$$

分别对 $v(w),{\theta }_j^u$ 求导
$${\nabla }_{{\theta }_j^u}L(v(w),{\theta }_j^u)=[1-d_j^u-\sigma (v(w{)}^T{\theta }_j^u)]v(w)$$

$${\nabla }_{v(w)}L(v(w),{\theta }_j^u)=[1-d_j^u-\sigma (v(w{)}^T{\theta }_j^u)]{\theta }_j^u$$

之后通过梯度上升法更新相应参数即可， ${\theta }_{l^w-1}^w$ 即为最终需要获得的词向量。

4 负采样

除了利用霍夫曼编码的性质优化计算，还可利用负采样方式简化计算。

4.1 负样本

该方法的本质是利用已知概率密度函数预测未知的概率密度函数。

1. CBOW模型中，对于给定的上下文 $context(w)$，将中心词 $w$ 看成是一个正样本，其他单词为负样本。
2. SkipGram模型中，对于给定的中心词 $w$，将 $context(w)$ 中的所有单词看成正样本，其他单词为负样本。

为了拟合 $p(w|context(w))$ 或 $p(context(w)|w)$，以语料库中各单词词频为权重，做带权重的随机采样，取出 $K$ 个负样本。

4.2 CBOW

在CBOW模型中，通过正样本和负样本的结合，拟合
$$\frac{exp[p(w|context(w)]}{{\sum }_{z\in V}exp[p(z|context(w)]}\approx p(w|context(w))\prod _{u\in NEG(w)}p(u|context(w))$$

记单词 $w$ 对应的词向量为 ${\theta }_w$，上下文对应向量为 $x_w$
p ( u ∣ c o n t e x t ( w ) ) = { σ ( x w T θ u ) ( u = w ) 1 − σ ( x w T θ u ) ( u ≠ w ) = [ σ ( x w T θ u ) ] δ ( u − w ) [ 1 − σ ( x w T θ u ) ] 1 − δ ( u − w )

$$\begin{aligned} p(u|context(w)) &= \left\{ \begin{matrix} &\sigma(x^T_w\theta_u) &\quad (u=w) \\ &1-\sigma(x^T_w\theta_u) &\quad (u\neq w) \end{matrix} \right. \\ &= [\sigma(x^T_w\theta_u)]^{\delta(u-w)}[1-\sigma(x^T_w\theta_u)]^{1-\delta(u-w)} \end{aligned}$$ p(u∣context(w))​={​σ(xwT​θu​)1−σ(xwT​θu​)​(u=w)(u​=w)​=[σ(xwT​θu​)]δ(u−w)[1−σ(xwT​θu​)]1−δ(u−w)​

由此可得模型的损失函数
L = l o g ∏ w ∈ C ∏ u ∈ { w , N E G ( w ) } [ σ ( x w T θ u ) ] δ ( u − w ) [ 1 − σ ( x w T θ u ) ] 1 − δ ( u − w ) = ∑ w ∈ C ∑ u ∈ { w , N E G ( w ) } δ ( u − w ) l o g [ σ ( x w T θ u ) ] + [ 1 − δ ( u − w ) ] l o g [ 1 − σ ( x w T θ u ) ]

$$\begin{aligned} L &= log \prod_{w\in{C}} \prod_{u\in{\{w,NEG(w)\}}} [\sigma(x^T_w\theta_u)]^{\delta(u-w)}[1-\sigma(x^T_w\theta_u)]^{1-\delta(u-w)} \\ &= \sum_{w\in{C}} \sum_{u\in{\{w,NEG(w)\}}} \delta(u-w)log[\sigma(x^T_w\theta_u)] + [1-\delta(u-w)]log[1-\sigma(x^T_w\theta_u)] \end{aligned}$$ L​=logw∈C∏​u∈{w,NEG(w)}∏​[σ(xwT​θu​)]δ(u−w)[1−σ(xwT​θu​)]1−δ(u−w)=w∈C∑​u∈{w,NEG(w)}∑​δ(u−w)log[σ(xwT​θu​)]+[1−δ(u−w)]log[1−σ(xwT​θu​)]​

定义
$$L(x_w,{\theta }_u)=\delta (u-w)log[\sigma (x_w^T{\theta }_u)]+[1-\delta (u-w)]log[1-\sigma (x_w^T{\theta }_u)]$$

分别对 $x_w,{\theta }_u$ 求导
∇ θ u L ( x w , θ u ) = δ ( u − w ) [ 1 − σ ( x w T θ u ) ] x w − [ 1 − δ ( u − w ) ] σ ( x w T θ u ) x w = [ δ ( u − w ) − σ ( x w T θ u ) ] x w

$$\begin{aligned} \nabla_{\theta_u}L(x_w,\theta_u) &= \delta(u-w)[1-\sigma(x^T_w\theta_u)]x_w- [1-\delta(u-w)]\sigma(x^T_w\theta_u)x_w \\ &= [\delta(u-w)- \sigma(x^T_w\theta_u)]x_w \end{aligned}$$ ∇θu​​L(xw​,θu​)​=δ(u−w)[1−σ(xwT​θu​)]xw​−[1−δ(u−w)]σ(xwT​θu​)xw​=[δ(u−w)−σ(xwT​θu​)]xw​​

∇ x w L ( x w , θ u ) = δ ( u − w ) [ 1 − σ ( x w T θ u ) ] θ u − [ 1 − δ ( u − w ) ] σ ( x w T θ u ) θ u = [ δ ( u − w ) − σ ( x w T θ u ) ] θ u

$$\begin{aligned} \nabla_{x_w}L(x_w,\theta_u) &= \delta(u-w)[1-\sigma(x^T_w\theta_u)]\theta_u- [1-\delta(u-w)]\sigma(x^T_w\theta_u)\theta_u \\ &= [\delta(u-w)- \sigma(x^T_w\theta_u)]\theta_u \end{aligned}$$ ∇xw​​L(xw​,θu​)​=δ(u−w)[1−σ(xwT​θu​)]θu​−[1−δ(u−w)]σ(xwT​θu​)θu​=[δ(u−w)−σ(xwT​θu​)]θu​​

之后通过梯度上升法更新相应参数即可， ${\theta }_w$ 即为最终需要获得的词向量。

4.3 SkipGram

在SkipGram模型中，通过正样本和负样本的结合，拟合
$$\frac{exp[p(u|w)]}{{\sum }_{z\in V}exp[p(z|w)]}\approx p(v(z)|w)\prod _{z\in NEG(context(w))}p(v(z)|w)$$

记中心词 $w$ 对应的词向量为 ${\theta }_w$，在上下文中的单词 $z$ 对应向量为 $v(w)$
p ( v ( z ) ∣ w ) = { σ ( v ( z ) T θ w ) ( z = w ) 1 − σ ( v ( z ) T θ w ) ( z ≠ w ) = [ σ ( v ( z ) T θ w ) ] δ ( z − w ) [ 1 − σ ( v ( z ) T θ w ) ] 1 − δ ( z − w )

$$\begin{aligned} p(v(z)|w) &= \left\{ \begin{matrix} &\sigma(v(z)^T\theta_w) &\quad (z=w) \\ &1-\sigma(v(z)^T\theta_w) &\quad (z\neq w) \end{matrix} \right. \\ &= [\sigma(v(z)^T\theta_w)]^{\delta(z-w)} [1-\sigma(v(z)^T\theta_w)]^{1-\delta(z-w)} \end{aligned}$$ p(v(z)∣w)​={​σ(v(z)Tθw​)1−σ(v(z)Tθw​)​(z=w)(z​=w)​=[σ(v(z)Tθw​)]δ(z−w)[1−σ(v(z)Tθw​)]1−δ(z−w)​

由此可得模型的损失函数
L = l o g ∏ w ∈ C ∏ u ∈ c o n t e x t ( w ) ∏ z ∈ { w , N E G ( c o n t e x t ( w ) ) } [ σ ( v ( z ) T θ w ) ] δ ( z − w ) [ 1 − σ ( v ( z ) T θ w ) ] 1 − δ ( z − w ) = ∑ w ∈ C ∑ u ∈ c o n t e x t ( w ) ∑ z ∈ { w , N E G ( c o n t e x t ( w ) ) } δ ( z − w ) l o g [ σ ( v ( z ) T θ w ) ] + [ 1 − δ ( z − w ) ] l o g [ 1 − σ ( v ( z ) T θ w ) ]

$$\begin{aligned} L &= log \prod_{w\in{C}} \prod_{u\in{context(w)}} \prod_{z\in{\{w,NEG(context(w))\}}} [\sigma(v(z)^T\theta_w)]^{\delta(z-w)} [1-\sigma(v(z)^T\theta_w)]^{1-\delta(z-w)} \\ &= \sum_{w\in{C}} \sum_{u\in{context(w)}} \sum_{z\in{\{w,NEG(context(w))\}}} \delta(z-w)log[\sigma(v(z)^T\theta_w)] + [1-\delta(z-w)]log[1-\sigma(v(z)^T\theta_w)] \end{aligned}$$ L​=logw∈C∏​u∈context(w)∏​z∈{w,NEG(context(w))}∏​[σ(v(z)Tθw​)]δ(z−w)[1−σ(v(z)Tθw​)]1−δ(z−w)=w∈C∑​u∈context(w)∑​z∈{w,NEG(context(w))}∑​δ(z−w)log[σ(v(z)Tθw​)]+[1−δ(z−w)]log[1−σ(v(z)Tθw​)]​

定义
$$L(v(z),{\theta }_w)=\delta (z-w)log[\sigma (v(z{)}^T{\theta }_w)]+[1-\delta (z-w)]log[1-\sigma (v(z{)}^T{\theta }_w)]$$

分别对 $v(z),{\theta }_w$ 求导
∇ θ w L ( v ( z ) , θ w ) = δ ( z − w ) [ 1 − σ ( v ( z ) T θ w ) ] v ( z ) − [ 1 − δ ( z − w ) ] σ ( v ( z ) T θ w ) v ( z ) = [ δ ( z − w ) − σ ( v ( z ) T θ w ) ] v ( z )

$$\begin{aligned} \nabla_{\theta_w}L(v(z), \theta_w) &= \delta(z-w)[1-\sigma(v(z)^T\theta_w)]v(z)- [1-\delta(z-w)]\sigma(v(z)^T\theta_w)v(z) \\ &= [\delta(z-w)- \sigma(v(z)^T\theta_w)]v(z) \end{aligned}$$ ∇θw​​L(v(z),θw​)​=δ(z−w)[1−σ(v(z)Tθw​)]v(z)−[1−δ(z−w)]σ(v(z)Tθw​)v(z)=[δ(z−w)−σ(v(z)Tθw​)]v(z)​

∇ v ( z ) L ( v ( z ) , θ w ) = δ ( z − w ) [ 1 − σ ( v ( z ) T θ w ) ] θ w − [ 1 − δ ( z − w ) ] σ ( v ( z ) T θ w ) θ w = [ δ ( z − w ) − σ ( v ( z ) T θ w ) ] θ w

$$\begin{aligned} \nabla_{v(z)}L(v(z),\theta_w) &= \delta(z-w)[1-\sigma(v(z)^T\theta_w)]\theta_w- [1-\delta(z-w)]\sigma(v(z)^T\theta_w)\theta_w \\ &= [\delta(z-w)- \sigma(v(z)^T\theta_w)]\theta_w \end{aligned}$$ ∇v(z)​L(v(z),θw​)​=δ(z−w)[1−σ(v(z)Tθw​)]θw​−[1−δ(z−w)]σ(v(z)Tθw​)θw​=[δ(z−w)−σ(v(z)Tθw​)]θw​​

之后通过梯度上升法更新相应参数即可， ${\theta }_w$ 即为最终需要获得的词向量。