Why language models predict words

Read the roadmap as one story. We want to predict the next word, so we count words in a corpus to estimate probabilities. We measure the result with Perplexity, and we look at what the model has learned by generating text from it. Then the model breaks: any word sequence it never saw gets probability zero. The second half of the lecture is the repair kit, from Smoothing through interpolation, Backoff and absolute discounting to Kneser-Ney, and it closes by connecting perplexity to Entropy.

1. Motivation: predicting words. What an LM computes and where that number is used. This part.
2. N-grams. The chain rule and the Markov assumption turn an impossible history into the last few words.
3. Estimating n-gram probabilities. Counting and dividing: maximum likelihood estimates, and log probabilities to avoid underflow.
4. Evaluating language models: perplexity. How to tell a better model from a worse one on held-out text without building a whole application.
5. Sampling from an LM. Generating text by drawing from the distribution, which shows what the model has actually learned.
6. Generalization and overfitting. Why a model tuned to its training corpus fails on new genres and assigns zero to unseen n-grams.
7. Smoothing, interpolation and backoff. Moving probability mass to unseen events and mixing in shorter contexts.
8. Absolute discounting. Subtracting a fixed amount from every seen count, justified by held-out data.
9. Kneser-Ney intuition. A lower-order distribution built from how many contexts a word completes, not how often it occurs.
10. Interpolated Kneser-Ney for bigrams. The full computation step by step on a toy corpus.
11. General Kneser-Ney. The recursion to higher-order n-grams, the standard count-based baseline.
12. Perplexity and entropy. The information-theoretic meaning of the evaluation metric.

Underneath the twelve stops there is a single question: how do we turn finite counts into a probability for every possible next word, including words never seen after this context? Stops 2 to 4 answer the easy half, for events we have seen. Stops 6 to 11 answer the hard half, for events we have not. The model family that carries all of it is the n-gram language model.

Finish this sentence: The water of Walden Pond is so beautifully ___. You probably thought of blue, green or clear. You did not think of refrigerator or this. You did not produce one word with certainty either. You produced a ranking with a sense of how much more likely some words are than others. That ranking, made numeric, is a language model.

A language model assigns a probability to each possible next word given the words so far, the history. Its output for one history is therefore a whole probability distribution over the vocabulary, and the task of producing it is next-word prediction. Writing the history as w<t, every word before position t:

The constraint that the probabilities sum to 1 is what makes the numbers comparable. If blue gains probability, something else must lose it. It also explains why the rest of the lecture worries about zeros: a model that spends all its mass on words it has seen has nothing left for refrigerator, even when a strange sentence really does continue that way.

This is not a toy objective. Jurafsky and Martin put it bluntly: large language models are built just by training them to predict words. GPT-3, with 175 billion parameters, is described by its authors as an autoregressive language model, which means exactly this: it computes P(w_t | w<t) one position at a time. A neural language model and an n-gram model answer the same question; they differ only in how they estimate the answer. GPT-3 itself was pretrained with plain next-token prediction, and modern LLMs use this objective or close variants of it; later tuning stages change the objective and shift the probabilities, but the output is still a distribution over the next token.

Run a dictionary spell checker over Their are two midterms. Every word is in the dictionary, so it passes. The error is a real-word error: the typo produced another valid word, and nothing about any single word reveals it. What reveals it is context. There are is a very common Bigram and Their are is rare, so a model that compares P(There are) with P(Their are) flags the sentence at once. The same holds for Everything has improve, where the fix improved makes the more probable sentence.

Now speech. A recognizer hears something that sounds like I will be back soonish, but the audio is almost identical to I will be bassoon dish. The acoustic evidence cannot separate them. The language model can: back soonish is a far more probable continuation of I will be than bassoon dish.

The pattern: candidates in, ranking out

Both examples share a structure, and it is worth naming because it covers almost every classical application. Some other component proposes candidates: a set of spelling variants, an acoustic model, a translation model, a keyboard decoder. The language model does not know what you meant. It scores how plausible each candidate is as a piece of language, and the system combines that score with the evidence. Brown and colleagues wrote this down for statistical machine translation in 1990 as the noisy channel decoder: given a foreign sentence T, output the English sentence S that maximizes the product below, and they call the first factor the language model probability of S.

