Katz Back-off (1987) › The Problem: Sparse Data
History of Language AIAll chapters Katz Back-off (1987) › The Problem: Sparse DataOne section · Sections in this chapter2 / 10 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
By the mid-1980s, statistical language models based on n-grams had shown considerable promise for applications like speech recognition and machine translation. The fundamental idea was simple: predict the next word based on the previous n words by counting how often each word sequence appeared in training text. A trigram model, for instance, would estimate the probability of seeing "jelly" after "peanut butter and" by counting how many times this exact sequence appeared in the training corpus.
The problem was that language is combinatorially explosive. Consider a trigram model trying to predict the next word after "peanut butter and." If this exact three-word sequence never appeared in your training data, the traditional approach would assign it zero probability. This might seem like a minor technical issue, but it had serious practical consequences. A zero probability means the model considers the sequence impossible, which in turn means it cannot generate sentences containing this phrase or properly evaluate the likelihood of sentences it encounters in real-world use.
This sparsity problem becomes dramatically worse as n increases. Bigrams are relatively manageable with large datasets. Most two-word combinations that native speakers would use appear at least occasionally in large corpora. Trigrams are more challenging but still feasible with substantial training data. However, four-grams and beyond become increasingly sparse. Even in massive text collections, the vast majority of linguistically valid four-word and five-word sequences simply never appear, not because they're ungrammatical or unnatural, but simply because there are too many possible combinations.
Katz's fundamental insight was deceptively simple yet powerful: while we might not have seen "peanut butter and jelly" in our training data, we probably have seen "butter and jelly" or simply "and jelly." These shorter sequences occur more frequently and can provide useful estimates for the longer sequence. The back-off method implements this intuition systematically. When you don't have enough data for a long sequence, fall back to shorter sequences that you do have data for, adjusting the probabilities appropriately to account for the reduced context.