语言模型简介（Language Model）
简单的说，语言模型 （Language Model） 是用来计算一个句子出现概率的模型，假设句子 
其中 , $p(w_n|w_1^{n-1}) = p(w_n|w_1,w_2,...,w_{n-1})$ , $ p(w_n|w_1^{n-1})$ 即为 Language Model 的参数，。通常参数的求解用方法是 N-gram 模型，最大熵模型，HMM,CRF 以及本文将重点讲述的 Neural Network Lauguage Model ，对于 N-gram 中的 $ p(w_n|w_1^{n-1})$ 是这样计算的，先引入大小为 
, 这样就大大简化了计算，k 即为 N-Gram 中的 N，比如 K = 2 ，有
这里还有一些平滑的技巧，比如 
神经网络语言模型（Neural Network Lauguage Model，NNLM）
神经网络语言模型（以下简称 NNLM ）正式由 Bengio 与于 2003 年提出，他也是用于计算 
的一种模型(该模型同样假设语料库中词语只与前 k 个相关)，这里为了便于表示, 另 $context(w_n) = w_{n-k+1}^{n-1}$ ，便可以得到给定词语 $w$ 在当前上下文中出现的概率为 
以上公式何解呢？就是假设语料库 $C$ 是按照 $F(w,context(w),\theta)$ 生成的 , 现在 $C$ 已经在那里了，但参数 $\theta^*$ 还不知道，很简单的 MLE 的思想就可解决了，此处 $R(\theta)$ 是引入 $\theta$ 的先验信息来构造成 MAP ，也可以叫做正则化，但是 NNLM 里是没有引入任何先验信息的，所以这里不考虑 $R(\theta)$ ,Bengio 提出的 NNLM 就长下边的那个样子
很复杂的图，其实 idea 并不复杂，来看 NNLM 构造 ,首先，引入了词向量的概念，即将词表中的词语 
假设输入为词语 $w$ ,其上下文 $context(w)$ 拼接成一个输入 $\mathbf{x}_w$ ,在 NN 中的计算如下所示：
最后得到的向量 
此处，
该 log 似然可以用梯度上升法来求解，具体这里不涉及了。参数求解完后，便得到了我们的语言模型，现在估计一个现实任务中的词语
NNLM 的副产品词向量也包含了丰富的信息，因为每个词语都被表示为长度为 
基于 Hierarchical Softmax 的模型
1）Continuous Bag-of-Words Model CBOW
CBOW 是在给定当前词 
语言模型还是那个问题，映射函数的构造，这里根据任务不同 CBOW 需要构造的是 
CBOW 的任务是给定词 $w_t$ ，预测其上下文
Input Layer
输入为词语 
Projection Layer
将 
Output Layer
这里的输出层不再是 NNLM 中的 softmax 了，而改为了 Huffman 树结构，该树是通过统计词表 V 的词语构建的，通过统计预料 C 中的词语的词频，来构建这颗 Huffman 树，根据 Huffman 数的性质，词频大的词语所处的层数一般会很浅，树中的每个叶节点均代表一个词表 V 中的词语。可见共有 |V| 个叶节点，且叶节点的顺序为左大右小。
CBOW这种层次的设计很大程度提高了网络的效率，但输出层树形结构的设计也导致了前向传导计算
上边的符号太多，用一个例子来说明，设当前的词表 V 为 {我，喜欢，观看，巴西，足球，世界杯} ，在语料库 C 中统计的词频分别为 {15，8，6 ，5，3，1} ，构建的 Huffman 树如下图所示：（注意建树时词频大的当做左子树，词频小的当做右子树，且编码为左 1 右 0）。
若当前的词语 
当输入词语 
分到负类的概率自然为：
注意 
，最终通过不断二分类向下传导到词语 $w$ 对应的叶节点，词语
其中：
写到一起有 $p(d_i^w|\mathbf{x}_w,\theta_{i-1}^w) = \left [\sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w)^{1-d_i^w} \right ] \cdot\left [(1-\sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) ^{d_i^w}\right]$，现在就可以进行最后的 MLE 了，列出语料库中的所有词语，最大化以下似然函数即可 ，形式如下：
\begin{aligned}
\ \ L &= \prod_{w \in C} p(w|context(w)) \\
&\Rightarrow \\
logL&= \sum_{w \in C} logp(w|context(w)) \\
&=\sum_{w \in C} log\left [\prod_{i=2}^{l^w} p(d_i^w|\mathbf{x}_w,\theta^w_{i-1}) \right ]\\
&= \sum_{w \in C} log \left \{\prod_{i=2}^{l^w} \left [ \sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w)^{1-d_i^w} \right ] \cdot\left [(1-\sigma( \theta^{w \ T}_{i-1}\mathbf{x}_w) ^{d_i^w} \right ] \right \} \\
&=\sum_{w \in C} \sum_{i=2} ^{l^w} \left \{ (1-d_i^w) \cdot log \left [ \sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] +d_i^w \cdot \left [1-\sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] \right \}
\end{aligned}
为了便于推倒，将上式花括号的内容写作 $L(w,i)$ ,即 $L(w,i) = (1-d_i^w) \cdot log \left [ \sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] +d_i^w \cdot \left [1-\sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] $ 。
$ L $ 便是 CBOW 的目标函数 ，对于 $ L$ 的优化，CBOW 采用的是梯度上升算法（因为要寻找的是 $max $ 值，寻找 $min $ 时采用梯度下降的方法即可），目标函数 $ L$ 中的参数包括 $ \mathbf{x}_w \ , \theta_{i}^w $ ，其中 $ w \in C $ , $ i = 1,2,...,l^{w-1} $ , 也就是所有非叶节点对应的权值向量 $\theta^w$ , 给定输入为 $w \in C$ 时，要计算 $L$ 首先看 $L(w,j)$ 对$ \mathbf{x}_w \ , \theta_{i-1}^w $ 的到倒数：
\begin{aligned}
\frac{\partial L(w,i) }{\partial \theta_{i-1}^w}
&= \frac{\partial }{\partial \theta_{i-1}^w}\left \{ (1-d_i^w) \cdot log \left [ \sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] +d_i^w \cdot \left [1-\sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] \right \} \\
&=(1-d_i^w) \cdot \left [ 1- \sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] \cdot \mathbf{x}_w - d_i^w \cdot \sigma (\theta^{w \ T}_{i-1}\mathbf{x}_w) \cdot \mathbf{x}_w \\
&=\left [ 1-d_i^w -\sigma(\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] \cdot \mathbf{x}_w
\end{aligned}
于是 $\theta_{i-1}^w $ 的梯度更新公式为：$ \theta_{i-1}^w := \theta_{i-1}^w + \eta \cdot \left [ 1-d_i^w -\sigma(\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] \cdot \mathbf{x}_w $
同时根据 $ \mathbf{x}_w $ 与 $ \theta_{i-1}^w $ 的对称性可得到 $ \mathbf{x}_w $ 的梯度：
\[\frac{\partial L(w,i) }{\partial \mathbf{x}_w } = \left [ 1-d_i^w -\sigma(\theta^{w \ T}_{i-1}\mathbf{x}_w) \right ] \cdot \theta_{i-1}^w \]
因为 $ \mathbf{x}_w $ 表示的是 $context(w)$ 中的词向量的和，如何采用 $\frac{\partial L(w,i) }{\partial \mathbf{x}_w} $ 来对 $context(w)$ 中 $2c$ 个词向量的和进行更新呢， CBOW 是这样做的：
\[ \mathbf{v}(\bar{w}) := \mathbf{v}(\bar{w}) + \eta \sum_{i=2}^{l^w}\frac{\partial L(w,i)}{\partial \mathbf{x}_w} \ \ \ , \bar{w} \in context(w)\]
注意这里有 $ \mathbf{x}_w = \sum \mathbf{v}(\bar{w}) $ ，因为梯度的更新是对向量的和进行的，那么是否有必要对 $\sum_{i=2}^{l^w}\frac{\partial L(w,i)}{\partial \mathbf{x}_w} $ 做平均，来使其分别贡献到求和前的各个词向量呢，其实不用，只用控制 $ \eta $ 的大小就可以了，这样就可以把 $\sum_{i=2}^{l^w}\frac{\partial L(w,i)}{\partial \mathbf{x}_w} $ 贡献到 $\bar{w} \in context(w)$ 中每个词的词向量了。
综上，当给定输入为 $w \ ,context(w)$ 时，给出 CBOW 的实现 word2vec 中主要部分的伪代码：
\begin{aligned}
\ &e = 0 \\
\ &\mathbf{x}_w = \sum_{\bar{w} \in context(w) } \mathbf{v}(\bar{w} ) \ \ \ \ \\
\ &for \ i=2 \rightarrow l^w \ do: \\
&\ \ \ \ \ \ q = \sigma(\theta^{w \ T}_{i-1}\mathbf{x}_w) \\
&\ \ \ \ \ \ g = \eta (1-d_i^w-q)\\
&\ \ \ \ \ \ e := e+ g \cdot \theta^{w }_{i-1} \\
&\ \ \ \ \ \ \theta^{w }_{i-1} := \theta^{w}_{i-1} +g \cdot \mathbf{x}_w \\
\ &for \ \bar{w} \in conetxt(w) : \\
&\ \ \ \ \ \ \mathbf{v}(\bar{w} ) := \mathbf{v}(\bar{w} ) +e
\end{aligned}
需要注意3中最后两步顺序不能颠倒，即 $\theta_{j-1}^w$ 先贡献到 $e$ 然后进行相应的更新，至此，CBOW 模型已全部推倒完成。接下来便是另一种基于 Hierarchical Softmax 的模型 Skip-gram 模型。
2）Skip-gram Model
Skip-gram 的任务是给出词 $w$ 来预测其前后各 $c$ 个词语 $context(w)$ ，其推倒与 CBOW 大同小异，网络结构也是大体相同，如下图：
Input Layer
对于输入词语 $w$ ,转化为词向量的形式 $\mathbf{v}(w) \in \mathbb{R}^m$ 当做输入
Projection Layer
由于只有一个词向量 $\mathbf{v}(w)$ ，投影层其实是多于的，只是为了和 CBOW 做对比
Output Layer
同 CBOW 一样为 一颗 Huffman 树
CBOW 的任务是给定 $context(w)$ 计算 $w$, 对应概率为 $p(w|context(w))$ ,而 Skip-gram 的任务是给定 $w$ ,来预测 $context(w)$ ,其对应的概率为 $p(w|context(w))$ , Skip-gram将 $p(w|context(w))$ 定义为如下的形式：
\[ p(context(w)|w) = \prod p(w'|w) \ , \ \ w' \in context(w) \]
类似于 CBOW 中 Hierarchical Softmax 的思想，每个 $w'$ 的概率可以表达为 $p(w'|w) = \prod_{i=2}^{l^{w'}}p(d_i^{w'}|\mathbf{v}(w),\theta_{i-1}^{w'})$ ,其中:
\[p(d_i^{w'}|\mathbf{v}(w),\theta_{i-1}^{w'}) = \left[ \sigma(\theta^{w' \ T}_{i-1}\mathbf{v}(w)) \right]^{1-d_i^{w'}} \cdot \left[ 1-\sigma(\theta^{w' \ T}_{i-1}\mathbf{v} (w)) \right]^{d_i^{w'}} \]
接下来写出似然函数的具体形式：
有了以上目标函数，接下来就可以进行进一步的对 $\theta^{w'} , \ \mathbf{v}(w)$ 求导.
同样，记 $L(w,w',i) =\left \{ (1-d_i^{w'}) \cdot log \left [\sigma (\theta^{w'\ T}_{i-1}\mathbf{v}(w)) \right ] +d_i^{w'} \cdot log\left [1-\sigma (\theta^{w' \ T}_{i-1}\mathbf{v}(w)) \right ]\right \}$ ,接下来对 $L(w,w',i)$ 对参数分别进行求导：
\begin{aligned}
\frac{\partial L(w,w',i)}{\partial \theta_{i-1}^{w'}}
&= \frac{\partial}{\partial \theta_{i-1}^{w'}}\left \{ (1-d_i^{w'}) \cdot log \left [\sigma (\theta^{w'\ T}_{i-1}\mathbf{v}(w)) \right ] +d_i^{w'} \cdot log\left [1-\sigma (\theta^{w' \ T}_{i-1}\mathbf{v}(w)) \right ]\right \} \\
&= (1-d_i^{w'}) \cdot \left [1- \sigma (\theta^{w'\ T}_{i-1}\mathbf{v}(w)) \right ] \cdot \mathbf{v}(w) +d_i^{w'} \cdot \left [1-\sigma (\theta^{w' \ T}_{i-1}\mathbf{v}(w)) \right ] \cdot \mathbf{v}(w) \\
&=\left [ 1 -d_i^{w'}-\sigma (\theta^{w'\ T}_{i-1} \mathbf{v}(w)) \right ]\cdot \mathbf{v}(w) \\
\end{aligned}
根据对称性可得到 $\mathbf{v}(w)$ 的导数：
\begin{aligned}
\frac{\partial L(w,w',i)}{\partial\mathbf{v}(w)} =\left [ 1 -d_i^{w'}-\sigma (\theta^{w'\ T}_{i-1} \mathbf{v}(w)) \right ]\cdot \theta^{w'\ T}_{i-1} \\
\end{aligned}
现在可以得到 $\mathbf{v}(w)$ 与 $\theta^{w'\ T}_{i-1}$ 的更新公式分别为：
\begin{aligned}
\theta^{w'}_{i-1} &: =\theta^{w'}_{i-1} + \eta \left[1-d_i^{w'} -\sigma(\theta^{w' \ T}_{i-1} \mathbf{v}(w))\right ] \cdot \mathbf{v}(w) \\
\mathbf{v}(w) &: =\cdot \mathbf{v}(w) + \eta \sum_{w' \in context(w)} \sum_{i=2}^{l^{w'}}\left[1-d_i^{w'}- \sigma(\theta^{w' \ T}_{i-1} \mathbf{v}(w)) \right ] \cdot \theta^{w'}_{i-1}
\end{aligned}
综上，当给定输入为 $w \ ,context(w)$ 时，给出 Skip-gram 主要部分的伪代码：
\begin{aligned}
& e = 0 \\
& for \ \ w'\in context(w) \ \ do: \\
& \ \ \ \ \ for \ i=2 \rightarrow l^{w'} \ do: \\
&\ \ \ \ \ \ \ \ \ \ \ q = \sigma(\theta^{w' \ T}_{i-1}\mathbf{v}(w)) \\
&\ \ \ \ \ \ \ \ \ \ \ g = \eta (1-d_i^{w'}-q)\\
&\ \ \ \ \ \ \ \ \ \ \ e := e+ g \cdot \theta^{w'}_{i-1} \\
&\ \ \ \ \ \ \ \ \ \ \ \theta^{w'}_{i-1} := \theta^{w'}_{i-1} +g \cdot \mathbf{v}(w) \\
&\mathbf{v}(w) := \mathbf{v}(w) +e
\end{aligned}
但 Skip-gram 的实现 word2vec 并不是等 $context(w)$ 中的所有词 $w'$ 处理完后才刷新 $ \mathbf{v}(w) $ ，而是每处理一个词就刷新一次，即
\begin{aligned}
& for \ \ w'\in context(w) \ \ do: \\
& \ \ \ \ \ e = 0 \\
& \ \ \ \ \ for \ i=2 \rightarrow l^{w'} \ do: \\
&\ \ \ \ \ \ \ \ \ \ \ q = \sigma(\theta^{w' \ T}_{i-1}\mathbf{v}(w)) \\
&\ \ \ \ \ \ \ \ \ \ \ g = \eta (1-d_i^{w'}-q)\\
&\ \ \ \ \ \ \ \ \ \ \ e := e+ g \cdot \theta^{w'}_{i-1} \\
&\ \ \ \ \ \ \ \ \ \ \ \theta^{w'}_{i-1} := \theta^{w'}_{i-1} +g \cdot \mathbf{v}(w) \\
& \ \ \ \ \ \mathbf{v}(w) := \mathbf{v}(w) +e
\end{aligned}
至此，基于 Hierarchical Softmax 的两个模型 CBOW 与 Skip-gram 均介绍完成。接下来是更加快速的基于 Negative-Sampling 的模型。
基于 Negative-Sampling 的模型
基于 Hierarchical Softmax 两个模型采用的 Huffman 树结构虽然大大优化了 NNLM 中的 softmax 层，但仍属于比较复杂的结构，有咩有更简单的方法呢，Mikolov提出的一种基于 Negative Sampling 的模型，他可以用来进一步提高训练速度，并且可以改善词向量的质量。
1）CBOW 模型
在 CBOW 中，任务是给定词语 $w$ 来预测期上下文 $context(w)$ ,因此对于给定的 $context(w)$ ， $w$ 就是一个正样本，语料库中其他词就是负样本了，所谓的负采样就是说在语料库中采样得到一批负样本 $\hat{w}_i$ 构造负样本集合 $ N(w) = \left \{ \hat{w}_i \right \} \neq \phi $ ，合起来写作 $ Neg(w) = N(w) \cup \left\{ w \right \} $ ，则样本 $w' \in Neg(w)$ 对应的正负标签可表示为:
\[L^w(w')=\left\{
\begin{aligned}
1 , \ \ \ w' = w \\
0 , \ \ \ w' = \hat{w} \\
\end{aligned}
\right.\]
现在通过集合 $Neg(w)$ 来构造合适的语言模型 $p(w,context(w))$ ，首先写出单个词语，我们希望最大化：\[ \prod_{w' \in Neg(w)}p(w'|context(w))\]
其中：
\[p(w'|context(w))=\left\{
\begin{aligned}
\sigma(\mathbf{x}_w^T\theta^{w'}), \ \ \ \ \ \ & L^{w}(w') = 1 \\
1-\sigma(\mathbf{x}_w^T\theta^{w'}), \ & L^{w}(w') = 0 \\
\end{aligned}
\right.\]
写到一起有：
\[p(w'|context(w))= \left [\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] ^{L^w(w')} \cdot \left [1-\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] ^{1-L^w(w')}\]
这里 $\mathbf{x}_w$ 仍为 $context(w)$ 中词向量的和， $\theta^{w'} \in\mathbb{R}^m$ 表示词语 $w'$ 对应的辅助向量，对于单个输入 $w$ ,现在就要最大化：
\[\left[ \sigma(\mathbf{x}_w^T\theta^{w}) \right ] \prod_{\hat{w}\in N(w)} \left [1-\sigma(\mathbf{x}_w^T\theta^{\hat{w}}) \right ] \]
最大化上式等价于最大化 $w$ 为正类，而所有 $\hat{w}$ 为负类的联合概率。即增大正样本概率的同时，降低负样本的概率，现在对于给定的语料库 $C$ ，似然函数可以写成：
\[L = \prod_{w \in C} \prod_{w' \in Neg(w)} p(w'|context(w))\]
现在根据似然函数来找到参数的极大值即可：
\begin{aligned}
L &= \prod_{w \in C} \prod_{w' \in Neg(w)} p(w'|context(w)) \\
\Rightarrow \\
logL &=log \left [ \prod_{w \in C} \prod_{w' \in Neg(w)} p(w'|context(w)) \right ] \\
&= \sum_{w \in C} log \prod_{w' \in Neg(w)} p(w'|context(w)) \\
&=\sum_{w \in C} log \prod_{w' \in Neg(w)} \left \{ \left [\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] ^{L^w(w')} \cdot \left [1-\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] ^{1-L^w(w')} \right \} \\
&=\sum_{w \in C} \sum_{w' \in Neg(w)} \left \{ L^w(w') \cdot log\left [\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] + \left [1-L^w(w') \right ] \cdot log \left [1-\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] \right \}
\end{aligned}
同样通过梯度上升的方式求解,首先记：
\[L(w,w') = \left \{ L^w(w') \cdot log\left [\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] + \left [1-L^w(w') \right ] \cdot log \left[1-\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] \right \}\]
首先看 $L(w,w')$ 对 $\theta^{w'}$ 的梯度：
\begin{aligned}
\frac{\partial L(w,w') }{\partial \theta^{w'}} &=\frac{\partial }{\partial \theta^{w'}} \left \{ L^w(w') \cdot log\left [\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] + \left [1-L^w(w') \right ] \cdot log \left[1-\sigma(\mathbf{x}_w^T\theta^{w'}) \right ] \right \} \\
&=L^w(w') \cdot \left [1-\sigma(\mathbf{x}_w^T\theta^{w'}) \right ]\mathbf{x}_w - \left [1-L^w(w') \right ] \cdot \left[\sigma(\mathbf{x}_w^T\theta^{w'}) \right ]\mathbf{x}_w \\
&=\left [ L^w(w') - \sigma(\mathbf{x}_w^T\theta^{w'}) \right ]\mathbf{x}_w
\end{aligned}
同样，考虑 $\mathbf{x}_w$ 与 $\theta^{w'}$ 的对称性，可得到 $L(w,w')$ 关于 $\mathbf{x}_w$ 的导数：
\[\frac{\partial L(w,w') }{\partial \mathbf{x}_w} = \left [ L^w(w') - \sigma(\mathbf{x}_w^T\theta^{w'}) \right ]\theta^{w'} \]
因此当给定输入为 $w$ ,$context(w)$ ，对于 $\bar{w} \in context(w)$ 与 $\theta^{w'} , \ w' \in Neg(w)$ ,分别给出$\theta^{w'} ,\mathbf{v}(\bar{w}) $ 的梯度更新公式：
\[\theta^{w'} = \theta^{w'} + \eta \left [ L^{w}(w') - \sigma(\mathbf{x}_w^T\theta^{w'}) \right ] \mathbf{x}_w \ \ \ \ \ \mathbf{v}(\bar{w}) = \mathbf{v}(\bar{w}) + \eta \sum_{w' \in Neg(w)} \frac{\partial L(w,w') }{\partial \mathbf{x}_w} \]
综上给出 基于 Negative Sampling 的 CBOW 的梯度上升代码
\begin{aligned}
\ &e = 0 \\
\ &\mathbf{x}_w = \sum_{\bar{w} \in context(w) } \mathbf{v}(\bar{w} ) \ \ \ \ \\
\ &for \ w' \in \ Neg(w) \ do: \\
&\ \ \ \ \ \ q = \sigma(\mathbf{x}_w^T \theta^{w'}) \\
&\ \ \ \ \ \ g = \eta (L^w(w')-q)\\
&\ \ \ \ \ \ e := e+ g \cdot \theta^{w' } \\
&\ \ \ \ \ \ \theta^{w'} := \theta^{w'} +g \cdot \mathbf{x}_w \\
\ &for \ \bar{w} \in conetxt(w) : \\
&\ \ \ \ \ \ \mathbf{v}(\bar{w} ) := \mathbf{v}(\bar{w} ) +e
\end{aligned}
至此，基于 Negative-Sampling 的CBOW 全部介绍完毕。
2) Skip-gram 模型
与 CBOW 任务相反，Skip-gram 的任务是给定 $w$ ,来预测 $context(w)$ ,这时我们要对每个 $\bar{w} \in context(w)$ ,来产生一个负采样集合 $N(\bar{w})$ ,与 $\left \{ \bar{w} \right\}$ 一起生成 $Neg(\bar{w})$ ,可见对于每个样本 $\bar{w}$ Skip-gram的任务是这样的
\[p(context(w)|w) = \prod_{\bar{w} \in context(w)} p(\bar{w}|w)\]
结合构造的负样本集，对每个 $\hat{w}$ ,我们要最大化的联合概率是：
\[p(context(w)|w) = \prod_{\bar{w} \in context(w)} p(\bar w|w)\prod_{w' \in Neg(\bar{w})}p(w'|\bar w)\]
这里，如果对 $w'$ ，满足 $w' \in Neg(\bar w) $ 且 $w' = \bar w$ ，（即 $w'$ 为负采样集合中的自身）,则 $L^{w}(w') = 1$，否则 $L^{w}(w') = 0$ ，这即为人工指定的标签。 现在可以写出：
\[ p(w'|\bar w)=\begin{cases}
&\sigma(\mathbf{v}(w)^T \theta^{(w')}), \ \ \ \ \ \ L^{w}(w') = 1\\
&1-\sigma(\mathbf{v}(w)^T \theta^{(w')}), \ L^{w}(w') = 0\\
\end{cases} \]
写到一起：
\[p(w'|\bar w) = \left [\sigma(\mathbf{v}(w)^T \theta^{(w')}) \right ]^{L^w(w')}+\left [1-\sigma(\mathbf{v}(w)^T \theta^{(w')}) \right ]^{1-L^w(w')}\]
现在可以写出整个语料库的似然函数：
\begin{aligned}
L &= \prod_{w \in C}p(context(w)|w) \\
&= \prod_{w \in C}\prod_{\bar w \in context(w)}p(\bar w|w) \\
&= \prod_{w \in C}\prod_{\bar w \in context(w)}\prod_{w' \in Neg(\bar w)}p(w'|\bar w,w)\\
\Rightarrow \\
logL&=\sum_{w \in C}log\prod_{\bar w \in context(w)}\prod_{w' \in Neg(\bar w)}\left \{ \left [\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]^{L^w(w')}+\left [1-\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]^{1-L^w(w')} \right \}\\
&=\sum_{w \in C}\sum_{\bar w \in context(w)}\sum_{w' \in Neg(\bar w)}\left \{L^w(w') \cdot log \left [\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]+ \left [1- L^w(w') \right ] \cdot log \left [1-\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ] \right \}
\end{aligned}
接下来对参数求导即可，另：
\[L(w,\bar w, w') = L^w(w') \cdot log \left [\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]+ \left [1- L^w(w') \right ] \cdot log \left [1-\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]\]
从而得到 $L(w,\bar w ,w')$ 关于 $\mathbf{v}(w)$ 与 $\theta^{w'}$ 的梯度：
\begin{aligned}
\frac{\partial L(w,\bar w, w')}{\partial \theta^{w'}} &= \frac{\partial }{\partial \theta^{w'}}L^w(w') \cdot log \left [\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]+ \left [1- L^w(w') \right ] \cdot log \left [1-\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ] \\
&=L^w(w') \left [1-\sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]\mathbf{v}(w)-\left [1- L^w(w') \right ]\sigma(\mathbf{v}(w)^T \theta^{w'})\mathbf{v}(w) \\
&=\left [L^w(w')- \sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]\mathbf{v}(w)
\end{aligned}
根据对称性：
\[\frac{\partial L(w,\bar w, w')}{\partial \mathbf{v}(w) } = \left [L^w(w')- \sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]\theta^{w'}\]
接下来可以写出随机坐标上升法的参数更新公式：
\[\theta^{w'} := \theta^{w'} + \eta \left [L^w(w')- \sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]\mathbf{v}(w)\]
\[\mathbf{v}(w) := \mathbf{v}(w) + \eta \sum_{ \bar w \in context(w)} \sum_{w' \in Neg(\bar w)} \left [L^w(w')- \sigma(\mathbf{v}(w)^T \theta^{w'}) \right ]\theta^{w'}\]
这里给出基于 Negative-Sampling 的 Skip-gram 的随机梯度上升的伪代码：
\begin{aligned}
for \ \bar w &\ \in context(w) \ do:\\
\ \ \ \ \ &e = 0 \\
\ \ \ \ \ &for \ w' \in \ Neg(\bar w) \ do: \\
&\ \ \ \ \ \ q = \sigma(\mathbf{v}(w)^T \theta^{w'}) \\
&\ \ \ \ \ \ g = \eta (L^w(w')-q)\\
&\ \ \ \ \ \ e := e+ g \cdot \theta^{w' } \\
&\ \ \ \ \ \ \theta^{w'} := \theta^{w'} +g \cdot \mathbf{v}(w) \\
&\mathbf{v}(w ) := \mathbf{v}(w ) +e
\end{aligned}
注意，这里并不是等所有 $\bar{w}$ 处理完后更新 $\mathbf{v}(w )$ ，而是处理一个 $\bar{w}$ 更新一次，同层次 softmax 的处理方式。
3）Negative-Sampling方法
以上两小节只是给出基于负采样的训练算法，这里承接上文,对给定的词语 $w$ , 给出负样本集 $Neg(w)$ 的选取方法，负样本选取遵循的规律是频率高则被选择的概率较大，反之较小，对于词典 $V$ ,每个词语的权重可以表示为：
\[p(w) = \frac{count(w)}{\sum_{w' \in V}count(w')}\]
$count(w)$表示词语 $w$ 在语料库 $C$ 的计数，类似于 $LDA$ 中的 $Gibbs Sampling$，将 $p(w)$ 累加起来，即
\begin{aligned}
for \ &i = 1 \rightarrow |V|-1 \ do: \\
&p[i] :=p[i] +p[i-1]
\end{aligned}
如果按照 $u \sim (0-p[|V|-1])$ 来生成一个随机数，看随机数落在哪个区间 $(p[k] \sim p[k+1])$，进而选取词语 $k$ ,这种做法无疑会大大增加时间复杂度，所以，可以对数组 $p$ 建立索引，即建立长度为 $M$ 的数组 $m$ ，使 $M >> |V| -1$ ,这样每个每个 $m[i] , i \in (1,M-1) $会对应一个 $p[k]$ ,每次生成一个 $1 \sim M$ 的随机数 $n$，采样结果为： $m[n] = p[k]$ 即可，原本已线性时间采样，现在变成了$O(1)$ ，具体可以看下图：
如果采样到自身，直接跳过即可， Google 的 word2vec 实现采取 $M =10^8$ ,且 p 的计算如下：
\[p(w) = \frac{count(w)^{\frac{3}{4}}}{\sum_{w' \in V}count(w')^{\frac{3}{4}}} \]
至此， word2vec 已经全部介绍完毕，有机会再继续深入，现在一些 paper 的工作集中在词向量的可解释性与词向量的本质，好像说与 LSA 的 SVD 矩阵分解是等价的，具体到时候再看。
参考：
[1] Bengio Y, Schwenk H, Senécal J S, et al. A neural probabilistic language model[J]. Journal of Machine Learning Research, 2003, 3(6):1137-1155.
[2] Mikolov T, Chen K, Corrado G, et al. Efficient Estimation of Word Representations in Vector Space[J]. Computer Science, 2013.
[3] Mikolov T, Sutskever I, Chen K, et al. Distributed Representations of Words and Phrases and their Compositionality[J]. Advances in Neural Information Processing Systems, 2013, 26:3111-3119.
[4]word2vec中的数学