Handout #2 — Language Modeling

Handout #1 ended with one line: a language model is a distribution over sequences, factored by the chain rule into one next-word prediction per position. This handout asks what that buys you, how to estimate those predictions by counting, how to measure whether they are any good, and what to do when one of them comes out as exactly zero.

1What a language model is

A language model assigns a probability to a sequence of words. That is the entire definition — and it is worth noticing how strange a goal it is. Nobody wants the number. What we want is what the model must know in order to produce a good one.

1.1  The problem, stated formally

Fix a finite vocabulary $\Sigma = \{x_1, x_2, \ldots, x_V\}$. Let $\Sigma^*$ be the set of all finite sequences over it — the, the cat, cat the the, and so on, an infinite set. A language model is a probability distribution over $\Sigma^*$:

Two things in that statement deserve attention. First, the mass has to be spread over an infinite set, which is why the end-of-sequence token matters so much — it is what lets the total converge rather than leaking away into ever-longer strings. Second, the definition never says what the atomic unit is. Words, characters, bytes, subword pieces: all are legal choices of $\Sigma$, and the choice turns out to matter enormously (both for the zero problem in §4 and for the numbers in §5).

1.2  Trained on conditionals, learning the joint

In practice we never touch $p_{\text{LM}}(e)$ directly. We train on next-word predictions — "the cat sat on the ___" — which are conditionals, sometimes loosely called the marginals the model is fit to. The chain rule from Handout #1 is what promotes those local predictions into the full joint distribution:

1.3  The Markov assumption

The factorization is exact — no assumptions. But there is a problem hiding in $x_{<t}$: as $t$ grows, the conditioning context grows without bound. To predict word 500 you would need a distribution conditioned on a specific 499-word prefix, and essentially every 499-word prefix in the language has occurred either once or never. No amount of data fixes this.

So we approximate, by truncating the context:

Concretely, for P(mat | the cat sat on the), keeping one word of context gives P(mat | the); two gives P(mat | on the); three gives P(mat | sat on the). This is the only approximation an n-gram model makes. Everything else — the counting, the smoothing — is bookkeeping.

It is also obviously false, and the lecture's example is the one to remember: "The computer which I had just put into the machine room on the fifth floor crashed." The subject of crashed is computer, thirteen words back. No n-gram model of any practical order can see it. And yet for two decades this was the best we had, and it was good enough to build speech recognition and machine translation on. Understanding why it worked, and precisely where it broke, is the fastest route to understanding what replaced it.

1.4  A very short history

2What you can do with one

Suppose someone hands you a trained language model. You can do exactly two things with it, and everything else is built from them.

2.1  Score, and therefore rank

An LM assigns a probability to any string. So you can compare strings, and the probability behaves as a rough measure of how familiar — how fluent, how grammatical, how plausible — the string is:

That last row is the one to dwell on. Nothing in the training objective mentions truth, and yet the true sentence is the more probable one — because true sentences are the ones people wrote. This is exactly the mechanism Handout #1 §2.3 described, now visible as a comparison of two numbers. It is also why the same mechanism fails: where the corpus is confidently wrong, the model will be too.

Ranking by probability is directly useful. Spelling correction, speech recognition and machine translation all generate several candidate strings by other means and then ask a language model which one sounds most like the language. That was the dominant application of LMs for thirty years.

2.2  Generate, by sampling recursively

The second thing is more surprising. A model that only ever predicts one next word can produce arbitrarily long text, by feeding its own output back in as context. Start with a prompt and repeat:

context = "Johns Hopkins is"
while True:
    next_word = sample(p(X | context))   # draw from the model's distribution
    if next_word == "</s>":
        break
    context = context + " " + next_word

Which might run:

Everything you have ever seen a chatbot do is this loop. The model is still only answering "what word comes next?"; the essay is an emergent property of asking that question a thousand times in a row.

2.3  Why care

