Word2Vec

一共有两种模式，以及两种近似训练的方法，个人认为CBOW搭配negative-sampling，以及SkipGram搭配H-softmax，所以以下小节按这个顺序排列。

参考资料：吾爱NLP(5)
有求导实例
https://zhuanlan.zhihu.com/p/53425736
实例计算
https://blog.csdn.net/qq_41664845/article/details/83108222
其他公式推导
https://blog.csdn.net/liuyuemaicha/article/details/52611219

1. CBOW

训练结束后，对于词语 $w^t\in W (|W|=T)$ ，获得其作为中心词和背景词的情况下的两组词向量 $u^t$ 和 $v^t$

中心词使用 $u$ 表示，背景词使用 $v$ 表示。

对于词语 $w^t\in W (|W|=T)$ ，当它作为中心词 $u_t$ 时，它的 $2m$ 个背景词为 $v_{t1}+...+v_{t2m}$ ，取背景词的平均向量。则用这些背景词生成它这个中心词的概率为， $2m$ 个背景词生成它的向量相乘数值 $/$ （ $2m$ 个背景词生成其他词语的向量相乘数值之和），即是
$P(w^t|w^{t-m},...,w^{t-1},w^{t+1},...,w^{t+m})=\frac{ \exp(\mathbf{u_t}^\mathrm{T}(v_{t1}+...+v_{t2m})/(2m) }{ \sum_{j=1}^{V}{\exp(\mathbf{u_j}^\mathrm{T}(v_{t1}+...+v_{t2m})/(2m)} }$
令 $v_t=(v_{t1}+...+v_{t2m})/(2m)$ ，则上式取log后的形式为
$u_t - \log{\sum_{j=1}^{V}{\exp(\mathbf{u_j}^\mathrm{T} v_t}}$

则求整体最大化似然估计
$\prod{i=1}^{V}{P(w^t|w^{t-m},...,w^{t-1},w^{t+1},...,w^{t+m})}$

因为求梯度，除了对应变量外其他数值都可以视为常数，所以 $v_{t1}+...+v_{t2m}=v_{ti}+rest$ ， $rest$ 为其余常数，求梯度时可以不影响结果，则求 $w_t$ 的其中一个背景词 $v_{ti}(i=1,2,...,2m)$ 生成中心词 $u_t$ 的梯度为，
$\frac{\partial{\log{P(w^t|w^{t-m},...,w^{t-1},w^{t+1},...,w^{t+m})}}}{\partial{v_{ti}}} = \frac{1}{2m}( u_t - \frac{ \sum_{k=1}^{V}{u_k \times \exp{u_k(v_{ti}+rest)}} }{ \sum_{j=1}^{V}{\exp{u_j(v_{ti}+rest)}} } )$
这个式子可以进一步写作，
$\frac{\partial{\log{P(w^t|w^{t-m},...,w^{t-1},w^{t+1},...,w^{t+m})}}}{\partial{v_{ti}}} = \frac{1}{2m}( u_t - \sum_{k=1}^{V}{u_k \times P(w_k|w_t)}$

2. Negative Sampling

改进的部分主要考虑词表大小的运算。softmax的运算考虑了背景词是词典中任何一个词的可能（该运算在分母）。

对于CBOW的改进

注意到 $(u_t - \sum_{k=1}^{V}{u_k \times P(w_k|w_t)}$ 中，第二项是考虑了“给定背景词，其生成整个词表中每个词成为中心词”的情况，所以其计算复杂度为 $O(V)$ 。一种缓解的方法是只考虑词表中部分词能成为中心词的情况，例如认为最多只有 $K$ 个词能成为中心词，则计算复杂度则降到 $O(K)$ 。
所以对于之前损失函数需要改变，
之前的损失函数，
$\log{\frac{1}{\exp{(-\mathbf{u_t}^\mathrm{T}v_t/(2m))}}}- \sum_{i=1}^{V}{ \log{\frac{1}{\exp{(\mathbf{u_i}^\mathrm{T}v_t/(2m))}}} }$
之后的损失函数（同时给分母加一防止分母为0，因为采样少数后可能出现0的情况），
$\log{\frac{1}{1+\exp{(-\mathbf{u_t}^\mathrm{T}v_t/(2m))}}}- \sum_{i=1}^{K}{ \log{\frac{1}{1+\exp{(\mathbf{u_i}^\mathrm{T}v_t/(2m))}}} }$
其中 $v_t=v_1+v_2+...+v_2m$

对于Skipgram的改进

其主要更改了中心词生成背景词的条件概率。中心词的生成变成了两个部分（背景词 $w_o$ 和噪声词 $w_k$ ）：

中心词 $w_c$ 和背景词 $w_o$ 同时出现在window中
中心词 $w_c$ 和噪声词 $w_1$ 不同时出现在window中
...
中心词 $w_c$ 和噪声词 $w_K$ 不同时出现在window中

$D=1$ 中心词和背景词同时出现， $D=0$ 中心词和噪声词不同时出现

其中 $\sigma(x)=1/(1+\exp(-x))$ ，即是sigmoid函数，这里用于计算概率

中心词 $u_c$ 与背景词 $v_o$ 同时出现的概率
$P(D=1|w_o,w_c)=\sigma(u_c, v_o)$
同理，加上中心词 $w_c$ 和噪声词(不出现 $w_o$ ， $D=1$ )不同时出现的情况
$P(D=0|w_o,w_c) = \prod_{k=1}^{K}{ \sigma(u_c,v_k) }$
则“中心词生成背景词的条件概率”为
$\log{P(w_o|w_c)}=\log{ P(D=1|w_o,w_c)\prod_{k=1}^{K}{ P(D=0|w_k,w_c) }}$

使用指数表达方式再加上平滑后，
$-logP(w_o|w_c)=-log(frac{1}{ 1+\exp{-\mathbf{u_c}^\mathrm{T} v_o} }) -\sum_{k=1}^{K}{ \log{frac{1}{ 1+\exp{-\mathbf{u_c}^\mathrm{T} v_k} }} }$

3. SkipGram

主要目的为使用一个词来预测它在文本序列周围的词。

对于长度为 $T$ 的一句话，整体最大似然估计
$\prod_{t=1}^{T}{\prod_{-m \leq j \leq m,j \neq 0}{ P(w^{t+i}|w^{t}) }}$

给定任意 $w_t$ 作为中心词 $u_t$ ，产生 $w_i$ 作为背景词 $v_i$ 的概率，使用softmax作为损失函数
$=\frac{ \exp{ \mathbf{u_t}^\mathrm{T}v_i }}{\sum_{j\in V}{ \exp{ \mathbf{u_t}^\mathrm{T}v_j }}}$

4. H-Softmax

整体改变了Softmax的计算方式，复杂度由O(|V|)下降到对应霍夫曼树的高度 $O(\log{|V|})$

判断函数：到达 $w_t$ 路径上第 $j$ 个节点，“它的左子节点” 是否等于 “到达 $w_t$ 路径上第 $j+1$ 个节点”
$I(w_t, j)=([node(w_t, j+1)]==leftchild(node(w_t, j))) = 1 if true else -1$

只考虑路径上的非叶子节点涉及的向量，而不再是把所有词表里的词轮流一遍。
$P(w_t|w_i) = \prod_{j=1}^{L(w_t)-1}{ \sigma (I(w_t, j) \times \mathbf{u_{n(w_t,j)}}^\mathrm{T} v_i) }$
其中 $\sigma(x)=1/(1+\exp(-x))$ ，即是sigmoid函数。

举例计算
需要将 $w_i$ 的词向量 $v_i$ 和根节点到 $w3$ 路径上的非叶子节点向量一一求内积。
在下面的例子中需要向左、向右、再向左遍历。

       n(w3,1)
      /       \
  n(w3,2)      *
   /   \       / \
  *  n(w3,3)      *
 / \    / \        \
w1  w2 w3  w4 ...  w|V|

（这里都是 $u^{T}v$ 相乘）
$P(w_3|w_i)=\sigma(u_{n(w3,1)}v_i) \cdot \sigma(-u_{n(w3,2)}v_i) \cdot \sigma(u_{n(w3,3)}v_i)$
第二个节点因为判断函数为负因为其节点和做子左节点不相同。

Word2Vec语言模型：低维稠密向量