Do leaf probabilities sum to one?

Yes, when each internal branching distribution is normalized and the leaves represent the complete output set.

Must the tree be binary?

No. Binary trees are common, but branching can use more than two children with normalized local probabilities.

Does greedy branch selection always return the most probable label?

No. A lower-probability subtree can contain a leaf with a larger total path probability than any leaf in the other subtree.

AI Glossary / Probabilistic machine learning / Intermediate

Hierarchical softmax

Definition

Hierarchical softmax represents a probability distribution over many output classes by arranging them as leaves of a tree and multiplying conditional branch probabilities along each root-to-leaf path. It can calculate the probability and training loss of a selected class without evaluating every class score.

What it means

A language model may need to assign probabilities to a large vocabulary. A conventional flat softmax normalizes scores across all vocabulary entries, which can be expensive. Hierarchical softmax replaces that single large normalization with a sequence of smaller decisions.

In a binary tree, each internal node predicts which of its two subtrees contains the output. Multiplying those decisions' probabilities gives a leaf probability. The resulting leaf probabilities sum to one when the branches are normalized and the tree covers the outputs properly. It is an alternative parameterization, not a promise to reproduce the probabilities of any particular flat-softmax model exactly.

How it works

Choose a tree whose leaves correspond to output labels. For a given context representation, each visited internal node produces a branch probability, commonly using a sigmoid of a learned score. The opposite branch receives the complementary probability. A target label has a known path through the tree.

The target probability is the product of its path probabilities. Its negative log probability is therefore the sum of the branch-level negative log probabilities, allowing training updates along that path. Other output paths need not be evaluated to compute this single target's loss.

A balanced binary tree has logarithmic path depth in the number of leaves. Frequency-based trees, such as Huffman trees, can place common labels on shorter paths and reduce expected work under the assumed frequencies. Computing every leaf probability still requires substantially more work than evaluating one path. Tree structure affects both computation and what the model must learn at each branch.

Three practical examples

1. Word representation training: predict a context word through a vocabulary tree. Compare representation quality as well as throughput, since different output objectives can produce different learned vectors.

2. Large-label classification: compute probabilities for selected candidate labels using their paths. The hierarchy need not correspond to a perfect semantic taxonomy, but it should be evaluated for the application's label distribution.

3. Probabilistic sampling: generate an output by sampling a branch at each node until reaching a leaf. This uses the tree distribution directly rather than normalizing a full list of leaf scores on every draw.

Think of it this way

Think of reaching a destination through a sequence of signposted junctions. The probability of arriving at one destination is the product of the probabilities of taking its required turns. The analogy describes path factorization. A tree branch need not have a human-understandable meaning, and choosing the most likely turn at every junction need not find the most likely final destination.

Worked example

Consider four outputs A, B, C and D. The root puts probability 0.6 on the left subtree containing A and B, and 0.4 on the right subtree containing C and D. Within the left subtree, the probabilities are 0.5 for A and 0.5 for B. Within the right subtree, they are 0.9 for C and 0.1 for D.

The leaf probabilities are P(A)=0.6 × 0.5=0.30, P(B)=0.30, P(C)=0.4 × 0.9=0.36 and P(D)=0.4 × 0.1=0.04. They sum to one. For target C, the negative log likelihood is -log(0.4)-log(0.9)=-log(0.36), approximately 1.02165 nats.

A greedy procedure that always takes the higher-probability branch would choose the left subtree at the root, then A or B, each with probability 0.30. It would miss the most probable leaf C at 0.36. Thus efficient evaluation of a specified leaf and efficient exact search for the highest-probability leaf are different tasks. These probabilities are illustrative, not learned.

Illustrative case study

Fictional case: Cedar Search tests a tree-based output layer for a large set of document labels. Its engineers initially report shorter training updates as if they guaranteed equally fast production ranking. The product, however, needs several likely labels for each document rather than the probability of one known label.

The team measures its actual search procedure, tests whether it misses high-probability leaves and reviews performance on rare labels. It also checks whether label frequencies have shifted since the tree was built. This fictional case illustrates workload-specific evaluation, not a universal speed or accuracy claim.

Common misconceptions and mistakes

Hierarchical softmax is not the same as negative sampling. The former defines normalized leaf probabilities through a tree; negative sampling uses a different training objective. The tree also need not reproduce an existing business taxonomy, and a frequency-efficient tree is not necessarily semantically intuitive.

Logarithmic work refers to a suitable path structure for a selected output, not automatically to listing all probabilities or finding every top-ranked class. Long paths can remain for some labels in an unbalanced tree. A locally uncertain branch affects every leaf beneath it, so errors and representational limitations can propagate through the hierarchy.

Business use

Consider hierarchical softmax when the output space is large and the actual workload benefits from path-based probability calculations. Measure training, sampling and ranking separately. Include tree construction, changes to the label set and the cost of maintaining the hierarchy in the operational comparison.

Evaluate calibration and quality across frequent and rare labels, not just average throughput. Record whether deployment uses exact search, approximate search or greedy traversal. If probabilities inform downstream decisions, ensure that users understand what was evaluated and how candidates were selected; a normalized distribution does not guarantee that a search procedure found its best outputs.

Check your understanding

Why is C the most probable output even though its root branch has probability only 0.4?

Answer: Most of that branch's mass goes to C: 0.4 × 0.9=0.36. The left branch splits its 0.6 equally into leaves of probability 0.30.

Related terms

Softmax
Conditional probability
Negative sampling
Language model
output vocabulary
binary tree
Huffman coding
tree search

Learn next

Build a four-leaf probability tree and verify normalization and path losses. Next compare balanced and frequency-based trees, then distinguish computing one target probability from sampling and exact top-label search.

Sources

Morin and Bengio, Hierarchical Probabilistic Neural Network Language Model: https://proceedings.mlr.press/r5/morin05a/morin05a.pdf

Mikolov and colleagues, Distributed Representations of Words and Phrases and Their Compositionality, section 2.1: https://arxiv.org/pdf/1310.4546

Independent review consulted Morin–Bengio section 3 and Mikolov section 2.1 on path factorization, normalization and Huffman trees. Original leaf probabilities and loss verified; case fictional.

Previous: Hierarchical (sequential) sums of squares Next: Hierarchical temporal memory