Two reasons, and the second is the ambitious one.

Language modeling is a subcomponent of an enormous number of tasks. Summarization, translation, spelling correction, dialogue — each needs to produce or evaluate fluent text, and that is what an LM provides.

Language modeling is a proxy for language understanding. To predict the next word reliably, you must have understood the context — the syntax, the topic, the facts, the intent. There is no shortcut that gets you low loss without that. This is a claim, not a theorem, and it is the bet the entire field has placed. Handout #1 §2.4 argued for it and against it; keep both arguments live.

3Estimating by counting

Given the Markov assumption, the maximum-likelihood estimate is exactly what you would guess: count, and divide.

"Of all the times I saw this context, what fraction of the time was the next word this?" There is no optimization, no gradient, no training loop — one pass over the corpus to build a table of counts, and you are done. A trigram model over a 1.7-million-word corpus trains in seconds on a laptop. That simplicity is worth appreciating before we spend the rest of the semester on the alternative.

3.1  Counting, hands on

The widget below does exactly this over an 18-sentence corpus, small enough that you can check any probability it reports by hand:

To see what generation looks like when the corpus is large enough that the model is not merely reciting, here is a trigram model trained on 1.7 million words of newswire, sampled freely:

Surprisingly grammatical, and completely incoherent. Every three-word window is plausible English, because that is precisely what the model was fit to; nothing holds the sentence together across a longer span, because the model cannot see that far. The obvious fix — raise $n$ — makes coherence better and sparsity worse, and that trade-off is a wall, not a dial. §3.3 says why.

3.2  The whole model, in code

§3 claimed the model is "one pass over the corpus and you are done." That is worth seeing literally, because it is the last time in this course a model will be this small. Here is the entire trigram estimator — the same one the widget runs:

from collections import Counter

N = 3                                    # trigram: condition on the previous N-1 = 2 words

context_counts, ngram_counts = Counter(), Counter()

for line in CORPUS:                                    # ONE pass. No epochs.
    tokens = ["<s>"] * (N - 1) + line.split() + ["</s>"]
    for i in range(N - 1, len(tokens)):
        context = tuple(tokens[i - N + 1:i])           # the two preceding words
        context_counts[context] += 1
        ngram_counts[(context, tokens[i])] += 1

def p(word, context):
    """MLE estimate. Returns None when the context was never observed."""
    context = tuple(context[-(N - 1):])
    if context_counts[context] == 0:
        return None                                    # not zero -- undefined
    return ngram_counts[(context, word)] / context_counts[context]

p("sat",   ("the", "cat"))     # 0.4   -- matches the widget, and 2/5 by hand
p("</s>", ("the", "cat"))     # 0.4   -- the two sentences that END here
p("on",    ("cat", "sat"))     # 1.0   -- certain, on two observations
p("on",    ("dog", "slept"))   # None  -- context never seen

Four details in there are the whole lesson of this section:

• ["<s>"] * (N - 1) — padding the left edge is what lets position 1 have a context at all. Get this wrong and you silently drop the first word of every sentence from training.
• + ["</s>"] — the end marker is appended as a real token, so p("</s>", ("the","cat")) = 0.4 falls out of the counting like any other word. §1.1's requirement that the distribution sum over $\Sigma^*$ is enforced right here.
• return None, not return 0.0 — an unseen context has no distribution, which is a different failure from an unseen word in a seen context. §5.2's “two different zeros” keeps that distinction alive; conflating them is how you end up dividing by zero.
• There is no loss, no backward(), no learning rate, and nothing to tune. Compare this against the five-line training loop in Handout #3 §5.2 — that is the price of generalization.

3.3  Why this stops working: sparsity

The failure of counting is not that it is inaccurate. On contexts it has seen often, the MLE is excellent. The failure is that most contexts are seen rarely or never, and the problem gets exponentially worse with $n$.

