An efficient probabilistic context-free parsing algorithm that computes prefix probabilities

ABSTRACT

We describe an extension of Earley's parser for stochastic context-free grammars that computes the following quantities given a stochastic context-free grammar and an input string: a) probabilities of successive prefixes being generated by the grammar; b) probabilities of substrings being generated by the nonterminals, including the entire string being generated by the grammar; c) most likely (Viterbi) parse of the string; d) posterior expected number of applications of each grammar production, as required for reestimating rule probabilities. Probabilities (a) and (b) are computed incrementally in a single left-to-right pass over the input. Our algorithm compares favorably to standard bottom-up parsing methods for SCFGs in that it works efficiently on sparse grammars by making use of Earley's top-down control structure. It can process any context-free rule format without conversion to some normal form, and combines computations for (a) through (d) in a single algorithm. Finally, the algorithm has simple extensions for processing partially bracketed inputs, and for finding partial parses and their likelihoods on ungrammatical inputs.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Bahl, Lalit R.; Jelinek, Frederick; and Mercer, Robert L. (1983). "A maximum likelihood approach to continuous speech recognition." IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(2), 179--190.
• 3: Baker, James K. (1979). "Trainable grammars for speech recognition." In Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, edited by Jared J. Wolf and Dennis H. Klatt, 547--550.
• 4: Baum, Leonard E.; Petrie, Ted; Soules, George; and Weiss, Norman (1970). "A maximization technique occurring in the statistical analysis of probabilistic functions in Markov chains." The Annals of Mathematical Statistics, 41(1), 164--171.
• 5: Booth, Taylor L., and Thompson, Richard A. (1973). "Applying probability measures to abstract languages." IEEE Transactions on Computers, C-22(5), 442--450.
• 6: Ted Briscoe , John Carroll, Generalized probabilistic LR parsing of natural language (Corpora) with unification-based grammars, Computational Linguistics, v.19 n.1, March 1993
• 7: F. Casacuberta , E. Vidal, A parsing algorithm for weighted grammars and substring recognition, Syntactic and structural pattern recognition, Springer-Verlag New York, Inc., New York, NY, 1988
• 8: Anna Corazza , Renato De Mori , Roberto Gretter , Giorgio Satta, Computation of Probabilities for an Island-Driven Parser, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.9, p.936-950, September 1991 [doi>10.1109/34.93811]
• 9: Dempster, A. P.; Laird, N. M.; and Rubin, D. B. (1977). "Maximum likelihood from incomplete data via the EM algorithm." Journal of the Royal Statistical Society, Series B, 34, 1--38.
• 10: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 11: Fujisaki, T.; Jelinek, F.; Cocke, J.; Black, E.; and Nishino, T. (1991). "A probabilistic parsing method for sentence disambiguation." In Current Issues in Parsing Technology, edited by Masaru Tomita, 139--152. Kluwer Academic Publishers.
• 12: Susan L. Graham , Michael Harrison and Walter L. Ruzzo, An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.415-462, July 1980 [doi>10.1145/357103.357112]
• 13: Jelinek, Frederick (1985). "Markov source modeling of text generation." In The Impact of Processing Techniques on Communications, Volume E91, NATO ASI Series, edited by J. K. Skwirzynski, 569--598. Nijhoff.
• 14: Frederick Jelinek , John D. Lafferty, Computation of the probability of initial substring generation by stochastic context-free grammars, Computational Linguistics, v.17 n.3, p.315-323, September 1991
• 15: Jelinek, Frederick; Lafferty, John D.; and Mercer, Robert L. (1992). "Basic methods of probabilistic context free grammars." In Speech Recognition and Understanding. Recent Advances, Trends, and Applications, Volume F75, NATO ASI Series, edited by Pietro Laface and Renato De Mori, 345--360. Springer Verlag.
• 16: Jones, Mark A., and Eisner, Jason M. (1992). "A probabilistic parser and its applications." In AAAI Workshop on Statistically-Based NLP Techniques, 20--27.
• 17: Jurafsky, Daniel; Wooters, Chuck; Segal, Jonathan; Stolcke, Andreas; Fosler, Eric; Tajchman, Gary; and Morgan, Nelson (1995). "Using a stochastic context-free grammar as a language model for speech recognition." In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, 189--192. Detroit, Michigan.
• 18: Jurafsky, Daniel; Wooters, Chuck; Tajchman, Gary; Segal, Jonathan; Stolcke, Andreas; Fosler, Eric; and Morgan, Nelson (1994). "The Berkeley restaurant project." In Proceedings, International Conference on Spoken Language Processing, 4, 2139--2142. Yokohama, Japan.
• 19: Kupiec, Julian (1992). "Hidden Markov estimation for unrestricted stochastic context-free grammars." In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, 1, 177--180, San Francisco, California.
• 20: Lari, K., and Young, S. J. (1990). "The estimation of stochastic context-free grammars using the Inside-Outside algorithm." Computer Speech and Language, 4, 35--56.
• 21: Lari, K., and Young, S. J. (1991). "Applications of stochastic context-free grammars using the Inside-Outside algorithm." Computer Speech and Language, 5, 237--257.
• 22: Magerman, David M., and Marcus, Mitchell P. (1991). "Pearl: A probabilistic chart parser." In Proceedings, Second International Workshop on Parsing Technologies. Cancun, Mexico, 193--199.
• 23: David M. Magerman , Carl Weir, Efficiency, robustness and accuracy in Picky chart parsing, Proceedings of the 30th annual meeting on Association for Computational Linguistics, p.40-47, June 28-July 02, 1992, Newark, Delaware [doi>10.3115/981967.981973]
• 24: Nakagawa, Sei-ichi (1987). "Spoken sentence recognition by time-synchronous parsing algorithm of context-free grammar." In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, 2, 829--832. Dallas, Texas.
• 25: Ney, Hermann (1992). "Stochastic grammars and pattern recognition." In Speech Recognition and Understanding. Recent Advances, Trends, and Applications, volume F75 of NATO ASI Series, edited by Pietro Laface and Renato De Mori, 319--344. Springer Verlag.
• 26: A. Paeseler, Modification of Earley's algorithm for speech recognition, Proceedings of the NATO Advanced Study Institute on Recent advances in speech understanding and dialog systems, p.465-472, January 1988, Germany
• 27: Fernando Pereira , Yves Schabes, Inside-outside reestimation from partially bracketed corpora, Proceedings of the 30th annual meeting on Association for Computational Linguistics, p.128-135, June 28-July 02, 1992, Newark, Delaware [doi>10.3115/981967.981984]
• 28: Fernando C. N. Pereira , Stuart M. Shieber, Prolog and natural-language analysis, Center for the Study of Language and Information, Stanford, CA, 1987
• 29: Rabiner, L. R., and Juang, B. H. (1986). "An introduction to hidden Markov models." IEEE ASSP Magazine, 3(1), 4--16.
• 30: Schabes, Yves (1991). "An inside-outside algorithm for estimating the parameters of a hidden stochastic context-free grammar based on Earley's algorithm." Paper presented at the Second Workshop on Mathematics of Language, Tarrytown, New York.
• 31: Andreas Stolcke , Jonathan Segal, Precise n-gram probabilities from stochastic context-free grammars, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.74-79, June 27-30, 1994, Las Cruces, New Mexico [doi>10.3115/981732.981743]
• 32: Stolcke, Andreas (1993). "An efficient probabilistic context-free parsing algorithm that computes prefix probabilities." Technical Report TR-93-065, International Computer Science Institute, Berkeley, CA. Revised 1994.
• 33: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 34: Wright, J. H. (1990). "LR parsing of probabilistic grammars with input uncertainty for speech recognition." Computer Speech and Language, 4, 297--323.