Katz's back-off model
Katz back-off is a generative n-gram language model that estimates the conditional probability of a word given its history in the n-gram. It accomplishes this estimation by backing off through progressively shorter history models under certain conditions. By doing so, the model with the most reliable information about a given history is used to provide the better results.
The model was introduced in 1987 by Slava M. Katz. Prior to that, n-gram language models were constructed by training individual models for different n-gram orders using maximum likelihood estimation and then interpolating them together.
Method
The equation for Katz's back-off model is:where
Essentially, this means that if the n-gram has been seen more than k times in training, the conditional probability of a word given its history is proportional to the maximum likelihood estimate of that n-gram. Otherwise, the conditional probability is equal to the back-off conditional probability of the -gram.
The more difficult part is determining the values for k, d and α.
is the least important of the parameters. It is usually chosen to be 0. However, empirical testing may find better values for k.
is typically the amount of discounting found by Good–Turing estimation. In other words, if Good–Turing estimates as, then
To compute, it is useful to first define a quantity β, which is the left-over probability mass for the -gram:
Then the back-off weight, α, is computed as follows:
The above formula only applies if there is data for the "-gram". If not, the algorithm skips n-1 entirely and uses the Katz estimate for n-2.