Arc-swift: A Novel Transition System for Dependency Parsing

What it is about

Transition-based parsers reach a distant attachment only through a sequence of local shifts and reduces, and every step is a place to make an error. Arc-swift adds transitions that attach a token on the stack to the buffer front, or the reverse, at any distance, in one step. With the same implementation and greedy search, arc-swift reaches LAS 92.2 on Penn Treebank Stanford dependencies, against 91.7–91.8 for arc-standard, arc-eager and arc-hybrid, and 82.2 on English UD v1.3, against 81.2–81.5. Its transition sequences are 77.5% of the length of arc-eager's, and its gain comes from prepositional-phrase and conjunction attachments: 545 PP attachment errors against 569 for arc-eager and 571 for arc-standard.

Ideas

• I1. en/src/parse.rs: add long-distance attachment transitions to the arc-standard system with the same features; measure cv LAS on the train folds and EWT test once per release, with the transitions per sentence reported.
• I2. en/src/explain.rs and en parse-eval: count the PP-attachment and conjunction-attachment errors on EWT test before and after any transition change, since these two classes carry the paper's gain.
• I3. en parse-eval: report LAS by dependency length bucket on EWT test; the paper shows the gain is in the long arcs, so the bucketed table says whether a change helps where the paper says it should.

For Mova

The chapters are 22-phrases (PP attachment), 24-coordination-subordination (conjunction attachment) and 21-clause-structure. The code is en/src/parse.rs, with en/src/explain.rs for the error classes. Measure first: the PP and conjunction error counts of idea I2 on EWT test, because they are where the paper's gain lies and they are cheap to count.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/p17-2018 · arXiv 1705.04434

@inproceedings{qi2017arc,
  title = {{Arc-swift: A Novel Transition System for Dependency Parsing}},
  author = {Qi, Peng and Manning, Christopher D.},
  booktitle = {Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2017},
  doi = {10.18653/v1/p17-2018},
  eprint = {1705.04434},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p17-2018}
}

References

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

1. Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. https://www.aclweb.… ↗
2. Gabor Angeli, Melvin Johnson Premkumar, and Christopher D Manning. 2015. Leveraging linguistic structure for open domain information extraction. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics (ACL 2015). http://www.aclweb.org/anthology/P15-1034. ↗
3. Giuseppe Attardi. 2006. Experiments with a mul-tilanguage non-projective dependency parser. In Proceedings of the Tenth Conference on Computational Natural Language Learning. Association for Computational Linguistics, pages 166–170. http://www.aclweb.org/anthology/W06-2922. ↗
4. Bernd Bohnet, Ryan McDonald, Emily Pitler, and Ji Ma. 2016. Generalized transition-based dependency parsing via control parameters. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. volume 1, pages 150–160. https://www.aclweb.org/anthology/P16-1015. ↗
5. Marco Kuhlmann, Carlos Gómez-Rodrı́guez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. pages 673–682. http://www.aclweb.org/ant… ↗
6. Samuel R Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D Manning, and Christopher Potts. 2016. A fast unified model for parsing and sentence understanding. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL 2016). http://www.aclweb.org/… ↗
7. Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014. The Stanford CoreNLP natural language processing toolkit. In Association for Computational Linguistics (ACL) System Demonstrations. pages 55–60. http://www.aclweb.org/anthology/P/P14/P14-50… ↗
8. Danqi Chen and Christopher D Manning. 2014. A fast and accurate dependency parser using neural networks. In EMNLP. pages 740–750. http://www.aclweb.org/anthology/D14-1082. ↗ our card
9. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing. pages 523–530. http://www.aclweb.org/anthology/H… ↗ our card
10. Marie-Catherine De Marneffe and Christopher D Manning. 2008. The Stanford typed dependencies representation. In COLING 2008: Proceedings of the Workshop on Cross-framework and Cross-domain Parser Evaluation. pages 1–8. http://www.aclweb.org/anthology/W08-1301. ↗ our card
11. Ryan T McDonald and Joakim Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In EMNLP-CoNLL. pages 122–131. http://www.aclweb.org/anthology/D07-1013. ↗ our card
12. Daniel Fernández-González and Carlos Gómez-Rodrı́guez. 2012. Improving transition-based dependency parsing with buffer transitions. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. pages 308–319. http://ww… find
13. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies. pages 149–160. http://stp.lingfil.uu.se/ nivre/docs/iwpt03.pdf. ↗ our card
14. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together. pages 50–57. https://www.aclweb.org/anthology/W04-0308. ↗ our card
15. Yoav Goldberg and Joakim Nivre. 2012. A dynamic oracle for arc-eager dependency parsing. In COLING. pages 959–976. http://www.aclweb.org/anthology/C12-1059. ↗
16. Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, et al. 2016. Universal dependencies v1: A multilingual treebank collection. In Proceedings of the 10th International Conference on La… find our card
17. Carlos Gómez-Rodrı́guez and Joakim Nivre. 2013. Divisible transition systems and multiplanar dependency parsing. Computational Linguistics 39(4):799–845. find
18. Joseph Gubbins and Andreas Vlachos. 2013. Dependency language models for sentence completion. In EMNLP. volume 13, pages 1405–1410. http://www.aclweb.org/anthology/D13-1143. ↗
19. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP). pages 1532– 1543. http://www.aclweb.org/anthology/D14-1162. ↗
20. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation 9(8):1735–1780. find
21. Diederik Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 . find
22. Francesco Sartorio, Giorgio Satta, and Joakim Nivre. 2013. A transition-based dependency parser using a dynamic parsing strategy. In Association for Computational Linguistics. pages 135–144. http://www.aclweb.org/anthology/P13-1014. ↗
23. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional lstm feature representations. Transactions of the Association for Computational Linguistics (TACL) https://aclweb.org/anthology/Q16-1023. ↗ our card
24. Michael Schmitz, Robert Bart, Stephen Soderland, Oren Etzioni, et al. 2012. Open language learning for information extraction. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. pages 523–534. https://www.aclwe… ↗
25. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics (ACL 2015). http://www.aclweb.org/anthology/P15-1032. ↗

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2017-qi-arc-swift-novel-transition-system/