Computation of the Probability of Initial Substring Generation by Stochastic Context-Free Grammars
Summary
Speech recognizers need a language model that predicts the next word from the words already heard. If that model is a stochastic context-free grammar (SCFG), the recognizer must know the probability that the grammar produces a sentence beginning with a given word sequence, not just the probability of a complete sentence. The standard Inside Algorithm does not provide this prefix probability. Jelinek and Lafferty derive the Left-to-Right Inside (LRI) Algorithm, which computes it for grammars in Chomsky Normal Form. The derivation is purely theoretical, with no corpus or experiments. Its key ingredient is a set of left-corner quantities: summed probabilities of derivations whose leftmost descendant is a given nonterminal or rule. These are obtained in closed form by inverting a matrix indexed by nonterminals. The algorithm runs in time cubic in prefix length, about twice the cost of the Inside Algorithm. It also updates incrementally as each new word arrives. This makes SCFGs usable as predictive language models for speech, handwriting or OCR systems.
Key points
- The paper places prefix probability alongside three classic SCFG problems: string probability (Inside Algorithm, Baker 1979), best parse (Viterbi), and rule estimation (Inside-Outside). It addresses the same question Wright and Wrigley (1989) studied for LR grammars.
- The left-corner matrix is computed as Q_L = P_L[I − P_L]⁻¹, and word-level left-corner terms as Q_w = [I + Q_L]P_w. Convergence relies on the grammar being proper and on all rule probabilities being positive.
- Cost is O(k³), roughly double the Inside Algorithm. Extending the prefix from k to k+1 words only requires recomputing a limited set of chart entries.
- To obtain the full next-word distribution, the procedure is run M times (once per nonterminal) rather than N times (once per vocabulary word). This is a large saving when the vocabulary is much larger than the nonterminal set.
- The main practical limit is inverting [I − P_L], which becomes hard when the grammar has very many nonterminals.
Topics Syntax & grammar formalisms
Institutions
United StatesCite
Cite as Frederick Jelinek and John D. Lafferty. 1991. Computation of the Probability of Initial Substring Generation by Stochastic Context-Free Grammars. Computational Linguistics.
@article{jelinek1991computation,
title = {{Computation of the Probability of Initial Substring Generation by Stochastic Context-Free Grammars}},
author = {Frederick Jelinek and John D. Lafferty},
journal = {Computational Linguistics},
year = {1991},
doi = {10.5555/971764.971768},
url = {https://doi.org/10.5555/971764.971768}
}References
- Bahl, L. R.; Jelinek, F.; and Mercer, R. L. (1983). "A maximum likelihood approach to continuous speech recognition." IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol PAMI-5, No 2, 1798-1790. find
- Baker, J. K. (1979). "Trainable grammars for speech recognition." Proceedings, Spring Conference of the Acoustical Society of America, Boston, MA, 547-550. find
- Graham, S. L.; Harrison, M. A.; and Ruzzo, W. L. (1980). "An improved context-free recognizer," ACM Transactions on Programming Languages and Systems, Vol 2, No 3, 415-462. find
- Jelinek, E (1985). "Markov source modeling of text generation." In The Impact of Processing Techniques on Communications, edited by J. K. Skwirzinski. Dordrecht: Nijhoff. find
- Wright, J. H.; and Wrigley, E. N. (1989). "Probabilistic LR parsing for speech recognition." International Workshop on Parsing Technologies. 105-114. find
- Younger, D. H. (1967). "Recognition and parsing of context free languages in time N3, " Information and Control 10, 1980-208. find
This page in Markdown → https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/