Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle

Proceedings of NAACL-HLT 2019, pages 204–217 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 204 Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle Maximin Coavoux∗ Naver Labs Europe maximin.coavoux@naverlabs.com Shay B. Cohen ILCC, School of Informatics University of Edinburgh scohen@inf.ed.ac.uk Abstract We introduce a novel transition system for dis- continuous constituency parsing. Instead of storing subtrees in a stack –i.e. a data structure with linear-time sequential access– the pro- posed system uses a set of parsing items, with constant-time random access. This change makes it possible to construct any discontinu- ous constituency tree in exactly 4n − 2 tran- sitions for a sentence of length n, whereas existing systems need a quadratic number of transitions to derive some structures. At each parsing step, the parser considers every item in the set to be combined with a focus item and to construct a new constituent in a bottom- up fashion. The parsing strategy is based on the assumption that most syntactic structures can be parsed incrementally and that the set – the memory of the parser– remains reasonably small on average. Moreover, we introduce a dynamic oracle for the new transition system, and present the first experiments in discontin- uous constituency parsing using a dynamic or- acle. Our parser obtains state-of-the-art results on three English and German discontinuous treebanks. 1 Introduction Discontinuous constituency trees extend standard constituency trees by allowing crossing branches to represent long distance dependencies, such as the wh-extraction in Figure 1. Discontinuous con- stituency trees can be seen as derivations of Linear Context-Free Rewriting Systems (LCFRS, Vijay- Shanker et al., 1987), a class of formal gram- mars more expressive than context-free grammars, which makes them much harder to parse. In par- ticular, exact CKY-style LCFRS parsing has an O(n3f) time complexity where f is the fan-out of the grammar (Kallmeyer, 2010). ∗Work done at the University of Edinburgh. SBARQ ┌─────────────┴────┬──────────────────┐ │ SQ │ │ ┌─────────┼────┐ │ │ │ │ VP │ │ │ ┌─── │ ───┴─────┐ │ │ │ VP │ │ │ │ ┌─── │ ───┴─── │ ──────── │ ──┐ │ │ WHNP │ NP │ │ │ │ │ │ ┌────┴────┐ │ │ │ RB WP VBZ DT NN TO VB . │ │ │ │ │ │ │ │ So what 's a parent to do ? Figure 1: Discontinuous constituency tree from the Discontinuous Penn treebank. A natural alternative to grammar-based chart parsing is transition-based parsing, that usually re- lies on fast approximate decoding methods such as greedy search or beam search. Transition- based discontinuous parsers construct discontin- uous constituents by reordering terminals with the SWAP action (Versley, 2014a,b; Maier, 2015; Maier and Lichte, 2016; Stanojevi´c and Gar- rido Alhama, 2017), or by using a split stack and the GAP action to combine two non-adjacent con- stituents (Coavoux and Crabb´e, 2017a; Coavoux et al., 2019). These proposals represent the mem- ory of the parser (i.e. the tree fragments being con- structed) with data structures with …

Content truncated to 500 words