Left-to-Right Dependency Parsing with Pointer Networks

Proceedings of NAACL-HLT 2019, pages 710–716 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 710 Left-to-Right Dependency Parsing with Pointer Networks Daniel Fern´andez-Gonz´alez Universidade da Coru˜na FASTPARSE Lab, LyS Group Departamento de Computaci´on Elvi˜na, 15071 A Coru˜na, Spain d.fgonzalez@udc.es Carlos G´omez-Rodr´ıguez Universidade da Coru˜na, CITIC FASTPARSE Lab, LyS Group Departamento de Computaci´on Elvi˜na, 15071 A Coru˜na, Spain carlos.gomez@udc.es Abstract We propose a novel transition-based algorithm that straightforwardly parses sentences from left to right by building n attachments, with n being the length of the input sentence. Sim- ilarly to the recent stack-pointer parser by Ma et al. (2018), we use the pointer network framework that, given a word, can directly point to a position from the sentence. How- ever, our left-to-right approach is simpler than the original top-down stack-pointer parser (not requiring a stack) and reduces transition se- quence length in half, from 2n − 1 actions to n. This results in a quadratic non-projective parser that runs twice as fast as the original while achieving the best accuracy to date on the English PTB dataset (96.04% UAS, 94.43% LAS) among fully-supervised single- model dependency parsers, and improves over the former top-down transition system in the majority of languages tested. 1 Introduction Dependency parsing, the task of automatically ob- taining the grammatical structure of a sentence expressed as a dependency tree, has been widely studied by natural language processing (NLP) re- searchers in the last decades. Most of the mod- els providing competitive accuracies fall into two broad families of approaches: graph-based (Mc- Donald et al., 2005a,b) and transition-based (Ya- mada and Matsumoto, 2003; Nivre, 2003) depend- ency parsers. Given an input sentence, a graph-based parser scores trees by decomposing them into factors, and performs a search for the highest-scoring tree. In the past two years, this kind of depend- ency parsers have been ahead in terms of accuracy thanks to the graph-based neural architecture de- veloped by Dozat and Manning (2016), which not only achieved state-of-the-art accuracies on the Stanford Dependencies conversion of the English Penn Treebank (hereinafter, PTB-SD), but also ob- tained the best results in the majority of languages in the CoNLL 2017 Shared Task (Dozat et al., 2017). This tendency recently changed, since a transition-based parser developed by Ma et al. (2018) managed to outperform the best graph- based model in the majority of datasets tested. Transition-based parsers incrementally build a dependency graph for an input sentence by ap- plying a sequence of transitions. This results in more efficient parsers with linear time complex- ity for parsing projective sentences, or quadratic for handling non-projective structures, when im- plemented with greedy or beam search. However, their main weakness is the lack of access to global context information when transitions are greedily chosen. This favours error propagation, mainly affecting long dependencies that require a larger number of transitions to be built (McDonald and Nivre, 2011). Many attempts have been made to alleviate the impact of error propagation in transition-based de- pendency parsing, but …

Content truncated to 500 words