Generalization, overfitting and add-one smoothing

Train four models on the complete works of Shakespeare, a unigram, a bigram, a trigram and a 4-gram model, and generate sentences from each by sampling one word at a time. The unigram model produces "To him swallowed confess hear both." Every word is Shakespearean, but no word knows its neighbor. The bigram model produces "What means, sir. I confess she?": each adjacent pair is locally fluent, yet the sentence has no plan. The trigram output starts to sound like a play. And the 4-gram model produces "It cannot be but so.", which is not an imitation of Shakespeare at all. It is a line from King John, copied word for word.

Why does more context first help and then turn into copying? A longer context makes the model fit the training set more closely, because each prediction is conditioned on more of what actually happened. But the count table becomes far sparser at the same time. The Shakespeare corpus has N = 884,647 tokens and a vocabulary of V = 29,066 types. There are V² ≈ 844 million possible bigrams, so even the bigram table is overwhelmingly empty, and there are V⁴ ≈ 7 × 10¹⁷ possible 4-grams against fewer than a million observed positions. This is sparsity at its most extreme: almost every long prefix was seen once or a handful of times.

Once the 4-gram sampler has generated "It cannot be", the corpus offers only six words that ever followed that prefix: but, I, that, thus, this and the period. The conditional distribution has only six nonzero entries, each one a continuation that actually occurs in the plays, so sampling from it does not invent anything. It replays training text. That is overfitting in an n-gram model: the parameters describe the particular sentences in the training data rather than the language they came from.

Now train the same kinds of models on about 40 million words of the Wall Street Journal. The trigram model produces "They also point to ninety nine point six billion dollars from two hundred four oh six three percent of the rates of interest stores as Mexico and Brazil on market conditions." This is unmistakably newswire, read aloud with the numbers spelled out. Jurafsky and Martin point out that the Shakespeare and WSJ samples share no generated sentences, and barely even short phrases, although both models were trained on English.

The lesson is that a language model is not a model of "English". It is a model of its own corpus, with that corpus's vocabulary, topics, register and sentence shapes. This is genre dependence, and it means the training data has to match the text the model will be used on, the test set in evaluation and the real input in deployment. Match it along several axes at once:

• Genre and domain. An LM that helps translate legal documents needs legal text. A question-answering system needs a corpus of questions, whose word order and opening words differ sharply from declarative prose.
• Dialect and variety. Tweets in African American English use forms such as finna and den with their own n-gram statistics, and Nigerian Pidgin tweets mix English and local vocabulary in patterns a standard-English model has never counted.
• Style and time. Formal versus conversational register, and language from different decades, shift the counts just as much.

SLP3 puts it bluntly: statistical models are "pretty useless as predictors if the training sets and the test sets are as different as Shakespeare and the WSJ." For a research project on Arabic this is concrete. A model trained on Modern Standard Arabic news will assign low probability to Gulf or Egyptian dialect text and report a high perplexity, not because the model is weak but because it was built for a different variety.

Suppose the training data contains the word ruby and the word slippers, but never the phrase ruby slippers. The maximum likelihood bigram estimate is then P(slippers | ruby) = C(ruby slippers) / C(ruby) = 0. A test sentence containing that phrase gets probability exactly zero, however natural it is.

It helps to separate two kinds of novelty. Older word-level systems faced unseen words, which they mapped to a special <UNK> token. Modern LMs work on subword or byte tokens (BPE from Lecture 02), and with byte-level BPE any word can be spelled from known pieces, so the test set can never contain an unseen token, even when it contains unseen words. But that guarantee is about single tokens. The sequences of known tokens are a different matter: most possible bigrams and trigrams never occur in any finite training set. SLP3 calls these zeros, "sequences that don't occur in the training set but do occur in the test set", and they occur all the time.

Zeros cause two separate problems.

1. They underestimate plausible text. A speech recognizer or translation system that scores "ruby slippers" as impossible will prefer a worse but previously seen alternative.
2. They destroy evaluation. A test-set probability is a product of conditional probabilities, so a single zero sends the whole product to zero, and perplexity is defined from that product.

With P(W) = 0 the formula asks for 1/0. In SLP3's words, "we can't compute perplexity at all, since we can't divide by zero." This is the zero-probability problem, a direct consequence of sparsity.

The standard fix is smoothing, also called discounting: lower the probability of what was seen and give the freed mass to what was not.

Look at the words that followed denied the in a small corpus: allegations three times, reports twice, claims once and request once, seven observations in all. The MLE gives P(allegations | denied the) = 3/7 and gives exactly zero to attack, man, outcome and offer, although "denied the offer" is an ordinary phrase.

