Hierarchical Softmax › Path Probability: The Mathematics

With the tree structure defined, we can now write the probability formula precisely. The key insight is that the probability of a word equals the product of probabilities of all correct binary decisions along its path from root to leaf.

Each internal node $n$ has a learned vector $\mathbf{v}_n$ of the same dimension as the word embeddings. To make the left-right decision at node $n$, we compare this node vector with the current context embedding $\mathbf{h}$ using a dot product, then pass the result through the sigmoid function:

$$\sigma(\mathbf{v}_n \cdot \mathbf{h}) = \frac{1}{1 + \exp(-\mathbf{v}_n \cdot \mathbf{h})}$$

where:

• $\sigma(\cdot)$: the sigmoid function, mapping any real number to $(0, 1)$
• $\mathbf{v}_n$: the learned vector at internal node $n$
• $\mathbf{h}$: the context embedding (center word's input embedding)

This output gives the probability of going left. The probability of going right is $1 - \sigma(\mathbf{v}_n \cdot \mathbf{h}) = \sigma(-\mathbf{v}_n \cdot \mathbf{h})$. These two always sum to 1, which is what ensures the tree defines a valid probability distribution.

Why the sigmoid function specifically? The sigmoid maps real numbers to the interval $(0, 1)$, making it a natural candidate for probabilities. More importantly, the symmetry property $\sigma(-x) = 1 - \sigma(x)$ means we can encode both the "go left" and "go right" probabilities using a single dot product and a sign flip. This symmetry is exploited compactly in the path probability formula.

The probability of word $w$ given context embedding $\mathbf{h}$ is the product of probabilities at each decision point along the root-to-leaf path:

$$P(w | \mathbf{h}) = \prod_{j=1}^{L(w)-1} \sigma\!\left( d_j \cdot \mathbf{v}_{n(w,j)} \cdot \mathbf{h} \right)$$

where:

• $L(w)$: the total number of nodes along the path from root to word $w$ (including root and leaf)
• $n(w, j)$: the $j$-th node along the path to $w$, with $n(w, 1)$ being the root
• $d_j \in \{+1, -1\}$: the direction code at step $j$, equal to $+1$ if the next node is the left child and $-1$ if it is the right child
• $\mathbf{v}_{n(w,j)}$: the learned vector at the $j$-th internal node
• $\mathbf{h}$: the context embedding

The direction encoding $d_j$ is the key mechanism. When $d_j = +1$ (go left), we compute $\sigma(\mathbf{v} \cdot \mathbf{h})$, which is high when the dot product is positive. When $d_j = -1$ (go right), we compute $\sigma(-\mathbf{v} \cdot \mathbf{h})$, which is the complementary probability. This compact encoding lets a single formula handle both directions without needing two separate parameters per node.

For a vocabulary of 100,000 words, a Huffman tree assigns paths of roughly 15 to 20 nodes. The final probability is a product of 15 to 20 sigmoid values, each between 0 and 1. Even if each step has probability 0.8, the product of 17 steps is $0.8^{17} \approx 0.0225$. This is expected behavior: 100,000 words share probability mass, so individual word probabilities must be small. The model is not failing; it is correctly distributing probability across a large vocabulary.

Working in log space helps numerically. Instead of multiplying probabilities (which can underflow to zero for long paths), we sum log-probabilities. This is numerically stable and is the natural form for the loss function we will derive below.