hierarc-softmax.md

# 基于Hierarchical Softmax的模型

---

# 1. 基于Hierarchical Softmax的模型概述

我们先回顾下传统的神经网络词向量语言模型，里面一般有三层，输入层（词向量），隐藏层和输出层（softmax层）。里面最大的问题在于从隐藏层到输出的softmax层的计算量很大，因为要计算所有词的softmax概率，再去找概率最大的值。这个模型如下图所示。其中V是词汇表的大小，

![](http://images2017.cnblogs.com/blog/1042406/201707/1042406-20170727105326843-18935623.png)

word2vec对这个模型做了改进，首先，对于从输入层到隐藏层的映射，没有采取神经网络的线性变换加激活函数的方法，而是采用简单的对所有输入词向量求和并取平均的方法。比如输入的是三个4维词向量：\(1,2,3,4\), \(9,6,11,8\),\(5,10,7,12\),那么我们word2vec映射后的词向量就是\(5,6,7,8\)。由于这里是从多个词向量变成了一个词向量。

第二个改进就是从隐藏层到输出的softmax层这里的计算量个改进。为了避免要计算所有词的softmax概率，word2vec采样了霍夫曼树来代替从隐藏层到输出softmax层的映射。我们在上一节已经介绍了霍夫曼树的原理。如何映射呢？这里就是理解word2vec的关键所在了。

由于我们把之前所有都要计算的从输出softmax层的概率计算变成了一颗二叉霍夫曼树，那么我们的softmax概率计算只需要沿着树形结构进行就可以了。如下图所示，我们可以沿着霍夫曼树从根节点一直走到我们的叶子节点的词$$w_2$$。

![](http://images2017.cnblogs.com/blog/1042406/201707/1042406-20170727105752968-819608237.png)

和之前的神经网络语言模型相比，我们的霍夫曼树的所有内部节点就类似之前神经网络隐藏层的神经元,其中，根节点的词向量对应我们的投影后的词向量，而所有叶子节点就类似于之前神经网络softmax输出层的神经元，叶子节点的个数就是词汇表的大小。在霍夫曼树中，隐藏层到输出层的softmax映射不是一下子完成的，而是沿着霍夫曼树一步步完成的，因此这种softmax取名为"Hierarchical Softmax"。

如何“沿着霍夫曼树一步步完成”呢？在word2vec中，我们采用了二元逻辑回归的方法，即规定沿着左子树走，那么就是负类\(霍夫曼树编码1\)，沿着右子树走，那么就是正类\(霍夫曼树编码0\)。判别正类和负类的方法是使用sigmoid函数，即：$$P(+) = \sigma(x_w^T\theta) = \frac{1}{1+e^{-x_w^T\theta}}$$

其中$$x_w$$是当前内部节点的词向量，而$$\theta$$则是我们需要从训练样本求出的逻辑回归的模型参数。

使用霍夫曼树有什么好处呢？首先，由于是二叉树，之前计算量为V,现在变成了$$log_2V$$。第二，由于使用霍夫曼树是高频的词靠近树根，这样高频词需要更少的时间会被找到，这符合我们的贪心优化思想。

容易理解，被划分为左子树而成为负类的概率为$$P(-) =  1-P(+)$$。在某一个内部节点，要判断是沿左子树还是右子树走的标准就是看$$P(-),P(+)$$谁的概率值大。而控制$$P(-),P(+)$$谁的概率值大的因素一个是当前节点的词向量，另一个是当前节点的模型参数$$\theta$$。

对于上图中的$$w_2$$，如果它是一个训练样本的输出，那么我们期望对于里面的隐藏节点$$n(w_2,1)$$的$$P(-)$$概率大，$$n(w_2,2)$$的$$P(-)$$概率大，$$n(w_2,3)$$的$$P(+)$$概率大。

回到基于Hierarchical Softmax的word2vec本身，我们的目标就是找到合适的所有节点的词向量和所有内部节点$$\theta$$, 使训练样本达到最大似然。那么如何达到最大似然呢？

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

我们使用最大似然法来寻找所有节点的词向量和所有内部节点$$\theta$$。先拿上面的$$w_2$$例子来看，我们期望最大化下面的似然函数：$$\prod_{i=1}^3P(n(w_i),i) = (1- \frac{1}{1+e^{-x_w^T\theta_1}})(1- \frac{1}{1+e^{-x_w^T\theta_2}})\frac{1}{1+e^{-x_w^T\theta_3}}$$

对于所有的训练样本，我们期望最大化所有样本的似然函数乘积。

为了便于我们后面一般化的描述，我们定义输入的词为w,其从输入层词向量求和平均后的霍夫曼树根节点词向量为$$x_w$$, 从根节点到w所在的叶子节点，包含的节点总数为$$l_w,w$$在霍夫曼树中从根节点开始，经过的第i个节点表示为$$p_i^w$$,对应的霍夫曼编码为$$d_i^w \in {0,1}$$,其中i =2,3,...$$l_w$$。而该节点对应的模型参数表示为$$\theta_i^w$$, 其中i =1,2,...$$l_w-1$$，没有$$i =l_w$$是因为模型参数仅仅针对于霍夫曼树的内部节点。

定义w经过的霍夫曼树某一个节点j的逻辑回归概率为$$P(d_j^w|x_w, \theta_{j-1}^w)$$，其表达式为：

$$P(d_j^w|x_w, \theta_{j-1}^w)= \begin{cases}  \sigma(x_w^T\theta_{j-1}^w)& {d_j^w=0}\\ 1-  \sigma(x_w^T\theta_{j-1}^w) & {d_j^w = 1} \end{cases}$$

那么对于某一个目标输出词w,其最大似然为：

$$\prod_{j=2}^{l_w}P(d_j^w|x_w, \theta_{j-1}^w) = \prod_{j=2}^{l_w} [\sigma(x_w^T\theta_{j-1}^w)] ^{1-d_j^w}[1-\sigma(x_w^T\theta_{j-1}^w)]^{d_j^w}$$

在word2vec中，由于使用的是随机梯度上升法，所以并没有把所有样本的似然乘起来得到真正的训练集最大似然，仅仅每次只用一个样本更新梯度，这样做的目的是减少梯度计算量。这样我们可以得到w的对数似然函数L如下：

$$L= log \prod_{j=2}^{l_w}P(d_j^w|x_w, \theta_{j-1}^w) = \sum\limits_{j=2}^{l_w} ((1-d_j^w) log [\sigma(x_w^T\theta_{j-1}^w)]  + d_j^w log[1-\sigma(x_w^T\theta_{j-1}^w)])$$

要得到模型中w词向量和内部节点的模型参数$$\theta$$, 我们使用梯度上升法即可。首先我们求模型参数$$\theta_{j-1}^w$$的梯度：

$$\begin{aligned} \frac{\partial L}{\partial \theta_{j-1}^w} & = (1-d_j^w)\frac{(\sigma(x_w^T\theta_{j-1}^w)(1-\sigma(x_w^T\theta_{j-1}^w)}{\sigma(x_w^T\theta_{j-1}^w)}x_w - d_j^w \frac{(\sigma(x_w^T\theta_{j-1}^w)(1-\sigma(x_w^T\theta_{j-1}^w)}{1- \sigma(x_w^T\theta_{j-1}^w)}x_w  \\ & =  (1-d_j^w)(1-\sigma(x_w^T\theta_{j-1}^w))x_w -  d_j^w\sigma(x_w^T\theta_{j-1}^w)x_w \\& = (1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))x_w \end{aligned}$$

同样的方法，可以求出$$x_w$$的梯度表达式如下：$$\frac{\partial L}{\partial x_w} = (1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))\theta_{j-1}^w$$

有了梯度表达式，我们就可以用梯度上升法进行迭代来一步步的求解我们需要的所有的$$\theta_{j-1}^w$$和$$x_w$$。

# 3. 基于Hierarchical Softmax的CBOW模型

由于word2vec有两种模型：CBOW和Skip-Gram,我们先看看基于CBOW模型时， Hierarchical Softmax如何使用。

首先我们要定义词向量的维度大小M，以及CBOW的上下文大小2c,这样我们对于训练样本中的每一个词，其前面的c个词和后面的c个词作为了CBOW模型的输入,该词本身作为样本的输出，期望softmax概率最大。

在做CBOW模型前，我们需要先将词汇表建立成一颗霍夫曼树。

对于从输入层到隐藏层（投影层），这一步比较简单，就是对w周围的2c个词向量求和取平均即可，即：$$x_w = \frac{1}{2c}\sum\limits_{i=1}^{2c}x_i$$

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

$$\theta_{j-1}^w = \theta_{j-1}^w + \eta  (1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))x_w$$

$$x_w= x_w +\eta  (1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))\theta_{j-1}^w \;(i =1,2..,2c)$$

其中$$\eta$$为梯度上升法的步长。

这里总结下基于Hierarchical Softmax的CBOW模型算法流程，梯度迭代使用了随机梯度上升法：

输入：基于CBOW的语料训练样本，词向量的维度大小M，CBOW的上下文大小2c,步长$$\eta$$

输出：霍夫曼树的内部节点模型参数$$\theta$$，所有的词向量w

1. 基于语料训练样本建立霍夫曼树。

2. 随机初始化所有的模型参数$$\theta$$，所有的词向量w

3. 进行梯度上升迭代过程，对于训练集中的每一个样本\(context\(w\), w\)做如下处理：

a\)  e=0， 计算$$x_w= \frac{1}{2c}\sum\limits_{i=1}^{2c}x_i$$

b\)  for j = 2 to $$l_w$$, 计算：

