Incremental Discontinuous Phrase Structure Parsing with the GAP Transition

Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 1259–1270, Valencia, Spain, April 3-7, 2017. c⃝2017 Association for Computational Linguistics Incremental Discontinuous Phrase Structure Parsing with the GAP Transition Maximin Coavoux1,2 and Benoˆıt Crabb´e1,2,3 1Univ. Paris Diderot, Sorbonne Paris Cit´e 2Laboratoire de linguistique formelle (LLF, CNRS) 3Institut Universitaire de France maximin.coavoux@etu.univ-paris-diderot.fr benoit.crabbe@linguist.univ-paris-diderot.fr Abstract This article introduces a novel transition system for discontinuous lexicalized con- stituent parsing called SR-GAP. It is an ex- tension of the shift-reduce algorithm with an additional gap transition. Evaluation on two German treebanks shows that SR-GAP outperforms the previous best transition- based discontinuous parser (Maier, 2015) by a large margin (it is notably twice as ac- curate on the prediction of discontinuous constituents), and is competitive with the state of the art (Fern´andez-Gonz´alez and Martins, 2015). As a side contribution, we adapt span features (Hall et al., 2014) to discontinuous parsing. 1 Introduction Discontinuous constituent trees can be used to model directly certain specific linguistic phenom- ena, such as extraposition, or more broadly to de- scribe languages with some degree of word-order freedom. Although these phenomena are some- times annotated with indexed traces in CFG tree- banks, other constituent treebanks are natively an- notated with discontinuous constituents, e.g. the Tiger corpus (Brants, 1998). From a parsing point of view, discontinuities pose a challenge. Mildly context-sensitive for- malisms, that are expressive enough to model dis- continuities have high parsing complexity. For ex- ample, the CKY algorithm for a binary probabilis- tic LCFRS is in O(n3k), where k is the fan-out of the grammar (Kallmeyer, 2010). Recently, there have been several proposals for direct discontinuous parsing. They correspond roughly to three different parsing paradigms. (i) Chart parsers are based on probabilistic LCFRS (Kallmeyer and Maier, 2013; Maier, 2010; Evang S NP NP PPER VVFIN ADV ADJA NN Es best¨unde somit hinreichender Spielraum Figure 1: Discontinuous tree extracted from the Tiger corpus (punctuation removed). and Kallmeyer, 2011), or on the Data-Oriented Parsing (DOP) framework (van Cranenburgh, 2012; van Cranenburgh and Bod, 2013; van Cra- nenburgh et al., 2016). However, the complex- ity of inference in this paradigm requires to de- sign elaborate search strategies and heuristics to make parsing run-times reasonable. (ii) Several approaches are based on modified non-projective dependency parsers, for example Hall and Nivre (2008), or more recently Fern´andez-Gonz´alez and Martins (2015) who provided a surprisingly ac- curate parsing method that can profit from effi- cient dependency parsers with rich features. (iii) Transition-based discontinuous parsers are based on the easy-first framework (Versley, 2014a) or the shift-reduce algorithm augmented with a swap ac- tion (Maier, 2015). In the latter system, which we will refer to as SR-SWAP, a SWAP action pushes the second element of the stack back onto the buffer. Although SR-SWAP is fast and obtained good results, it underperforms Fern´andez-Gonz´alez and Martins (2015)’s parser by a large margin. We be- lieve this result does not indicate a fatal problem for the transition-based framework for discontin- …

Content truncated to 500 words