Elamur Research⌕
☰
home / papers / 2018 / Unsupervised Grammar Induction with Depth-bounded PCFG

Unsupervised Grammar Induction with Depth-bounded PCFG

Summary

Unsupervised grammar induction tries to learn syntactic structure from raw word strings. Earlier unbounded context-free approaches tended to get stuck in poor solutions. Depth-bounded sequence models had their own limits: some could not express full grammar rules, and others needed very many parameters. Jin et al. propose DB-PCFG, a Bayesian Dirichlet model that learns a PCFG directly. It then derives a depth-bounded version of that grammar through a model-to-model transform adapted from supervised work by van Schijndel et al. (2013). The bound reflects working-memory limits in left-corner parsing, which rule out deep center embedding. This shrinks the space of candidate trees without multiplying rule parameters. The model induces both tree structures and category labels, assuming no linguistic universals beyond memory limits. The authors tested it on transcribed child-directed speech and on Penn Treebank newswire. Its parsing accuracy matched or beat competing systems, and its labels were used consistently, which the authors show in a noun-phrase discovery task. The work matters for cognitive questions about language acquisition and for parsing low-resource languages without annotation.

Key points

  • Comparison systems: CCL, UPPARSE, BMMM+DMV, UHHMM (Shain et al., 2016) and a right-branching baseline. Code is released at github.com/lifengjin/db-pcfg.
  • Penn Treebank setup: WSJ sentences of at most 20 words (WSJ20) were split in half into WSJ20dev for hyperparameter tuning and WSJ20test. A subset of test sentences of at most 10 words formed WSJ10test.
  • Penn Treebank results: DB-PCFG and CCL both beat the right-branching baseline on both test sets. CCL keeps a statistically significant F1 lead, though the gap is small on WSJ20test. DB-PCFG's scores are driven by recall, possibly because it always outputs fully binary trees.
  • Published-results comparison (not strictly comparable): DB-PCFG (D2K15) scores P 65.5 / R 83.6 / F1 73.4 on WSJ10 and P 47.0 / R 63.6 / F1 54.1 on WSJ40. CCL scores F1 75.7 / 57.2 and UPPARSE scores 70.5 / 54.2. DB-PCFG has the highest recall in both cases.
  • Noun phrases and labels: The right-branching baseline scores well on PARSEVAL for child-directed speech but finds noun phrases poorly. DB-PCFG's consistent category labels support NP discovery.

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

Institutions

🎓University of Illinois Urbana-ChampaignUrbana · United States76 works · 63 460 citations🎓Harvard UniversityCambridge · United States64 works · 35 670 citations🎓The Ohio State UniversityColumbus · United States46 works · 16 163 citations🏥Boston Children's HospitalBoston · United States5 works · 657 citations

Cite

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

@article{jin2018unsupervised,
  title = {{Unsupervised Grammar Induction with Depth-bounded PCFG}},
  author = {Jin, Lifeng and Doshi-Velez, Finale and Miller, Timothy and Schuler, William and Schwartz, Lane},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2018},
  doi = {10.1162/tacl\_a\_00016},
  url = {https://doi.org/10.1162/tacl_a_00016}
}

