Interpolation and Backoff

Let's back up to our original motivation. At the start of our discussion on smoothing, we proceeded from the intuition that, as humans, we almost never judge the probability of a given token sequence as literally 0. Many token sequences may be unlikely, but they're not impossible.

Smoothing is a "blunt instrument" approach to mathematically formalizing this intuition. By adding "fake counts" it ensures that no token has literally 0 probability. But the bluntness comes from the fact that the \( k \) in add-\( k \) smoothing is a constant; it is not a function of the actual context. This limitation may strike us as unsatisfying. Let's think back to our "Seven cat cafes are located near Los Angeles" example. In order to make the probability of "Angeles" following the context "Seven cat cafes are located near Los" nonzero, smoothing would simply pretend that we've actually seen the token "Angeles" follow the context "Seven cat cafes are located near Los" \( k \) times.

Yet this feels misaligned with how a human would resolve the problem. As humans, we are probably more inclined to say that tokens like "Seven", "cafes", etc. are actually irrelevant, and that almost all of the intuition we need to determine the probability of "Angeles" is determined by the single token "Los". We judge the probability of "Angeles" following "Los" to be high regardless of what's in the rest of the context; conversely, if the last token of the context had been "San", then we would think "Angeles" is unlikely as the next token (but "Francisco" becomes much more likely). In other words: sometimes, we actually get more information out of reducing the amount of context!

As it turns out, there's a second approach to handling zero probabilities that matches this intuition much more closely. This approach is known as interpolation.

Interpolation

Interpolation proceeds from the premise that, if you're going to bother training an \( n \)-gram Markov language model, you might as well simultaneously train an \( (n-1) \)-gram model, and an \( (n-2) \)-gram model, and all the way down to the unigram level. After all, the code and logic are exactly the same, the only thing that changes is the size of the context window.

If you have this set of multiple models (with successively reduced context sizes), then instead of always sampling from the probability given by the biggest model, you can aggregate the model results. How can we aggregate them? Well, one naive first try might be to simply sum them. For example:

$$ P_{agg}(\text{"Angeles"}|\text{"near Los"}) = P(\text{"Angeles"}|\text{"near Los"}) + P(\text{"Angeles"}|\text{"Los"}) + P(\text{"Angeles"}) $$

But this naive approach runs into the same problem as our naive first attempt at smoothing: it could result in an invalid probability. Consider the most extreme case where all three probabilities in the sum are equal to 1.0. Then the sum would give us \( P_{agg}(\text{"Angeles"}|\text{"located near Los"}) = 3.0 \), which is definitely not a valid probability!

The fix is actually an approach that is fairly common throughout machine learning: instead of taking a direct sum, we take a weighted sum with weights that individually add up to 1:

$$ P_{agg}(\text{"Angeles"}|\text{"near Los"}) = \lambda_3 P(\text{"Angeles"}|\text{"near Los"}) + \lambda_2 P(\text{"Angeles"}|\text{"Los"}) + \lambda_1 P(\text{"Angeles"}) $$

$$ (\text{where } \lambda_3 + \lambda_2 + \lambda_1 = 1) $$

This way, even in the extreme case where all the individual probabilities are equal to 1.0, we end up just taking the sum of the weights, which we have defined to be 1.0.

In CS 159, we don't require you to actually know how to compute weights for interpolation. In practice, they are often computed using an algorithm known as the expectation maximization (EM) algorithm, which we won't cover in this class (but which you may learn about if you take a machine learning class).

One last thing to notice about interpolation: like smoothing, it is guaranteed to always give a nonzero probability as the result. This is because the last term in the sum is the unigram probability: the probability of the token without any context. This should always be nonzero since any token we're considering would be a token in the vocabulary, and the unigram probability is just the relative frequency of that token in the training data (which can't be zero since the token must have appeared in the training data to be in the vocabulary to begin with).

Backoff

Interpolation is a neat way of mathematically approximating our intuition that we don't always need the entire context to make a judgement about the likely next token. However, it suffers from the drawback of relying on weights that need to be learned. Backoff is a similar technique that uses a much simpler algorithm.

Like interpolation, backoff assumes that we've trained Markov language models for all context sizes from \( n \)-gram (for some desired \( n \)) down to unigram. Unlike interpolation, we do not combine the model probabilities. Instead, we simply check each model, starting from the \( n \)-gram model and working our way down, and take the first nonzero probability we find.

Once again, let's say we're trying to compute \( P(\text{"Angeles"}|\text{"near Los"}) \). This is a case where the context size is 2, so it's a trigram model. We would simply check this probability in the trigram model (which, remember, is estimated as the relative frequency \( R(\text{"near"}, \text{"Los"}, \text{"Angeles"}) \)). If it's nonzero, we're all good and we'll use that probability. If it is zero, we will back off to the bigram model, checking \( P(\text{"Angeles"}|\text{"Los"}) \). Again, if that's nonzero we're all good; if it is zero, we'll back off again to the unigram model and check \( P(\text{"Angeles"}) \), which as noted above is guaranteed to be nonzero.

We can write this algorithm in pseudocode as follows, where t is the next-token candidate whose probability we want, and c is a context (a list of preceding tokens):

function backoff(c, t):
    while c is nonempty:
        let p = P(t|c) as estimated by the relevant Markov language model
        if p > 0:
            return p
        else:
            pop the first element from c (the size of c gets reduced by 1)
    return P(t), the unigram probability of token t

Some versions of backoff multiply the probability by a fixed constant weight \( \lambda \) on every iteration of the loop, partly imitating the weighting done in interpolation. Unlike in interpolation, however, this weight is not learned and is instead an arbitrary constant.

(When logged in, completion status appears here.)