liveBook · Manning

Hierarchical softmax

As explained in Retrieval Augmented Generation, The Foundational Ideas

Hierarchical softmax computes vocabulary probabilities through paths in a binary tree instead of evaluating every vocabulary item directly.

Hierarchical softmax computes vocabulary probabilities by replacing a flat choice among every word with a walk through a binary tree. Instead of scoring roughly one million vocabulary items, training makes about twenty binary decisions along a path. section 2.1.2

The technique addresses the normalization bottleneck in Word2Vec: probabilities must sum to one across the entire vocabulary, making each training step expensive for large word-level vocabularies. It is an alternative to negative sampling, which avoids probabilities and asks a small number of yes-or-no classification questions instead. section 2.1.2 section 2.1.5

From dictionary scan to tree walk

A vocabulary of 692,000 words would require summing across all words under the flat formulation. Hierarchical softmax follows a binary-tree path of roughly twenty decisions, like playing “20 Questions” instead of reading the dictionary line by line. section 2.1.2

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains the computational bottleneck and tree-walk substitution, but does not detail tree construction or probability equations.
Examples
Uses a 692,000-word vocabulary and a “20 Questions” analogy to contrast flat normalization with tree-based computation.
What it assumes
Assumes understanding that softmax probabilities must normalize across the vocabulary and that Word2Vec learns word vectors.
What you can do after
Evaluate hierarchical softmax as a large-vocabulary training approximation and contrast it with negative sampling.
How it connects
Connects hierarchical softmax to Word2Vec, negative sampling, CBOW, skip-gram, and dense embeddings.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.