Precise n-gram Probabilities from
Stochastic Context-free Grammars

Andreas Stolcke - Jonathan Segal
University of California, Berkeley
and
International Computer Science Institute
1947 Center Street
Berkeley, CA 94704
stolcke@icsi.berkeley.edu jsegal@icsi.berkeley.edu

Abstract:

We present an algorithm for computing n-gram probabilities 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 linguistic structure, among others). The method operates via the computation of substring expectations, which in turn is accomplished by solving systems of linear equations derived from the grammar. The procedure is fully implemented and has proved viable and useful in practice.

• node1.html
• Introduction
• Preliminaries
• Motivation
• The Algorithm
  • Normal form for SCFGs
  • Probabilities from expectations
  • Computing expectations
  • Computing prefix and suffix probabilities
• Efficiency and Complexity Issues
• Summary
• Experiments
• Conclusions
• Acknowledgments
• Appendix: Consistency of SCFGs
• node16.html
• References
• About this document ...