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

Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 163–172, Sofia, Bulgaria, August 8-9 2013. c⃝2013 Association for Computational Linguistics A Non-Monotonic Arc-Eager Transition System for Dependency Parsing Matthew Honnibal Department of Computing Macquarie University Sydney, Australia matthew.honnibal@mq.edu.edu.au Yoav Goldberg Department of Computer Science Bar Ilan University Ramat Gan, Israel yoav.goldberg@gmail.com Mark Johnson Department of Computing Macquarie University Sydney, Australia mark.johnson@mq.edu.edu.au Abstract Previous incremental parsers have used monotonic state transitions. However, transitions can be made to revise previous decisions quite naturally, based on further information. We show that a simple adjustment to the Arc-Eager transition system to relax its monotonicity constraints can improve ac- curacy, so long as the training data in- cludes examples of mistakes for the non- monotonic transitions to repair. We eval- uate the change in the context of a state- of-the-art system, and obtain a statistically significant improvement (p < 0.001) on the English evaluation and 5/10 of the CoNLL languages. 1 Introduction Historically, monotonicity has played an im- portant role in transition-based parsing systems. Non-monotonic systems, including the one pre- sented here, typically redundantly generate multi- ple derivations for each syntactic analysis, leading to spurious ambiguity (Steedman, 2000). Early, pre-statistical work on transition-based parsing such as Abney and Johnson (1991) implicitly as- sumed that the parser searches the entire space of possible derivations. The presence of spuri- ous ambiguity causes this search space to be a di- rected graph rather than a tree, which considerably complicates the search, so spurious ambiguity was avoided whenever possible. However, we claim that non-monotonicity and spurious ambiguity are not disadvantages in a modern statistical parsing system such as ours. Modern statistical models have much larger search spaces because almost all possible analyses are al- lowed, and a numerical score (say, a probability distribution) is used to distinguish better analy- ses from worse ones. These search spaces are so large that we cannot exhaustively search them, so instead we use the scores associated with partial analyses to guide a search that explores only a mi- nuscule fraction of the space (In our case we use greedy decoding, but even a beam search only ex- plores a small fraction of the exponentially-many possible analyses). In fact, as we show here the additional redun- dant pathways between search states that non- monotonicity generates can be advantageous be- cause they allow the parser to “correct” an ear- lier parsing move and provide an opportunity to recover from formerly “fatal” mistakes. Infor- mally, non-monotonicity provides “many paths up the mountain” in the hope of making it easier to find at least one. We demonstrate this by modifying the Arc- Eager transition system (Nivre, 2003; Nivre et al., 2004) to allow a limited capability for non- monotonic transitions. The system normally em- ploys two deterministic constraints that limit the parser to actions consistent with the previous his- tory. We remove these, and update the transitions so that conflicts are resolved in favour of the latest prediction. The non-monotonic behaviour provides an im- provement …

Content truncated to 500 words