The split of labour is clean. Pr(T | S) rewards faithfulness to the input. Pr(S) rewards fluency, and it does not care about the input at all, which is why one well trained language model can be reused across speech, translation and spelling. It is also why these are the settings where language models are judged by extrinsic evaluation: a better LM is one that lowers the word error rate or raises the translation score of the whole system.

Prediction on its own

In a second family of applications there is no separate candidate generator. The prefix you have typed is the history, and the system shows the top few entries of P(next | prefix). Search autocomplete turns a quick into brown fox. A translation input box suggests think after what do you. A phone keyboard offers bro, brown and brother while you type The quick bro. All of these are argmax or top-k over the same distribution from the previous concept.

The application with the highest stakes is augmentative and alternative communication (AAC). People who cannot speak or sign may select words from a menu with eye gaze or other small movements. Trnka and colleagues report that AAC users often communicate at under 10 words per minute, against 150 to 200 for speech, and that in a study with simulated AAC users (able-bodied typists slowed by an artificial key delay), advanced word prediction produced 59.9% more words per minute than no prediction. More accurate predictions significantly improve the communication rate, so here a better language model is directly a faster conversation.

Gboard is the best documented production example. Hard and colleagues describe how the keyboard shows three suggestions and the numbers behind them, and they make a useful benchmark for the comparison in the last concept of this part.

Compare all of a sudden I notice three guys standing on the sidewalk with on guys all I of notice sidewalk three a sudden standing the. Same twelve words, and none repeats, so there are 12! = 479,001,600 orderings. A good language model must put the fluent one near the top of all of them. That asks for something new: not a next word, but a probability for a whole sentence.

Language models offer two views. View one is the next-word distribution, P(w_t | w<t). View two is the probability of an entire sequence, P(w_1:T). They are not two models. The chain rule of probability turns one into the other exactly:

Going the other way, a next-word probability is a ratio of two sequence probabilities, P(w_t | w<t) = P(w_1:t) / P(w_1:t-1), so either view gives you the other. That is why slide 8 can call them equivalent. Here is a preview of the computation with the toy corpus Part 03 uses to teach counting.

Is the sentence view really enough to recover word order? Brown and colleagues tested exactly the claim on slide 8 with an experiment they called bag translation. They cut sentences into an unordered bag of words, then asked a Trigram language model to choose the ordering with the highest Pr(S).

The idea is older still. In 1948 Shannon drew each word of English text from the distribution of words that follow the previous word, a word bigram model done by hand, and got strings such as THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER: not meaningful, but recognizably English in its local order. Local next-word statistics already carry a surprising amount of a sentence's shape.

Train a model on the cat sat on the mat, then ask it about the dog sat on the rug. A model that only counts has never seen dog sat, so it has no evidence for it beyond whatever Smoothing hands out. A model that knows dog behaves like cat and rug like mat can carry the probability across. That difference is the whole of slide 9.

A count-based language model, also called statistical, estimates P(w | h) by maximum likelihood estimation: the relative frequency of the exact n-gram among all n-grams that share its history. It is transparent, fast and cheap. Its weakness is Sparsity. Bengio and colleagues put the problem as the curse of dimensionality: modelling the joint distribution of 10 consecutive words with a vocabulary of 100,000 has potentially 100,000^10 − 1 = 10^50 − 1 free parameters, and a test sequence is likely to differ from every sequence seen in training.

A neural language model maps each word or token to a continuous vector and learns a function from those vectors to the next-word distribution. Bengio and colleagues explain why this generalizes: an unseen sequence gets high probability if it is made of words similar to words in an already-seen sentence. Jurafsky and Martin name the two n-gram problems neural models solve: the number of parameters increases exponentially as the n-gram order increases, and n-grams have no way to generalize from training to test examples unless they use identical words.

This lecture is about count-based models only, which is why slide 9 sets them in bold. That is not nostalgia. Around the turn of the century the standard baseline was modified interpolated Kneser-Ney, available in public toolkits such as SRILM and KenLM, and it is still what you compare against when you need a cheap, inspectable model or a strong prior for a small device.