Word Triggers and the EM Algorithm

Word Triggers and the EM Algorithm Christoph Tillmann and Hermann Ney Lehrstuhl ffir Informatik VI Aachen - University of Technology D-52074 Aachen, Germany {t illmann, ney}©inf ormat ik. rwth-aachen, de Abstract In this paper, we study the use of so-called word trigger pairs to improve an existing language model, which is typically a tri- gram model in combination with a cache component. A word trigger pair is de- fined as a long-distance word pair. We present two methods to select the most significant single word trigger pairs. The selected trigger pairs are used in a com- bined model where the interpolation pa- rameters and trigger interaction parame- ters are trained by the EM algorithm. 1 Introduction In this paper, we study the use of so-called word trigger pairs (for short: word triggers) (Bahl et al., 1984, Lau and Rosenfeld, 1993, Tillmann and Ney, 1996) to improve an existing language model, which is typically a trigram model in combination with a cache component (Ney and Essen, 1994). We use a reference model p(wlh), i.e. the con- ditional probability of observing the word w for a given history h. For a trigram model, this history h includes the two predecessor words of the word under consideration, but in general it can be the whole sequence of the last M predecessor words. The criterion for measuring the quality of a lan- guage model p(Wlh ) is the so-called log-likelihood criterion (Ney and Essen, 1994), which for a corpus Wl, ..., wn, ...wN is defined by: F N ~= y~logp(wn[hn), rt-~--1 According to this definition, the log-likelihood cri- terion measures for each position n how well the language model can predict the next word given the knowledge about the preceeding words and com- putes an average over all word positions n. In the context of language modeling, the log-likelihood cri- terion F is converted to perplexity PP, defined by PP := -FIN. For applications where the topic-dependence of the language model is important, e.g. text dicta- tion, the history h may reach back several sentences so that the history length M covers several hundred words, say, M = 400 as it is for the cache model. To illustrate what is meant by word triggers, we give a few examples: airline concerto asks neither we ...... flights ...... orchestra ...... replies ...... nor ...... ourselves Thus word trigger pairs can be viewed as long- distance word bigrams. In this view, we are faced the problem of finding suitable word trigger pairs. This will be achieved by analysing a large text corpus (i.e. several millions of running words) and learning those trigger pairs that are able to improve the base- line language model. A related approach to captur- ing long-distance dependencies is based on stochastic variants of link grammars (Pietra and Pietra, 1994). In several papers (Bahl et al., 1984, Lau and Rosenfeld, 1993, Tillmann and Ney, 1996), selection criteria for single word trigger pairs were studied. In this paper, this work is extended as follows: …

Content truncated to 500 words