4.5.1 Laplace Smoothing

One simple way to do smoothing might be just to take our matrix of bigram counts, before we normalize them into probabilities, and add one to all the counts. This algorithm is called Laplace smoothing, or Laplace's Law (Lidstone, 1920; Johnson, 1932; Jeffreys, 1948). Laplace smoothing does not perform well enough to be used in modern N-gram models, but we begin with it because it introduces many of the concepts that we will see in other smoothing algorithms and also gives us a useful baseline.

Let's start with the application of Laplace smoothing to unigram probabilities. Recall that the unsmoothed maximum likelihood estimate of the unigram probability of the word $ w_{i} $ is its count $ c_{i} $ normalized by the total number of word tokens N:

$$ P(w_{i})=\frac{c_{i}}{N} $$

Laplace smoothing merely adds one to each count (hence its alternate name add-

one smoothing). Since there are V words in the vocabulary, and each one got incremented, we also need to adjust the the denominator to take into account the extra V observations. $ ^{6} $

$$ P_{Laplace}(w_{i})=\frac{c_{i}+1}{N+V} $$

Instead of changing both the numerator and denominator it is convenient to describe how a smoothing algorithm affects the numerator, by defining an \textit{adjusted count} $ c^* $. This adjusted count is easier to compare directly with the MLE counts, and can be turned into a probability like an MLE count by normalizing by $ N $. To define this count, since we are only changing the numerator, in addition to adding one we'll also need to multiply by a normalization factor $ \frac{N}{N+V} $:

$$ c_{i}^{*}=(c_{i}+1)\frac{N}{N+V} $$

We can now turn $c^{*}$ into a probability $p_{i}^{*}$ by normalizing by $N$.

A related way to view smoothing is as \textit{discounting} (lowering) some non-zero counts in order to get the probability mass that will be assigned to the zero counts. Thus instead of referring to the discounted counts $ c^{*} $, we might describe a smoothing algorithm in terms of a relative \textit{discount} $ d_{c} $, the ratio of the discounted counts to the original counts:

$$ d_{c}=\frac{c^{*}}{c} $$

Now that we have the intuition for the unigram case, let's smooth our Berkeley Restaurant Project bigrams. Fig. 4.5 shows the add-one smoothed counts for the bigrams in Fig. 4.1.

Fig. 4.6 shows the add-one smoothed probabilities for the bigrams in Fig. 4.2. Recall that normal bigram probabilities are computed by normalizing each row of counts by the unigram count:

$$ P(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})}{C(w_{n-1})} $$

For add-one smoothed bigram counts we need to augment the unigram count by the number of total word types in the vocabulary V:

$$ P_{Laplace}^{*}(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})+1}{C(w_{n-1})+V} $$

Thus each of the unigram counts given in the previous section will need to be augmented by V = 1446. The result is the smoothed bigram probabilities in Fig. 4.6.

It is often convenient to reconstruct the count matrix so we can see how much a smoothing algorithm has changed the original counts. These adjusted counts can be computed by Equation (4.24). Fig. 4.7 shows the reconstructed counts.

$$ c^{*}(w_{n-1}w_{n})=\frac{[C(w_{n-1}w_{n})+1]\times C(w_{n-1})}{C(w_{n-1})+V} $$

Note that add-one smoothing has made a very big change to the counts. $ C(\text{want to}) $ changed from 608 to 238! We can see this in probability space as well: $ P(to|\text{want}) $

decreases from .66 in the unsmoothed case to .26 in the smoothed case. Looking at the discount $ d $ (the ratio between new and old counts) shows us how strikingly the counts for each prefix word have been reduced; the discount for the bigram want to is .39, while the discount for Chinese food is .10, a factor of 10!

One snarp change in counts and probabilities occurs because too much probability mass is moved to all the zeros. We could move a bit less mass by adding a fractional count rather than 1 (add-δ smoothing; (Lidstone, 1920; Johnson, 1932; Jeffreys, 1948)), but this method requires a method for choosing δ dynamically, results in an inappropriate discount for many counts, and turns out to give counts with poor variances. For these and other reasons (Gale and Church, 1994), we'll need better smoothing methods for N-grams like the ones we'll see in the next section.