在外网发现一篇把word2vec的hierarchical softmax优化讲得比较好的博客，详见：http://building-babylon.net/2017/08/01/hierarchical-softmax/
总结：
1、层次化softmax是为了解决用softmax进行V分类时(V是词典大小)，由于词典巨大导致计算目标词的似然概率的低效问题。
2、层次化softmax通常和CBOW模型一起讲，但它作为一种优化手段，也可以用于skip-gram的优化。
3、层次化softmax改变了原来的模型结构。原来是1*V(输入one-hot)，经过V*D的矩阵(input-embedding) ，再经过D*V矩阵(output-embedding)，即一系列矩阵乘法(1,V)*(V,D)*(D,V)=(1,V)【其中的第一次乘法，一般用查表的方式直接读取，不用相乘】,再softmax，得到目标词是词典中每个词的概率。使用层次化softmax时，output-embedding被取消了，查表后直接用(1,D)的向量与每个中间路径节点对应的一个向量γn【形状为(D,1)】，进行相乘，得到一个scalar，再经过sigmoid，转为一个0到1之间的小数，此数从就是从树(树是二叉树，树的每个叶子节点都对应一个单词)的根节点到某个叶子节点的路径上每次在中间节点选择向左(也可定为向右)走的概率。也就是这段话的意思：
如此这般，路径上每条边的概率进行连乘，就是从根节点到叶子节点的总的概率，也就是模型的预测值为该叶子节点(目标单词)的概率。层次化softmax的目标函数就是最大化目标词的路径概率，换句话说，我们只需要关注目标词的路径概率即可，而目标词是已知的，完全不需要计算其他的词的路径概率。这点是后续优化措施的关键。
4、那层次化softmax的优点体现在哪里？体现在计算预测输出值为每个单词的概率时，由于概率是从根节点到叶子节点的路径上的边进行连乘，也就是计算量与目标词(叶子节点)的路径长度成正比，原来的softmax的目标函数在反向传播时需要求导，而求导时，由于分母是e的指数的累加和，导致必须算出所有单词的概率，计算量是与词表大小V成正比。【目标函数为交叉熵，loss=-ΣYi*logPi, 其中i代表某个类别，而只有目标词的Yi为1，其余词的Yi为0，因此loss=-logP(target)。而Pi=softmax(w1*w2)，w1,w2分别是input-embedding、output-embedding矩阵中的参数, 先求对w2的梯度：d(loss) /d(w2)=-1/P(target)* d(P(target))/d(w2)，可见梯度中包括P(target)的计算，因此必须包含V个e的指数计算。】
而层次化softmax的树是二叉树，路径长度也就是树的高度，假设是满二叉树，则树高=V取2为底的对数值，远远小于V，节省了很多计算过程。比如一个大小为1024的词典，原来softmax是1024个e的指数计算，现在是log1024=10次sigmoid值再连乘，共节省了1024-10=1014次计算。
5、是否还可以进一步优化？可以。以上表述中层次化的softmax用到的树，一般认为是满的二叉树，也就是树的高度为logV，其实还有优化的空间。因为目标词的概率仅与根节点到目标词的路径长度有关，如果我们能够优化根节点到目标词的路径长度，就可以进一步节省计算。什么二叉树的根节点到叶子节点的路径长度最短？答案是哈夫曼树。
因此可以把树做成哈夫曼树。mikolov的论文就是采用了哈夫曼树，且构建哈夫曼树时，比较节点的权重大小是依据该节点(也就是单词)的词频，词频大的放在离根节点近的地方，词频小的远离根节点。如此词频大的词只需要很少的比较次数，路径就结束了，计算次数比较少。
6、由于是根据词频来构建哈夫曼树，所以一开始这课树的结构就是已经确定的，每个叶子节点对应的单词也是已知的，换言之根节点到目标节点的路径包括中间节点、向左还是向右也是已知的，每个中间节点对应的向量的形状已经定好了，并不是真的需要每次都要判断向左走还是向右走。后续优化时只需要更新中间节点对应的向量、词向量即可。
