Elamur Research⌕
☰
home / papers / 1998 / Estimation of Probabilistic Context-Free Grammars

Estimation of Probabilistic Context-Free Grammars

Summary

A probabilistic context-free grammar (PCFG) can be "improper," or not tight: if production probabilities are chosen carelessly, some probability mass goes to derivations that never terminate, so finite parse trees together receive less than one. Classical tests based on the expected growth of symbols can detect this. Chi and Geman ask a different question: is a PCFG whose probabilities are estimated from data automatically tight? They consider two settings. In the first, the corpus contains parse trees, and maximum-likelihood estimation reduces to relative frequencies of productions. In the second, the corpus contains only sentences (yields), and the EM (Baum-Welch / inside-outside) algorithm is used. The paper is purely theoretical and has no experiments. Its proofs bound the non-termination probability of each nonterminal and use the fact that the start symbol S appears as a root more often than as an internal node. The main result is that the estimated distribution is always proper. Practitioners can therefore train PCFGs from treebanks or raw text without separately checking for lost probability mass.

Key points

  • Toy example: The grammar A → AA | a is tight only when P(A → AA) ≤ ½. Any finite tree with m leaves uses m−1 AA-rules and m terminal rules, so the relative-frequency estimate always stays below ½.
  • Theorem (parsed corpus): Maximum-likelihood (relative-frequency) production probabilities always give total probability 1 over finite trees. This holds even when null and unit productions are present.
  • Corollary (unparsed corpus): Every EM iterate is tight, provided the grammar has no null or unit productions. Under that assumption, symbol counts are bounded by twice the sentence length.
  • Unobserved nonterminals: Nonterminals that never occur in the sample can receive arbitrary probabilities without affecting the likelihood or tightness, because they are reached with probability zero.
  • Related work: The result settles a question in the spirit of Wetherell's (1980) conjecture. Sánchez and Benedí (1997, IEEE TPAMI) independently gave another proof of the EM result.

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

Cite

Cite as Zhiyi Chi and Stuart Geman. 1998. Estimation of Probabilistic Context-Free Grammars. Computational Linguistics.

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

@article{chi1998estimation,
  title = {{Estimation of Probabilistic Context-Free Grammars}},
  author = {Zhiyi Chi and Stuart Geman},
  journal = {Computational Linguistics},
  year = {1998},
  url = {https://aclanthology.org/J98-2005/}
}

References

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

  1. Baker, J. 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
  2. Baum, L. E. 1972. An inequality and associated maximization techniques in n (6) statistical estimation of probabilistic functions of Markov processes. Inequalities, 3:1-8. find
  3. Booth, T. L. and R. A. Thompson. 1973. Applying probability measures to abstract languages. IEEE Trans. on Computers, C-22:442-450. find
  4. Dempster, A., N. Laird, and D. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39:1-38. find
  5. Grenander, U. 1976. Lectures in Pattern Theory Volume 1, Pattern Synthesis. find
  6. Harris, T. E. 1963. The Theory of Branching Processes. Springer-Verlag, Berlin. find
  7. Hopcroft, J. E. and J. D. Ullman. 1979. find
  8. Introduction to Automata Theory, Languages, and Computation. Addison Wesley. S~nchez, J. A. and J. M. Benedf. 1997. Consistency of stochastic context-free grammars from probabilistic estimation based on growth transformations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:1052-1… find
  9. Stolcke, A. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21:165-201. our card
  10. Wetherell, C. S. 1980. Probabilistic languages: A review and some open questions. Computing Surveys, 12:361-379. find

This page in Markdown → https://md.research.elamur.ai/free/en/papers/chi-1998-estimation-probabilistic-context-free-grammars/