A Non-Monotonic Arc-Eager Transition System for Dependency Parsing

What it is about

The paper relaxes the two deterministic constraints of the arc-eager transition system, which keep each step consistent with earlier head decisions. Left-Arc may delete an existing arc and Reduce may insert a missing one, labelled from the best Right-Arc label, so that a wrong Shift or Right-Arc decision can be repaired later. Training uses a dynamic oracle, so the averaged perceptron sees configurations that follow its own mistakes; the authors show that repair is not learned without such examples. The parser is greedy and runs over 500 sentences per second. On the English WSJ test it reaches 91.1% UAS, 0.2 points above the 90.9% baseline, and it also improves Chinese, Czech, English, Greek and Italian at p < 0.001 on the multilingual evaluation.

Ideas

• I1. en/src/parse.rs: move the arc-standard perceptron from the static oracle to a dynamic oracle, keeping the feature set fixed, and measure LAS on EWT dev through en parse-eval, twice.
• I2. en/src/parse.rs: count how many gold arcs the current parser loses in a state where a later word would have fixed the decision (use en explain on EWT dev), to size the room a repair step has before any code is written.
• I3. Measure the effect of any repair step on ESLSpok dev and on the English test data (test only for NC sets) separately, because the gain reported here is small and only significant on some languages.

For Mova

The ideas touch the oracle in en/src/parse.rs and the explanations of en explain. The chapters are languages/en/21-clause-structure and languages/en/29-ellipsis-word-order-information-structure, where attachment is decided late. The paper's gain is 0.2 points, so measure first I2 and see whether the room exists before building anything.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{honnibal2013non,
  title = {{A Non-Monotonic Arc-Eager Transition System for Dependency Parsing}},
  author = {Honnibal, Matthew and Goldberg, Yoav and Johnson, Mark},
  booktitle = {Proceedings of the Seventeenth Conference on Computational Natural Language Learning},
  year = {2013},
  url = {https://aclanthology.org/W13-3518/}
}

References

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

1. Stephen Abney and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20(3):233–250. find
2. Giuseppe Attardi and Massimiliano Ciaramita. 2007. Tree revision learning for dependency parsing. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 388–395. Association for Com… find
3. Miguel Ballesteros and Joakim Nivre. 2013. Going to the roots of dependency parsing. Computational Linguistics. 39:1. find
4. Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC). find our card
5. Lyn Frazier and Keith Rayner. 1982. Making and correcting errors during sentence comprehension: Eye movements in the analysis of structurally ambiguous sentences. Cognitive Psychology, 14(2):178–210. find
6. Yoav Goldberg and Michael Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT), pages 742–750. find
7. Yoav Goldberg and Joakim Nivre. 2012. A dynamic oracle for arc-eager dependency parsing. In Proceedings of the 24th International Conference on Computational Linguistics (Coling 2012). Association for Computational Linguistics, Mumbai, India. find
8. Keith Hall and Vaclav Novák. 2005. Corrective modeling for non-projective dependency parsing. In Proceedings of the 9th International Workshop on Parsing Technologies (IWPT), pages 42–52. find
9. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1077–1086. find
10. Akihiro Inokuchi and Ayumu Yamaoka. 2012. Mining rules for rewriting states in a transition-based dependency parser for English. In Proceedings of COLING 2012, pages 1275–1290. find
11. The COLING 2012 Organizing Committee, Mumbai, India. find
12. Terry Koo and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1– 11. find
13. 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 - Volume 1, HLT ’11, pages 673–682. Assoc… find
14. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19:313– 330. find our card
15. André Filipe Martins, Dipanjan Das, Noah A. Smith, and Eric P. Xing. 2008. Stacking dependency parsers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 157–166. find
16. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 149–160. find our card
17. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553. find our card
18. Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Hwee Tou Ng and Ellen Riloff, editors, HLT-NAACL 2004 Workshop: Eighth Conference on Computational Natural Language Learning (CoNLL-2004), pages 49–56. Association for Computational Linguistics, Boston, Massachuset… find
19. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL), pages 950–958. find
20. Mark Steedman. 2000. The Syntactic Process. MIT Press, Cambridge, MA. find
21. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 562–571. Association for Computational Linguistics, Honolulu, Ha… find our card
22. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 188–193. Association for Computational Linguistics, Portland, Oregon, USA… find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/lingbulk-2013-honnibal-non-monotonic-arc-eager-transition/