Count the parameters. With a vocabulary of $V$ words, an order-$n$ model has $V^{n-1}$ possible contexts, each needing a distribution over $V$ words — so $V^n$ numbers. For a modest $V = 50{,}000$:

So the overwhelming majority of entries in the table are zero, and they are zero because of absence of evidence, not evidence of impossibility. the dog slept is a perfectly good English trigram; our corpus simply never used it. An unsmoothed model declares it impossible.

Sparsity also degrades the estimates that do exist. In the newswire model above, the context today the yields company and bank at $0.153$ each and price at $0.077$ — probabilities that are multiples of $1/13$, because the context was seen thirteen times. There is no granularity available; the distribution is as coarse as the count is small.

4Filling the zeros

Three families of fix, in increasing order of sophistication. All of them are moving probability mass from the things you saw to the things you did not.

4.1  Smoothing: pretend you saw a bit more

Add a constant $k$ to every count before normalizing (add-one smoothing is $k=1$, also called Laplace smoothing):

The $kV$ in the denominator is doing the accounting: we added $k$ to each of $V$ possible next words, so the total went up by $kV$. Now nothing is zero.

It is also a rather bad estimator, and it is worth being clear about why. With $V$ large and most counts zero, the $kV$ term dominates the denominator, so add-one smoothing takes a great deal of mass away from the words you actually observed and spreads it thinly over an enormous number of words you did not. It is the right first idea and the wrong final answer — which is roughly its role in this course too.

4.2  Interpolation: ask a shorter question too

A better instinct than add-$k$: if you have never seen the dog slept, you have probably seen dog slept, and you have certainly seen slept. The shorter the context, the more evidence you have for it — exactly what item 3 of the widget exercise showed. So rather than trusting one order, use them all at once.

Interpolation mixes the orders into a single estimate:

The weights $\lambda_i$ are fit on held-out data. Because the $\lambda$'s sum to one and each $p_i$ is a distribution, the mixture is a valid distribution too — and because $\lambda_1 > 0$ and the unigram is non-zero for any word in the vocabulary, no estimate is ever exactly zero. The unseen-context problem is gone, and unlike add-$k$ the mass it moves is small and tuned rather than proportional to $V$.

There is a second benefit worth noticing: even a well-observed trigram gains from being pulled slightly toward the lower orders, because a ratio built from three observations is noisy. Interpolation shrinks confident-but-thinly-evidenced estimates toward more robust ones — which is the same complaint the check-yourself question about $\hat{p} = 1$ raises in §6.

The best-known refinement is Kneser–Ney smoothing, and its central idea is a genuinely clever one worth carrying with you. When you fall back on a lower order, do not ask "how frequent is this word?" — ask "in how many distinct contexts does this word appear?" The word Francisco is common, but almost exclusively after San. A frequency-based lower-order estimate will happily predict Francisco after anything; a diversity-based one will not. Kneser–Ney remained the best-performing n-gram model for two decades.

5Measuring quality

We have models. Which is better? For a language model there is a natural answer: the one that assigns higher probability to text it has not seen. Train on one set of documents, evaluate on different, unseen ones. Evaluating on the training text measures memorization, not modelling.

5.1  Perplexity, two ways

Start from the obvious thing. Take a real sentence $w_1, \ldots, w_n$ from held-out data and look at $\mathbf{P}(w_1, \ldots, w_n)$. A good model gives it high probability. Two problems: the number is inconveniently tiny, and it shrinks with length, so you could not compare across test sets. Fix both — invert it, and take the $n$-th root:

The negative exponent flips small probabilities into large scores; the $1/n$ normalizes for length. Lower is better. Now expand the joint with the chain rule:

These are the same quantity. The first form says inverse probability, length normalized; the second says exponentiated average negative log-probability. The second is what you compute, because it is a sum of logs rather than a product of tiny numbers — Handout #1 §1.2's point about log space, arriving where it matters.

5.2  Perplexity is a branching factor

