Hierarchical Softmax for Word2Vec
What you'll learn: An efficient alternative to negative sampling that uses a binary tree structure to drastically reduce the computational cost of training Word2Vec models.
The Computational Problem
Remember that in standard Word2Vec, we need to compute probabilities over the entire vocabulary. With vocabularies of 50,000+ words, calculating the full softmax for every training example becomes prohibitively expensive—we'd need to compute scores for all 50,000 words just to predict one target word.
The Binary Tree Solution
Hierarchical softmax replaces the flat output layer with a binary tree where:
- Each leaf node represents a word in your vocabulary
- Each internal node has learned parameters (like a mini binary classifier)
- The path from root to leaf represents a sequence of binary decisions
Instead of computing one probability across 50,000 words, you compute roughly log₂(50,000) ≈ 16 binary decisions. This transforms the complexity from O(V) to O(log V), where V is vocabulary size.
How It Works
Think of it like playing "20 Questions" to guess a word:
- At each node, ask: "Is the target word in the left subtree or right subtree?"
- Train the model to make correct left/right choices at each step
- The probability of a word is the product of probabilities along its path
For example, if "cat" is reached by going left→right→left, you'd compute:
P(cat) = P(left at root) × P(right at node2) × P(left at node5)
Each binary decision uses a sigmoid function, making the math simple and fast.
Why This Matters
Hierarchical softmax was crucial for making Word2Vec practical on large vocabularies before GPUs became ubiquitous. While negative sampling is more popular today, hierarchical softmax is still valuable when you need exact probabilities or have extremely large vocabularies.
Key Takeaway: Hierarchical softmax reduces Word2Vec's output complexity from linear to logarithmic by organizing vocabulary into a binary tree, computing word probabilities as products of binary decisions along tree paths.