Word2Vec模型总结

Huffman树的构造
解析：给定n个权值作为n个叶子节点，构造一棵二叉树，若它的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称Huffman树。数的带权路径长度规定为所有叶子节点的带权路径长度之和。Huffman树构造，如下所示：
（1）将{w1,w2,...,w3}看成是有n颗树的森林；
（2）在森林中选出两个根节点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根节点权值为其左、右子树根节点权值之和；
（3）从森林中删除选取的两颗树，并将新树加入森林；
（4）重复（2）（3）步，直到森林中只剩一棵树为止，该树即为所求的Huffman树。
说明：利用Huffman树设计的二进制前缀编码，称为Huffman编码，它既能满足前缀编码条件，又能保证报文编码总长最短。
基于Hierarchical Softmax的模型（CBOW模型）
解析：

其中参数的物理意义，如下所示：
（1）Xw=∑i=12cv(Context(w)i)∈Rm
（2）dwj表示路径pw中第j结点对应的编码（根结点不对应编码）
（3）θwj表示路径pw中第j非叶子结点对应的向量
（4）pw表示从根结点出发到达w对应叶子结点的路径。
（5）lw表示路径pw中包含结点的个数。
Hierarchical Softmax基本思想，如下所示：
$p (w | C o n t e x t (w)) = \prod j = 2 l w p (d w j | x w, θ w j - 1)$
$p (d w j | x w, θ w j - 1) = [σ (x T w θ w j - 1)] 1 - d w j \cdot [1 - σ (x T w θ w j - 1)] d w j$
对于word2vec中基于Hierarchical Softmax的CBOW模型，优化的目标函数，如下所示：
$L = \sum w \in C log p (w | C o n t e x t (w))$
这样得到对数似然函数，如下所示：
$L = \sum w \in C log \prod j = 2 l w {[σ (x T w θ w j - 1)] 1 - d w j \cdot [1 - σ (x T w θ w j - 1)] d w j} = \sum w \in C \sum j = 2 l w {(1 - d w j) \cdot log [σ (x T w θ w j - 1)] + d w j \cdot log [1 - σ (x T w θ w j - 1)]}$
将花括号中的内容简记为L(w,j)，如下所示：
$L (w, j) = (1 - d w j) \cdot log [σ (x T w θ w j - 1)] + d w j \cdot log [1 - σ (x T w θ w j - 1)]$
使用随机梯度上升法对θwj−1求偏导，如下所示：
$\partial L (w, j) \partial θ w j - 1 = \partial \partial θ w j - 1 {(1 - d w j) \cdot log [σ (x T w θ w j - 1)] + d w j \cdot log [1 - σ (x T w θ w j - 1)]} = (1 - d w j) \cdot [1 - σ (x T w θ w j - 1)] x w - d w j \cdot σ (x T w θ w j - 1) x w = {(1 - d w j) \cdot [1 - σ (x T w θ w j - 1)] - d w j \cdot σ (x T w θ w j - 1)} x w = [1 - d w j - σ (x T w θ w j - 1)] x w$
θwj−1的更新方程，如下所示：
$θ w j - 1 : = θ w j - 1 + η [1 - d w j - σ (x T w θ w j - 1)] x w$
使用随机梯度上升法对xw求偏导，如下所示：
$\partial L (w, j) \partial x w = [1 - d w j - σ (x T w θ w j - 1)] θ w j - 1$
对于词典中每个词的词向量v(w~)更新方程，如下所示：
$v (w ~) : = v (w ~) + η \sum j = 2 l w \partial L (w, j) \partial x w, w ~ \in C o n t e x t (w)$
基于Hierarchical Softmax的模型（Skip-Gram模型）
解析：

