Elamur Research⌕
☰
home / papers / 1999 / Statistical Properties of Probabilistic Context-Free Grammars

Statistical Properties of Probabilistic Context-Free Grammars

Summary

This theoretical article addresses when probabilistic context-free grammars (PCFGs) define proper distributions over finite parses, and how they relate to Gibbs (maximum-entropy) models. No corpus or experiments are involved. The results are mathematical propositions built from probability theory, branching processes and information theory. Chi extends an earlier result by Chi and Geman (1998), which showed that ML-estimated rule probabilities are always proper, into a general recipe called the relative weighted frequency method. Grammars weighted this way are proper and have finite entropy, and parse sizes have finite moments of every order. The paper also shows that a Gibbs distribution using only rule counts as features is itself a PCFG. Its ML estimates differ numerically from PCFG ones, yet both yield the same parse distribution. Rescaling an improper PCFG by its total mass also produces a PCFG. These results matter because maximum-entropy and relative-entropy language models assume finite entropy and properness. The paper supplies the formal guarantees behind those assumptions.

Key points

  • Improper PCFGs exist. For the grammar S → SS | a, where p is the probability of S → SS, total parse mass equals min(1, 1/p − 1). The grammar is therefore improper whenever p > 1/2.
  • Entropy and parse size are linked. For PCFG distributions, mean parse size is finite exactly when entropy is finite.
  • Branching-process view. PCFGs weighted by the relative weighted frequency method are subcritical, meaning their branching rate is below 1. This generalizes Sánchez and Benedí (1997) with a simpler proof. Connected supercritical PCFGs also become subcritical after renormalization.
  • Identifiability. Distinct production probabilities always give distinct parse distributions. The λ parameters of the rule-count Gibbs form are not identifiable, since infinitely many settings produce the same distribution.
  • Approximation via finite subsets. Production probabilities can be recovered as limits of conditional rule-frequency ratios computed over growing finite sets of parses. The convergence proof relies on Kullback-Leibler divergence and Lagrange multipliers.

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: Natural language processing

Topics Syntax & grammar formalisms

Institutions

🎓University of ChicagoChicago · United States21 works · 49,048 citations

Cite

Cite as Zhiyi Chi. 1999. Statistical Properties of Probabilistic Context-Free Grammars. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{chi1999statistical,
  title = {{Statistical Properties of Probabilistic Context-Free Grammars}},
  author = {Zhiyi Chi},
  journal = {Computational Linguistics},
  year = {1999},
  url = {https://aclanthology.org/J99-1004/}
}

References

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

  1. Abney, Steven P. 1997. Stochastic attribute-value grarmnars. Computational Linguistics, 23(4):597-618. find
  2. Baker, James K. 1979. Trainable grammars for speech recognition. In Speech Communications Papers of the 97th Meeting of the Acoustical Society of America, pages 547-550, Cambridge, MA. find
  3. Baum, Leonard E. 1972. An inequality and associated maximization technique in statistical estimation of probabilistic functions of Markov processes. Inequalities, 3:1-8. find
  4. Berger, Adam L., Stephen Della Pietra, and-Vincent Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39-71. our card
  5. Booth, Taylor L. and Richard A. Thompson. 1973. Applying probability measures to abstract languages. IEEE Transactions on Computers, C-22:442-450. find
  6. Chi, Zhiyi and Stuart Geman. 1998. Estimation of probabilistic context-free grammars. Computational Linguistics, 24(2):299-305. our card
  7. Cover, Thomas M. and Joy A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons, Inc. find
  8. Della Pietra, Stephen, Vincent Della Pietra, and John Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):1-13, April. find
  9. Dempster, Arthur Pentland, N. M. Laird, and Donald B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of Royal Statistical Society, Series B, 39:1-38. find
  10. Grenander, Ulf. 1976. Lectures in Pattern Theory Volume 1, Pattern Synthesis. Springer-Verlag, New York. find
  11. Harris, Theodore Edward. 1963. The Theory of Branching Processes. Springer-Verlag, Berlin. find
  12. Johnson, Mark. 1998. PCFG models of linguistic tree representations. Computational Linguistics. To appear. our card
  13. Mark, Kevin E. 1997. Markov Random Field Models for Natural Language. Ph.D. thesis, Department of Electrical Engineering, Washington University, May. find
  14. Mark, Kevin E., Michael I. Miller, and Ulf Grenander. 1996. Constrained stochastic language models. In S. E. Levinson and L. Shepp, editors, Image Models (and Their Speech Model Cousins). Springer-Verlag, pages 131-140. find
  15. Mark, Kevin E., Michael I. Miller, Ulf Grenander, and Steven P. Abney. 1996. Parameter estimation for constrained context-free language models. In Proceedings of the DARPA Speech and Natural Language Workshop, Image Models (and Their Speech Model Cousins), pages 146-149, Harriman, NY, February. Morg… find
  16. Miller, Michael I. and Joseph A. O'Sullivan. 1992. Entropies and combinatorics of random branching processes and context-free languages. IEEE Transactions on Information Theory, 38(4), July. find
  17. Sdnchez, Joan-Andreu and Josd-Miguel Bened(. 1997. Consistency of stochastic context-free grammars from probabilistic estimation based on growth transformations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(9):1052-1055, September. find
  18. Walters, Peter. 1982. An Introduction to Ergodic Theory. Springer-Verlag, NY. find
  19. Zhu, Song Chun, Ying Nian Wu, and David B. Mumford. 1997. Minimax entropy principle and its application to texture modeling. Neural Computation, 9(8):1627-1660. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/chi-1999-statistical-properties-probabilistic-context-free/