--- title: Smoothing and Backoff module: Foundations moduleNumber: 1 lessonNumber: 5 order: 105 summary: > Every finite corpus is missing good word sequences it simply never saw, so a raw n-gram model assigns them probability zero and breaks. Smoothing repairs the zeros: add-one and add-k shave mass off seen events, backoff and interpolation fall back on shorter contexts, and Kneser-Ney — worked here by hand — replaces raw frequency with how many contexts a word completes. We close on web-scale stupid backoff and the neural models that dissolve the zero problem rather than patch it. topics: [Foundations] sources: - book: Jurafsky ref: "§3.3 Generalization and Zeros; §3.4–3.5 Unknown Words and Smoothing; §3.6 Kneser-Ney" - book: Jurafsky ref: "§3.7 Huge Language Models and Stupid Backoff" --- This builds on [N-Gram Language Models](/natural-language-processing/foundations/n-gram-language-models), which set up the model — factor a sequence by the chain rule, truncate the history with the Markov assumption, estimate each conditional by counting, and score with perplexity. That model works until the test set contains a word sequence the training corpus never included; then the count is zero, the probability is zero, and perplexity is undefined. This lesson is about that failure and its repair. ## Generalization and the zero problem An n-gram model is a mirror of its training corpus. That has two consequences. Higher $n$ models the training text more and more faithfully — sample from a $4$-gram trained on Shakespeare and you get fragments that are nearly verbatim Shakespeare, because with $V = 29{,}066$ word types there are $V^2 \approx 8.4 \times 10^8$ possible bigrams and his entire corpus is only $N = 884{,}647$ words, so most n-grams that _do_ occur occur exactly once and have only one continuation. The model has memorized rather than generalized. The flip side is fragility across genres. An n-gram grammar trained on Shakespeare generates nothing resembling the Wall Street Journal, and vice versa. A model only works on text like its training data, which is why matching the **genre** and dialect of the training corpus to the intended task matters. But the deeper problem is **sparsity**: any finite corpus is missing perfectly good word sequences that simply never appeared. Consider the bigram _denied the_ in a news corpus, with the continuations actually seen: ``` denied the allegations 5 denied the speculation 2 denied the rumors 1 denied the report 1 ``` If the test set contains _denied the offer_ or _denied the loan_, the model estimates $P(\texttt{offer} \mid \texttt{denied the}) = 0$ — a **zero**. These zeros are harmful for two reasons. They understate the probability of everything that could legitimately occur, hurting any downstream task. And worse, a single zero anywhere in the test set makes the whole test-set probability zero, so perplexity is undefined — you cannot divide by zero. A usable model cannot assign zero probability to unseen but possible events. ### Unknown words A related gap is words never seen at all — **out-of-vocabulary** (OOV) words. In a **closed vocabulary** task (say, a speech recognizer with a fixed pronunciation dictionary) this cannot arise. Otherwise we build an **open vocabulary** by adding a pseudo-word ``: fix a vocabulary in advance (or keep only words above a frequency threshold), replace every other word in the training data with ``, and then estimate ``'s probability from its counts like any ordinary word. Because a model can lower its perplexity by shrinking the vocabulary and loading probability onto ``, perplexities are only comparable across models with identical vocabularies. ## Smoothing **Smoothing** (or **discounting**) is the family of fixes for the zero problem: shave a little probability mass off the events the model _has_ seen and redistribute it to the events it has not, so nothing gets exactly zero.[^jm-smooth] The name comes from the picture — flattening a spiky count distribution so the sharp zeros fill in. ### Laplace (add-one) smoothing The simplest scheme adds one to every count before normalizing. For unigrams, the MLE $P(w_i) = c_i / N$ becomes, after adding $1$ to each of the $|V|$ word counts and adjusting the denominator by $|V|$ so the probabilities still sum to one, $$ P_{\text{Laplace}}(w_i) = \frac{c_i + 1}{N + |V|}. $$ For bigrams, the prefix count $C(w_{i-1})$ in the denominator must likewise be augmented by $|V|$, because every one of the $|V|$ possible following words has gained a phantom count: $$ P^\ast_{\text{Laplace}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i) + 1}{C(w_{i-1}) + |V|}. $$ It helps to see the effect through the **adjusted count** $c^\ast$ — the smoothed count that, divided by the original denominator, reproduces the smoothed probability. For add-one bigrams, $$ c^\ast(w_{i-1} w_i) = \frac{[C(w_{i-1} w_i) + 1]\, C(w_{i-1})}{C(w_{i-1}) + |V|}. $$ On the Berkeley corpus this adjustment is drastic. The count $C(\texttt{want to})$ falls from $608$ to an adjusted $238$, and $P(\texttt{to} \mid \texttt{want})$ drops from $0.66$ to $0.26$ — a discount of $d_c = c^\ast/c \approx 0.39$. Because $|V| = 1446$ zero cells each gain a phantom count, add-one moves far too much mass onto the zeros. It is a useful baseline and a real method for [text classification](/natural-language-processing/classification/naive-bayes-and-sentiment), but too blunt for serious language modeling. $$ % caption: Smoothing redistributes probability mass. The MLE (left) gives seen bigrams % all the mass and unseen ones zero; smoothing (right) shaves mass from the seen events % (the discount) and spreads it over the previously-zero events so none is exactly zero. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % --- left: MLE --- \draw[->, black] (0,0) -- (4.0,0); \draw[->, black] (0,0) -- (0,2.7); \node[anchor=south, font=\scriptsize] at (2.0,2.55) {MLE}; \foreach \x/\h in {0.5/2.2,1.1/1.5,1.7/0.9} \fill[acc!22, draw=acc] (\x-0.2,0) rectangle (\x+0.2,\h); \foreach \x in {2.3,2.9,3.5} \fill[red!14, draw=red] (\x-0.2,0) rectangle (\x+0.2,0.02); \node[anchor=north, font=\scriptsize, text=black] at (2.9,-0.08) {zeros}; % --- arrow --- \draw[->, black, thick] (4.4,1.3) -- (5.4,1.3); % --- right: smoothed --- \begin{scope}[xshift=5.9cm] \draw[->, black] (0,0) -- (4.0,0); \draw[->, black] (0,0) -- (0,2.7); \node[anchor=south, font=\scriptsize] at (2.0,2.55) {smoothed}; \foreach \x/\h in {0.5/1.85,1.1/1.25,1.7/0.75} \fill[acc!22, draw=acc] (\x-0.2,0) rectangle (\x+0.2,\h); \foreach \x in {2.3,2.9,3.5} \fill[red!14, draw=red] (\x-0.2,0) rectangle (\x+0.2,0.42); \node[anchor=north, font=\scriptsize, text=black] at (2.9,-0.08) {non-zero}; \end{scope} \end{tikzpicture} $$ ### Add-k smoothing A gentler variant adds a fraction $k$ (say $0.5$, $0.05$, $0.01$) instead of a full $1$: $$ P^\ast_{\text{Add-}k}(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i) + k}{C(w_{i-1}) + k|V|}. $$ Choosing $k$ is itself a tuning problem, done on the development set. Add-k is better than add-one for some tasks, but still generates poorly-shaped counts and awkward discounts for language modeling. Better methods use a different idea. ### Backoff and interpolation The idea behind the better methods: when a high-order n-gram has no evidence, fall back on a lower-order one that does. If a trigram $w_{i-2} w_{i-1} w_i$ was never seen, its bigram $w_{i-1} w_i$ or even its unigram $w_i$ probably was. Two ways to use this hierarchy:[^jm-backoff] - **Backoff.** Use the trigram if its count is nonzero; otherwise _back off_ to the bigram; otherwise to the unigram. Only the highest order with evidence is consulted. - **Interpolation.** Always mix all orders, weighting each by a $\lambda$. For the trigram case, $$ \hat{P}(w_i \mid w_{i-2} w_{i-1}) = \lambda_1 P(w_i) + \lambda_2 P(w_i \mid w_{i-1}) + \lambda_3 P(w_i \mid w_{i-2} w_{i-1}), \qquad \sum_i \lambda_i = 1. $$ The $\lambda$s sum to one so the result is a proper distribution; they are set to maximize the likelihood of a held-out corpus. In the more refined version each $\lambda$ is itself conditioned on the context, so a context with plenty of trigram evidence leans harder on the trigram term. For backoff to stay a valid distribution, the higher orders must be **discounted** to free up mass for the lower orders — otherwise the borrowed probability pushes the total above one. Backoff with discounting is **Katz backoff**. $$ % caption: The backoff hierarchy. If the trigram context has counts, use the trigram; % otherwise back off to the bigram, then to the unigram. Each fallback trades context % for evidence, and higher orders are discounted to leave mass for the lower ones. \begin{tikzpicture}[>=stealth, font=\footnotesize, lvl/.style={draw, minimum width=42mm, minimum height=9mm, align=center, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[lvl, draw=acc, text=acc] (tri) at (0,0) {trigram P(w $\mid$ w-2 w-1)}; \node[lvl] (bi) at (0,-1.6) {bigram P(w $\mid$ w-1)}; \node[lvl] (uni) at (0,-3.2) {unigram P(w)}; \draw[->, acc, thick] (tri) -- (bi) node[midway, right, font=\scriptsize, text=acc, xshift=2mm] {if zero count}; \draw[->, acc, thick] (bi) -- (uni) node[midway, right, font=\scriptsize, text=acc, xshift=2mm] {if zero count}; \end{tikzpicture} $$ ### Kneser-Ney, in one idea The best-performing classical smoother is **interpolated Kneser-Ney**.[^jm-kn] It starts from **absolute discounting**: subtract a fixed constant $d$ (empirically near $0.75$) from every nonzero count, which — as Church and Gale found by comparing a corpus to a held-out copy — closely matches how counts actually shrink from one sample to the next, then interpolate with a lower-order term. Kneser-Ney's own contribution is the lower-order term. A standard unigram estimates how frequent $w$ is, but frequency is the wrong quantity for a fallback. The word _Kong_ is frequent, yet only ever appears after _Hong_; _glasses_ is less frequent but appears in many contexts. As a novel continuation for an unseen bigram, _glasses_ is the better bet. So Kneser-Ney replaces raw frequency with a **continuation probability**: how many _distinct_ contexts a word completes. $$ P_{\text{CONTINUATION}}(w) = \frac{\bigl|\{\,v : C(vw) > 0\,\}\bigr|}{\bigl|\{\,(u', w') : C(u' w') > 0\,\}\bigr|}. $$ The numerator counts the distinct words $v$ that precede $w$; the denominator counts all distinct bigram types. _Kong_, seen in only one context, gets a low continuation probability despite its high raw frequency. Combining absolute discounting on the higher order with continuation probability on the lower gives the interpolated Kneser-Ney bigram estimate: $$ P_{\text{KN}}(w_i \mid w_{i-1}) = \frac{\max\bigl(C(w_{i-1} w_i) - d,\; 0\bigr)}{C(w_{i-1})} + \lambda(w_{i-1})\, P_{\text{CONTINUATION}}(w_i), $$ with $\lambda(w_{i-1})$ a normalizing weight that redistributes exactly the mass the discount $d$ removed. The recursion bottoms out at the unigram, interpolated with the uniform distribution $1/|V|$. The production variant, **modified Kneser-Ney**, uses three separate discounts for counts of one, two, and three-or-more. #### Why $d \approx 0.75$: the Church-Gale held-out experiment The absolute discount is measured, not tuned. Church and Gale built a bigram model from $22$ million words of AP newswire and then looked up, for every bigram that occurred $c$ times in that corpus, how often the _same_ bigram occurred in a second, independent $22$-million-word sample.[^jm-kn] The held-out count is what the training count _should_ have been if the corpus were unbiased, and it is almost exactly the training count minus a constant near $0.75$. | Count $c$ in training | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | Avg. count in held-out | 0.0000 | 0.45 | 1.25 | 2.24 | 3.23 | 4.21 | 5.23 | 6.21 | 7.21 | 8.26 | Read across from $c = 2$ onward: the held-out average sits about $0.75$ below the training count in every column ($2 - 1.25 = 0.75$, $3 - 2.24 = 0.76$, $4 - 3.23 = 0.77$, $\ldots$). The high counts are barely touched — subtracting $0.75$ from a count of $9$ changes little — while the small counts, the ones we trust least, are pulled down hardest in relative terms. That single measured constant is the discount $d$ absolute discounting subtracts. $$ % caption: The Church-Gale held-out experiment behind absolute discounting. Bigrams % of training count c (blue) reappear in an independent sample at the height of the % orange bar, roughly c - 0.75 for c >= 2. The constant gap is the discount d. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \draw[->, black] (0,0) -- (9.6,0) node[right, black, font=\scriptsize] {training count c}; \draw[->, black] (0,0) -- (0,5.0) node[above, black, font=\scriptsize] {count}; % training bars (height = c), held-out bars (height = held-out avg), scaled by 0.48 \foreach \c/\ho in {1/0.45, 2/1.25, 3/2.24, 4/3.23, 5/4.21, 6/5.23, 7/6.21, 8/7.21, 9/8.26} { \fill[acc!22, draw=acc] (\c-0.30,0) rectangle (\c-0.02,{\c*0.48}); \fill[red!16, draw=red] (\c+0.02,0) rectangle (\c+0.30,{\ho*0.48}); \node[anchor=north, font=\scriptsize] at (\c,-0.05) {\c}; } \node[anchor=west, font=\scriptsize, text=acc] at (5.6,4.4) {training count}; \node[anchor=west, font=\scriptsize, text=red] at (5.6,3.9) {held-out avg}; \end{tikzpicture} $$ The normalizing weight $\lambda(w_{i-1})$ is not arbitrary either. It must give the lower-order term _exactly_ the mass the discount removed from the higher order. Each of the distinct words that can follow $w_{i-1}$ contributed one discount of $d$, so the total mass freed is $d$ times the number of such continuation types, all divided by the prefix count $C(w_{i-1})$: $$ \lambda(w_{i-1}) = \frac{d}{C(w_{i-1})} \; \bigl|\{\, w : C(w_{i-1} w) > 0 \,\}\bigr|. $$ The first factor is the normalized discount; the second counts how many times the discount was applied — the number of word types seen after $w_{i-1}$. Multiply them and $\lambda(w_{i-1})$ is precisely the probability mass to redistribute, so $P_{\text{KN}}$ still sums to one over the vocabulary. #### A full Kneser-Ney computation For a worked example, take the same three-sentence corpus from the bigram example, without the sentence markers for brevity: ``` I am Sam Sam I am I do not like green eggs and ham ``` Set the discount to $d = 0.75$ and estimate $P_{\text{KN}}(\texttt{am} \mid \texttt{I})$. Two ingredients are needed: the discounted higher-order term, and the continuation-probability lower-order term. **Higher-order term.** The word `I` occurs three times ($C(\texttt{I}) = 3$), and the bigram `I am` occurs twice ($C(\texttt{I am}) = 2$). Absolute discounting shaves $0.75$ off that count: $$ \frac{\max\bigl(C(\texttt{I am}) - d,\; 0\bigr)}{C(\texttt{I})} = \frac{2 - 0.75}{3} = \frac{1.25}{3} = 0.417. $$ **Continuation probability of `am`.** Ask in how many _distinct_ contexts `am` appears as the second word of a bigram. Scanning the corpus, `am` is preceded only by `I` — twice, once in each of the first two sentences — and by no other word, so it completes exactly one distinct bigram type: $\{v : C(v\,\texttt{am}) > 0\} = \{\texttt{I}\}$, size $1$. The denominator is the number of distinct bigram _types_ in the corpus. Listing them — `I am`, `am Sam`, `Sam I`, `I do`, `do not`, `not like`, `like green`, `green eggs`, `eggs and`, `and ham` — gives $10$ distinct types (note `I am` appears twice but counts once as a type): $$ P_{\text{CONTINUATION}}(\texttt{am}) = \frac{\bigl|\{v : C(v\,\texttt{am}) > 0\}\bigr|}{\bigl|\{(u',w') : C(u'w') > 0\}\bigr|} = \frac{1}{10} = 0.1. $$ **The weight.** After `I` we see two distinct word types (`am` and `do`), so the discount was applied twice: $$ \lambda(\texttt{I}) = \frac{d}{C(\texttt{I})}\,\bigl|\{w : C(\texttt{I}\,w) > 0\}\bigr| = \frac{0.75}{3}\times 2 = 0.5. $$ **Combine.** The Kneser-Ney estimate mixes the two: $$ P_{\text{KN}}(\texttt{am} \mid \texttt{I}) = 0.417 + 0.5 \times 0.1 = 0.417 + 0.05 = 0.467. $$ Compare the plain MLE, $P(\texttt{am} \mid \texttt{I}) = 2/3 = 0.667$. Kneser-Ney has pulled the estimate down from $0.667$ to $0.467$, moving the freed $0.2$ of mass onto _all_ the words that could plausibly follow `I` — weighted by how broadly each word appears as a continuation, not by raw frequency. The figure traces the two streams into the final estimate. $$ % caption: The two streams of interpolated Kneser-Ney for P_KN(am | I) on the toy % corpus. The discounted bigram (2 - 0.75)/3 = 0.417 flows down the left; the % weighted continuation term lambda(I) * P_cont(am) = 0.5 * 0.1 = 0.05 down the % right; they sum to 0.467. \begin{tikzpicture}[>=stealth, font=\footnotesize, tbox/.style={draw, minimum width=40mm, minimum height=10mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[tbox, draw=acc, text=acc] (hi) at (-2.6,1.3) {discounted bigram\\ (2 - 0.75) / 3 = 0.417}; \node[tbox] (lo) at (2.6,1.3) {weighted continuation\\ 0.5 x 0.1 = 0.05}; \node[tbox, draw=black, thick] (sum) at (0,-1.1) {P-KN(am given I) = 0.467}; \draw[->, acc, thick] (hi.south) -- (sum.north west); \draw[->, acc, thick] (lo.south) -- (sum.north east); \node[font=\scriptsize, anchor=south] at (0,1.95) {absolute discounting + continuation probability}; \end{tikzpicture} $$ ## Stupid backoff and web-scale n-grams Kneser-Ney is the best classical smoother, but the counts it smooths can come from very large corpora. Google's **Web 1 Trillion 5-gram** release holds n-grams up to length five drawn from over $10^{12}$ words of English web text; its Google Books n-grams add hundreds of billions more tokens across many languages.[^jm-huge] At that scale two things change: the model is too big to hold naively, and the normalization Kneser-Ney requires stops being worth its cost. ### Storing a huge model A trillion-word model cannot keep its n-grams as plain strings and its probabilities as $8$-byte floats — the table would not fit in memory. Production toolkits make three compromises.[^jm-huge] - **Hashing.** Each word is stored not as a string but as a $64$-bit hash number, with the string forms kept on disk. The n-grams themselves live in reverse **tries**, a prefix tree read from the last word back, which shares structure across n-grams with common suffixes. - **Quantization.** A probability is stored in only $4$ to $8$ bits rather than a full float. The precision lost is negligible against the size saved. - **Pruning.** Drop the n-grams that carry little information — for instance, keep only those with a count above a threshold (Google's release used a count of $40$), or prune by an entropy criterion that discards the n-grams whose removal least perturbs the model. Approximate structures like **Bloom filters** shrink the model further at the cost of occasional false positives. Toolkits like KenLM combine a backoff weight and a probability into a single stored value and build the tables with a few merge-sort passes over the corpus, so that even web-scale Kneser-Ney models are buildable. But at that size a much cruder scheme often suffices. ### The stupid-backoff rule **Stupid backoff** gives up on being a true probability distribution altogether.[^jm-stupid] It does no discounting: if the full-order n-gram has a nonzero count, use its relative frequency directly; otherwise fall back to the next-lower order, multiplied by a fixed, context-independent weight $\lambda$. Because the result is not normalized, it is written $S$ rather than $P$: $$ S(w_i \mid w_{i-k+1:i-1}) = \begin{cases} \dfrac{C(w_{i-k+1:i})}{C(w_{i-k+1:i-1})} & \text{if } C(w_{i-k+1:i}) > 0, \\[3mm] \lambda \; S(w_i \mid w_{i-k+2:i-1}) & \text{otherwise.} \end{cases} $$ The recursion bottoms out at the unigram, scored by its own relative frequency $S(w) = C(w)/N$. Brants et al. found $\lambda = 0.4$ works well. Contrast this with Katz backoff earlier in this lesson: Katz discounts the higher orders to free up exactly the right mass for the lower ones, keeping the total a valid distribution. Stupid backoff skips all of that — it just scales the lower order by a constant and never renormalizes. $$ % caption: The stupid-backoff cascade for a trigram. If the trigram count is % nonzero, return its relative frequency; otherwise multiply the bigram score by % lambda = 0.4; if the bigram is also unseen, multiply the unigram score by % lambda again. No discounting and no normalization: the result S is a score, not % a probability. \begin{tikzpicture}[>=stealth, font=\footnotesize, lvl/.style={draw, minimum width=46mm, minimum height=9mm, align=center, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[lvl, draw=acc, text=acc] (tri) at (0,0) {trigram: C(w-2 w-1 w) / C(w-2 w-1)}; \node[lvl] (bi) at (0,-1.7) {bigram: 0.4 x C(w-1 w) / C(w-1)}; \node[lvl] (uni) at (0,-3.4) {unigram: 0.4 x C(w) / N}; \draw[->, acc, thick] (tri) -- (bi) node[midway, right, font=\scriptsize, text=acc, xshift=2mm] {if trigram count = 0}; \draw[->, acc, thick] (bi) -- (uni) node[midway, right, font=\scriptsize, text=acc, xshift=2mm] {if bigram count = 0}; \end{tikzpicture} $$ Dropping normalization is what saves the cost. Renormalizing a backoff model means, for every context, summing over the vocabulary to redistribute the discounted mass — prohibitive when the model has billions of contexts. Stupid backoff skips that sum entirely. The scores $S$ no longer sum to one, so they cannot be compared as probabilities across contexts, but for _ranking_ candidate continuations — which is what a downstream system such as machine translation actually needs — a monotonic score is enough. With a large enough corpus the volume of evidence outweighs the crudeness of the estimate, and stupid backoff comes within reach of full Kneser-Ney at a fraction of the engineering. ## Beyond n-grams: neural and self-attention language models Every smoothing scheme in this lesson responds to sparsity the same way: back off to a shorter context. That is a workaround, not a solution. The n-gram treats `cat` and `dog` as unrelated atoms, so a bigram model that has seen _the cat sat_ learns nothing about _the dog sat_. The models that displaced the n-gram all address this one weakness, and all originate in named, public work that postdates the counting-and-smoothing view above. ### Distributed representations (Bengio et al., 2003) The **neural probabilistic language model** of Bengio, Ducharme, Vincent, and Jauvin (_JMLR_, 2003) keeps the n-gram's prediction task verbatim — estimate $P(w_t \mid w_{t-n+1:t-1})$ from a fixed window — but changes how the context is represented. Each word is mapped to a learned dense vector, its **embedding**, and the network predicts the next word from the _concatenated embeddings_ of the context rather than from the raw word identities. Words that behave alike are pushed to nearby vectors during training, so evidence _shares_ across them. Having seen _the cat gets fed_, the model raises its estimate of _fed_ after _the dog gets_ as well, because _cat_ and _dog_ sit close in embedding space. Bengio et al. framed this as breaking the **curse of dimensionality**: an n-gram must store a separate parameter for each of the exponentially many word combinations, while the neural model shares a small set of embedding dimensions across all of them.[^neural-lm] Smoothing stitches together backoff levels after the fact; the neural model never manufactures the zeros in the first place, because similarity, not exact match, drives its estimate. $$ % caption: The n-gram versus the neural language model on the same prediction task. % The n-gram matches the exact context string and backs off when it is unseen; the % neural model embeds each context word into a dense vector, so similar words (cat, % dog) share evidence and no exact match is required. \begin{tikzpicture}[>=stealth, font=\footnotesize, nbox/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}, ebox/.style={draw, minimum width=13mm, minimum height=7mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % --- n-gram row --- \node[font=\scriptsize, anchor=east, text=black] at (-0.3,1.4) {n-gram}; \node[nbox] (ctx1) at (1.7,1.4) {the dog gets}; \node[nbox, draw=red, text=red] (miss) at (5.4,1.4) {exact match? no}; \node[nbox] (bo) at (9.2,1.4) {back o\/f\/f to bigram}; \draw[->, black] (ctx1) -- (miss); \draw[->, red] (miss) -- (bo); % --- neural row --- \node[font=\scriptsize, anchor=east, text=black] at (-0.3,-0.8) {neural}; \node[ebox] (e1) at (1.1,-0.8) {the}; \node[ebox] (e2) at (2.5,-0.8) {dog}; \node[ebox] (e3) at (3.9,-0.8) {gets}; \node[nbox, draw=acc, text=acc] (net) at (6.9,-0.8) {network over embeddings}; \node[nbox] (pred) at (10.6,-0.8) {P(fed) high}; \draw[->, acc] (e3) -- (net); \draw[->, acc, thick] (net) -- (pred); \node[font=\scriptsize, anchor=north, text=acc] at (2.5,-1.3) {dog ~ cat in vector space}; \end{tikzpicture} $$ ### Recurrent and self-attention models (Mikolov 2010; Vaswani et al., 2017) Bengio's model still truncates history to a fixed window, inheriting the n-gram's Markov assumption. Two later architectures removed even that limit. The **recurrent neural network language model** (Mikolov et al., _Interspeech_ 2010) carries a hidden state forward token by token, in principle conditioning each prediction on the entire preceding sentence rather than a window of $n-1$ words. The **transformer** (Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser, and Polosukhin, _NeurIPS_ 2017) replaced recurrence with **self-attention**: at each position the model computes a weighted sum over the representations of all earlier positions, the weights learned per pair of positions, so any prior word can directly influence the current prediction regardless of distance. Self-attention parallelizes across positions in a way recurrence cannot, which is what made training on billions of tokens practical and put the transformer under every large language model that followed. $$ % caption: How three language-model families reach into the history to predict the % next word. The n-gram sees only the last n-1 words; the RNN threads a hidden state % through the whole prefix; the transformer attends directly from the current % position to every earlier one. \begin{tikzpicture}[>=stealth, font=\footnotesize, tok/.style={draw, minimum width=8mm, minimum height=7mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % tokens shared baseline \foreach \i/\w in {0/w1, 1/w2, 2/w3, 3/w4, 4/w5} \node[tok] (a\i) at (\i*1.3,3.0) {\w}; \foreach \i/\w in {0/w1, 1/w2, 2/w3, 3/w4, 4/w5} \node[tok] (b\i) at (\i*1.3,1.3) {\w}; \foreach \i/\w in {0/w1, 1/w2, 2/w3, 3/w4, 4/w5} \node[tok] (c\i) at (\i*1.3,-0.4) {\w}; \node[anchor=west, font=\scriptsize, text=black] at (6.6,3.0) {n-gram: last 2 words only}; \node[anchor=west, font=\scriptsize, text=black] at (6.6,1.3) {RNN: state through all words}; \node[anchor=west, font=\scriptsize, text=black] at (6.6,-0.4) {transformer: attend to all}; % n-gram: only a2->a4, a3->a4 \draw[->, red, thick] (a2.north) to[bend left=30] (a4.north); \draw[->, red, thick] (a3.north) to[bend left=30] (a4.north); % rnn chain \foreach \i in {0,1,2,3} {\pgfmathtruncatemacro{\j}{\i+1} \draw[->, acc] (b\i.east) -- (b\j.west);} % transformer: all to c4 \foreach \i in {0,1,2,3} \draw[->, acc, thick] (c\i.north) to[bend left=25] (c4.north); \end{tikzpicture} $$ The n-gram vocabulary is fully preserved in these models. They still assign a probability to the next word, still factor a sequence by the chain rule, still report perplexity, and still contend with rare and unseen words — the very problems set up in this lesson. What changed is only the estimator: from counting and backing off to a learned function that shares statistical strength across similar contexts. On the Penn Treebank and larger benchmarks, neural models cut perplexity far below the best Kneser-Ney n-gram, at the cost of far heavier training. For a small task on a small corpus, a smoothed n-gram is still the right tool and often the faster one; the tradeoff is accuracy against complexity, not one paradigm rendering the other wrong. ## Where n-grams lead The n-gram's prediction task — assign a probability to the next word given a context — is verbatim the task a neural language model solves; the difference is only in how the conditional is estimated. The n-gram counts and smooths; the neural model learns a distributed representation of the context and computes the conditional with a network, which sidesteps sparsity by _sharing_ statistical strength across similar contexts instead of stitching together backoff levels. The vocabulary set up here — sequence probability, the Markov approximation, maximum likelihood, perplexity, the zero problem — is the vocabulary those models inherit. We pick the thread up with [vector semantics](/natural-language-processing/semantics/vector-semantics-and-embeddings), which learns to represent a word's meaning as a vector, and then with [neural language models](/natural-language-processing/semantics/neural-language-models), which use those vectors to predict the next word. [^neural-lm]: Neural successors to the n-gram model. **Bengio, Ducharme, Vincent, and Jauvin**, "A Neural Probabilistic Language Model," _Journal of Machine Learning Research_ 3 (2003) — learned word embeddings and a feedforward network that estimates the next-word probability from the context embeddings, breaking the curse of dimensionality by sharing statistical strength across similar words. **Mikolov, Karafiát, Burget, Černocký, and Khudanpur**, "Recurrent Neural Network Based Language Model," _Interspeech_ (2010) — a hidden state carried across the whole prefix, removing the fixed-window Markov assumption. **Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser, and Polosukhin**, "Attention Is All You Need," _NeurIPS_ (2017) — the transformer, which replaces recurrence with self-attention over all prior positions and underlies modern large language models. All three keep the n-gram's prediction task, chain-rule factorization, and perplexity metric, changing only the estimator. [^jm-smooth]: **Jurafsky & Martin**, §3.5 — Smoothing: Laplace (add-one) and add-k smoothing, the adjusted count $c^\ast$ and discount, worked on the Berkeley bigrams. [^jm-backoff]: **Jurafsky & Martin**, §3.5.3; §3.6 — Backoff and Interpolation, and Katz backoff: using less context when a higher-order n-gram lacks evidence, with discounting to preserve a valid distribution. [^jm-kn]: **Jurafsky & Martin**, §3.6 — Kneser-Ney Smoothing: absolute discounting and the continuation-probability lower-order term, interpolated into $P_{\text{KN}}$, with modified Kneser-Ney as the production variant. [^jm-huge]: **Jurafsky & Martin**, §3.7 — Huge Language Models and Stupid Backoff: the Google Web 1 Trillion 5-gram and Books n-gram corpora, and the efficiency measures for web-scale models — $64$-bit word hashes, reverse tries, $4$–$8$-bit probability quantization, count- and entropy-based pruning, Bloom filters, and toolkits like KenLM. [^jm-stupid]: **Jurafsky & Martin**, §3.7 — Stupid Backoff (Brants et al. 2007): the un-normalized score $S$ that uses the full-order relative frequency when the count is nonzero and otherwise backs off to the lower order scaled by a fixed $\lambda \approx 0.4$, terminating in the unigram $S(w) = C(w)/N$; it abandons discounting and normalization but matches Kneser-Ney at web scale.