Smoothing

Earlier, we observed that if the exact phrase "Seven cat cafes are located near Los Angeles" never shows up in the training data, the Markov language model will consider it to have a probability of 0; in other words, that sequence will be considered literally impossible. This strikes us humans as far too extreme—it's an unlikely sequence of tokens, perhaps, but impossible?

Smoothing is an idea that builds upon this intuition. Its goal is to adjust the probability distribution of token sequences such that even the most unlikely sequences have some small but nonzero probability.

Redistributing Probability

At first glance, the naive solution might indeed be to assign a fixed, small-but-nonzero "default" probability to all token sequences that were not seen in the training data. However, a huge problem with this arises right away: language models are meant to represent a probability distribution over possible next tokens, and simply adding more probability to certain tokens would result in an invalid distribution!

As a simple example, consider a scenario where we have a vocabulary with two types: "cat" and "dog". Let's say "cat" has probability 1.0 and "dog" has probability 0.0. The sum of all the probabilities is 1.0, so this is a valid probability distribution. If we manually set the probability of "dog" to 0.001, and do nothing else, then the sum of all the probabilities is 1.0 + 0.001 = 1.001. This sum is greater than 1, making this an invalid probability distribution!

The root of the problem is that, according to probability theory, you can't just add probability to one part of the distribution; any increase in one part of the distribution has to be "paid for" by a decrease in another part. In the simple example, there's only one option available to us: we can subtract 0.001 from the probability of "cat", so that its probability is 0.999. Then the probabilities sum to 0.999 + 0.001 = 1.0, and our distribution is once again valid. But things get more complicated for more realistic distributions, where we might be dealing with way more than two tokens (or token sequences). How do we decide which other probabilities to decrease? Thankfully, it turns out that there's a general approach for redistributing probability...

Add-One Smoothing

Recall that in the simple Markov language model, the conditional probability of a specific token \( w_b \) following a context \( w_a \), written abstractly as \( P(w_b|w_a) \), is estimated as the relative frequency of the sequence \( w_a,w_b \):

$$ P(w_b|w_a) \approx R(w_a,w_b) = \frac{C(w_a,w_b)}{\sum_{w_o \in V}C(w_a,w_o)} $$

This forms a valid probability because \( C(w_a,w_b) \) is the count of the specific token \( w_b \) following context \( w_a \), and we are normalizing that count by the sum of the counts of all tokens \( w_o \) that have ever followed context \( w_a \).

If the probability \( P(w_b|w_a) \) is 0 according to the model, then that must be because we never saw token \( w_b \) following context \( w_a \): the count \( C(w_a,w_b) \) was 0. Our naive intuition from before would say that to make this probability nonzero, we can simply pretend we actually did see token \( w_b \) following context \( w_a \). We don't want to make the probability too big, so let's set our "fake count" to 1: that is, instead of accepting \( C(w_a,w_b) = 0 \), we could instead pretend that \( C(w_a,w_b) = 1 \).

This works fine for an isolated case. In practice, however, there will be many counts that are 0, especially for longer (and therefore more specific) contexts. Rather than painstakingly keeping track of all the counts we manually set to 1, the more common approach is to just globally pretend that all tokens were seen one more time than they were actually seen. So, if the count of \( w_b \) after \( w_a \) was actually 0 we'll pretend it was 1...but if the count was actually already 1, we'll pretend it was 2. If the count was actually 42 we'll pretend it was 43. And so on and so forth.

This approach is preferred because it makes the math cleaner. Since we're just globally adding 1 to everything, the modified relative frequency becomes:

$$ R_s(w_a,w_b) = \frac{C(w_a,w_b)+1}{\sum_{w_o \in V}(C(w_a,w_o)+1)} = \frac{C(w_a,w_b)+1}{\sum_{w_o \in V}C(w_a,w_o)+\sum_{w_o \in V} 1} = \frac{C(w_a,w_b)+1}{\sum_{w_o \in V} C(w_a,w_o) + |V|} $$

Where \( |V| \) is the total size of the vocabulary.

This approach is known as add-one smoothing, where "add-one" comes from the fact that we have, well, added one to all the counts.

Generalizing: Add-\( k \) Smoothing

We used 1 as the add-on count somewhat arbitrarily, but we could have chosen any number. So add-one smoothing is actually a special case of add-\( k \) smoothing where \( k=1 \). The corresponding more general formula for the modified relative frequency then becomes:

$$ R_s(w_a,w_b) = \frac{C(w_a,w_b)+k}{\sum_{w_o \in V}C(w_a,w_o)+k|V|} $$

Although we conceptually think of \( k \) as representing a "fake extra count" (that is, some number of extra times we saw token \( w_o \) after context \( w_a \)), you may notice that the math doesn't actually constrain \( k \) to be an integer. In practice, fractional values of \( k \) that are less than 1 are quite common. A fractional \( k \) doesn't have a clean human interpretation, but the math still works.

The Effects of Different Values of \( k \)

How do we choose a value of \( k \)? This is yet another human decision, so really you can pick any value you like, but it might help to first build some intuition about what increasing the value of \( k \) actually does.

Keeping for the moment our interpretation of \( k \) as a fake extra count (setting aside the complication of fractional \( k \)'s), these fake extra counts "steal" probability mass from the real counts. For example, suppose we had a small corpus where most token counts are less than 10. If we set \( k=50 \), then the effective count of most tokens is dominated by the fake counts contributed by \( k \). In fact, we can make it even more extreme: if we set \( k \) to a ridiculous number like 10000, then the probability mass is almost entirely just the fake counts; the real counts are so small that they would barely register as noise, and we would effectively be saying that all tokens have equal probability.

It might be easier to actually see the effects of different values of \( k \) on some sample data. In the applet below, you can see a toy probability distribution over some tokens. You can drag the slider to increase the value of \( k \).

You should observe that as \( k \) increases, the probability distribution starts to look more and more even, matching our intuition from above.

So while there is no universal rule for what \( k \) should be, in general you should be thinking about how much effect you want the true counts to have on the probabilities. The smaller \( k \) is, the more similar the probability distribution is to the raw counts.

(When logged in, completion status appears here.)

Previous Page Next Page