Elamur Research⌕
☰
home / papers / 2019 / Compound Probabilistic Context-Free Grammars for Grammar Induction

Compound Probabilistic Context-Free Grammars for Grammar Induction

Summary

The authors address grammar induction, i.e., learning the hierarchical syntactic structure of sentences from raw, unannotated text. Classical PCFGs are hard to train by direct likelihood maximization. There are two reasons for this: a difficult optimization landscape and overly strict independence assumptions. The authors propose two steps. The first is the neural PCFG: rule probabilities are computed by a neural network over vector representations of symbols. Such a model is noticeably easier to train than a conventional one. The second is the compound PCFG. A continuous latent vector is introduced for each sentence, which shifts the rule probabilities. When the vector is fixed, the model remains an ordinary PCFG. If it is integrated out, however, dependencies arise between distant parts of the tree. Training combines two techniques. Trees are summed over exactly by dynamic programming (inside algorithm). The latent vector is estimated by amortized variational inference with a separate inference network. Evaluated on widely used English and Chinese benchmark datasets, the method holds up well against recent neural approaches that extract syntax from language models. The work shows that probabilistic grammars, previously considered unpromising, are competitive again when combined with modern parameterization.

Key points

  • The compound PCFG is a continuous mixture of PCFGs. The prior distribution of the latent vector z is a spherical Gaussian. z is concatenated with the symbol embeddings, and from this the rule probabilities are computed for each sentence separately.
  • Training uses collapsed amortized variational inference: trees are marginalized exactly, while reparameterized samples from the variational posterior are used for z.
  • The comparison is made with PRPN, ON-LSTM (Shen et al., 2018, 2019), DIORA (Drozdov et al., 2019) and URNNG (Kim et al., 2019). Only tree topology is evaluated, without constituent labels.
  • Limitations: dynamic programming has complexity O(|R||x|³), so training is considerably more expensive in time and memory than for NLM-based systems. The model is also sensitive to parameterization (residual layers in the MLP are important), grammar size, and the optimization method. In the authors' preliminary experiments, a classical PCFG with direct parameterization could not be trained successfully.
  • Code is available: github.com/harvardnlp/compound-pcfg.

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: AI & machine learning

Topics: Syntax & grammar formalisms

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p19-1228 · arXiv 1906.10225

@inproceedings{kim2019compound,
  title = {{Compound Probabilistic Context-Free Grammars for Grammar Induction}},
  author = {Kim, Yoon and Dyer, Chris and Rush, Alexander},
  booktitle = {Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1228},
  eprint = {1906.10225},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p19-1228}
}

