Precise N-Gram Probabilities From Stochastic Context-Free Grammars

PRECISE N-GRAM PROBABILITIES FROM STOCHASTIC CONTEXT-FREE GRAMMARS Andreas Stolcke and Jonathan Segal University of California, Berkeley and International Computer Science Institute 1947 Center Street Berkeley, CA 94704 {stolcke, j segal}@icsi, berkeley, edu Abstract We present an algorithm for computing n-gram probabil- ities from stochastic context-free grammars, a procedure that can alleviate some of the standard problems associated with n-grams (estimation from sparse data, lack of linguis- tic structure, among others). The method operates via the computation of substring expectations, which in turn is ac- complished by solving systems of linear equations derived from the grammar. The procedure is fully implemented and has proved viable and useful in practice. INTRODUCTION Probabilistic language modeling with n-gram grammars (particularly bigram and trigram) has proven extremely use- ful for such tasks as automated speech recognition, part-of- speech tagging, and word-sense disambiguation, and lead to simple, efficient algorithms. Unfortunately, working with these grammars can be problematic for several reasons: they have large numbers of parameters, so reliable estimation requires a very large training corpus and/or sophisticated smoothing techniques (Church and Gale, 1991); it is very hard to directly model linguistic knowledge (and thus these grammars are practically incomprehensible to human inspec- tion); and the models are not easily extensible, i.e., if a new word is added to the vocabulary, none of the information contained in an existing n-gram will tell anything about the n-grams containing the new item. Stochastic context-free grammars (SCFGs), on the other hand, are not as suscep- tible to these problems: they have many fewer parameters (so can be reasonably trained with smaller corpora); they capture linguistic generalizations, and are easily understood and written, by linguists; and they can be extended straight- forwardly based on the underlying linguistic knowledge. In this paper, we present a technique for computing an n-gram grammar from an existing SCFG--an attempt to get the best of both worlds. Besides developing the mathematics involved in the computation, we also discuss efficiency and implementation issues, and briefly report on our experience confirming its practical feasibility and utility. The technique of compiling higher-level grammat- ical models into lower-level ones has precedents: Zue et al. (1991) report building a word-pair grammar from more elaborate language models to achieve good coverage, by random generation of sentences. In our own group, the current approach was predated by an alternative one that essentially relied on approximating bigram probabili- ties through Monte-Carlo sampling from SCFGs. PRELIMINARIES An n-gram grammar is a set of probabil- ities P(w,~lWlW2...wn_a), giving the probability that wn follows a word string Wl w2... wn-1, for each possible com- bination of the w's in the vocabulary of the language. So for a 5000 word vocabulary, a bigram grammar would have approximately 5000 x 5000 = 25,000,000 free parameters, and a trigram grammar would have ~ 125,000,000,000. This is what we mean when we say n-gram grammars have many parameters. A SCFG is a set of phrase-structure rules, annotated with probabilities of choosing a certain production given the left- hand side nonterminal. For …

Content truncated to 500 words