Smoothing changes the counts before normalizing. In this example each seen count gives up half a unit, so the counts become 2.5, 1.5, 0.5 and 0.5, and the two freed units are pooled as "other" and shared among the unseen words. The total is still seven, so the distribution still sums to one, but now 2/7 ≈ 0.29 of the probability mass covers words the corpus never showed after denied the.

That is the whole idea of smoothing: when the statistics are sparse, steal a little probability mass from frequent events and give it to unseen ones, so that plausible unseen sequences such as "ruby slippers" or "denied the offer" get a nonzero probability. Every smoothing method answers two questions differently: how much mass to take from each seen count (the discount), and how to divide it among the unseen events. The rest of this part covers the simplest answer, and later parts cover better ones.

Take a toy vocabulary of five types with counts a = 4, b = 3, c = 2, d = 1 and e = 0, so N = 10 tokens and V = 5 types. The MLE is the relative frequency: 0.4, 0.3, 0.2, 0.1 and a zero for e. Now pretend every type was seen once more than it was. The counts become 5, 4, 3, 2, 1, the total becomes 15, and the probabilities become 5/15, 4/15, 3/15, 2/15, 1/15. Nothing is zero, and the five values still sum to one.

That is Laplace (add-one) smoothing. The detail that matters is the denominator. Adding one to each of V counts adds V to the total, so the denominator must grow from N to N + V. Forget it and the probabilities sum to more than one.

For bigrams the same reasoning applies row by row. Each row of the bigram table is the distribution of words following one prefix w_{n-1}. Add one to every cell of that row, including all the zero cells, and the row total grows by the number of cells, which is V.

To see how much smoothing changed the model, it is useful to turn the smoothed probability back into a count on the original scale. Multiplying the smoothed probability by the prefix count gives the reconstituted (or adjusted) count C*, which can be compared directly with the raw count.

Now apply this to the Berkeley Restaurant Project corpus from Part 03: 9332 sentences and V = 1446, with unigram counts i 2533, want 927, to 2417, eat 746, chinese 158, food 1093, lunch 341 and spend 278. The smoothed count table on the slides is simply the raw table plus one in every cell: i want goes from 827 to 828, want to from 608 to 609, chinese food from 82 to 83, and every former zero becomes 1.

Add-one is old. It goes back to Laplace's 1812 law of succession, and was applied to the zero-frequency problem by Jeffreys (1948) after Johnson (1932); Chen and Goodman also credit Lidstone (1920) with the idea of pretending each event occurred once more. SLP3 is clear that Laplace smoothing "does not perform well enough to be used in modern n-gram models", but it is the natural baseline and it works well enough in text classification, where you will meet it again in Naive Bayes.

Compare raw and reconstituted counts. C(want to) falls from 608 to C* ≈ 238, a discount ratio d_c = C*/C = 0.39, and P(to | want) falls from 0.66 to 0.26. C(chinese food) falls from 82 to 8.2, a ratio of d_c = 0.10: the model now believes food follows chinese one time in twenty instead of about half the time. A frequent, highly predictable bigram has been cut by a factor of ten.

The last column explains the pattern. In the chinese row the denominator is 158 + 1446 = 1604, and 1446 of that, about 90%, is pseudo-counts. The invented evidence outweighs the real evidence nine to one. In the i row the pseudo-counts are only 1446 / 3979 ≈ 36%, so the damage is milder. Add-one moves too much mass to unseen events, and it hits rare contexts hardest, because V is fixed while the real count of the prefix is small. In a realistic vocabulary of tens of thousands of types, almost every context is rare in this sense. That is why add-one is a teaching baseline rather than a production language model.

Add-k: a smaller pseudo-count

The obvious repair is to add less. Add-k smoothing adds a fractional k to every count, and therefore kV to the denominator.

Nothing in the training counts tells you what k should be: 0.5, 0.1, 0.01? It is a hyperparameter, chosen by trying several values and keeping the one with the lowest perplexity on a development set. The table shows the trade-off on the chinese and want rows. Here the pseudo-count share is kV / (C(h) + kV), the part of the denominator made of pseudo-counts. It is not the same as the mass given to unseen words, because some pseudo-counts land on seen words too.

As k shrinks, the smoothed estimates climb back toward the MLE, and at k = 0 they are the MLE again, zeros included. So k slides between "trust the counts" and "trust the uniform distribution". Try it yourself below.

Even a well-tuned k does not make additive smoothing a good language model. Gale and Church (1994), as summarized in SLP3, found that add-k gives counts with poor variances and often inappropriate discounts, and Chen and Goodman's large comparison concludes flatly that "additive smoothing performs poorly". The flaw is structural: every unseen continuation of a prefix gets the same pseudo-count, whether it is offer or a random rare word, and the same k is used for every context regardless of how much evidence it has. Real systems use interpolation, backoff and Kneser-Ney, which start in Part 07 with absolute discounting.