References

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

  1. Sanjeev Arora, Nadav Cohen, and Elad Hazan. 2018. On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization. In Proceedings of ICML. find
  2. Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer Normalization. In Proceedings of NIPS. find our card
  3. James K. Baker. 1979. Trainable Grammars for Speech Recognition. In Proceedings of the Spring Conference of the Acoustical Society of America. find
  4. Yoshua Bengio, Jerome Louradour, Ronan Collobert, and Jason Weston. 2009. Curriculum Learning. In Proceedings of ICML. find our card
  5. James O. Berger. 1985. Statistical Decision Theory and Bayesian Analysis. Springer. find
  6. Rens Bod. 2006. An All-Subtrees Approach to Unsupervised Parsing. In Proceedings of ACL. find
  7. Glenn Carroll and Eugene Charniak. 1992. Two Experiments on Learning Probabilistic Dependency Grammars from Corpora. In AAAI Workshop on Statistically-Based NLP Techniques. find
  8. Andrew Drozdov, Patrick Verga, Mohit Yadev, Mohit Iyyer, and Andrew McCallum. 2019. Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Auto-Encoders. In Proceedings of NAACL. find
  9. Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. 2019. Gradient Descent Provably Optimizes Over-parameterized Neural Networks. In Proceedings of ICLR. find
  10. Greg Durrett and Dan Klein. 2015. Neural CRF Parsing. In Proceedings of ACL. find
  11. Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. 2016. Recurrent Neural Network Grammars. In Proceedings of NAACL. find
  12. Dave Golland, John DeNero, and Jakob Uszkoreit. 2012. A Feature-Rich Constituent Context Model for Grammar Induction. In Proceedings of ACL. find
  13. Junxian He, Graham Neubig, and Taylor Berg-Kirkpatrick. 2018. Unsupervised Learning of Syntactic Structure with Invertible Neural Projections. In Proceedings of EMNLP. find
  14. Eugene Charniak. 1993. Statistical Language Learning. MIT Press. find
  15. Phu Mon Htut, Kyunghyun Cho, and Samuel R. Bowman. 2018. Grammar Induction with Neural Language Models: An Unusual Replication. In Proceedings of EMNLP. find
  16. Danqi Chen and Christopher D. Manning. 2014. A Fast and Accurate Dependency Parser using Neural Networks. In Proceedings of EMNLP. find our card
  17. Yun Huang, Min Zhang, and Chew Lim Tan. 2012. Improved Constituent Context Model with Features. In Proceedings of PACLIC. find
  18. Mingda Chen, Qingming Tang, Sam Wiseman, and Kevin Gimpel. 2019a. Controllable Paraphrase Generation with a Syntactic Exemplar. In Proceedings of ACL. find our card
  19. Lifeng Jin, Finale Doshi-Velez, Timothy Miller, William Schuler, and Lane Schwartz. 2018. Unsupervised Grammar Induction with Depth-bounded PCFG. In Proceedings of TACL. find our card
  20. Mingda Chen, Qingming Tang, Sam Wiseman, and Kevin Gimpel. 2019b. A Multi-task Approach for Disentangling Syntax and Semantics in Sentence Sepresentations. In Proceedings of NAACL. find
  21. Mark Johnson. 1998. PCFG Models of Linguistic Tree Representations. Computational Linguistics, 24:613–632. find our card
  22. Alexander Clark. 2001. Unsupervised Induction of Stochastic Context Free Grammars Using Distributional Clustering. In Proceedings of CoNLL. find
  23. Mark Johnson, Thomas L. Griffiths, and Sharon Goldwater. 2007. Bayesian Inference for PCFGs via Markov chain Monte Carlo. In Proceedings of NAACL. find our card
  24. Shay B. Cohen. 2016. Bayesian Analysis in Natural Language Processing. Morgan and Claypool. find
  25. Shay B. Cohen, Kevin Gimpel, and Noah A Smith. 2009. Logistic Normal Priors for Unsupervised Probabilistic Grammar Induction. In Proceedings of NIPS. find
  26. Shay B. Cohen and Noah A Smith. 2009. Shared Logistic Normal Distributions for Soft Parameter Tying in Unsupervised Grammar Induction. In Proceedings of NAACL. find
  27. Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. 1977. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1–38. find
  28. Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazeer, and Yonghui Wu. 2016. Exploring the Limits of Language Modeling. arXiv:1602.02410. find
  29. Yoon Kim, Yacine Jernite, David Sontag, and Alexander M. Rush. 2016. Character-Aware Neural Language Models. In Proceedings of AAAI. find our card
  30. Yoon Kim, Alexander M. Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. 2019. Unsupervised Recurrent Neural Network Grammars. In Proceedings of NAACL. find
  31. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In Proceedings of ICLR. find
  32. Diederik P. Kingma, Tim Salimans, and Max Welling. 2016. Improving Variational Inference with Autoregressive Flow. arXiv:1606.04934. — [arXiv:1606.04934](https://arxiv.org/abs/1606.04934) find
  33. Bernard Merialdo. 1994. Tagging English Text with a Probabilistic Model. Computational Linguistics, 20(2):155–171. find our card
  34. Diederik P. Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes. In Proceedings of ICLR. find our card
  35. Hiroshi Noji, Yusuke Miyao, and Mark Johnson. 2016. Using Left-corner Parsing to Encode Universal Structural Constraints in Grammar Induction. In Proceedings of EMNLP. find
  36. Nikita Kitaev and Dan Klein. 2018. Constituency Parsing with a Self-Attentive Encoder. In Proceedings of ACL. find our card
  37. Ankur P. Parikh, Shay B. Cohen, and Eric P. Xing. 2014. Spectral Unsupervised Parsing with Additive Tree Metrics. In Proceedings of ACL. find
  38. Dan Klein and Christopher Manning. 2002. A Generative Constituent-Context Model for Improved Grammar Induction. In Proceedings of ACL. find our card
  39. Hao Peng, Ankur P. Parikh, Manaal Faruqui, Bhuwan Dhingra, and Dipanjan Das. 2019. Text Generation with Exemplar-based Adaptive Decoding. In Proceedings of NAACL. find
  40. Dan Klein and Christopher Manning. 2004. Corpus-based Induction of Syntactic Structure: Models of Dependency and Constituency. In Proceedings of ACL. find
  41. Dan Klein and Christopher D. Manning. 2003. Accurate Unlexicalized Parsing. In Proceedings of ACL. find our card
  42. Adhiguna Kuncoro, Chris Dyer, John Hale, Dani Yogatama, Stephen Clark, and Phil Blunsom. 2018. LSTMs Can Learn Syntax-Sensitive Dependencies Well, But Modeling Structure Makes Them Better. In Proceedings of ACL. find
  43. Kenichi Kurihara and Taisuke Sato. 2006. Variational Bayesian Grammar Induction for Natural Language. In Proceedings of International Colloquium on Grammatical Inference. find
  44. Karim Lari and Steve Young. 1990. The Estimation of Stochastic Context-Free Grammars Using the Inside-Outside Algorithm. Computer Speech and Language, 4:35–56. find
  45. Bowen Li, Lili Mou, and Frank Keller. 2019. An Imitation Learning Approach to Unsupervised Parsing. In Proceedings of ACL. find
  46. Percy Liang, Slav Petrov, Michael I. Jordan, and Dan Klein. 2007. The Infinite PCFG using Hierarchical Dirichlet Processes. In Proceedings of EMNLP. find
  47. Chu-Cheng Lin, Waleed Ammar, Chris Dyer, , and Lori Levin. 2015. Unsupervised POS Induction with Word Embeddings. In Proceedings of NAACL. find
  48. Yang Liu, Matt Gardner, and Mirella Lapata. 2018. Structured Alignment Networks for Matching Sentences. In Proceedings of EMNLP. find
  49. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19:313–330. find our card
  50. Rebecca Marvin and Tal Linzen. 2018. Targeted Syntactic Evaluation of Language Models. In Proceedings of EMNLP. find
  51. Fernando Pereira and Yves Schabes. 1992. Inside-Outside Reestimation from Partially Bracketed Corpora. In Proceedings of ACL. find our card
  52. Elis Ponvert, Jason Baldridge, and Katrin Erk. 2011. Simpled Unsupervised Grammar Induction from Raw Text with Cascaded Finite State Methods. In Proceedings of ACL. find
  53. Ofir Press and Lior Wolf. 2016. Using the Output Embedding to Improve Language Models. In Proceedings of EACL. find our card
  54. Roi Reichart and Ari Rappoport. 2010. Improved Fully Unsupervised Parsing with Zoomed Learning. In Proceedings of EMNLP. find
  55. Danilo J. Rezende and Shakir Mohamed. 2015. Variational Inference with Normalizing Flows. In Proceedings of ICML. find
  56. Danilo J. Rezende, Shakir Mohamed, and Daan Wierstra. 2014. Stochastic Backpropagation and Approximate Inference in Deep Generative Models. In Proceedings of ICML. find our card
  57. Herbert Robbins. 1951. Asymptotically Subminimax Solutions of Compound Statistical Decision Problems. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 131–149. Berkeley: University of California Press. find
  58. Herbert Robbins. 1956. An Empirical Bayes Approach to Statistics. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, pages 157–163. Berkeley: University of California Press. find
  59. Cı́cero Nogueira dos Santos and Bianca Zadrozny. 2014. Learning Character-level Representations for Part-of-Speech Tagging. In Proceedings of ICML. find
  60. Yoav Seginer. 2007. Fast Unsupervised Incremental Parsing. In Proceedings of ACL. find
  61. Yikang Shen, Zhouhan Lin, Chin-Wei Huang, and Aaron Courville. 2018. Neural Language Modeling by Jointly Learning Syntax and Lexicon. In Proceedings of ICLR. find
  62. Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. 2019. Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks. In Proceedings of ICLR. find
  63. Noah A. Smith and Jason Eisner. 2004. Annealing Techniques for Unsupervised Statistical Language Learning. In Proceedings of ACL. find
  64. Cun-Hui Zhang. 2003. Compound Decision Theory and Empirical Bayes Methods. The Annals of Statistics, 31:379–390. find
  65. Xiaodan Zhu, Parinaz Sobhani, and Hongyu Guo. 2015. Long Short-Term Memory Over Tree Structures. In Proceedings of ICML. find
  66. Benjamin Snyder, Tahira Naseem, and Regina Barzilay. 2009. Unsupervised Multilingual Grammar Induction. In Proceedings of ACL. find
  67. Valentin I. Spitkovsky, Hiyan Alshawi, and Daniel Jurafsky. 2012. Three Dependency-and-Boundary Models for Grammar Induction. In Proceedings of EMNLP-CoNLL. find
  68. Valentin I. Spitkovsky, Hiyan Alshawi, and Daniel Jurafsky. 2013. Breaking Out of Local Optima with Count Transforms and Model Recombination: A Study in Grammar Induction. In Proceedings of EMNLP. find
  69. Mitchell Stern, Jacob Andreas, and Dan Klein. 2017. A Minimal Span-Based Neural Constituency Parser. In Proceedings of ACL. find our card
  70. Karl Stratos. 2019. Mutual Information Maximization for Simple and Accurate Part-of-Speech Induction. In Proceedings of NAACL. find
  71. Kai Sheng Tai, Richard Socher, and Christopher D. Manning. 2015. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. In Proceedings of ACL. find
  72. Ke Tran, Yonatan Bisk, Ashish Vaswani, Daniel Marcu, and Kevin Knight. 2016. Unsupervised Neural Hidden Markov Models. In Proceedings of the Workshop on Structured Prediction for NLP. find
  73. Pengyu Wang and Phil Blunsom. 2013. Collapsed Variational Bayesian Inference for PCFGs. In Proceedings of CoNLL. find
  74. Wenhui Wang and Baobao Chang. 2016. Graph-based Dependency Parsing with Bidirectional LSTM. In Proceedings of ACL. find
  75. Ethan Wilcox, Peng Qian, Richard Futrell, Miguel Ballesteros, and Roger Levy. 2019. Structural Supervision Improves Learning of Non-Local Grammatical Dependencies. In Proceedings of NAACL. find
  76. Sam Wiseman, Stuart M. Shieber, and Alexander M. Rush. 2018. Learning Neural Templates for Text Generation. In Proceedings of EMNLP. find our card
  77. Ji Xu, Daniel Hsu, and Arian Maleki. 2018. Benefits of Over-Parameterization with EM. In Proceedings of NeurIPS. find
  78. Naiwen Xue, Fei Xia, Fu dong Chiou, and Marta Palmer. 2005. The Penn Chinese Treebank: Phrase Structure Annotation of a Large Corpus. Natural Language Engineering, 11:207–238. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kim-2019-compound-probabilistic-context-free-grammars/