Elamur Research⌕
☰
home / papers / 2002 / A Generative Constituent-Context Model for Improved Grammar Induction

A Generative Constituent-Context Model for Improved Grammar Induction

Summary

The paper addresses unsupervised grammar induction: recovering unlabeled syntactic trees from part-of-speech sequences without any annotated parses. Klein and Manning replace their earlier conditional model with a generative Constituent-Context Model (CCM). The CCM scores every contiguous span of a sentence, whether it is a constituent or a distituent, through two parts: the span's yield (its tag sequence) and its context (the tags immediately before and after it). A prior that is uniform over binary trees and zero elsewhere forces EM to consider only coherent, non-crossing bracketings. A cubic inside-outside-style dynamic program computes the expected counts. Experiments on ATIS and short Penn treebank WSJ sentences give the best published unsupervised parsing scores of the time, about 71% F1 on non-trivial brackets for WSJ-10. Results stay well above a right-branching baseline even when the input tags are induced by distributional clustering. The work matters because it combines parameter search with distributional clustering in a model that is stable, fast, deterministic, and whose likelihood tracks accuracy.

Key points

  • On WSJ sentences, the CCM cuts parsing error by 13% relative to the authors' earlier conditional model. The 2-class version reaches F1 71.1 (precision 63.8, recall 80.2), and a 12-class variant gets 70.9.
  • Reference points on the same F1 measure:
    • right-branching baseline: 60.0
    • DEP-PCFG (dependency PCFG trained with EM from uniform initialization): 48.2
    • supervised dependency PCFG: 53.5
    • supervised treebank PCFG: 82.1
  • With induced tags, F1 drops to 63.2. Those tags come from 200 word classes, built by:
    • counting left and right co-occurrence with the 500 most frequent words (Treebank plus 1994–96 WSJ text),
    • reducing the vectors to 50 dimensions with SVD,
    • clustering with weighted k-means.
  • With induced tags, VP and S recall actually rise. The authors attribute this to nouns being spread across many induced classes.
  • Training is robust and deterministic:
    • changing smoothing counts tenfold in either direction moved F1 by under 1%;
    • convergence came by iteration 38 (usually within 40, nearly always within 80);
    • F1 and log-likelihood both rose monotonically during training.

Interesting ideas

  • I1. Model non-constituents explicitly. The model gives distituent spans their own yield and context distributions, so the constituent/non-constituent decision becomes a probabilistic choice. This framing could carry over to other segmentation or chunking problems.
  • I2. Turn clustering into structure induction with a constrained prior. Plain two-class clustering of spans would collapse into mostly distituent classes. Restricting the bracketing prior to valid binary trees makes the same model induce trees. Placing structural constraints in the prior, rather than in heuristic filters, is a reusable trick.
  • I3. Start EM symmetrically. Uniform initialization, rather than random seeds, lets the data break the symmetry, and the authors found it gave better grammars than Carroll and Charniak's random starts. It is worth trying in any EM setup with many local optima.
  • I4. Bound what the model class can achieve. Training the supervised version of the same model family (e.g., the supervised dependency PCFG) separates search failures from limits of the representation. This is a cheap diagnostic for any unsupervised method.
  • I5. Check for gold-tag leakage. Rerunning the pipeline with distributionally induced tags tests whether the results depend on syntactic hints hidden in the treebank tagset. Tracking likelihood against accuracy across iterations is a similarly useful sanity check.

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: Treebanks

Cited by

102 papers of our library cite it (of the 140884 whose bibliographies we read); 4 of them have a page here, 98 not yet.

Cite

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

@inproceedings{klein2002generative,
  title = {{A Generative Constituent-Context Model for Improved Grammar Induction}},
  author = {Klein, Dan and Manning, Christopher D.},
  booktitle = {Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics},
  year = {2002},
  doi = {10.3115/1073083.1073106},
  url = {https://doi.org/10.3115/1073083.1073106}
}

References

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

  1. Stephen P. Abney. 1987. The English Noun Phrase in its Sentential Aspect. Ph.D. thesis, MIT. find
  2. Pieter Adriaans and Erik Haas. 1999. Grammar induction as substructural inductive logic programming. In James Cussens, editor, Proceedings of the 1st Workshop on Learning Language in Logic, pages 117–127, Bled, Slovenia. find
  3. James K. Baker. 1979. Trainable grammars for speech recognition. In D. H. Klatt and J. J. Wolf, editors, Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, pages 547–550. find
  4. Eric Brill. 1993. Automatic grammar induction and parsing free text: A transformation-based approach. In ACL 31, pages 259–265. find
  5. Glenn Carroll and Eugene Charniak. 1992. Two experiments on learning probabilistic dependency grammars from corpora. In C. Weir, S. Abney, R. Grishman, and R. Weischedel, editors, Working Notes of the Workshop Statistically-Based NLP Techniques, pages 1–13. AAAI Press. find
  6. Stanley F. Chen. 1995. Bayesian grammar induction for language modeling. In ACL 33, pages 228–235. find
  7. Alexander Clark. 2000. Inducing syntactic categories by context distribution clustering. In The Fourth Conference on Natural Language Learning. find
  8. Alexander Clark. 2001. Unsupervised induction of stochastic context-free grammars using distributional clustering. In The Fifth Conference on Natural Language Learning. find
  9. Steven Paul Finch. 1993. Finding Structure in Language. Ph.D. thesis, University of Edinburgh. find
  10. M. A. K. Halliday. 1994. An introduction to functional grammar. Edward Arnold, London, 2nd edition. find
  11. Dan Klein and Christopher D. Manning. 2001a. Distributional phrase structure induction. In Proceedings of the Fifth Conference on Natural Language Learning (CoNLL 2001), pages 113–120. find
  12. Dan Klein and Christopher D. Manning. 2001b. Natural language grammar induction using a constituent-context model. In Advances in Neural Information Processing Systems, volume 14. MIT Press. find
  13. K. Lari and S. J. Young. 1990. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 4:35–56. find
  14. Donald Cort Olivier. 1968. Stochastic Grammars and Language Acquisition Mechanisms. Ph.D. thesis, Harvard University. find
  15. Fernando Pereira and Yves Schabes. 1992. Inside-outside reestimation from partially bracketed corpora. In ACL 30, pages 128–135. find our card
  16. Andrew Radford. 1988. Transformational Grammar. Cambridge University Press, Cambridge. find
  17. Hinrich Schütze. 1995. Distributional part-of-speech tagging. In EACL 7, pages 141–148. find
  18. Andreas Stolcke and Stephen M. Omohundro. 1994. Inducing probabilistic grammars by Bayesian model merging. In Grammatical Inference and Applications: Proceedings of the Second International Colloquium on Grammatical Inference. Springer Verlag. find
  19. M. van Zaanen. 2000. ABL: Alignment-based learning. In COLING 18, pages 961–967. find
  20. J. G. Wolff. 1988. Learning syntax and meanings through optimization and distributional analysis. In Y. Levy, I. M. Schlesinger, and M. D. S. Braine, editors, Categories and processes in language acquisition, pages 179–215. Lawrence Erlbaum, Hillsdale, NJ. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/klein-2002-generative-constituent-context-model-improved/