$$f = \sigma(x_w^T\theta_{j-1}^w)$$

$$g = (1-d_j^w-f)\eta$$

$$e = e + g\theta_{j-1}^w$$

$$\theta_{j-1}^w= \theta_{j-1}^w + gx_w$$

c\) 对于context\(w\)中的每一个词向量$$x_i$$\(共2c个\)进行更新：$$x_i = x_i + e$$

d\) 如果梯度收敛，则结束梯度迭代，否则回到步骤3继续迭代。

# 4. 基于Hierarchical Softmax的Skip-Gram模型

现在我们先看看基于Skip-Gram模型时， Hierarchical Softmax如何使用。此时输入的只有一个词w,输出的为2c个词向量context\(w\)。

我们对于训练样本中的每一个词，该词本身作为样本的输入， 其前面的c个词和后面的c个词作为了Skip-Gram模型的输出,，期望这些词的softmax概率比其他的词大。

Skip-Gram模型和CBOW模型其实是反过来的，在上一篇已经讲过。

在做CBOW模型前，我们需要先将词汇表建立成一颗霍夫曼树。

对于从输入层到隐藏层（投影层），这一步比CBOW简单，由于只有一个词，所以，即$$x_w$$就是词w对应的词向量。

第二步，通过梯度上升法来更新我们的$$\theta_{j-1}^w$$和$$x_w$$，注意这里的$$x_w$$周围有2c个词向量，此时如果我们期望$$P(x_i|x_w), i=1,2...2c$$最大。此时我们注意到由于上下文是相互的，在期望$$P(x_i|x_w), i=1,2...2c$$最大化的同时，反过来我们也期望$$P(x_w|x_i), i=1,2...2c$$最大。那么是使用$$P(x_i|x_w)$$好还是$$P(x_w|x_i)$$好呢，word2vec使用了后者，这样做的好处就是在一次迭代时，我们不是更新$$x_w$$一个词，而是$$x_i, i=1,2...2c$$共2c个词。这样整体的迭代会更加的均衡。因为这个原因，Skip-Gram模型并没有和CBOW模型一样对输入进行迭代更新，而是对2c个输出进行迭代更新。

这里总结下基于Hierarchical Softmax的Skip-Gram模型算法流程，梯度迭代使用了随机梯度上升法：

输入：基于Skip-Gram的语料训练样本，词向量的维度大小M，Skip-Gram的上下文大小2c,步长$$\eta$$

输出：霍夫曼树的内部节点模型参数$$\theta$$，所有的词向量w

1. 基于语料训练样本建立霍夫曼树。

2. 随机初始化所有的模型参数$$\theta$$，所有的词向量w,

3. 进行梯度上升迭代过程，对于训练集中的每一个样本\(w, context\(w\)\)做如下处理：

a\)  for i =1 to 2c:

i\) e=0  
ii\)for j = 2 to $$l\_w$$, 计算：  
$$f = \sigma(x\_i^T\theta\_{j-1}^i)$$  
$$g = (1-d\_j^i-f)\eta$$  
$$e = e + g\theta\_{j-1}^i$$$  
$$\theta\_{j-1}^i= \theta\_{j-1}^i + gx\_i$$

iii\) $$x\_i = x\_i + e$$

b\)如果梯度收敛，则结束梯度迭代，算法结束，否则回到步骤a继续迭代。

# 5. Hierarchical Softmax的模型源码和算法的对应

这里给出上面算法和[word2vec源码](https://github.com/tmikolov/word2vec/blob/master/word2vec.c)中的变量对应关系。

在源代码中，基于Hierarchical Softmax的CBOW模型算法在435-463行，基于Hierarchical Softmax的Skip-Gram的模型算法在495-519行。大家可以对着源代码再深入研究下算法。

在源代码中，neule对应我们上面的e, syn0对应我们的$$x_w, syn1$$对应我们的$$\theta_{j-1}^i, layer1_size$$对应词向量的维度，window对应我们的c。

另外，vocab\[word\].code\[d\]指的是，当前单词word的，第d个编码，编码不含Root结点。vocab\[word\].point\[d\]指的是，当前单词word，第d个编码下，前置的结点。