上一期介绍了word2vec中的模型更新优化的比较“弱”的形式NEGATIVE SAMPLING。这一期将推出另一种优化方案，Hierarchical Softmax。
Hierarchical Softmax
我们的目标是加速project->output层的计算。下图描述了新的project->output层情况
回到我们的初衷，我们的目的是对于一个输入词，把周围词作为输出词，期待输出词的值是最大的。
假设我们期待的输出词（答案）是\(w_2\)(不是权值矩阵 \(w2\))。那么我们扔一个小球从root开始，有向左滚概率0.8，向右0.2，然后继续滚，最后总会滚到低，我们期望滚到\(w_2\)洞的概率最大。
图示的情况下，滚到\(w_2\)的概率为0.80.40.7，显然滚到所有洞的概率和为1。
明确每个部分的含义：
每个白色节点是一个球洞，代表了滚到这个词。
每个黑色节点是一个H维向量，替代了之前的权值矩阵 \(w2\)。给个新表示\(v_1,v_2,....\)).
再起个别名n(w, j) means the j-th unit on the path from root to the word w.
每条边为一个概率，表示球滚到父亲节点时，往这条边滚的概率。
往左边滚的概率是
$$ p(n, left) = σ（v_i^Th） $$
，往右是
$$ 1-σ（v_i^Th） $$
其中\(v_i\)是父亲节点的表示H维，h为hidden层的表示H维。σ为sigmoid函数。
再考虑下更新的逻辑
forward
$$ p=σ（[*]n(w, 1)^Th)*σ（[*]n(w, 2)^Th)....其中[*]表示向左走取+1，向右走取-1 $$
backward
$$ E=loss=-log p $$
可以发现这里的累乘其实是变量独立的，并不是recursive neural network那种，对p中各变量n(w, i)(写作\(v_i\))取导数后,
$$ \frac{\partial E}{\partial v_i^Th}=σ( v_i^Th)-t_j $$
其中
$$ [*]=+1时,t_j=1,[*]=-1时,t_j=0 $$
对权重变量求导
$$ \frac{\partial E}{\partial v_i}=(σ( v_i^Th)-t_j)*h $$
可以发现最终更新变量\(v_i\)时，只和它的output error有关，和其他权重变量无关。所以在实际计算时，我们可以像NEGATIVE SAMPLING一样，计算projection->output中的一列（就是只用一个\(v_i\)），然后求导更新。
代码分析
for (d = 0; d < vocab[word].codelen; d++) {
f = 0;
l2 = vocab[word].point[d] * layer1_size;
// Propagate hidden -> output
for (c = 0; c < layer1_size; c++) f += neu1e[c] * syn1[c + l2];
g= 输出层错误 \partial E / \partial v_i^T*h
// Learn weights hidden -> output
for (c = 0; c < layer1_size; c++) syn1[c + l2] += g * neu1e[c];
}在for循环中 vocab[word].point[d] 记录了单词word在权重变量（projection->output）(上面的那棵树)中具体经过的子节点，即n(word, i)。
syn1 ：在前一篇文章中也提到 是\(w2\)即现在上图中的黑色节点的集合，然后把两维拉成了一维。
l2 = vocab[word].point[d] * layer1_size 计算了这个词每个经过节点在syn1数组中的开始地址。
在上面分析中提到过，每个节点n(word, i)的更新和其他节点无关。再看次模型更新
$$ \frac{\partial E}{\partial v_i}=(σ( v_i^Th)-t_j)*h $$
我们只需要计算 \(v_i^Th\) 乘积,计算error,然后乘以h即可。这三部对应接下来的三行程序。
for (c = 0; c < layer1_size; c++) f += neu1e[c] * syn1[c + l2];计算 \(v_i^Th\) 乘积，neu1e即h。
g= 输出层错误 \partial E / \partial v_i^T*h计算了输出层错误*学习速率。
for (c = 0; c < layer1_size; c++) syn1[c + l2] += g*neu1e[c];neu1e即h。符合上面公式的推导。
Hierarchical Softmax 速度分析
由于现在的\(w2\)变成了一个完全二叉树，更新的节点为树高，故为log(2,V).
如果V=30000,那现在只需要进行 大约15次。 比原来大约快2000倍。
也就是说用了以后能单机跑，不用就要分布式了。
Hierarchical Softmax 讨论
这个方法可以看成一种改进的softmax方法，原来每个节点的值都依赖于所有其他节点的值，而现在只依赖于一些节点的值。使得模型的计算变得非常高效。
但是它并不比NEGATIVE SAMPLING来得好，原因是，它对V的树状分层其实是随机的，这不像是决策树，最root的分叉是最有效的，因此这只是一种类似于人为缩减更新数量的方法，和NEGATIVE SAMPLING本质无异。只是听上去厉害好多啊！
