Elamur Research
☰
home / papers / 2015 / An Improved Non-monotonic Transition System for Dependency Parsing

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

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.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/D15-1162.pdf

Summary

Greedy transition-based dependency parsers make each decision once and never revisit it. An early wrong attachment can therefore trap them in a garden path. Honnibal and Johnson propose a richer non-monotonic variant of the arc-eager system that lets the parser revise earlier choices. It combines two prior ideas: the non-monotonic Left-Arc/Reduce actions introduced by Honnibal et al. (2013) and the Unshift operation proposed by Nivre and Fernandez-Gonzalez (2014). In the new system, Unshift is allowed whenever the stack-top word has no head, not only after the buffer runs out. A bit-vector blocks Shift/Unshift loops, so parsing stays linear-time. Repairs only make sense after mistakes, so training uses a dynamic oracle on configurations reached by following the model's own predictions. The parser is a greedy perceptron with Zhang and Nivre (2011) features plus Brown clusters. On OntoNotes it reaches 91.85 UAS and 89.91 LAS, about 0.6 UAS above an otherwise identical arc-eager baseline. Each earlier modification alone gained only about 0.1–0.15. Because the change concerns the transition system rather than the classifier, the authors expect it to complement neural transition scorers.

Key points

  • Data: OntoNotes converted to dependencies with ClearNLP 3.1, using the CoNLL 2012 train/dev/test split (the setup of Tetreault et al., 2015). POS tags come from a greedy averaged perceptron with 97.2% accuracy, trained jointly with the parser.
  • Results (UAS/LAS):
    • Orig. Arc Eager: 91.25/89.40
    • Tree Constrained: 91.40/89.50
    • Prev. Non-Monotonic: 91.36/89.52
    • This work: 91.85/89.91
  • All four compared systems share features and dynamic-oracle training and differ only in their transitions. The new system beats the greedy parsers of Chen and Manning (2014) (89.59 UAS) and Goldberg and Nivre (2012) (90.54 UAS). It remains below beam, branch and graph-based parsers (up to 92.50 UAS for Bohnet, 2010), which are much slower.
  • Each word can be pushed and popped at most twice, so parsing ends within 4n transitions. No dummy root token is needed.
  • Unshift and Reduce apply to disjoint configurations and are modelled as one shared class. In preliminary tests, a separate Unshift class did not work well.

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