N-gram language models

AOverview

This lecture builds the first real language model of the course from nothing but counts. It asks how likely a sentence is, and how likely each next word is given the words before it, and then answers both questions with a table of n-gram frequencies. Along the way it meets every problem that any language model, count-based or neural, still has to solve: histories too long to count, probabilities too small to multiply, a fair way to score a model, and the zeros that appear the moment a test sentence contains something the training data never saw.

As a PhD student you need it in three places. Exam questions are computational: estimate a bigram probability from a toy corpus, score a sentence in log space, turn a probability into perplexity, apply add-one smoothing to a row of counts, or compute an interpolated Kneser-Ney probability step by step. Your research will report perplexity and cross-entropy for years, and you can only read those numbers honestly if you know what a test set, a vocabulary and a smoothing choice do to them. And the systems you build, from spelling correction and speech recognition to the evaluation of large neural models, still rest on the same quantity: the probability of the next token given its context.

The path has five stops. You count: n-grams become probabilities by relative frequency, and a sentence becomes a product of them through the chain rule. You truncate: the Markov assumption keeps only the last n - 1 words, which is what makes counting possible at all. You measure: a held-out test set and perplexity tell you whether one model is better than another, and sampling lets you see what a model has learned. You smooth: add-one, add-k, interpolation, backoff and absolute discounting move a little probability from seen events to unseen ones. And you continue: Kneser-Ney replaces raw unigram frequency with the number of distinct contexts a word follows, and its recursive and modified forms are the strongest count-based models, tied back to entropy and cross-entropy at the end.

Success looks like

• Explain why next-word prediction and sentence probability are the same model, and name applications that depend on it, such as speech recognition, spelling correction and machine translation.
• Decompose a sentence with the chain rule, apply the Markov assumption for a stated n, and pad it with the sentence boundary tokens <s> and </s> correctly.
• Estimate bigram probabilities by maximum likelihood from a small corpus or a count table, and score a sentence by summing log probabilities instead of multiplying raw ones.
• Compute the perplexity of a short test sequence, read it as a weighted branching factor, and state why it is only comparable across models that share a vocabulary and a test set.
• Sample a sentence from a unigram or bigram model by hand, and use samples to diagnose overfitting and genre dependence.
• Apply add-one and add-k smoothing to a row of counts, and explain how linear interpolation, backoff, stupid backoff and absolute discounting redistribute probability mass.
• Compute the continuation probability and the interpolated Kneser-Ney bigram probability for a toy corpus, extend it recursively to higher orders, and relate perplexity to cross-entropy through PP = 2^H.

How to study this lecture

1. Choose your route. Read the full guide in one sitting for the big picture, or work through one part at a time when you want depth on a single technique.
2. Answer every recall prompt in your head, or on paper, before you reveal it. Counting a bigram, normalizing a row and computing a perplexity only stick if you have done them cold at least once.
3. Take each quiz and read the explanation even when you are right. The explanations carry the distinctions an examiner probes, such as interpolation against backoff or frequency against continuation count.
4. Use the simulators: build a bigram table, slide k in add-k smoothing, run the Kneser-Ney recursion and convert entropy into perplexity. Changing a count and watching the probabilities move is faster than rereading a formula.
5. Mark a concept as understood only when you could explain it to a classmate without looking. Unmarked concepts show you where to return.
6. Keep the glossary open when a term slips, and use the reference sheet for the formulas: MLE, perplexity, Laplace, interpolation and Kneser-Ney on one page.
7. Come back after a few days and retry the recall prompts and quizzes cold. Spaced practice builds the long-term memory an exam needs.

BThe 10 parts

1. 01Why language models predict wordsThe motivation for language modeling, the applications that rely on next-word probabilities, the two equivalent views of what an LM computes, and the split between count-based and neural models.5 conceptsSlides 1-930 min
   1. 1.1The lecture in one map: from counting words to Kneser-Ney
   2. 1.2A language model is a probability distribution over the next word
   3. 1.3Applications: the LM as a referee between competing candidates
   4. 1.4Two views of one model: next-word probability and sentence probability
   5. 1.5Count-based versus neural language models
2. 02N-grams, the chain rule and the Markov assumptionWhat an n-gram is, why full histories cannot be counted, how the chain rule decomposes sentence probability, and how the Markov assumption truncates the history to the last n minus 1 words.6 conceptsSlides 10-1636 min
   1. 2.1N-grams: sliding windows over text
   2. 2.2Why full histories cannot be counted
   3. 2.3The chain rule: an exact factorization
   4. 2.4The Markov assumption: keep only the last N-1 words
   5. 2.5Scoring a whole sentence with bigrams and boundary tokens
   6. 2.6Unigram, bigram, trigram: context against sparsity
