Aggregate and mixed-order Markov models for statistical language processing

Aggregate and mixed-order Markov models for statistical language processing Lawrence Saul and Fernando Pereira {Isaul, pereira}©research, att. com AT~T Labs - Research 180 Park Ave, D-130 Florham Park, NJ 07932 Abstract We consider the use of language models whose size and accuracy are intermedi- ate between different order n-gram models. Two types of models are studied in partic- ular. Aggregate Markov models are class- based bigram models in which the map- ping from words to classes is probabilis- tic. Mixed-order Markov models combine bigram models whose predictions are con- ditioned on different words. Both types of models are trained by Expectation- Maximization (EM) algorithms for maxi- mum likelihood estimation. We examine smoothing procedures in which these mod- els are interposed between different order n-grams. This is found to significantly re- duce the perplexity of unseen word combi- nations. 1 Introduction The purpose of a statistical language model is to as- sign high probabilities to likely word sequences and low probabilities to unlikely ones. The challenge here arises from the combinatorially large number of possibilities, only a fraction of which can ever be observed. In general, language models must learn to recognize word sequences that are functionally similar but lexically distinct. The learning problem, one of generalizing from sparse data, is particularly acute for large-sized vocabularies (Jelinek, Mercer, and Roukos, 1992). The simplest models of natural language are n- gram Markov models. In these models, the prob- ability of each word depends on the n- 1 words that precede it. The problems in estimating ro- bust models of this form are well-documented. The number of parameters--or transition probabilities-- scales as V n, where V is the vocabulary size. For typical models (e.g., n = 3, V = 104), this num- ber exceeds by many orders of magnitude the total number of words in any feasible training corpus. The transition probabilities in n-gram models are estimated from the counts of word combinations in the training corpus. Maximum likelihood (ML) esti- mation leads to zero-valued probabilities for unseen n-grams. In practice, one adjusts or smoothes (Chen and Goodman, 1996) the ML estimates so that the language model can generalize to new phrases. Smoothing can be done in many ways--for example, by introducing artificial counts, backing off to lower- order models (Katz, 1987), or combining models by interpolation (Jelinek and Mercer, 1980). Often a great deal of information:is lost in the smoothing procedure. This is due to the great dis- crepancy between n-gram models of different order. The goal of this paper is to investigate models that are intermediate, in both size and accuracy, between different order n-gram models. We show that such models can "intervene" between different order n- grams in the smoothing procedure. Experimentally, we find that this significantly reduces the perplexity of unseen word combinations. The language models in this paper were evalu- ated on the ARPA North American Business News (NAB) corpus. All our experiments used a vo- cabulary of sixty-thousand words, including tokens for punctuation, sentence boundaries, and an …

Content truncated to 500 words