Elamur Research⌕
☰
home / papers / 1995 / An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities

An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities

Summary

The paper deals with stochastic context-free grammars (SCFG) and four classical problems associated with them: the probability of a string, the most probable parse, the probability of a prefix, and the training of rule probabilities. Previously these problems were solved by separate algorithms, mostly bottom-up ones based on CYK. Stolcke proposes a probabilistic extension of the top-down Earley parser that solves all four problems within a single algorithm. Prefix and substring probabilities are built up step by step during one pass that moves from left to right, so the estimate for a prefix is available as soon as its last word has been read. Viterbi parsing and rule re-estimation require one more, backward, pass over the chart. The algorithm accepts rules of any form without conversion to CNF. On sparse grammars it is more efficient, because top-down prediction immediately prunes impossible branches. The main practical significance of the work is that incremental prefix probabilities make it possible to predict the next word. As a result, SCFGs can be used as language models in place of finite-state ones, for example in speech recognition decoders.

Key points

  • The algorithm computes four quantities: (a) probabilities of successive prefixes, (b) inside probabilities of substrings, including the whole sentence, (c) the Viterbi parse, (d) the expected number of uses of each rule, needed for EM training.
  • Quantities (a) and (b) are computed in a single left-to-right pass. Quantities (c) and (d) require an additional backward pass over the Earley chart.
  • The conditional probability of the next word is obtained by dividing the probability of the longer prefix by the probability of the shorter one. It can be used in Viterbi and stack decoders, as well as for deriving n-gram probabilities from an SCFG (Stolcke and Segal, 1994).
  • In the worst case, the complexity is no worse than that of known specialized algorithms, and on certain classes of grammars it is considerably better. Chomsky Normal Form (CNF) is not required.
  • There are extensions for partially bracketed input and for finding partial parses with their probabilities for ungrammatical sentences. The paper appeared in Computational Linguistics (ACL, 1995) and derives from the ICSI technical report TR-93-065.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cite

Cite as Andreas Stolcke. 1995. An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities.

The paper itself, not this page. BibTeX from the library's record of the work. arXiv cmp-lg/9411029

@misc{stolcke1995efficient,
  title = {{An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities}},
  author = {Andreas Stolcke},
  year = {1995},
  eprint = {cmp-lg/9411029},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cmp-lg/9411029}
}

References

34 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aho, Alfred V., and Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing. Prentice-Hall. find
  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. find
  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. find
  4. Baum, Leonard E.; Petrie, Ted; Soules, George; and Weiss, Norman (1970). "A maximization technique occuring in the statistical analysis of probabilistic functions in Markov chains." The Annals of Mathematical Statistics, 41(1), 164-171. find
  5. Booth, Taylor L., and Thompson, Richard A. (1973). "Applying probability measures to abstract languages." IEEE Transactions on Computers, C-22(5), 442-450. find
  6. Briscoe, Ted, and Carroll, John (1993). "Generalized probabilistic LR parsing of natural language (corpora) with unification-based grammars." Computational Linguistics, 19(1), 25-59. find
  7. Casacuberta, E, and Vidal, E. (1988). "A parsing algorithm for weighted grammars and substring recognition." In Syntactic and Structural Pattern Recognition, Volume F45, NATO ASI Series, edited by Gabriel Ferrat6, Theo Pavlidis, Alberto Sanfeliu, and Horst Bunke, 51-67. Springer Verlag. find
  8. Corazza, Anna; De Mori, Renato; Gretter, Roberto; and Satta, Giorgio (1991). "Computation of probabilities for an island-driven parser." IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(9), 936-950. find
  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. find
  10. Earley, Jay (1970). "An efficient context-free parsing algorithm." Communications of the ACM, 6(8), 451-455. find
  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. find
  12. Graham, Susan L.; Harrison, Michael A.; and Ruzzo, Walter L. (1980). "An improved context-free recognizer." ACM Transactions on Programming Languages and Systems, 2(3), 415-462. find
  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. find
  14. Jelinek, Frederick, and Lafferty, John D. (1991). "Computation of the probability of initial substring generation by stochastic context-free grammars." Computational Linguistics, 17(3), 315-323. our card
  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… find
  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. find
  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. Det… find
  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. find
  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. find
  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. find
  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. find
  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. find
  23. Magerman, David M., and Weir, Carl (1992). "Efficiency, robustness and accuracy in Picky chart parsing." In Proceedings, 30th Annual Meeting of the Association for Computational Linguistics. Newark, Delaware, 40-47. find
  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. find
  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. find
  26. P~iseler, Annedore (1988). "Modification of Earley's algorithm for speech recognition/' In Recent Advances in Speech Understanding and Dialog Systems, volume F46 of NATO ASI Series, edited by H. Niemann, M. Lang, and G. Sagerer, 466-472. Springer Verlag. find
  27. Pereira, Fernando C. N., and Schabes, Yves (1992). "Inside-outside reestimation from partially bracketed corpora." In Proceedings, 30th Annual Meeting of the Association for Computational Linguistics. Newark, Delaware, 128-135. our card
  28. Pereira, Fernando C. N., and Shieber, Stuart M. (1987). Prolog and Natural-Language Analysis. CLSI Lecture Notes Series, Number 10. Center for the Study of Language and Information, Stanford, California. find
  29. Rabiner, L. R., and Juang, B. H. (1986). "An introduction to hidden Markov models." IEEE ASSP Magazine, 3(1), 4-16. find
  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. find
  31. Stolcke, Andreas, and Segal, Jonathan (1994). "Precise n-gram probabilities from stochastic context-free grammars." In Proceedings, 3 lth Annual Meeting of the Association for Computational Linguistics. Las Cruces, New Mexico, 74-79. find
  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. find
  33. Tomita, Masaru (1986). Efficient Parsing for Natural Language. Kluwer Academic Publishers. find
  34. Wright, J. H. (1990). "LR parsing of probabilistic grammars with input uncertainty for speech recognition." Computer Speech and Language, 4, 297-323. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/stolcke-1995-efficient-probabilistic-context-free-parsing/