3. 03Estimating n-gram probabilities with maximum likelihoodRelative-frequency (MLE) estimation for bigrams and general n-grams, worked on the I am Sam toy corpus and the Berkeley Restaurant Project tables, plus why we compute in log space and when longer n-grams pay off.5 conceptsSlides 17-2830 min
   1. 3.1Maximum likelihood: count the pair, divide by the history
   2. 3.2Doing MLE by hand on I am Sam, then for any N
   3. 3.3Reading real count and probability tables: the Berkeley Restaurant Project
   4. 3.4Chaining bigrams into a sentence probability, and what the numbers know
   5. 3.5Scaling up: log probabilities and longer n-grams
4. 04Evaluating language models with perplexityExtrinsic versus intrinsic evaluation, train, dev and test splits and contamination, and perplexity as the length-normalized inverse probability, read as a weighted branching factor.5 conceptsSlides 29-4130 min
   1. 4.1Two ways to judge a language model, and what 'better' means
   2. 4.2Train, dev and test splits, and how contamination fakes progress
   3. 4.3Perplexity: inverse test probability, normalized per token
   4. 4.4Computing and comparing perplexity honestly
   5. 4.5Perplexity as a weighted branching factor
5. 05Sampling sentences from a language modelHow to generate text from a unigram or n-gram model by placing words on the unit interval and drawing random numbers, walked through step by step on a deep learning example.5 conceptsSlides 42-5330 min
   1. 5.1Sampling: making a model show what it knows
   2. 5.2Unigram sampling on the unit interval
   3. 5.3The n-gram sampling loop: start at <s>, stop at </s>
   4. 5.4One step of the walkthrough: condition, get a distribution, draw
   5. 5.5Sliding the context window: discard the oldest word
6. 06Generalization, overfitting and add-one smoothingHow higher-order n-grams memorize sparse training data and depend on genre, why unseen n-grams create zero probabilities, and how Laplace and add-k smoothing fix zeros at a cost.6 conceptsSlides 54-6736 min
   1. 6.1Longer context buys fluency, then memorization
   2. 6.2A model only knows its own genre
   3. 6.3Unseen tokens versus unseen n-grams, and why one zero is fatal
   4. 6.4Smoothing: steal mass from the seen, give it to the unseen
   5. 6.5Laplace (add-one) smoothing for unigrams and bigrams
   6. 6.6What add-one costs, and add-k as the softer fix
7. 07Interpolation, backoff and absolute discountingCombining n-gram orders by linear interpolation or backoff, stupid backoff at web scale, tuning on held-out data, and the Church and Gale observation that motivates subtracting a fixed discount of about 0.75.6 conceptsSlides 68-8036 min
   1. 7.1Linear interpolation: mixing unigram, bigram and trigram
   2. 7.2Choosing the weights on held-out data
   3. 7.3Backoff, and stupid backoff at web scale
   4. 7.4Why add-k is not enough: the idea of discounting
   5. 7.5Church and Gale: measuring the discount on held-out data
   6. 7.6Absolute discounting and choosing d
8. 08Kneser-Ney smoothing for bigramsWhy backing off to raw unigram frequency fails (reading Kong versus reading glasses), the continuation probability that counts distinct contexts, the interpolated Kneser-Ney bigram formula, and a full step-by-step toy computation.6 conceptsSlides 81-9436 min
   1. 8.1Why raw frequency is the wrong thing to back off to
   2. 8.2Counting contexts instead of tokens: continuation count and P_cont
   3. 8.3The interpolated Kneser-Ney bigram formula
   4. 8.4Where lambda comes from and why everything sums to 1
   5. 8.5Computing Kneser-Ney by hand on the Hong Kong corpus
   6. 8.6Frequency versus diversity, and the history Hong sanity check
9. 09Recursive and modified Kneser-NeyThe recursive interpolated Kneser-Ney form for higher-order n-grams, the KN count that switches to continuation counts at lower orders, termination at a uniform distribution, modified KN with three discounts, and why neural LMs came next.6 conceptsSlides 95-10136 min
   1. 9.1One formula for every order: Kneser-Ney as a recursion
   2. 9.2Which count each level uses: raw at the top, continuation below
   3. 9.3Where the recursion stops: unigrams, a uniform floor, and <UNK>
   4. 9.4Three discounts instead of one: modified Kneser-Ney
   5. 9.5Kneser-Ney in real toolkits: tuning, KenLM and SRILM
   6. 9.6Why n-grams hit a wall and neural language models came next
10. 10Entropy, cross-entropy and chapter summaryEntropy as uncertainty in bits, cross-entropy of a model as an upper bound on true entropy, perplexity as two to the cross-entropy, and the chapter's key takeaways.4 conceptsSlides 102-10524 min
    1. 10.1Entropy as average surprise in bits
    2. 10.2Cross-entropy, its upper bound, and perplexity as two to the cross-entropy
    3. 10.3The chapter in one picture: each problem, its fix, and the next problem
    4. 10.4Where to read more: the primary textbook and its draft dates

CGlossary and reference

• GlossaryEvery term from the lecture, defined once, with links back to the slides that use it.
• Reference sheetThe lecture on one printable page, for revision before a quiz or exam.