An Improved Non-monotonic Transition System for Dependency Parsing

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1373–1378, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. An Improved Non-monotonic Transition System for Dependency Parsing Matthew Honnibal spaCy.io Berlin, Germany matt@spacy.io Mark Johnson Department of Computing Macquarie University Sydney, Australia mark.johnson@mq.edu.edu.au Abstract Transition-based dependency parsers usu- ally use transition systems that monotoni- cally extend partial parse states until they identify a complete parse tree. Honni- bal et al. (2013) showed that greedy one- best parsing accuracy can be improved by adding additional non-monotonic tran- sitions that permit the parser to “repair” earlier parsing mistakes by “over-writing” earlier parsing decisions. This increases the size of the set of complete parse trees that each partial parse state can derive, en- abling such a parser to escape the “gar- den paths” that can trap monotonic greedy transition-based dependency parsers. We describe a new set of non-monotonic transitions that permits a partial parse state to derive a larger set of completed parse trees than previous work, which allows our parser to escape from a larger set of gar- den paths. A parser with our new non- monotonic transition system has 91.85% directed attachment accuracy, an improve- ment of 0.6% over a comparable parser us- ing the standard monotonic arc-eager tran- sitions. 1 Introduction Recent work from Dyer et al. (2015) and Weiss et al. (2015) show that neural network models can improve greedy transition-based parsers dramat- ically, even beyond the 20% error reduction re- ported by Chen and Manning (2014). Improve- ments on beam-search parsing are much more lim- ited, due to the difficulty of applying neural net- works to structured prediction. We suggest that the lack of a ready search so- lution may present the next barrier to further im- provements in accuracy. Some degree of search flexibility seems inherently necessary, no mat- ter how powerful the local model becomes, as even the human sentence processor can be ‘garden pathed’ by local structural ambiguities. We take inspiration from Frazier and Rayner (1982) and other psycholinguists and propose re- pair actions as a light-weight alternative to beam- search. In a transition-based dependency parser, transitions map parse states to parse states, ulti- mately producing completed parse trees. This pro- cess is non-deterministic, since usually more than one transition can apply to a parse state. This means that each partial parse state can be associ- ated with a set of complete parse trees (i.e., the complete parses that can be produced by applying sequences of transitions to the partial parse state). In general adding additional transitions (mono- tonic or non-monotonic) increases the number of complete parse trees that any given partial parse state can derive. We explore adding non-monotonic parsing tran- sitions to a greedy arc-eager dependency parser in this paper, in order to permit the parser to recover from attachment errors made early in the parsing process. These additional non-monotonic transi- tions permit the parser to modify what would have been irrevocable parsing decisions in the mono- tonic …

Content truncated to 500 words