其中，v(w)∈Rm表示当前样本的中心词w的词向量。
对于word2vec中基于Hierarchical Softmax的Skip-Gram模型，优化的目标函数，如下所示：
$L = \sum w \in C log p (C o n t e x t (w) | w)$
Skip-Gram模型中条件概率函数p(Context(w)|w)，如下所示：
$p (C o n t e x t (w) | w) = \prod u \in C o n t e x t (w) p (u | w)$
$p (u | w) = \prod j = 2 l u p (d u j | v (w), θ u j - 1)$
$p (d u j | v (w), θ u j - 1) = [σ (v (w) T θ u j - 1)] 1 - d u j \cdot [1 - σ (v (w) T θ u j - 1)] d u j$
这样得到对数似然函数，如下所示：
$L = \sum w \in C log \prod u \in C o n t e x t (w) \prod j = 2 l u {[σ (v (w) T θ u j - 1)] 1 - d u j \cdot [1 - σ (v (w) T θ u j - 1)] d u j} = \sum w \in C \sum u \in C o n t e x t (w) \sum i = 2 l u {(1 - d u j) \cdot log [σ (v (w) T θ u j - 1)] + d u j \cdot log [1 - σ (v (w) T θ u j - 1)]}$
将花括号中的内容简记为L(w,u,j)，如下所示：
$L (w, u, j) = (1 - d u j) \cdot log [σ (v (w) T θ u j - 1)] + d u j \cdot log [1 - σ (v (w) T θ u j - 1)]$
基于Negative Sampling的模型（CBOW模型）
Negative Sampling不再使用Huffman树，而是使用随机负采样，能大幅度提高性能。假定已经选好w的负样本子集NEG(w)≠∅，定义词w~的标签（正样本为1，负样本为0），如下所示：
$L w (w ~) = {1, w ~ = w 0, w ~ \neq w$
对于给定的正样本(Context(w),w)，最大化g(w)，如下所示：
$g (w) = \prod u \in {w} \cup N E G (w) p (u | C o n t e x t (w))$
$p (u | C o n t e x t (w)) = [σ (x T w θ u)] L w (u) \cdot [1 - σ (x T w θ u)] [1 - L w (u)]$
其中，xw表示Context(w)中各词的词向量之和，θu∈Rm表示词u对应的一个辅助向量，为待训练的参数。简化g(w)方程，如下所示：
$g (w) = σ (x T w θ w) \prod u \in N E G (w) [1 - σ (x T w θ u)]$
其中，σ(xTwθw)表示当上下文为Context(w)时，预测中心词为w的概率，同样σ(xTwθu),u∈NEG(w)表示当上下文为Context(w)时，预测中心词为u的概率。
对于给定的语料库C，目标函数如下所示：
$L = log G = log \prod w \in C g (w) = \sum w \in C log g (w) = \sum w \in C log \prod u \in {w} \cup N E G (w) {[σ (x T w θ u)] L w (u) \cdot [1 - σ (x T w θ u)] 1 - L w (u)} = \sum w \in C \sum u \in {w} \cup N E G (w) {L w (u) \cdot log [σ (x T w θ u)] + [1 - L w (u)] \cdot log [1 - σ (x T w θ u)]} = \sum w \in C ⎧ ⎩ ⎨ log [σ (x T w θ w)] + \sum u \in N E G (w) log [1 - σ (x T w θ u)] ⎫ ⎭ ⎬ = \sum w \in C ⎧ ⎩ ⎨ log [σ (x T w θ w)] + \sum u \in N E G (w) log [σ (- x T w θ u)] ⎫ ⎭ ⎬$
记L(w,u)=Lw(u)⋅log[σ(xTwθu)]+[1−Lw(u)]⋅log[1−σ(xTwθu)]，使用随机梯度上升法对θu求偏导，如下所示：
$\partial L (w, u) \partial θ u = \partial \partial θ u {L w (u) \cdot log [σ (x T w θ u)] + [1 - L w (u)] \cdot log [1 - σ (x T w θ u)]} = L w (u) [1 - σ (x T w θ u)] x w - [1 - L w (u)] σ (x T w θ u) x w = {L w (u) [1 - σ (x T w θ u)] - [1 - L w (u)] σ (x T w θ u)} x w = [L w (u) - σ (x T w θ u)] x w$
参数θu的更新方程，如下所示：
$θ u : = θ u + η [L w (u) - σ (x T w θ u)] x w$
使用随机梯度上升法对xw求偏导，如下所示：
$\partial L (w, u) \partial x w = [L w (u) - σ (x T w θ u)] θ u$
参数v(w~),w~∈Context(w)的更新方程，如下所示：
$v (w ~) : = v (w ~) + η \sum u \in {w} \cup N E G (w) \partial L (w, u) \partial x w, w ~ \in C o n t e x t (w)$
基于Negative Sampling的模型（Skip-Gram模型）
对于给定的语料库C，目标函数如下所示：
$G = \prod w \in C \prod u \in C o n t e x t (w) g (u)$
$g (u) = \prod z \in {u} \cup N E G {u} p (z | w)$
$p (z | w) = [σ (v (w) T θ z)] L u (z) \cdot [1 - σ (v (w) T θ z)] 1 - L u (z)$
$L = log G = log \prod w \in C \prod u \in C o n t e x t (w) g (u) = \sum w \in C \sum u \in C o n t e x t (w) log g (u) = \sum w \in C \sum u \in C o n t e x t (w) log \prod z \in {u} \cup N E G {u} p (z | w) = \sum w \in C \sum u \in C o n t e x t (w) \sum z \in {u} \cup N E G {u} log {[σ (v (w) T θ z)] L u (z) \cdot [1 - σ (v (w) T θ z)] 1 - L u (z)} = \sum w \in C \sum u \in C o n t e x t (w) \sum z \in {u} \cup N E G {u} {L u (z) \cdot log [σ (v (w) T θ z)] + [1 - L u (z)] \cdot log [1 - σ (v (w) T θ z)]}$
对每一个样本(w,Context(w))，需要针对Context(w)中的每一个词进行负采样，但是word2vec源码中只是针对w进行了|Context(w)|次负采样。它本质上用的还是CBOW模型，只是将原来通过求和累加做整体用的上下文Context(w)拆成一个一个来考虑。对于给定的语料库C，目标函数如下所示：
$g (w) = \prod w ~ \in C o n t e x t (w) \prod u \in {w} \cup N E G w ~ (w) p (u | w ~)$
$p (u | w ~) = [σ (v (w ~) T θ u)] L w (u) \cdot [1 - σ (v (w ~) T θ u)] 1 - L w (u)$
$L = log G = log \prod w \in C g (w) = \sum w \in C log g (w) = \sum w \in C log \prod w ~ \in C o n t e x t (w) \prod u \in {w} \cup N E G w ~ (w) {[σ (v () T θ u)] L w (u) \cdot [1 - σ (v () T θ u)] 1 - L w (u)} = \sum w \in C log \sum w ~ \in C o n t e x t (w) \sum u \in {w} \cup N E G w ~ (w) {L w (u) \cdot log [σ (v (w ~) T θ u)] + [1 - L w (u)] \cdot log [1 - σ (v (w ~) T θ u)]}$
记L(w,w~,u)=Lw(u)⋅log[σ(v(w~)Tθu)]+[1−Lw(u)]⋅log[1−σ(v(w~)Tθu)]。使用随机梯度上升法，对θu求偏导，如下所示：
$\partial L (w, w ~, u) \partial θ u = \partial L \partial θ u {L w (u) \cdot log [σ (v (w ~) T θ u)] + [1 - L w (u)] \cdot log [1 - σ (v (w ~) T θ u)]} = L w (u) [1 - σ (v (w ~) T θ u)] v (w ~) - [1 - L w (u)] σ (v (w ~) T θ u) v (w ~) = {L w (u) [1 - σ (v (w ~) T θ u)] - [1 - L w (u)] σ (v (w ~) T θ u)} v (w ~) = [L w (u) - σ (v (w ~) T θ u)] v (w ~)$
θu的更新方程，如下所示：
$θ u : = θ u + η [L w (u) - σ (v (w ~) T θ u)] v (w ~)$
使用随机梯度上升法，对v(w~)求偏导，如下所示：
$\partial L (w, w ~, u) \partial v (w ~) = [L w (u) - σ (v (w ~) T θ u)] θ u$
参数v(w~)的更新，如下所示：
$v (w ~) : = v (w ~) + η \sum u \in {w} \cup N E G w ~ (w) \partial L (w, w ~, u) \partial v (w ~)$
其中，NEGw~(w)表示处理词w~时生成的负样本子集。
Negative Sampling算法
（1）带权采样原理
设词典D中的每一个词w对应一个线段l(w)，长度如下所示：
$l e n (w) = c o u n t e r (w) \sum u \in D c o u n t e r (u)$
这里counter(⋅)表示一个词在语料C中出现的次数。现在将这些线段首尾相连地拼接在一起，形成一个长度为1的单位线段。如果随机地往这个单位线段上打点，那么其中长度越长的线段（对应高频词）被打中的概率就越大。
（2）word2vec负采样
记l0=0，lk=∑j=1klen(wj),k=1,2,⋯,N，这里wj表示词典D中第j个词，则以{lj}Nj=0为剖分结点可得到区间[0,1]上的一个非等距剖分，Ii=(li−1,li],i=1,2,⋯,N为其N个剖分区间。进一步引入区间[0,1]上的一个等距离剖分，剖分结点为{mj}Mj=0，其中M≫N，具体示意图如下所示：

将内部剖分结点{mj}M−1j=1投影到非等距剖分上，则可建立{mj}M−1j=1与区间{Ij}Nj=1（或{wj}Nj=1）的映射关系，如下所示：
$T a b l e (i) = w k, m i \in I k, i = 1, 2, \dots, M - 1$
根据映射每次生成一个[1,M−1]间的随机整数r，Table(r)就是一个样本。当对wi进行负采样时，如果采样为wi，那么就跳过去。

参考文献：
[1] word2vec中的数学原理详解

相关推荐