本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
上一篇介绍了word2vec两种基础模型CBOW和Skip-gram的训练过程，但是我们发现这样可能会出现计算量过大的问题，怎么改进网络减少计算量呢？
有两种改进方式，（1）分层Softmax（Hierachical Softmax），（2）负采样（Negative Sampling）。现在介绍第一种分层Softmax。
首先，Hierachical Softmax改进的核心是使用哈夫曼树（霍夫曼树）代替原来的softmax分类，有必要先简述下。
一、哈夫曼树
哈夫曼树，又称为最有二叉树，构建哈夫曼树的过程：
（1）将看作n个树的森林，每棵树一个节点。
（2）将最小的两棵树合并为一颗新树，新树权重为两子树权重之和
（3）去除合并的树，将新树加入森林
（4）重复（2）、（3）直至构建为一棵树。具体例子如下图所示。
哈夫曼树有什么特点，有什么作用呢？我们发现哈夫曼树的权重值越大越靠近根节点，权重越低越远离根节点，这样权重大的哈夫曼编码短，权重小的哈夫曼编码长。也就表示权重大的词路径越短，权重小的词路径越长。
对于词的权重，取每个词的词频作为权重构建哈夫曼树。常用词离根节点距离越短，计算量就越少。假如词典确定情况下，首先通过词频构建一颗哈夫曼树，并获得每个词的哈夫曼编码。
二、Hierarchical Softmax
基于传统神经网络的词向量语言模型，包含输入层、隐藏层和输出层，只是去掉了激活层。由于输出层通过softmax计算概率，计算量较大，为了减少计算量，使用哈夫曼树代替原来的softmax，可以大大减少了计算量。整体结构也发生了变化，去掉了之前输入层和隐藏层之间映射，词向量随机初始化，而且多个词向量采取求和取平均的方式。例如，输入的是三个4维词向量：(1,2,3,4),(9,6,11,8),(5,10,7,12),那么我们求和取平均后的词向量就是(5,6,7,8)。
1、哈夫曼树如何代替softmax？
我们可以把哈夫曼树的父节点（图中黄点）理解为原来神经网络语言模型的隐藏层神经元，叶子节点理解为输出层Softmax的神经元。
哈夫曼树的输出需要按照树结构一步一步往下走，一直找到叶子节点，因为每个父节点包含左右两个子节点，往左走为1，网右走为0。因此，走到叶子节点的路径都包含一个唯一哈夫曼编码，判断0和1输出使用sigmoid函数：
其中，为词向量，
为模型参数。其实就是用多个独立的二分类代替了softmax的作用，假设原来softmax计算量为
，变成了
。同时高频词靠近根节点，可以用更少的时间找到。
2、具体流程是什么样子呢？
这里以基于Hierarchical Softmax的CBOW模型为例。如下图
（1）首先如上述，需要对我们的词典表构建一个哈夫曼树，并记录每个词的哈夫曼编码
（2）设置固定窗口大小，取2C个词的词向量求和取平均（与之前讲过神经网络语言模型的One hot不同，这里的词向量是随机初始化的）
（3）通过梯度更新网络参数和词向量
如何更新参数和词向量，就是下面要介绍的梯度推导。
三、Hierarchical Softmax梯度推导
怎么输出真实叶子节点的概率和更新参数呢？使用概率公式和极大似然函数进行更新。哈夫曼树中某一条路径上的节点都是相对独立的二分类，所以可以通过每个节点概率相乘的方式表示叶子节点的概率。假设路径上有三个节点，即：
每单个节点的概率表达式如下：
其中，为词向量，
为节点参数，
为哈夫曼编码值。因此最后的似然函数为：
对词向量和模型参数
求导，得：
