A Fast Algorithm for Deleted Interpolation

Deleted interpolation is a widely used technique for smoothing probability distributions associated with Markov models in speech recognition. In recent years it has been used by the IBM Tangora system, the CMU Sphinx system, BBN Byblos system, etc. Jelinek and Mercer showed that the forward-back ward algorithm can be used to obtain linear weighting coefficients for smoothing probability distributions. In this paper we extend some of their results. First we prove a general convexity theorem about linear combinations of probability distributions. Then we show how this theorem can be used to derive a fast algorithm for deleted interpolation.