Sequential Graph Dependency Parser

Proceedings of Recent Advances in Natural Language Processing, pages 1338–1345, Varna, Bulgaria, Sep 2–4, 2019. https://doi.org/10.26615/978-954-452-056-4_153 1338 Sequential Graph Dependency Parser Sean Welleck New York University wellecks@nyu.edu Kyunghyun Cho New York University CIFAR Azrieli Global Scholar Facebook AI Research kyunghyun.cho@nyu.edu Abstract We propose a method for non-projective dependency parsing by incrementally pre- dicting a set of edges. Since the edges do not have a pre-specified order, we pro- pose a set-based learning method. Our method blends graph, transition, and easy- first parsing, including a prior state of the parser as a special case. The pro- posed transition-based method success- fully parses near the state of the art on both projective and non-projective languages, without assuming a certain parsing order. 1 Introduction Dependency parsing methods can be categorized as graph-based and transition-based. Typical graph-based methods support non-projective pars- ing, but introduce independence assumptions and rely on external decoding algorithms. Conversely, transition-based methods model joint dependen- cies, but without modification are typically limited to projective parses. There are two recent exceptions of interest here. (Ma et al., 2018) developed the Stack-Pointer parser, a transition-based, non-projective parser that maintains a stack populated in a top-down, depth-first manner, and uses a pointer network to determine the dependent of the stack’s top node, 1.resulting in a transition sequence of length 2n − Recently, (Fern´andez-Gonz´alez and G´omez- Rodrguez, 2019) developed a variant of the Stack- Pointer parser which parses in n steps by travers- ing the sentence left-to-right, selecting the head of the current node in the traversal, while incremen- tally checking for, and prohibiting, cycles. We take inspiration from both graph-based and transition-based approaches by viewing parsing as sequential graph generation. In this view, a graph is incrementally built by adding edges to an edge set. No distinction between projective and non-projective trees is necessary. Since edges do not have a pre-specified order, we propose a set-based learning method. Like (Fern´andez- Gonz´alez and G´omez-Rodrguez, 2019), our parser runs in n steps. However, our learning method and transitions do not impose a left-to-right pars- ing order, allowing easy-first (Tsuruoka and Tsu- jii, 2005; Goldberg and Elhadad, 2010) behavior. Experimentally, we find that the proposed method can yield a sequential parser with preferred, input- dependent generation orders and performance gains over strong one-step methods.1 2 Graph Dependency Parser Given a sentence x = x1, . . . , xN, a dependency parser constructs a graph G = (V, E) with V = (x0, x1, . . . , xN) and E = {(i, j)1, . . . (i, j)N}, where x0 is a special root node, and E ⊂ E forms a dependency tree.2 We describe a family of sequential graph-based dependency parsers. A parser in this family gen- erates a sequence of graphs where V is fixed and E = �T t=1 Et: Henc = fenc(x0, . . . xN) (1) Hhead t , Hdep t = fV(Henc, E<t, ht−1) (2) St = fE(Hhead t , Hdep t , St−1) (3) Et = fdec(St, E<t). (4) …

Content truncated to 500 words