New Techniques for Context Modeling

New Techniques for Context Modeling Eric Sven Ristad and Robert G. Thomas Department of Computer Science Princeton University {ristad, rgt }~cs. princeton, edu Abstract We introduce three new techniques for sta- tistical language models: extension mod- eling, nonmonotonic contexts, and the di- vergence heuristic. Together these tech- niques result in language models that have few states, even fewer parameters, and low message entropies. 1 Introduction Current approaches to automatic speech and hand- writing transcription demand a strong language model with a small number of states and an even smaller number of parameters. If the model entropy is high, then transcription results are abysmal. If there are too many states, then transcription be- comes computationally infeasible. And if there are too many parameters; then "overfitting" occurs and predictive performance degrades. In this paper we introduce three new techniques for statistical language models: extension modeling, nonmonotonic contexts, and the divergence heuris- tic. Together these techniques result in language models that have few states, even fewer parameters, and low message entropies. For example, our tech- niques achieve a message entropy of 1.97 bits/char on the Brown corpus using only 89,325 parameters. By modestly increasing the number of model param- eters in a principled manner, our techniques are able to further reduce the message entropy of the Brown Corpus to 1.91 bits/char. 1 In contrast, the charac- ter 4-gram model requires 250 times as many pa- rameters in order to achieve a message entropy of only 2.47 bits/char. Given the logarithmic nature of codelengths, a savings of 0.5 bits/char is quite significant. The fact that our model performs signif- icantly better using vastly fewer parameters argues 1The only change to our model selection procedure is to replace the incremental cost formula ALe(w, ~', a) with a constant cost of 2 bits/extension. This small change reduces the test message entropy from 1.97 to 1.91 bits/char but it also quadruples the number of model parameters and triples the total codelength. that it is a much better probability model of natural language text. Our first two techniques - nonmonolonic contexts and exlension modeling - are generalizations of the traditional context model (Cleary and Witten 1984; Rissanen 1983,1986). Our third technique - the di- vergence heuristic - is an incremental model selec- tion criterion based directly on Rissanen's (1978) minimum description length (MDL) principle. The MDL principle states that the best model is the sim- plest model that provides a compact description of the observed data. In the traditional context model, every prefix and every suffix of a context is also a context. Three consequences follow from this property. The first consequence is that the context dictionary is un- necessarily large because most of these contexts are redundant. The second consequence is to attenu- ate the benefits of context blending, because most contexts are equivalent to their maximal proper suf- fixes. The third consequence is that the length of the longest candidate context can increase by at most one symbol at each time step, which impairs the model's …

Content truncated to 500 words