word2vec基于Hierarchical softmax的模型细节

参考地址:http://www.cnblogs.com/pinard/p/7243513.html

1,基于Hierarchical softmax的模型的改进点

首选回顾传统的神经网络词向量语言模型,里面一般有三层:输入层(词向量)，隐藏层，输出层(softmax层)。里面最大的问题就是在于从隐藏层到输出层的softmax层的计算量太大，因为他是要计算所有词的softmax概率，然后再找到概率最大的值，模型如下，其中V代表词汇表的大小:

word2vec的改进:

1,首先，对于从输入层到隐藏层的映射，没有采取神经网络的线性变换加**函数的方法，而是采用简单的对所有的输入词向量求和并取平均的方法。
2，第二个改进就是从隐藏层到输出层的softmax层这里的计算量的改进。为了避免要计算所有词的softmax概率，word2vec采用了huffman树来代替从隐藏层到输出softmax层的映射。

具体的计算过程如图:

1,和之前的神经网络模型相比，这里的huffmax树的所有内部节点就类似之前神经网络隐藏层的神经元。其中，根节点的词向量对应我们的投影后的词向量，而所有的叶子节点就类似于之前神经网络softmax输出层的神经元。叶子节点的个数就是词汇表的大小.
2,和之前的相比，从隐藏层到输出层的softmax映射不是一下就完成的，而是沿着huffman树一步步完成的，因此这种softmax取名为”Hierarchical softmax”.
3,沿着huffman树走的细节可以如下理解:在word2vec中，采用二元逻辑回归的方法，规定沿着左子树走，那么就是负类(huffman编码为1)，沿着右子树走，就是正类(huffman编码为0)。那么判别是正类还是负类用的是sigmoid函数即:
P(+)=σ(xTwθ)=11+e(−xTwθ)$P(+)=\sigma (x_{w^{\theta }}^T)=\frac{1}{1+e^{(}-x_{w^{\theta }}^T)}$
其中，xw$x_w$是当前内部节点的词向量，而θ$\theta$则是我们需要从训练数据中求出的逻辑回归的模型参数。

使用Huffman树的好处是:(1),由于是二叉树，所以之前的计算量为V，现在变成了log2V${\log }_{2}V$。(2),高频的词靠近词根，这样高频词需要更少的时间会被找到。
那么对于上图中的w2$w_2$,如果他是一个训练样本的输出，那么我们希望对于里面的隐藏层的节点n(w2,1)$n(w_2,1)$的P(-)更大，n(w2,2)$n(w_2,2)$的P(-)概率大，n(w2,3)$n(w_2,3)$的P(+)概率大。
回到Hierarchical softmax的word2vec本身，我们的目标就是找到合适的所有节点的词向量和所有内部节点θ$\theta$,来是训练样本达到最大似然

2，基于Hierarchical Softmax的模型梯度计算

我们使用最大似然法来寻找所有节点的词向量和所有内部节点θ$\theta$，先拿上面的w2$w_2$例子来看，我们期望最大化下面的似然函数:

同时，如果是所有的训练样本，那么我们期望最大化所有样本的似然函数乘积。
为了便于后面的描述，先定义输入的词为w,其从输出层词向量求和平均后的huffman根节点词向量为xw$x_w$,从根节点到w所在的叶子节点，包含的节点总数为lw$l_w$,w在huffman中从根节点开始，经过的第i$i$个节点表示为pwi$p_i^w$,对应的huffman编码为dwi∈{0,1}$d_i^w\in \{0,1\}$,其中i$i$=2,3…lw$l_w$,而该节点对应的模型参数表示为θwi${\theta }_i^w$,其中i$i$=1,2…lw−1$l_w-1$,没有i=lw$i=l_w$是因为模型参数仅仅针对于huffman树的内部节点。
下图，式子一则是先定义经过一个huffman树节点后期望得到的概率值，式子二则是期望得到一个目标输出词w，其最大使然函数的目标值，式子三则是对最大似然函数值取log便与运算，式子四则是用目标函数对内部节点θ$\theta$的导数值，以便于得到其内部节点的模型参数θ$\theta$,式子五则是对根节点的xw$x_w$的词向量的求导，以便于更新根节点的词向量值:

由上图我们可以得到，他每次只是用一个样本来更新模型，模型最终要学的主要是两部分：xw$x_w$和θ$\theta$.

3,基于Hierarchical Softmax的CBOW模型

word2vec有两种模型，分别是CBOW和Skip-Gram,下面我们介绍基于CBOW模型，Hierarchical Softmax是如何使用的。