References

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

  1. Steven P. Abney and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. J. Psycholinguistic Research, 20(3):233–250. Taylor Berg-kirkpatrick, Alexandre Bouchard-Côté, John DeNero, and Dan Klein. 2010. Painless unsupervised learning with features. In Proceedings of… find
  2. Yonatan Bisk and Julia Hockenmaier. 2013. An HDP Model for Inducing Combinatory Categorial Grammars. In Transactions Of The Association For Computational Linguistics, pages 75–88. find
  3. Rens Bod. 2006. Unsupervised parsing with U-DOP. In Proceedings of the Conference on Computational Natural Language Learning, pages 85–92. find
  4. Glenn Carroll and Eugene Charniak. 1992. Two experiments on learning probabilistic dependency grammars from corpora. Working Notes of the Workshop on Statistically-Based NLP Techniques, (March):1–13. find
  5. C. K. Carter and R. Kohn. 1996. Markov chain Monte Carlo in conditionally Gaussian state space models. Biometrika, 83(3):589–601. find
  6. Noam Chomsky and George A. Miller. 1963. Introduction to the formal analysis of natural languages. In Handbook of Mathematical Psychology, pages 269– 321. find
  7. Wiley, New York, NY. Noam Chomsky. 1965. Aspects of the Theory of Syntax. find
  8. MIT Press, Cambridge, MA. Christos Christodoulopoulos, Sharon Goldwater, and Mark Steedman. 2012. Turning the pipeline into a loop: iterated unsupervised dependency parsing and POS induction. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational L… find
  9. Alexander Clark. 2001. Unsupervised induction of stochastic context-free grammars using distributional clustering. In Proceedings of the Workshop on Computational Natural Language Learning, volume 7, pages 1–8. Michael Collins, Lance Ramshaw, Jan Hajič, and Christoph Tillmann. 1999. A Statistical P… find
  10. Wenjuan Han, Yong Jiang, and Kewei Tu. 2017. Dependency grammar induction with neural lexicalization and big training data. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1684–1689. find
  11. Zellig Harris. 1954. Distributional structure. In Jerry A. Fodor and Jerrold J. Katz, editors, The Structure of Language: Readings in the Philosophy of Language, volume 10, pages 33–49. find
  12. Prentice-Hall. William P. Headden, III, Mark Johnson, and David Mc-Closky. 2009. Improving unsupervised dependency parsing with richer contexts and smoothing. In Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Techno… find
  13. Yong Jiang, Wenjuan Han, and Kewei Tu. 2016. Unsupervised neural dependency parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, number 61503248, pages 763– 771. find
  14. Mark Johnson, Thomas L. Griffiths, and Sharon Goldwater. 2007. Adaptor grammars: A framework for specifying compositional nonparametric Bayesian models. In Advances in Neural Information Processing Systems, volume 19, page 641. find
  15. Philip N. Johnson-Laird. 1983. Mental models: Towards a cognitive science of language, inference, and consciousness. find
  16. Harvard University Press, Cambridge, MA, USA. Richard Kayne. 1981. Unambiguous Paths. In R. May and J. Koster, editors, Levels of Syntactic Representation, pages 143–183. find
  17. Foris Publishers. Dan Klein and Christopher D. Manning. 2002. A generative constituent-context model for improved grammar induction. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pages 128–135. find our card
  18. Dan Klein and Christopher D. Manning. 2004. Corpus-based induction of syntactic structure: Models of dependency and constituency. In Proceedings of the Annual Meeting on Association for Computational Linguistics, volume 1, pages 478–485. find
  19. Tom Kwiatkowski, Luke S. Zettlemoyer, Sharon Goldwater, and Mark Steedman. 2010. Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1223–1233. find
  20. Tom Kwiatkowski, Sharon Goldwater, Luke S. Zettlemoyer, and Mark Steedman. 2012. A probabilistic model of syntactic and semantic acquisition from child-directed utterances and their meanings. In Proceedings of the Annual Meeting of European Chapter of Association for Computational Linguistics. find our card
  21. Richard K. Larson. 1988. On the double object construction. Linguistic Inquiry, 19(3):335–391. find
  22. Percy Liang, Michael I. Jordan, and Dan Klein. 2009. Probabilistic Grammars and Hierarchical Dirichlet Processes. The Handbook of Applied Bayesian Analysis. find
  23. Brian Macwhinney. 1992. The CHILDES Project: Tools for Analyzing Talk. Lawrence Elrbaum Associates, Mahwah, NJ, third edition. find
  24. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
  25. George A. Miller and Stephen Isard. 1964. Free recall of self-embedded English sentences. Information and Control, 7:292–303. find
  26. Letitia R. Naigles. 1990. Children use syntax to learn verb meanings. The Journal of Child Language, 17:357–374. find
  27. Hiroshi Noji and Mark Johnson. 2016. Using Left-corner Parsing to Encode Universal Structural Constraints in Grammar Induction. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 33–43. find
  28. The Ohio Supercomputer Center. 1987. Ohio Supercomputer Center. \\url{http://osc.edu/ark:/19495/f5s1ph73}. find
  29. John K. Pate and Mark Johnson. 2016. Grammar induction from ( lots of ) words alone. In Proceedings of the International Conference on Computational Linguistics, pages 23–32. find
  30. Lisa Pearl and Jon Sprouse. 2013. Syntactic islands and learning biases: Combining experimental syntax and computational modeling to investigate the language acquisition problem. Language Acquisition, 20(1):23– 68, 1. find
  31. Elias Ponvert, Jason Baldridge, and Katrin Erk. 2011. Simple unsupervised grammar induction from raw text with cascaded finite state models. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pages 1077–1086. find
  32. Philip Resnik. 1992. Left-corner parsing and psychological plausibility. In Proceedings of the International Conference on Computational Linguistics, pages 191– 197. find
  33. Stanley J. Rosenkrantz and Philip M. Lewis, II. 1970. Deterministic left corner parser. In IEEE Conference Record of the 11th Annual Symposium on Switching and Automata, pages 139–152. find
  34. William Schuler, Samir AbdelRahman, Tim Miller, and Lane Schwartz. 2010. Broad-coverage parsing using human-Like memory constraints. Computational Linguistics, 36(1):1–30. find
  35. James Scicluna and Colin de la Higuera. 2014. PCFG induction for unsupervised parsing and language modelling. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1353–1362. find
  36. Yoav Seginer. 2007a. Fast Unsupervised Incremental Parsing. In Proceedings of the Annual Meeting of the Association of Computational Linguistics, pages 384– 391. find
  37. Yoav Seginer. 2007b. Learning Syntactic Structure. Ph.D. thesis, University of Amsterdam. find
  38. Cory Shain, William Bryce, Lifeng Jin, Victoria Krakovna, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. 2016. Memory-bounded left-corner unsupervised grammar induction on child-directed input. In Proceedings of the International Conference on Computational Linguistics, page… find
  39. Mark Steedman. 2000. The Syntactic Process. MIT Press/Bradford Books, Cambridge, MA. find
  40. Marten van Schijndel, Andy Exley, and William Schuler. 2013. A Model of language processing as hierarchic sequential prediction. Topics in Cognitive Science, 5(3):522–540. find
  41. Luke S. Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the Proceedings of the Conference Annual Conference on Uncertainty in Artificial Intelligence, pages 658–666, Arlington, Virgi… find our card
  42. AUAI Press. Willem Zuidema. 2003. How the poverty of the stimulus solves the poverty of the stimulus. In Advances in Neural Information Processing Systems, volume 15, page 51. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/jin-2018-unsupervised-grammar-induction-depth-bounded/