hierarchical softmax：把 Huffman 树搬进神经网络
训练 word2vec 这类模型时，每一步都要算一个 softmax：给词表里每一个词打分再 normalize，选出「下一个词是谁」。词表动辄几十万、上百万，这一步 O(V) 的开销极为高昂。hierarchical softmax 的解法，正是本系列反复出现的结构——一棵 Huffman 树（建法见动手建树一页）。
核心改写： 把「从 V 个词里一次选一个」，换成「沿一棵二叉树走 log V 步，每步只做一次二选一」。词放在 leaf node；每个内部 node 是一个二分类器 ，输出「往左还是往右」的概率。于是 P（某个词）= 沿它那条根→叶路径上，每一步二选一概率的乘积。每次预测 / 更新只碰路径上的 ≈log V 个 node，不再是全部 V 个。
1 · 动手：点一个词，观察它的「路径 = 决策序列」
下面用一个小词表（词:频率）建 Huffman 树。点任意词，高亮它的根→叶路径：路径上每条边的 0/1 就是该层分类器「往左 (0) / 往右 (1)」的决策，路径长度 = 要算几次 σ。对比扁平 softmax 要算的 V 次，差距一目了然。
2 · 那「概率」是怎么来的？——一串 σ 相乘，自动 normalize
给每个内部 node 一组（这里是随机示意的）分类器参数，记它「往右走」的概率为 r、往左为
。某个词的概率 = 沿路径把这些 r /
连乘起来。关键性质在于：因为每个 node 左右概率天然和为 1，所有 leaf node（词）的概率自动加起来正好 = 1——不需要再对 V 个词做一次 normalize，省掉的正是那 O(V)。点「换一组参数」反复验证这个「和恒为 1」。
3 · 为什么是 Huffman 树，而不是任意一棵平衡树？
用平衡树，每个词路径都 ，无论高频低频一视同仁。但训练时高频词被访问得最频繁——让它们路径短，总计算量才最省。「期望每步计算量」正是 ∑（词的 frequency × 路径长度），最小化它的，就是 Huffman 那个 greedy。这和压缩里的 ∑（frequency × codeword 长度）、石子合并里的 ∑（大小 × 深度） 是同一笔账——只不过这次，「省下来的」是 GPU 的乘加。
顺带： 它和 word2vec 的另一种做法 negative sampling 是并列的两种「避开 O(V)」思路——hierarchical softmax 用树把一次大选择拆成 log V 次小选择；negative sampling 则干脆只更新少数几个负样本。
边界： hierarchical softmax 主要加速训练（只更新路径上的 node）。要在推理时获得完整分布或做 argmax，并非 O(log V) 即可完成（需遍历 / 束搜索）。如今 GPU 上常直接算全 softmax 或用采样近似，hierarchical softmax 是 word2vec 时代处理超大词表的经典手法——而它的骨架，依旧是这棵 Huffman 树。
4 · 整个系列，一棵树的三种读法
同一棵「按 frequency 建、高频靠根」的 Huffman 树，换三种视角：
- 压缩：深度 = codeword 长度，最小化总 bit 数。
- 石子合并：深度 = 被合并次数，最小化总代价。
- hierarchical softmax：深度 = σ 计算次数，最小化期望计算量。
greedy 完全不变，变的只是「深度」在那个场景里对应的成本。