High-Dimensional Outputs · Combining with n-grams

§12.4.3 High-dimensional outputs

When the output is a word, the vocabulary $V$ may hold hundreds of thousands of entries — and a naive softmax over all of them is crushing:

The affine-softmax output layer (eqs 12.8–12.9)

a_i = b_i + \sum_j W_{ij} h_j, \qquad \hat y_i = \frac{e^{a_i}}{\sum_{i'=1}^{|V|} e^{a_{i'}}}, \qquad \text{cost } = O(|V|\,n_h)

$a_i = b_i + \sum_j W_{ij} h_j$	a score for word i — an affine map of the top hidden vector h	score per word
$W$	the output weight matrix, \|V\| × nₕ — huge memory and compute when \|V\| is hundreds of thousands	\|V\|×nₕ
$\sum_{i'} e^{a_{i'}}$	softmax normalizes over ALL \|V\| words, so the full matrix multiply is needed even at test time	normalizer
$O(\|V\|\,n_h)$	dominates the computation of most neural language models — you cannot compute only the correct word's score	cost

The normalizer is the villain

To report the probability of even one word, the denominator needs the score of every word. Put small real numbers in: $|V| = 100{,}000$ words and $n_h = 512$ make $W$ alone $51.2$ million parameters, and every single prediction spends $51.2$ million multiply-adds in this one layer — usually more than the entire rest of the network combined. Every trick below attacks the same enemy: the sum over the full vocabulary.

Four families of tricks tame this cost:

Handling a large output vocabulary — click a cell for the tradeoff.
	How it works	Tradeoff
Short list	neural net predicts the frequent words; an n-gram model handles the rare tail	generalization limited to frequent words
Hierarchical softmax	tree of word classes; probability = product of binary decisions along the path	O(log\|V\|); helps train AND test
Importance sampling	estimate the negative-phase gradient from negatives sampled from a proposal q	speeds TRAINING only; cost ∝ #samples
Ranking loss / NCE	margin between the correct score and negatives, or noise-contrastive estimation	ranking gives scores, not probabilities

Dotted-underlined cells have explanations — click one.

Hierarchical softmax

Arrange words as the leaves of a tree of nested categories. A word’s probability is the product of the binary (left/right) decisions along its root-to-leaf path — so evaluating it costs $O(\log|V|)$ logistic decisions, not $O(|V|)$ . Click a word to trace its path, and grow the vocabulary to see the gap widen:

Fig 12.4 (interactive) — hierarchical softmax. 8 words at the leaves of a depth-3 tree; a word's probability is the product of the 3 binary decisions on its path (≈ log₂|V|), versus one score per word for a flat softmax.

w4: path = R→L→L, so P(w4) = 0.45 × 0.45 × 0.65 = 0.132 — just 3 logistic decisions (≈ log₂|V|), not one score per word.

vocabulary |V| = 10,000

flat softmax: O(|V|) = 10,000 ops/word

hierarchical: O(log₂|V|) ≈ 14

A logistic regression at each node predicts its decision (all sharing the same context $C$ ), trained by cross-entropy. Even a depth-2 tree — a flat set of word classes — captures most of the benefit. How best to build the tree (or learn it) remains open, since the choice is discrete and not gradient-friendly.

Importance sampling and ranking losses

The softmax gradient splits into a positive phase (push the correct word’s score up) and a negative phase (push every other word’s score down, weighted by its probability) — and the negative phase is an expectation, so we can estimate it by importance sampling from a cheap proposal $q$ (a unigram/bigram) instead of computing all $|V|$ scores. An alternative avoids probabilities entirely — a ranking loss that just makes the correct word outscore the negatives:

Ranking loss (eq 12.19)

L = \sum_i \max\!\big(0,\ 1 - a_y + a_i\big)

$a_y$	the score of the correct (observed) word	positive
$a_i$	the score of a negative (incorrect) word	negative
$\max(0,\ 1 - a_y + a_i)$	zero once the correct word beats the negative by a margin of 1; otherwise a penalty	hinge

Worked example — two negatives, one margin

Say the correct word scores $a_y = 2.5$ . A negative scoring $a_i = 0.9$ contributes $\max(0,\ 1 - 2.5 + 0.9) = \max(0, -0.6) = 0$ — it is already beaten by more than the margin of 1, so its gradient is zero and it costs nothing. A negative scoring $a_i = 3.1$ contributes $\max(0,\ 1 - 2.5 + 3.1) = 1.6$ — a live penalty pushing $a_y$ up and $a_i$ down. Training effort concentrates on the negatives that are still competitive.

Its downside: it produces scores, not conditional probabilities (needed for speech and translation). Noise-contrastive estimation (§18.6) is a probabilistic alternative.

§12.4.4 Combining neural language models with n-grams

A neural net’s compute grows with its parameter count; an n-gram model has huge capacity (many stored tuple frequencies) at almost no per-example cost (a few lookups). So ensemble them — the combination reduces test error when the two make independent mistakes. One can even train a neural net jointly with a maximum-entropy model whose extra inputs are sparse n-gram indicators connected directly to the output: enormous added capacity ( $|sV|^n$ parameters) for minimal extra computation, since those inputs are very sparse.

Fig — a neural LM trained jointly with a maximum-entropy model. The same context feeds a dense hidden path (left) and a huge set of sparse n-gram indicator features wired directly to the output (right): enormous added capacity for almost no added compute, because only the few indicators matching the current context are non-zero.

Next: putting it together for translation — the encoder–decoder and attention — neural machine translation and other applications.

Check yourself — high-dimensional outputs and combining with n-grams

1.Why is a softmax output layer over a large vocabulary so expensive?

2.What is the 'short list' approach to a large output vocabulary?

3.How does hierarchical softmax reduce output cost? (See the HierSoftmaxLab.)

4.How does importance sampling speed up training a large-softmax language model?

5.What does the ranking loss L = Σᵢ max(0, 1 − a_y + aᵢ) do, and what is its limitation?

6.Why combine a neural language model with an n-gram model?

6 questions