Katz Back-off (1987) › How Back-off Works

The Katz back-off method implements a hierarchical decision process that mirrors how humans often reason about uncertain situations. The model begins by trying to use the most specific information available, then progressively falls back to more general information when the specific data is unreliable.

The process starts with the longest n-gram available. If you're building a trigram model and trying to predict what comes after "peanut butter and," the model first checks whether it has sufficient data about this exact three-word sequence. What counts as "sufficient" depends on a threshold, typically requiring that the sequence appear at least a certain number of times in the training data.

If the trigram has insufficient data, the model backs off to a shorter context, using just the bigram "butter and." This shorter sequence appears more frequently in typical training data, providing a more reliable probability estimate. If even the bigram is too sparse, the model backs off further to the unigram "and," and potentially all the way to the base frequency of each word in the vocabulary if necessary.

The discount factor made this approach work. Simply using shorter n-grams when longer ones are unavailable isn't enough. You also need to adjust the probabilities to account for two related problems. First, probability estimates based on limited observations tend to be overconfident. If you've seen "butter and jelly" five times and "butter and jam" twice, you shouldn't conclude that "jelly" has exactly 5/7 probability of following "butter and." The sample is too small to support such precision. Second, you need to reserve some probability mass for events you haven't seen at all.

Katz's discount factor solves both problems simultaneously. It reduces the probability assigned to observed events slightly, creating a pool of probability mass that can be distributed to less frequent or entirely unseen events. This ensures that the model assigns reasonable probabilities across the board. Frequent events still get high probabilities reflecting their commonality. Rare events that appeared in the training data get lower but non-zero probabilities. Most importantly, events that never appeared in training get small but positive probabilities, preventing the model from declaring valid language sequences impossible.