Generalized Interpolation in Decision Tree LM
Denis Filimonov, Mary P. Harper · 2011
In the face of sparsity, statistical models are often interpolated with lower order (backoff) models, particularly in Language Modeling. In this paper, we argue that there is a relation between the higher order and the backoff model that must be satisfied in order for the interpolation to be effective. We show that in n-gram models, the relation is trivially held, but in models that allow arbitrary clustering of context (such as decision tree models), this relation is generally not satisfied. Based on this insight, we also propose a generalization of linear interpolation which significantly improves the performance of a decision tree language model. Note the context space for this function, w i−1 1 is arbitrarily long, necessitating some independence assumption, which usually consists of reducing the relevant context to n − 1 immediately preceding tokens: p(wi|w i−1 1) ≈ p(wi|w i−1 i−n+1) These distributions are typically estimated from observed counts of n-grams wi i−n+1 in the training data. The context space is still far too large; therefore, the models are recursively smoothed using lower order distributions. For instance, in a widely used n-gram LM, the probabilities are estimated as follows: 1