Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Hierarchical Softmax › Gradient Computation Along Paths

Michael BrenndoerferUpdated February 8, 20265 min read

Language AI HandbookAll chapters

Part 4 of 67Word Embeddings

Chapter 22Hierarchical Softmax › Gradient Computation Along Paths

Reading section 7 of 16 · Gradient Computation Along Paths · 5 minSection 7 of 16 · 5 min

Section 7 of 16 · 5 min read

Hierarchical Softmax › Gradient Computation Along PathsOne section · Sections in this chapter7 / 16 ↓

Sections in this chapter16

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The gradients needed for training involve two sets of parameters: the node vectors $\{\mathbf{v}_n\}$ at internal nodes, and the input embeddings $\mathbf{h}$ (which is the embedding of the center word, and also affects embeddings of context words in the general formulation).

Gradient for a Single Node VectorLink Copied

For a single internal node $n_j$ at step $j$ along the path, the loss contribution is:

\mathcal{J}_j = -\log \sigma(d_j \cdot \mathbf{v}_j \cdot \mathbf{h})

Let $s_j = d_j \cdot \mathbf{v}_j \cdot \mathbf{h}$ denote the signed dot product at step $j$ . Then $\mathcal{J}_j = -\log \sigma(s_j)$ .

Using the identity $\frac{d}{dx}\log \sigma(x) = 1 - \sigma(x) = \sigma(-x)$ , we can derive the gradient of $\mathcal{J}_j$ with respect to the node vector $\mathbf{v}_j$ by applying the chain rule:

\begin{aligned} \frac{\partial \mathcal{J}_j}{\partial \mathbf{v}_j} &= -\frac{\partial}{\partial \mathbf{v}_j} \log \sigma(s_j) \\ &= -(1 - \sigma(s_j)) \cdot \frac{\partial s_j}{\partial \mathbf{v}_j} \\ &= -(1 - \sigma(s_j)) \cdot d_j \cdot \mathbf{h} \\ &= \left(\sigma(s_j) - 1\right) d_j \mathbf{h} \end{aligned}

where:

$\sigma(s_j)$ : the current sigmoid output at node $j$ (the model's current left-probability)
$1 - \sigma(s_j)$ : the error at this node, measuring how far from certainty the current prediction is
$d_j$ : direction code, propagating sign for left vs right
$\mathbf{h}$ : context embedding, which provides the gradient direction in embedding space

When the model makes a correct and confident prediction at node $j$ (say $\sigma(s_j)$ is close to 1 when $d_j = +1$ ), the error term $\sigma(s_j) - 1$ is near zero and the gradient is small. When the prediction is wrong or uncertain, the error term is large and the gradient drives a substantial update. This is the same feedback mechanism used in logistic regression.

Gradient for the Context EmbeddingLink Copied

The gradient of the total path loss with respect to the context embedding $\mathbf{h}$ accumulates contributions from every node along the path:

\frac{\partial \mathcal{J}}{\partial \mathbf{h}} = \sum_{j=1}^{L(w_o)-1} \left(\sigma(s_j) - 1\right) d_j \mathbf{v}_j

where the sum runs over all $L(w_o) - 1$ internal nodes on the path to the target word $w_o$ .

This gradient tells us how to adjust the center word's embedding. Each internal node on the path contributes a term proportional to its error $(\sigma(s_j) - 1)$ , scaled by its direction code and node vector. Only nodes along the specific path to the target word contribute: nodes off the path have zero contribution to this gradient. This locality is what makes training efficient. A single training step for predicting word $w$ only requires reading and updating $\log_2 V$ node vectors, not all $V$ word vectors.

The locality also has an important consequence for what the model learns. The center word's embedding is updated in a direction that incorporates the geometry of all the node vectors along the path to the observed context word. This means the embedding is shaped by the cumulative evidence from every binary decision on the path. A single output vector cannot provide this cumulative signal. In practice, this often produces embeddings that capture hierarchical semantic structure, since semantically related words tend to share subtrees in a well-constructed tree.

In[13]:

Code

import numpy as np


def sigmoid(x):
    return np.where(x >= 0, 1 / (1 + np.exp(-x)), np.exp(x) / (1 + np.exp(x)))


def hs_loss_and_gradients(h, path_vectors, path_directions):
    """
    Compute hierarchical softmax loss and gradients.

    Args:
        h: Context embedding (dim,)
        path_vectors: Node vectors along the path
        path_directions: +1 for left, -1 for right

    Returns:
        loss: Negative log-probability
        grad_h: Gradient w.r.t. h
        grad_nodes: List of gradients w.r.t. each node vector
    """
    loss = 0.0
    grad_h = np.zeros_like(h)
    grad_nodes = []

    for v, d in zip(path_vectors, path_directions):
        s = d * np.dot(v, h)
        sig_s = float(sigmoid(s))
        # Loss: -log σ(s)
        loss += -np.log(sig_s + 1e-12)
        # Error at this node: σ(s) - 1
        error = sig_s - 1.0
        # Gradient for node vector v
        grad_v = error * d * h
        grad_nodes.append(grad_v)
        # Accumulate gradient for h
        grad_h += error * d * v

    return loss, grad_h, grad_nodes


np.random.seed(99)
dim = 50
h = np.random.randn(dim) * 0.3
path_vecs = [np.random.randn(dim) * 0.3 for _ in range(4)]
path_dirs = [1, -1, -1, 1]

loss, grad_h, grad_nodes = hs_loss_and_gradients(h, path_vecs, path_dirs)

Out[14]:

Console

Hierarchical Softmax: Loss and Gradients
--------------------------------------------------
Path length:          4 decisions
Total loss:           3.5567
||grad_h||:           2.3153

Per-node gradients:
 Node  Direction   ||grad_v||
--------------------------------
    1       left       1.0372
    2      right       1.4054
    3      right       1.2050
    4       left       1.1646

The gradient norms reveal which nodes are receiving the largest updates. Nodes where the model made more uncertain or wrong decisions (larger error term $|\sigma(s_j) - 1|$ ) receive larger gradient updates. As training progresses, the model learns to make these decisions more confidently, reducing the loss at each node and causing the gradients to shrink toward zero.