The interpretation that makes perplexity intuitive: it is the effective number of equally likely words the model is choosing among at each step — its average branching factor. Three cases pin this down. Work each out before reading the answer; they are the fastest way to internalize the metric.

The comparison table in the §3 widget computes exactly this, and it is worth being precise about what it shows. On familiar text the trigram wins by a wide margin ($1.78$ against the unigram's $21.0$). On the dog slept on the mat — all known words, one unknown trigram — the ordering reverses: the unigram scores $25.2$ and the higher-order models score $\infty$. A model that hedges everywhere cannot be caught out; a model that is confident and wrong even once is, by this metric, infinitely bad.

5.3  What the numbers actually look like

The canonical demonstration that order helps — trained on 38 million words of the Wall Street Journal, evaluated on a held-out 1.5 million:

Two things to read off this. Each extra word of context buys a large improvement, and the gains are shrinking — $962 \to 170$ is a factor of $5.7$, $170 \to 109$ only $1.6$. That deceleration is the sparsity wall arriving: a four-gram model would help less still, and eventually not at all. Note also that the evaluation is on text held out from the counting, which is the only honest way to do it.

Perplexity on standard benchmarks has fallen more or less monotonically for thirty years, which is why the field trusts it. An oversimplified but not unfair history of the last decade of AI: lower perplexity turned out to mean more capability, further than anyone expected it to.

5.4  A bigram model, end to end

This is the exercise that has appeared, in some form, on every Quiz 1 for the last three years. It uses only §3's counting and §5.1's definition, and it is entirely doable by hand. Do it by hand.

BOS who EOS
BOS The dog ran EOS
BOS The cat ran EOS
BOS The dog barked EOS
BOS Tianjian ran EOS

5.5  What perplexity does not tell you

Perplexity is the field's workhorse and it is genuinely load-bearing. It is also narrower than it looks, in ways that matter for reading papers critically.

• It is not comparable across tokenizations or vocabularies. A model that splits words into subword pieces is predicting more, easier tokens; its per-token perplexity is not commensurable with a word-level model's. Numbers are also incomparable across test sets. A perplexity with no stated corpus and tokenizer is not a claim. (This is the "choice of atomic unit" from §1.1 coming back to bite.)
• It rewards hedging. A model that spreads mass broadly is protected from catastrophic surprises. This is right for a probability estimate and wrong for a system that has to commit to an answer — one reason generation needs its own machinery (Sessions 9–10).
• It says nothing about whether the text is true, useful, or safe. Perplexity measures fit to a distribution. If the training distribution contains confident falsehoods, lower perplexity means predicting those falsehoods better — the technical root of §2.1's Baltimore/Virginia asymmetry cutting the other way.
• Correlation with downstream quality is real but loose. Held-out perplexity reliably tracks capability across large gaps and unreliably across small ones — which is why the rest of the course leans on task benchmarks too.

6Check yourself

Show all answers

7Optional further reading

Strictly optional — nothing here is assumed in class or on a quiz.

• Jurafsky & Martin, Speech and Language Processing (3rd ed. draft), Ch. 3 "N-gram Language Models" — the canonical treatment of this session, and the closest companion to this handout. If you read one thing here, read §3.1–3.5 (counting, smoothing) and §3.7 (perplexity).
• Shannon, Prediction and Entropy of Printed English (1951) — the origin of measuring a language model by how well it predicts, and of the $k$-th order approximations in §1.4. Short, and worth reading once in your life.
• Chen & Goodman, An Empirical Study of Smoothing Techniques for Language Modeling (1996/1999) — the definitive comparison. Skim it for the shape of the result: this is what the field looked like when generalization was the modeller's job.
• Bengio, Ducharme, Vincent & Jauvin, A Neural Probabilistic Language Model (2003) — argued for the first time, and the subject of Handout #3. The clearest single statement of why distributed representations solve sparsity.