Leave some probability for things we have not seen Lec 3 · Sep 1 · recapped Lec 4 · Sep 3
If the training text never contains “denied the offer,” a model based only on raw counts gives that continuation zero probability. But an absent example is not enough evidence to conclude that the phrase can never occur.
This problem appears even with a small vocabulary. Take I, like, to, eat, cake, but, want, pizza, right, now, ., Mary, told, her, brother, too. A vocabulary with \(|V|\) distinct words allows \(|V|^2\) possible pairs, and a small training sample leaves most of them unseen.
Smoothing adjusts the probabilities estimated from counts. It reserves some probability for unseen events by taking a little away from events we have already observed.
| Observed counts after “denied the” | Illustrative adjusted counts |
|---|---|
| 3 allegations 2 reports 1 claims 1 request 7 total | 2.5 allegations 1.5 reports 0.5 claims 0.5 request 2 other 7 total |
The total stays at 7, but 2 units are now reserved for other continuations. Dividing by the same total gives a probability distribution that leaves room for events absent from the sample. This table illustrates the idea; it is not the add-one calculation introduced below.
Why a bigger dataset still contains many rare words Lec 3 · Sep 1
Some words appear constantly, while many others appear only a few times. This uneven pattern is described by Zipf's law, a power-law relationship discussed in Zipf's 1949 book Human behavior and the principle of least effort.
Rank the words from most frequent to least frequent. Their frequency tends to decrease roughly according to:
Here \(r\) is the word's rank by frequency. A few words dominate the counts, followed by a long tail of rare words. This is why language-processing methods need to cope with events that occur rarely, or never, in the training sample.
Add one to every possible outcome Lec 3 · Sep 1 · recapped Lec 4 · Sep 3
A classic approach is add-one smoothing, also called Laplace smoothing. Pretend that each possible word has been observed once more than it really has. A zero count becomes 1, and every other count also increases by 1.
The denominator must increase too. In the formulas below, \(V\) is the vocabulary size, so adding one to every possible outcome adds that many observations to the total.
If we increased the numerators but left the denominator unchanged, the probabilities would add up to more than 1. The \(+V\) accounts for all the added counts and keeps the distribution normalized.
What this does to the restaurant-query example
In the Berkeley Restaurant Corpus bigram table, add-one changes every zero count to 1 and increases each nonzero count by 1. We then divide by the enlarged row total, using \((c+1)/(c(w_{i-1})+V)\) with \(V = 1446\).
Put the new probabilities back on the old count scale
Adding one sounds like a small change. To see its actual effect, multiply each smoothed probability by the original context count. The resulting value \(c^*\) is called a reconstituted count: it shows how much of the original row total the event effectively receives now.
The change is large. The effective count for want to falls from 608 to about 238, and chinese food falls from 82 to about 8.2. Although we added only one to each cell, there were so many empty cells that they absorbed a large share of the total probability.
Use a smaller addition when one is too much
Add-k smoothing follows the same rule with a chosen positive amount, often smaller than one, for example 0.5, 0.05, or 0.01:
The amount \(k\) is a hyperparameter: a choice we tune using a separate held-out set, also called a validation set. This lets us check how much smoothing helps on new data before the final test.
The lecture discourages add-one for practical n-gram language models because it can move too much probability into the many unseen combinations. It is still useful in other settings, including Naïve Bayes text classification and problems with fewer zero counts. Add-k gives finer control, but still spreads the added counts uniformly.
Combine long-context and short-context predictions Lec 3 · Sep 1
Suppose we have little evidence about a two-word context. We may still know something about its last word, and we know how frequent the candidate word is overall. Rather than treating all unseen continuations alike, we can use those shorter-context estimates.
Interpolation combines predictions from several context lengths. For a trigram model, mix the unigram, bigram, and trigram probabilities. More generally, combine the n-gram estimate with the (n−1)-gram estimate and so on down to the unigram. The lecture presents this as a more effective approach than add-one smoothing.
The λ weights must be nonnegative and sum to one, so the mixture is still a probability distribution. In the second formula, the context determines the weights: a well-observed context can receive a different balance from one with little evidence.
Choose the weights using separate validation text
We want weights that assign high probability to text the count estimates were not trained on:
- Estimate the n-gram probabilities from the training data, then keep those estimates fixed.
- Search for λ values that maximize the probability of the held-out validation set.
Use the same separation for other hyperparameters, including add-k's \(k\): learn counts on training data, choose settings on validation data, and reserve the test data for the final evaluation.
Let the available text determine the context length Lec 3 · Sep 1
Lecture 3 also introduces the infini-gram idea. Instead of choosing one fixed context length in advance, use the longest matching context available in the corpus, shortening it when necessary. The slides describe this as allowing \(n = \infty\) in principle; the context actually used is still limited by the text that has been observed.
- The lecture discusses models built from open text collections including Dolma, RedPajama, Pile, and C4, which are also used to train large language models.
- These models support searching for n-grams, looking up their counts and probabilities, and generating text.
- Rare and unseen events are a normal part of language data. A model needs a way to handle them when predicting new text.
- Add-one and add-k are easy to calculate. Their uniform adjustment can be too crude for sparse n-gram tables, though these methods are useful in settings such as Naïve Bayes.
- Interpolation draws on estimates from shorter contexts. Tune its weights, and other hyperparameters, on validation data rather than the test set.
- Smoothing helps an n-gram model rely less completely on its training counts. Regularization addresses the same broad problem of overfitting in models such as logistic regression.