Efficient Second-Order TreeCRF for Neural Dependency Parsing

What it is about

The paper adds two things to the biaffine graph parser: a probabilistic TreeCRF loss, which trains over whole trees rather than single arcs, and second-order scores for adjacent sibling arcs, computed by a triaffine term. The inside and Viterbi algorithms are batched so they run as large matrix operations on a GPU, and the outside pass is replaced by back-propagation. Experiments on 27 datasets from 13 languages show that the gains are uneven: on PTB the CRF variants do not beat the local biaffine baseline, while on CoNLL09 and other sets they do, and the CRF helps most when the training trees are only partly annotated. The authors also report that greedy head choice already gives a legal projective tree for more than 99% of the sentences they tested, so the slower Eisner decoding can be skipped for most input.

Ideas

• I1. Greedy fast path in gparse/src/eisner.rs: take the best head for each word, check for one root, no cycles and projectivity, and run Eisner only when the check fails; the gate is identical trees on EWT dev, then decoding time.
• I2. Partial-tree training on silver: keep only the silver arcs that pass treeagree gates and train gparse with a loss over the trees that are compatible with the kept arcs; compare EWT test LAS with the full-silver run, since the paper finds partial losses useful.
• I3. Adjacent-sibling feature: add a cheap sibling feature (a head's other dependents) to the gparse biaffine scorer and measure EWT test LAS; the paper's PTB result shows that a gain on one bank may not carry over, so test on EWT and GUM (test only).

For Mova

The code is gparse/src/eisner.rs and the biaffine scorer, plus the silver filters in tools/treeagree and annot. The chapter is 24. Coordination and subordination (for the sibling and coordination cases). Measure first: the fast-path agreement and time on EWT dev, because it is a pure speed change and must give byte-identical output.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.acl-main.302

@inproceedings{zhang2020efficient,
  title = {{Efficient Second-Order TreeCRF for Neural Dependency Parsing}},
  author = {Zhang, Yu and Li, Zhenghua and Zhang, Min},
  booktitle = {Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.302},
  url = {https://doi.org/10.18653/v1/2020.acl-main.302}
}

References

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

1. Jiong Cai, Yong Jiang, and Kewei Tu. 2017. CRF autoencoder for unsupervised dependency parsing. In Proceedings of EMNLP, pages 1638–1643. find
2. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of EMNLP, pages 957–961. find
3. Danqi Chen and Christopher Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of EMNLP, pages 740–750. find our card
4. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL, pages 4171– 4186. find
5. Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency parsing. In Proceedings of ICLR. find our card
6. Timothy Dozat, Peng Qi, and Christopher D. Manning. 2017. Stanford’s graph-based neural dependency parser at the CoNLL 2017 shared task. In Proceedings of CoNLL, pages 20–30. find our card
7. Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit Iyyer, and Andrew McCallum. 2019. Unsupervised latent tree induction with deep inside-outside recursive auto-encoders. In Proceedings of NAACL, pages 1129–1141. find
8. Jason Eisner. 2000. Bilexical grammars and their cubic-time parsing algorithms. In Advances in Probabilistic and Other Parsing Technologies. find
9. Jason Eisner. 2016. Inside-outside and forward-backward algorithms are just backprop (tutorial paper). In Proceedings of WS, pages 1–17. find
10. Agnieszka Falenska and Jonas Kuhn. 2019. The (non-)utility of structural features in BiLSTM-based dependency parsers. In Proceedings of ACL, pages 117–128. find
11. Jenny Rose Finkel, Alex Kleeman, and Christopher D. Manning. 2008. Efficient, feature-based, conditional random field parsing. In Proceedings of ACL, pages 959–967. find
12. David Gaddy, Mitchell Stern, and Dan Klein. 2018. What’s going on in neural constituency parsers? an analysis. In Proceedings of NAACL, pages 999– 1010. find
13. Jan Hajič, Massimiliano Ciaramita, Richard Johansson, Daisuke Kawahara, Maria Antònia Martı́, Lluı́s Màrquez, Adam Meyers, Joakim Nivre, Sebastian Padó, Jan Štěpánek, Pavel Straňák, Mihai Surdeanu, Nianwen Xue, and Yi Zhang. 2009. The CoNLL-2009 shared task: Syntactic and semantic dependenc… find our card
14. Rebecca Hwa. 1999. Supervised grammar induction using training data with limited constituent information. In Proceedings of ACL, pages 73–79. find
15. Tao Ji, Yuanbin Wu, and Man Lan. 2019. Graph-based dependency parsing with graph neural networks. In Proceedings of ACL, pages 2475–2485. find
16. Xinzhou Jiang, Zhenghua Li, Bo Zhang, Min Zhang, Sheng Li, and Luo Si. 2018. Supervised treebank conversion: Data and approaches. In Proceedings of ACL, pages 2706–2716. find
17. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of ACL, pages 313–327. find our card
18. Terry Koo and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of ACL, pages 1–11. find
19. Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016. Neural architectures for named entity recognition. In Proceedings of NAACL, pages 2475–2485. find
20. Phong Le and Willem Zuidema. 2014. The inside-outside recursive neural network model for dependency parsing. In Proceedings of EMNLP, pages 729–739. find
21. Ying Li, Zhenghua Li, Min Zhang, Rui Wang, Sheng Li, and Luo Si. 2019. Self-attentive biaffine dependency parsing. In Proceedings of IJCAI, pages 5067–5073. find
22. Zhenghua Li, Min Zhang, Yue Zhang, Zhanyi Liu, Wenliang Chen, Hua Wu, and Haifeng Wang. 2016. Active learning for dependency parsing with partial annotation. In Proceedings of ACL, pages 344–354. find
23. Xuezhe Ma and Hai Zhao. 2012. Fourth-order dependency parsing. In Proceedings of COLING, pages 785–796. find
24. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91– 98. find our card
25. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL, pages 81–88. find our card
26. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of EMNLP, pages 523–530. find our card
27. Joakim Nivre, Yoav Goldberg, and Ryan McDonald. 2014. Squibs: Constrained arc-eager dependency parsing. CL, pages 249–257. find
28. Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016. Universal dependencies v1: A multilingual treebank collection. In Proceedings of LREC, pages… find our card
29. Joakim Nivre and Jens Nilsson. 2005. Pseudo-projective dependency parsing. In Proceedings of ACL, pages 99–106. find
30. Wenzhe Pei, Tao Ge, and Baobao Chang. 2015. An effective neural network model for graph-based dependency parsing. In Proceedings of ACL-IJCNLP, pages 313–322. find
31. Xue Peng, Zhenghua Li, Min Zhang, Rui Wang, Yue Zhang, and Luo Si. 2019. Overview of the nlpcc 2019 shared task: cross-domain dependency parsing. In Proceedings of NLPCC, pages 760–771. find
32. Fernando Pereira and Yves Schabes. 1992. Inside-outside reestimation from partially bracketed corpora. In Proceedings of ACL, pages 128–135. find
33. Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. In Proceedings of NAACL, pages 2227– 2237. find
34. David A. Smith and Noah A. Smith. 2007. Probabilistic models of nonprojective dependency trees. In Proceedings of EMNLP, pages 132–140. find
35. Robert Endre Tarjan. 1977. Finding optimum branchings. Networks, pages 25–35. find
36. Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph attention networks. In Proceedings of ICLR. find
37. Wenhui Wang and Baobao Chang. 2016. Graph-based dependency parsing with bidirectional LSTM. In Proceedings of ACL, pages 2475–2485. find
38. Xinyu Wang, Jingxian Huang, and Kewei Tu. 2019. Second-order semantic dependency parsing with end-to-end neural networks. In Proceedings of ACL, pages 4609–4618. find
39. Daniel Zeman, Jan Hajič, Martin Popel, Martin Potthast, Milan Straka, Filip Ginter, Joakim Nivre, and Slav Petrov. 2018. find
40. CoNLL 2018 shared task: Multilingual parsing from raw text to universal dependencies. In Proceedings of CoNLL, pages 1–21. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/acl-2020-zhang-efficient-second-order-treecrf-neural/