NLP（八）补充：基于Hierarchical Softmax的word2vec两种模型（CBOW与Skip-Gram）
目录
1.基于Hierarchical Softmax的CBOW模型
3.基于Hierarchical Softmax的Skip-Gram模型
word2vec一般分为CBOW(Continuous Bag-of-Words 与Skip-Gram两种模型。在上篇文章中简单介绍了这两种模型。本文具体介绍基于Hierarchical Softmax的word2vec两种模型
本文参考： 1.《word2voc中的数学原理》--peghoty
2.http://www.cnblogs.com/pinard/p/7243513.html
1.基于Hierarchical Softmax的CBOW模型
先回顾一下上篇文章中提到的NNLM神经网络语言模型：
Word2vec中的CBOW模型如下图所示：
基于Hierarchical Softmax的
相比较NNLH，主要有三点不同：
首先，对于从输入层到隐藏层的映射，没有采取神经网络的线性变换加**函数的方法，而是采用简单的对所有输入词向量求和并取平均的方法或者采取累加的方法。
第二个改进就是从隐藏层到输出的softmax层这里的计算量个改进。为了避免要计算所有词的softmax概率，word2vec采样了霍夫曼树来代替从隐藏层到输出softmax层的映射。我们在上篇文章中已经介绍了霍夫曼树Huffman tree的原理。这一步的映射就是word2vec的关键。
我们把之前所有都要计算的从输出softmax层的概率计算变成了一颗二叉霍夫曼树，那么我们的softmax概率计算只需要沿着树形结构进行就可以了。
和之前的神经网络语言模型相比，我们的霍夫曼树的所有内部节点就类似之前神经网络隐藏层的神经元,其中，根节点的词向量对应我们的投影后的词向量，而所有叶子节点就类似于之前神经网络softmax输出层的神经元，叶子节点的个数就是词汇表的大小。在霍夫曼树中，隐藏层到输出层的softmax映射不是一下子完成的，而是沿着霍夫曼树的一个个节点推算，因此这种softmax取名为"Hierarchical Softmax"。
在word2vec中，我们采用了二元逻辑回归的方法，即规定沿着左子树走，那么就是负类(霍夫曼树编码1)，沿着右子树走，那么就是正类(霍夫曼树编码0)。判别正类和负类的方法是使用sigmoid函数:
其中是当前内部节点的词向量，而θ则是我们需要从训练样本求出的逻辑回归的模型参数。
使用霍夫曼树有什么好处如下：
第一，由于是二叉树，之前计算量为V,现在变成了。
第二，由于使用霍夫曼树是高频的词靠近树根，这样高频词需要更少的时间会被找到，这符合我们的贪心优化思想。
2.CBOW模型的求解
我们定义输入的词为,其从输入层词向量求和平均后的霍夫曼树根节点词向量为
, 从根节点到
所在的叶子节点，包含的节点总数为
，
在霍夫曼树中从根节点开始，经过的第ii个节点表示为pwipiw,对应的霍夫曼编码为
,其中
。而该节点对应的模型参数表示为
, 其中
，没有
是因为模型参数仅仅针对于霍夫曼树的内部节点。
定义经过的霍夫曼树某一个节点
的逻辑回归概率为
，其表达式为：
那么对于某一个目标输出词，其最大似然为：
在word2vec中，由于使用的是随机梯度上升法，所以并没有把所有样本的似然乘起来得到真正的训练集最大似然，仅仅每次只用一个样本更新梯度，这样做的目的是减少梯度计算量。这样我们可以得到的对数似然函数
如下：
得到模型中词向量和内部节点的模型参数θ
, 我们使用梯度上升法即可。首先我们求模型参数
的梯度：
梯度推导过程基本类似logistics回归，同样的方法，可以求出xwxw的梯度表达式如下：
有了梯度表达式，我们就可以用梯度上升法进行迭代来一步步的求解我们需要的所有的和
更新公式如下，输入的2c个词向量都需要进行更新：
其中η为梯度上升法的步长。
这里总结下基于Hierarchical Softmax的CBOW模型算法流程，梯度迭代使用了随机梯度上升法：
输入：基于CBOW的语料训练样本，词向量的维度大小M，CBOW的上下文大小2c,步长η
输出：霍夫曼树的内部节点模型参数θ，所有的词向量
1. 基于语料训练样本建立霍夫曼树。
2. 随机初始化所有的模型参数θ，所有的词向量w
3. 进行梯度上升迭代过程，对于训练集中的每一个样本(context(w),w)做如下处理：
（图中的等同于文中的词向量
）
3.基于Hierarchical Softmax的Skip-Gram模型
Skip-Gram网络如下图所示：
输入层：词w的词向量v或者x
投影层：词w的词向量v或者x
输出层：huffman tree
Skip-Gram模型和CBOW模型其实是反过来的。输入的只有一个词的词向量，输出的为2C个词context(w)的词向量。我们对于训练样本中的每一个词，该词的词向量本身作为样本的输入， 其前面的C个词和后面的C个词的词向量作为了Skip-Gram模型的输出,，期望这些词的softmax概率比其他的词大。
4.Skip-Gram模型的求解
数学模型的梯度求取公式同CBOW相同。不同的针对2C个词，对输入词w进行2c词更新。
按照CBOW中的梯度计算公式的话，伪代码如下：
但是word2vec中，并不是对2c个词都计算完后才更新输入，而是每次处理完content(w)中一个词就更新
。
（图中=
）
5.word2vec源代码
源代码地址：https://github.com/tmikolov/word2vec/blob/master/word2vec.c
在源代码中，基于Hierarchical Softmax的CBOW模型算法在435-463行，基于Hierarchical Softmax的Skip-Gram的模型算法在495-519行。
在源代码中，neule对应我们上面的, syn0对应我们的
，syn1对应我们的
, layer1_size对应词向量的维度，window对应我们的C。
另外，vocab[word].code[d]指的是，当前单词word的，第d个编码，编码不含Root结点。vocab[word].point[d]指的是，当前单词word，第d个编码下，前置的结点。