Hierarchical Softmax › Summary

Hierarchical softmax solves the computational bottleneck of standard softmax by reorganizing vocabulary prediction into a sequence of binary decisions along a binary tree. The key ideas are:

• Binary tree decomposition: The probability of any word is computed as a product of sigmoid decisions along its root-to-leaf path, reducing complexity from $O(V)$ to $O(\log V)$. The tree structure ensures all leaf probabilities sum to 1 without any explicit normalization step.
• Huffman coding: Assigns shorter paths to frequent words, minimizing the expected path length weighted by training frequency and concentrating cheaper computations on the most common words. The expected path length equals the Shannon entropy of the frequency distribution, which is theoretically optimal.
• Node vectors: Each internal node has a learned vector that parameterizes the left-right decision at that node. These vectors, combined with sigmoid activations, produce valid conditional probabilities. They encode discriminative boundaries between vocabulary subsets, not word-level semantic representations.
• Path probability formula: $P(w | \mathbf{h}) = \prod_{j=1}^{L(w)-1} \sigma(d_j \cdot \mathbf{v}_j \cdot \mathbf{h})$, where $d_j \in \{+1, -1\}$ encodes the direction at each step and ensures complementary probabilities sum to 1.
• Gradient locality: Only node vectors along the target word's path receive gradient updates per training step, making each update efficient and local. The center word embedding accumulates contributions from every node on the path, capturing hierarchical semantic structure through the path geometry.
• Trade-offs vs negative sampling: Hierarchical softmax produces a valid probability distribution and benefits from frequency skew via Huffman coding, while negative sampling is simpler to implement, requires fewer operations per step at common vocabulary sizes, and often produces embeddings with slightly better semantic quality for downstream tasks.
• Historical impact: Together with negative sampling, hierarchical softmax made billion-word training runs practical for the first time, enabling the word2vec embeddings that transformed how NLP researchers think about word representations and set the stage for scaling as a primary research strategy.

The next chapter on Word2Vec training covers how these approximation methods fit into a complete training pipeline, including subsampling of frequent words, learning rate scheduling, and the practical differences between training with hierarchical softmax and negative sampling on real corpora.