Course contentsShow
← Machine Learning and Deep Learning
Lesson 1122 of 3,53825. Word Embeddings and Contextual RepresentationsFree lesson

Hierarchical Softmax for Word2Vec

Learn the alternative hierarchical softmax approach that uses a binary tree to reduce computational complexity.

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.