A Full Non-Monotonic Transition System for Unrestricted Non-Projective Parsing

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 288–298 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1027 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 288–298 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1027 A Full Non-Monotonic Transition System for Unrestricted Non-Projective Parsing Daniel Fern´andez-Gonz´alez and Carlos G´omez-Rodr´ıguez Universidade da Coru˜na FASTPARSE Lab, LyS Research Group, Departamento de Computaci´on Campus de Elvi˜na, s/n, 15071 A Coru˜na, Spain d.fgonzalez@udc.es, carlos.gomez@udc.es Abstract Restricted non-monotonicity has been shown beneficial for the projective arc- eager dependency parser in previous re- search, as posterior decisions can repair mistakes made in previous states due to the lack of information. In this paper, we pro- pose a novel, fully non-monotonic trans- ition system based on the non-projective Covington algorithm. As a non-monotonic system requires exploration of erroneous actions during the training process, we de- velop several non-monotonic variants of the recently defined dynamic oracle for the Covington parser, based on tight approx- imations of the loss. Experiments on data- sets from the CoNLL-X and CoNLL-XI shared tasks show that a non-monotonic dynamic oracle outperforms the mono- tonic version in the majority of languages. 1 Introduction Greedy transition-based dependency parsers are widely used in different NLP tasks due to their speed and efficiency. They parse a sentence from left to right by greedily choosing the highest- scoring transition to go from the current parser configuration or state to the next. The resulting se- quence of transitions incrementally builds a parse for the input sentence. The scoring of the trans- itions is provided by a statistical model, previously trained to approximate an oracle, a function that selects the needed transitions to parse a gold tree. Unfortunately, the greedy nature that grants these parsers their efficiency also represents their main limitation. McDonald and Nivre (2007) show that greedy transition-based parsers lose ac- curacy to error propagation: a transition erro- neously chosen by the greedy parser can place it in an incorrect and unknown configuration, caus- ing more mistakes in the rest of the transition se- quence. Training with a dynamic oracle (Goldberg and Nivre, 2012) improves robustness in these situations, but in a monotonic transition system, erroneous decisions made in the past are perman- ent, even when the availability of further informa- tion in later states might be useful to correct them. Honnibal et al. (2013) show that allowing some degree of non-monotonicity, by using a limited set of non-monotonic actions that can repair past mistakes and replace previously-built arcs, can in- crease the accuracy of a transition-based parser. In particular, they present a modified arc-eager trans- ition system where the Left-Arc and Reduce trans- itions are non-monotonic: the former is used to repair invalid attachments made in previous states by replacing them with a leftward arc, and the latter allows the parser to link two words with a rightward arc that were previously left unattached due to …

Content truncated to 500 words