An Improved Non-monotonic Transition System for Dependency Parsing

What it is about

Greedy transition parsers usually commit to every attachment as soon as it is made, which traps them in garden paths. The paper allows repair by adding an Unshift action from the work of Nivre and Fernández-González to the non-monotonic arc-eager system of Honnibal et al. (2013). Left-Arc and Reduce no longer forbid what earlier steps decided: they remove or insert an arc, so the parser can revisit an attachment once later words make it clear. Training uses a dynamic oracle, so that the parser sees configurations reached through its own mistakes, which the authors call critical for learning repair. The parser stays linear in time. On the English OntoNotes corpus it reaches 91.85% UAS, 0.6 points above a comparable arc-eager parser, which is a 6.25% error reduction against the baseline.

Ideas

• I1. en/src/parse.rs: count the configurations where the stack top has no head when the buffer runs out, under en explain on EWT dev; if they are frequent, a repair action is worth adding.
• I2. en/src/parse.rs: switch the perceptron from the static oracle to a dynamic oracle (the gold-consistent move from any reached state), keeping the rest fixed, and measure LAS on EWT dev, twice, since the paper says repair cannot be learned without it.
• I3. Test the repair action on ESLSpok and CHILDES dev (speech-like, disfluent text) against EWT dev, because repair should help more where the first attachment is most often wrong.

For Mova

The ideas touch the transition system and the oracle in en/src/parse.rs, and they use en explain to find the failure cases. The chapter that matters is languages/en/23-complementation, where attachment of a coordinated noun phrase is decided early (the paper's own example, "saw Jack and Jill" against "saw Jack and Jill fall"), and languages/en/24-coordination-subordination. Measure first I1, a count on existing traces that costs nothing, and I2 only if I1 shows a real share of such errors.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/d15-1162

@inproceedings{honnibal2015improved,
  title = {{An Improved Non-monotonic Transition System for Dependency Parsing}},
  author = {Honnibal, Matthew and Johnson, Mark},
  booktitle = {Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  doi = {10.18653/v1/d15-1162},
  url = {https://doi.org/10.18653/v1/d15-1162}
}

References

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

1. Miguel Ballesteros and Joakim Nivre. 2013. Going to the roots of dependency parsing. Computational Linguistics. 39:1. find
2. Danqi Chen and Christopher Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 740– 750. Association for Computational Linguistics, Doha, Qatar. find our card
3. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015. Transition-based dependency parsing with stack long short-term memory. In Proceedings of the 53nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13–24. Association for… find our card
4. 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
5. 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
6. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. TACL, 1:403–414. find
7. Matthew Honnibal, Yoav Goldberg, and Mark Johnson. 2013. A non-monotonic arc-eager transition system for dependency parsing. In Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 163–172. Association for Computational Linguistics, Sofia, Bulgaria. find our card
8. 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
9. 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
10. Joakim Nivre and Daniel Fernandez-Gonzalez. 2014. Arc-eager parsing with the tree constraint. Computational Linguistics, 40(2):259– 267. find
11. Joel Tetreault, Jin ho Choi, and Amanda Stent. 2015. It depends: Dependency parser comparison using a web-based evaluation tool. In Proceedings of the 53nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13–24. Association for Computational Linguistics,… find our card
12. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of the 53nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13–24. Association for Computational Linguist… find
13. 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/missing-2015-honnibal-improved-non-monotonic-transition-system/