Proceedings

Fast and Accurate Neural CRF Constituency Parsing

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 4046-4053.

https://doi.org/10.24963/ijcai.2020/560

Abstract

Estimating probability distribution is one of the core issues in the NLP field.

However, in both deep learning (DL) and pre-DL eras, unlike the vast applications of linear-chain CRF in sequence labeling tasks, very few works have applied tree-structure CRF to constituency parsing, mainly due to the complexity and inefficiency of the inside-outside algorithm.

This work presents a fast and accurate neural CRF constituency parser.

The key idea is to batchify the inside algorithm for loss computation by direct large tensor operations on GPU, and meanwhile avoid the outside algorithm for gradient computation via efficient back-propagation.

We also propose a simple two-stage bracketing-then-labeling parsing approach to improve efficiency further.

To improve the parsing performance, inspired by recent progress in dependency parsing, we introduce a new scoring architecture based on boundary representation and biaffine attention, and a beneficial dropout strategy.

Experiments on PTB, CTB5.1, and CTB7 show that our two-stage CRF parser achieves new state-of-the-art performance on both settings of w/o and w/ BERT, and can parse over 1,000 sentences per second.

We release our code at https://github.com/yzhangcs/crfpar.

  1. [Akoury et al., 2019] Nader Akoury, Kalpesh Krishna, and Mohit Iyyer. Syntactically supervised transformers for faster neural machine translation. In Proceedings of ACL, pages 1269-1281, 2019.
  2. [Collins, 1997] Michael Collins. Three generative, lexi- calised models for statistical parsing. In Proceedings of ACL, pages 16-23, 1997.
  3. [Cross and Huang, 2016] James Cross and Liang Huang. Span-based constituency parsing with a structure-label system and provably optimal dynamic oracles. In Proceed- ings of EMNLP, pages 1-11, 2016.
  4. [Devlin et al., 2019] Jacob Devlin, Ming-Wei Chang, Ken- ton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understand- ing. In Proceedings of NAACL, pages 4171-4186, 2019.
  5. [Dozat and Manning, 2017] Timothy Dozat and Christo- pher D. Manning. Deep biaffine attention for neural de- pendency parsing. In Proceedings of ICLR, 2017.
  6. [Durrett and Klein, 2015] Greg Durrett and Dan Klein. Neu- ral CRF parsing. In Proceedings of ACL-IJCNLP, pages 302-312, 2015.
  7. [Eisner, 2016] Jason Eisner. Inside-outside and forward- backward algorithms are just backprop (tutorial paper). In Proceedings of WS, pages 1-17, 2016.
  8. [Finkel et al., 2008] Jenny Rose Finkel, Alex Kleeman, and Christopher D. Manning. Efficient, feature-based, condi- tional random field parsing. In Proceedings of ACL, pages 959-967, 2008.
  9. [Gaddy et al., 2018] David Gaddy, Mitchell Stern, and Dan Klein. What's going on in neural constituency parsers? an analysis. In Proceedings of NAACL, pages 999-1010, 2018.
  10. [Gómez-Rodríguez and Vilares, 2018] Carlos Gómez- Rodríguez and David Vilares. Constituent parsing as sequence labeling. In Proceedings of EMNLP, pages 1314-1324, 2018.
  11. [Jin et al., 2020] Lifeng Jin, Linfeng Song, Yue Zhang, Kun Xu, Wei yun Ma, and Dong Yu. Relation extraction ex- ploiting full dependency forests. In Proceedings of AAAI, 2020.
  12. [Kaplan et al., 2004] Ron Kaplan, Stefan Riezler, Tracy H. King, John T. Maxwell III, Alex Vasserman, and Richard Crouch. Speed and accuracy in shallow and deep stochas- tic parsing. In Proceedings of HLT-NAACL, pages 97-104, 2004.
  13. [Kitaev and Klein, 2018] Nikita Kitaev and Dan Klein. Con- stituency parsing with a self-attentive encoder. In Proceed- ings of ACL, pages 2676-2686, 2018.
  14. [Kitaev et al., 2019] Nikita Kitaev, Steven Cao, and Dan Klein. Multilingual constituency parsing with self- attention and pre-training. In Proceedings of ACL, pages 3499-3505, 2019.
  15. [Lample et al., 2016] Guillaume Lample, Miguel Balles- teros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. Neural architectures for named entity recogni- tion. In Proceedings of NAACL, pages 2475-2485, 2016.
  16. [Le and Zuidema, 2014] Phong Le and Willem Zuidema. The inside-outside recursive neural network model for de- pendency parsing. In Proceedings of EMNLP, pages 729- 739, 2014.
  17. [Li et al., 2019] Ying Li, Zhenghua Li, Min Zhang, Rui Wang, Sheng Li, and Luo Si. Self-attentive biaffine depen- dency parsing. In Proceedings of IJCAI, pages 5067-5073, 2019. IJCAI
  18. [Matsuzaki et al., 2005] Takuya Matsuzaki, Yusuke Miyao, and Jun'ichi Tsujii. Probabilistic CFG with latent annota- tions. In Proceedings of ACL, pages 75-82, 2005.
  19. [Peters et al., 2018] Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representa- tions. In Proceedings of NAACL, pages 2227-2237, 2018.
  20. [Petrov and Klein, 2007] Slav Petrov and Dan Klein. Im- proved inference for unlexicalized parsing. In Proceedings of NAACL, pages 404-411, 2007.
  21. [Rush, 2020] Alexander M. Rush. Torch-struct: Deep struc- tured prediction library. arXiv:2002.00876, 2020.
  22. [Sagae and Lavie, 2005] Kenji Sagae and Alon Lavie. A classifier-based parser with linear run-time complexity. In Proceedings of IWPT, pages 125-132, 2005.
  23. [Shen et al., 2018] Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. Straight to the tree: Constituency parsing with neural syntactic distance. In Proceedings of ACL, pages 1171-1180, 2018.
  24. [Smith and Smith, 2007] David A. Smith and Noah A. Smith. Probabilistic models of nonprojective dependency trees. In Proceedings of EMNLP, pages 132-140, 2007.
  25. [Stern et al., 2017] Mitchell Stern, Jacob Andreas, and Dan Klein. A minimal span-based neural constituency parser. In Proceedings of ACL, pages 818-827, 2017.
  26. [Taskar et al., 2004] Ben Taskar, Dan Klein, Mike Collins, Daphne Koller, and Christopher Manning. Max-margin parsing. In Proceedings of EMNLP, pages 1-8, 2004.
  27. [Teng and Zhang, 2018] Zhiyang Teng and Yue Zhang. Two local models for neural constituent parsing. In Proceed- ings of COLING, pages 119-132, 2018.
  28. [Vilares et al., 2019] David Vilares, Mostafa Abdou, and Anders Søgaard. Better, faster, stronger sequence tag- ging constituent parsers. In Proceedings of NAACL, pages 3372-3383, 2019.
  29. [Wang and Chang, 2016] Wenhui Wang and Baobao Chang. Graph-based dependency parsing with bidirectional LSTM. In Proceedings of ACL, pages 2475-2485, 2016.
  30. [Wang et al., 2018] Xinyi Wang, Hieu Pham, Pengcheng Yin, and Graham Neubig. A tree-based decoder for neu- ral machine translation. In Proceedings of EMNLP, pages 4772-4777, 2018.
  31. [Zhang et al., 2020] Yu Zhang, Zhenghua Li, and Zhang Min. Efficient second-order TreeCRF for neural depen- dency parsing. In Proceedings of ACL, 2020.
  32. [Zhou and Zhao, 2019] Junru Zhou and Hai Zhao. Head- driven phrase structure grammar parsing on Penn treebank. In Proceedings of the ACL, pages 2396-2408, 2019.
  33. [Zhu et al., 2013] Muhua Zhu, Yue Zhang, Wenliang Chen, Min Zhang, and Jingbo Zhu. Fast and accurate shift-reduce constituent parsing. In Proceedings of ACL, pages 434- 443, 2013.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards