Representation Learning and Dynamic Programming for Arc-Hybrid Parsing

Proceedings of the 23rd Conference on Computational Natural Language Learning, pages 238–248 Hong Kong, China, November 3-4, 2019. c⃝2019 Association for Computational Linguistics 238 Representation Learning and Dynamic Programming for Arc-Hybrid Parsing Joseph Le Roux Antoine Rozenknop Mathieu Lacroix Laboratoire d’Informatique de Paris Nord, Universit´e Paris 13 – SPC, CNRS UMR 7030, F-93430, Villetaneuse, France {leroux,rozenknop,lacroix}@lipn.fr Abstract We present a new method for transition-based parsing where a solution is a pair made of a dependency tree and a derivation graph de- scribing the construction of the former. From this representation we are able to derive an ef- ficient parsing algorithm and design a neural network that learns vertex representations and arc scores. Experimentally, although we only train via local classifiers, our approach im- proves over previous arc-hybrid systems and reach state-of-the-art parsing accuracy. 1 Introduction While transition-based dependency parsing is usu- ally implemented as a beam-search procedure, e.g. (Kiperwasser and Goldberg, 2016), some re- cent work such as (Shi et al., 2017) showed that global inference can be performed efficiently with dynamic programming. To this end, the stack rep- resenting pending subparses and the buffer repre- senting the unconsumed input must both be ab- stracted into equivalence classes, while remaining rich enough to help with accurate predictions. In this paper we first explicitly consider that a solution in transition-based parsing is represented as a pair made of a derivation graph and a derived dependency tree allowing the scoring function to be expressed naturally as a sum over these 2 struc- tures. While we restrict our presentation to arc- hybrid systems, our method can be applied quite directly to other transition rule systems. Secondly we show that this representation leads to an exact O(n4) parsing algorithm using dy- namic programming. This algorithm can be seen as an extension of the minimal feature set arc- hybrid parsing algorithm presented in (Shi et al., 2017) where the contribution of the dependency arcs can be explicitly added to the scoring function as in the Eisner parsing algorithm (Eisner, 1996). We then propose an alternative approach to global inference where derivation steps are repre- sented as dense vectors based on the number and type of steps in a derivation. With this abstrac- tion we design a neural architecture based on non- local networks (Wang et al., 2017) related to self- attention mechanism (Vaswani et al., 2017; Gu et al., 2018) to learn these representations while maintaining the possibility for exact decoding. Our contribution can be summarized as follows: (i) a representation of arc-hybrid parsing as max- imum subgraphs selection where a solution con- tains dependencies and derivation information; (ii) a polynomial dynamic programming algorithm to solve this problem exactly; (iii) a neural architec- ture able to learn representations for the subgraph vertices and compute arc scores without explicit stack and buffer representations. These contributions are validated empirically by experimental results on the Penn Treebank where our system reaches state-of-the-art accu- racy (94.8% UAS) for arc-hybrid parsing with net- works of comparable size. We first review …

Content truncated to 500 words