Katz Back-off (1987) › 1987: Katz Back-off

In 1987, Slava Katz published a paper that changed how statistical language models handled sparse data. At the time, researchers were grappling with a problem that seemed almost paradoxical: language is infinite in its creative possibilities, yet any training dataset is finite. When a language model encounters a word sequence it has never seen before, what should it do? Assigning zero probability would make the model brittle and unreliable. Yet claiming to know the probability of something never observed seemed equally problematic.

Katz's solution was both elegant and practical. Rather than trying to estimate probabilities for long sequences that rarely appear in training data, the model should "back off" to shorter sequences that occur more frequently. If you've never seen the phrase "quantum chromodynamics explains," you might still have seen "chromodynamics explains" or simply "explains." This hierarchical approach to probability estimation would become fundamental not just to language modeling but to the broader challenge of learning from sparse data.

The problem Katz addressed has a formal name in machine learning: the curse of dimensionality. In language modeling, this curse manifests in a particularly acute way. As you increase the length of your n-grams from bigrams to trigrams to four-grams and beyond, the number of possible word combinations grows exponentially. A vocabulary of just 10,000 words yields 100 million possible bigrams, one trillion possible trigrams, and 10 quadrillion possible four-grams. Even with massive amounts of training data, the vast majority of these combinations will never appear, leaving the model unable to assign meaningful probabilities to perfectly valid sentences it simply hasn't encountered.