Vol. I · What a Language Model Is Plate 6 of 10data sparsity, unseen contexts, smoothing, overfitting, generalisationDL

Why Counting Fails.

The longer the context a count table remembers, the more of the contexts in new text it has never seen.

An n-gram model with a long context should predict better: more of the past, more information. On the text it was counted from, it does — at n = 8 it nearly memorises the corpus. But on new text the opposite happens. A context of seven characters that never occurred in the training slice has no counts at all, and the model either gives the true next character probability zero (an infinite surprisal) or falls back on something cruder. The number of possible contexts grows exponentially with n, and any corpus is far too small to visit them.

The classical patch is smoothing: pretend every continuation was seen a few extra times, so nothing has probability zero. It removes the infinities but not the problem. The real fix is a model that can say something sensible about a context it has never seen because it resembles contexts it has — which is what a neural network does (plate I.7).

Below: character n-gram models counted from 140 000 characters of the corpus and tested on the next 20 000. Left: the share of test positions whose context never occurred in training, and the share that would get probability zero without smoothing. Right: bits per character on the training and test text, with add-a smoothing.

What you will learn

Measure how often a test context was never seen in training.
Explain why unsmoothed n-gram models assign zero probability to real text.
Apply add-a smoothing and see what it does and does not fix.
Recognise overfitting: training loss falls while held-out loss rises.

Workshop

Character n-gram models from n = 1 to 8. Left: unseen contexts and zero-probability positions on held-out text. Right: bits per character on training text (blue) and held-out text (red); the vertical line marks the chosen n.

The table runs out of experience

At n = 4, 4.2% of the held-out positions have a three-character context that never appeared in the 140 000 training characters, and without smoothing 13.1% of them would get probability zero — an infinite loss from a single unseen continuation. With a little smoothing (a = 0.01) the model spends 3.15 bits per character on held-out text and 1.94 on its own training text. At n = 2 the two are close (3.48 and 3.63); at n = 7 the training text costs only 1.36 bits while held-out text costs 5.13, and 43% of held-out contexts are new. The best n on held-out text is 4, at 3.15 bits.

The gap between the two curves is overfitting: a model that has learned its training data rather than the language. Smoothing only decides how to spend probability on the unseen; heavy smoothing (a = 1) makes long contexts useless, 4.15 bits at n = 4. Decades of better smoothing and back-off schemes — Katz, Kneser–Ney — pushed n-grams a long way, but the root problem stays: a table treats the cat sat and the dog sat as unrelated contexts. A neural model represents tokens as vectors, so similar contexts get similar predictions. That is the step to plate I.7.

Kneser–Ney smoothing (1995) was the strongest n-gram method for twenty years; it backs off to how many different contexts a word appears in, not how often it appears — so Francisco, frequent but almost always after San, is not predicted elsewhere.

Terms

Data sparsity: Most possible contexts are rare or absent in any finite corpus, so counts for them are zero or unreliable.
Smoothing: Moving some probability to unseen events so that nothing gets probability zero.
Overfitting: Fitting the training data so closely that performance on new data gets worse.
Generalisation: Making good predictions on data not seen in training.

Longer contexts make a count table better at reciting and worse at predicting: on new text, most long contexts were never seen. Smoothing hides the zeros; only a model that generalises fixes the problem.