Katz Back-off (1987) › The Mathematical Foundation

Michael BrenndoerferFebruary 27, 20252 min read
History of Language AIAll chapters
Part 2 of 9The Statistical Turn
Chapter 19Katz Back-off (1987) › The Mathematical Foundation
Reading section 5 of 10 · The Mathematical Foundation · 2 minSection 5 of 10 · 2 min

Book contents

History of Language AI9 parts · 110 chaptersView the whole book →
Active chapter 19 of 110

Section 5 of 10 · 2 min read

Katz Back-off (1987) › The Mathematical FoundationOne section · Sections in this chapter5 / 10 ↓
Sections in this chapter10
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

Katz back-off combines probability estimates that have different levels of reliability. The mathematical formulation captures the intuition that we should trust longer contexts when we have good data, but smoothly transition to shorter contexts when we don't.

The general form of the back-off probability can be written as:

P(w∣context)={d×PML(w∣context)if count(context,w)>0α(context)×Pbackoff(w∣shorter_context)otherwiseP(w|context) = \begin{cases} d \times P_{ML}(w|context) & \text{if count}(context, w) > 0 \\ \alpha(context) \times P_{backoff}(w|shorter\_context) & \text{otherwise} \end{cases}

Here, PML(w∣context)P_{ML}(w|context) represents the maximum likelihood estimate based on observed counts, which is simply the number of times we saw word ww following the given context divided by the total times we saw that context. The discount factor dd (which is less than one) reduces this probability slightly to reserve probability mass for unseen events.

When we haven't observed a particular word following a context, we multiply the backed-off probability by a normalization factor α(context). This factor ensures that the probabilities of all possible next words sum to one, maintaining the mathematical requirement that we have a proper probability distribution.

The real sophistication lies in choosing the discount factor dd. Katz used the Good-Turing estimator, a statistical technique with origins in cryptanalysis during World War II. The Good-Turing method estimates the probability of events you've never seen by examining the frequency distribution of events you have seen. Intuitively, if many events that appear once in your data would likely appear again with more data, then events that appear zero times might also have non-zero probability.

The parameter α controls the interpolation between estimates at different levels of specificity. When α equals one, we trust the original estimate completely and ignore the backed-off probability. When α equals zero, we discard the specific context entirely and rely only on the more general distribution. In practice, α varies based on how much data we have for each context. Contexts that appear frequently in training get α values closer to one, reflecting our confidence in the specific estimate. Rare contexts get α values closer to zero, indicating we should rely more heavily on the backed-off distribution.

This mathematical framework achieves something subtle but important: it makes optimal use of limited data by combining information at multiple levels of granularity, weighting each level by its reliability.