0，首先我们定义词向量的维度大小为M$M$,以及CBOW的上下文大小为2c$2c$,这样我们对于训练样本中的每一个词，其前面的c$c$个词和后面的c$c$个词作为了CBOW模型的输入，该词本身作为样本的输出，期望softmax概率最大。
1，在做CBOW模型前，我们需要先将词汇表建立成一棵huffman树，对于从输入层到隐藏层(投影层)，这一步就是对w$w$周围的2c$2c$个词向量求和取平均即可，即:

2,通过梯度上升法来更新我们的θwj−1${\theta }_{j-1}^w$和xw$x_w$,注意这里的xw$x_w$是由2c$2c$个词向量相加而成，我们做梯度更新完毕后会用梯度项直接更新原始的各个xi$x_i$(i$i$=1,2,…2c),即如下：

下面我们来介绍下基于Hierarchical softmax的CBOW模型的总体算法流程，梯度迭代使用了随机梯度上升法

输入:基于CBOW的语料训练样本，词向量的维度大小为M$M$,CBOW的上下文大小为2c$2c$,步长为γ$\gamma$
输出:huffman树的内部节点模型参数θ$\theta$,所有的词向量w$w$.
1,基于语料训练样本建立huffman树
2,随机初始化所有的模型参数θ$\theta$,所有的词向量w$w$
3,进行梯度上升迭代过程，对于训练集中的每一个样本(context(w$w$),w$w$)，作如下处理:

a) e = 0,计算xw=12c∑2c1xi$x_w=\frac{1}{2c}\sum _1^{2c}{x}_i$
b) for j=2 to lw$l_w$计算:

注意这里的g$g$可以理解为是用来更新模型内的节点的参数θ$\theta$的，而e$e$则可以理解为将每个节点的梯度都加起来，然后最后用来更新最初的根节点，进而更新上下文的2c$2c$个向量。
c)对于context(w$w$)中的每一个词向量xi$x_i$(共2c$2c$个)进行更新:
xi=xi+e$x_i=x_i+e$
d)如果梯度收敛，则结束梯度迭代，否则回到步骤3继续迭代。

4,基于Hierarchical Softmax的Skip-Gram模型

对于Skip-gram模型来说，他的输入只有一个词w$w$,输出的为2c$2c$个词向量context(w$w$).
对于训练样本中的每一个词，该词作为样本的输入，其前面的c$c$个词和后面的c$c$个词作为了Skip-gram模型的输出，期望这些词的softmax概率比其他的词大。下面介绍模型构造步骤。

1，从输入层到隐藏层的映射，这一步比CBOW简单，由于只有一个词，所以，即xw$x_w$就是词w$w$对应的词向量。
2，通过梯度上升法来更新我们的θwj−1${\theta }_{j-1}^w$和xw$x_w$,注意这里的xw$x_w$周围有2c$2c$个词向量，此时我们期望P(xi|xw),i=1,2...2c$P(x_i|x_w),i=1,\mathrm{2...2}c$最大。

这里注意，由于上下文是相互的，在期望P(xi|xw),i=1,2...2c$P(x_i|x_w),i=1,\mathrm{2...2}c$最大化的同时，反过来我们也期望P(xw|xi),i=1,2....2c$P(x_w|x_i),i=1,\mathrm{2....2}c$最大。那么我们是使用P(xi|xw)$P(x_i|x_w)$,还是使用P(xw|xi)$P(x_w|x_i)$呢。word2vec使用了后者，这样做的好处就是在一次迭代时，我们不是更新xw$x_w$一个词，而是xi,i=1,2...2c$x_i,i=1,\mathrm{2...2}c$共2c个词。 这样的话整体的迭代会更加的均衡。因为这个原因。Skip-gram模型并没有和CBOW模型一样对输入进行迭代更新，而是对2c$2c$个输出进行迭代更新。
对基于Hierarchical Softmax的Skip-gram模型算法流程，梯度迭代使用的是随机梯度上升法:

输入: 基于skip-gram的语料训练集，词向量的维度大小为M$M$,skip-gram的上下文大小为2c$2c$,步长为γ$\gamma$
输出: huffman树的内部节点的模型参数θ$\theta$,所有的词向量w$w$.

具体算法流程:对于训练集中的每一个样本(w,context(w)$w,context(w)$)做如下处理:

理解为:对于上下文的2c个词向量，每一个单一作为根节点然后走到huffman树的叶子节点，最终叶子节点为xw$x_w$。
注意这里与上面CBOW模型的区别在于，上面CBOW其实也是由2c个上下文词向量来走到Huffman树的叶子节点，但是他的根节点为2c个词向量的求和均值，并且更新的也是context(w)中的2c个词向量。而skip-gram每次单一的输入2c个词向量中的一个，最后更新的也是这个输入的词向量和Huffman内部节点的参数。
总而言之，CBOW和Skip-gram最后更新的都是2c个词向量和huffman树内部节点的参数。