[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/lingbulk-2013-honnibal-non-monotonic-arc-eager-transition/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [English](https://md.mova.elamur.ai/free/en/docs/papers/en/) / A Non-Monotonic Arc-Eager Transition System for Dependency Parsing

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

**Authors:** [Matthew Honnibal](https://md.mova.elamur.ai/free/en/docs/papers/authors/matthew-honnibal/), [Yoav Goldberg](https://md.mova.elamur.ai/free/en/docs/papers/authors/yoav-goldberg/), [Mark Johnson](https://md.mova.elamur.ai/free/en/docs/papers/authors/mark-johnson/) · **Year:** 2013 · **Venue:** Proceedings of the Seventeenth Conference on Computational Natural Language Learning **Link:** [aclanthology.org/W13-3518](https://aclanthology.org/W13-3518/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**22** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/lingbulk-2013-honnibal-non-monotonic-arc-eager-transition/) of the 140673 papers whose bibliographies we read[Proceedings of the Seventeenth Conference on Computational Natural Language Learning](https://aclanthology.org/volumes/W13-35/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/W13-3518/)
- [PDF](https://aclanthology.org/W13-3518.pdf)

**Authors (3)**

1. Matthew Honnibal
2. Yoav Goldberg
3. Mark Johnson

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## 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](https://md.mova.elamur.ai/free/en/docs/papers/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/}
}
```

- [← previous Towards Semi-Automated Annotation for Prepositional Phrase Attachment](https://md.mova.elamur.ai/free/en/docs/papers/lingbulk-2010-rosenthal-semi-automated-annotation-prepositional-phrase/)
- [next → Building a reference lexicon for countability in English](https://md.mova.elamur.ai/free/en/docs/papers/lingbulk-2014-kiss-building-reference-lexicon-countability-english/)
- [↑ back to English](https://md.mova.elamur.ai/free/en/docs/papers/en/)

## 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](https://scholar.google.com/scholar?q=Stephen+Abney+and+Mark+Johnson%2E+1991%2E+Memory+requirements+and+local+ambiguities+of+parsing+strategies%2E+Journal+of+Psycholinguistic+Research%2C+20%283%29%3A233%E2%80%93250%2E)
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](https://scholar.google.com/scholar?q=Giuseppe+Attardi+and+Massimiliano+Ciaramita%2E+2007%2E+Tree+revision+learning+for+dependency+parsing%2E+In+Human+Language+Technologies+2007%3A+The+Conference+of+the+North+American+Chapter+of+the+Association+f)
3. Miguel Ballesteros and Joakim Nivre. 2013. Going to the roots of dependency parsing. Computational Linguistics. 39:1. [find](https://scholar.google.com/scholar?q=Miguel+Ballesteros+and+Joakim+Nivre%2E+2013%2E+Going+to+the+roots+of+dependency+parsing%2E+Computational+Linguistics%2E+39%3A1%2E)
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](https://scholar.google.com/scholar?q=Marie%2DCatherine+de+Marneffe%2C+Bill+MacCartney%2C+and+Christopher+D%2E+Manning%2E+2006%2E+Generating+typed+dependency+parses+from+phrase+structure+parses%2E+In+Proceedings+of+the+5th+International+Conference+on+L) [our card](https://md.mova.elamur.ai/free/en/docs/papers/map-2006-marneffe-generating-typed-dependency-parses-phrase/)
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](https://scholar.google.com/scholar?q=Lyn+Frazier+and+Keith+Rayner%2E+1982%2E+Making+and+correcting+errors+during+sentence+comprehension%3A+Eye+movements+in+the+analysis+of+structurally+ambiguous+sentences%2E+Cognitive+Psychology%2C+14%282%29%3A178%E2%80%93210%2E)
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](https://scholar.google.com/scholar?q=Yoav+Goldberg+and+Michael+Elhadad%2E+2010%2E+An+efficient+algorithm+for+easy%2Dfirst+non%2Ddirectional+dependency+parsing%2E+In+Human+Language+Technologies%3A+The+2010+Annual+Conference+of+the+North+American+Chap)
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](https://scholar.google.com/scholar?q=Yoav+Goldberg+and+Joakim+Nivre%2E+2012%2E+A+dynamic+oracle+for+arc%2Deager+dependency+parsing%2E+In+Proceedings+of+the+24th+International+Conference+on+Computational+Linguistics+%28Coling+2012%29%2E+Association+for)
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](https://scholar.google.com/scholar?q=Keith+Hall+and+Vaclav+Nova%CC%81k%2E+2005%2E+Corrective+modeling+for+non%2Dprojective+dependency+parsing%2E+In+Proceedings+of+the+9th+International+Workshop+on+Parsing+Technologies+%28IWPT%29%2C+pages+42%E2%80%9352%2E)
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](https://scholar.google.com/scholar?q=Liang+Huang+and+Kenji+Sagae%2E+2010%2E+Dynamic+programming+for+linear%2Dtime+incremental+parsing%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%29%2C+pages+1077)
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](https://scholar.google.com/scholar?q=Akihiro+Inokuchi+and+Ayumu+Yamaoka%2E+2012%2E+Mining+rules+for+rewriting+states+in+a+transition%2Dbased+dependency+parser+for+English%2E+In+Proceedings+of+COLING+2012%2C+pages+1275%E2%80%931290%2E)
11. The COLING 2012 Organizing Committee, Mumbai, India. [find](https://scholar.google.com/scholar?q=The+COLING+2012+Organizing+Committee%2C+Mumbai%2C+India%2E)
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](https://scholar.google.com/scholar?q=Terry+Koo+and+Michael+Collins%2E+2010%2E+Efficient+third%2Dorder+dependency+parsers%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%29%2C+pages+1%E2%80%93+11%2E)
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](https://scholar.google.com/scholar?q=Marco+Kuhlmann%2C+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2C+and+Giorgio+Satta%2E+2011%2E+Dynamic+programming+algorithms+for+transition%2Dbased+dependency+parsers%2E+In+Proceedings+of+the+49th+Annual+Meeting+of+the+Association+)
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](https://scholar.google.com/scholar?q=Mitchell+P%2E+Marcus%2C+Beatrice+Santorini%2C+and+Mary+Ann+Marcinkiewicz%2E+1993%2E+Building+a+large+annotated+corpus+of+English%3A+The+Penn+Treebank%2E+Computational+Linguistics%2C+19%3A313%E2%80%93+330%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/bank-1993-marcus-building-large-annotated-corpus-english/)
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](https://scholar.google.com/scholar?q=Andre%CC%81+Filipe+Martins%2C+Dipanjan+Das%2C+Noah+A%2E+Smith%2C+and+Eric+P%2E+Xing%2E+2008%2E+Stacking+dependency+parsers%2E+In+Proceedings+of+the+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2C+p)
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](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2003%2E+An+efficient+algorithm+for+projective+dependency+parsing%2E+In+Proceedings+of+the+8th+International+Workshop+on+Parsing+Technologies+%28IWPT%29%2C+pages+149%E2%80%93160%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/)
17. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2008%2E+Algorithms+for+deterministic+incremental+dependency+parsing%2E+Computational+Linguistics%2C+34%3A513%E2%80%93553%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2008-nivre-algorithms-deterministic-incremental-dependency-parsing/)
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](https://scholar.google.com/scholar?q=Joakim+Nivre%2C+Johan+Hall%2C+and+Jens+Nilsson%2E+2004%2E+Memory%2Dbased+dependency+parsing%2E+In+Hwee+Tou+Ng+and+Ellen+Riloff%2C+editors%2C+HLT%2DNAACL+2004+Workshop%3A+Eighth+Conference+on+Computational+Natural+Languag)
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](https://scholar.google.com/scholar?q=Joakim+Nivre+and+Ryan+McDonald%2E+2008%2E+Integrating+graph%2Dbased+and+transition%2Dbased+dependency+parsers%2E+In+Proceedings+of+the+46th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%29%2C)
20. Mark Steedman. 2000. The Syntactic Process. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Mark+Steedman%2E+2000%2E+The+Syntactic+Process%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
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](https://scholar.google.com/scholar?q=Yue+Zhang+and+Stephen+Clark%2E+2008%2E+A+tale+of+two+parsers%3A+Investigating+and+combining+graph%2Dbased+and+transition%2Dbased+dependency+parsing%2E+In+Proceedings+of+the+2008+Conference+on+Empirical+Methods+in) [our card](https://md.mova.elamur.ai/free/en/docs/papers/zhang-2008-tale-two-parsers-investigating-combining/)
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](https://scholar.google.com/scholar?q=Yue+Zhang+and+Joakim+Nivre%2E+2011%2E+Transition%2Dbased+dependency+parsing+with+rich+non%2Dlocal+features%2E+In+Proceedings+of+the+49th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%3A+Human+La)