Efficient Discontinuous Phrase-Structure Parsing via the Generalized Maximum Spanning Arborescence

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1644–1654 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Efficient Discontinuous Phrase-Structure Parsing via the Generalized Maximum Spanning Arborescence Caio Corro Joseph Le Roux Mathieu Lacroix Laboratoire d’Informatique de Paris Nord, Universit´e Paris 13 – SPC, CNRS UMR 7030, F-93430, Villetaneuse, France {corro,leroux,lacroix}@lipn.fr Abstract We present a new method for the joint task of tagging and non-projective depen- dency parsing. We demonstrate its use- fulness with an application to discontinu- ous phrase-structure parsing where decod- ing lexicalized spines and syntactic deriva- tions is performed jointly. The main con- tributions of this paper are (1) a reduction from joint tagging and non-projective de- pendency parsing to the Generalized Max- imum Spanning Arborescence problem, and (2) a novel decoding algorithm for this problem through Lagrangian relax- ation. We evaluate this model and obtain state-of-the-art results despite strong inde- pendence assumptions. 1 Introduction Discontinuous phrase-structure parsing relies ei- ther on formal grammars such as LCFRS, which suffer from a high complexity, or on reductions to non-projective dependency parsing with complex labels to encode phrase combinations. We pro- pose an alternative approach based on a variant of spinal TAGs, which allows parses with disconti- nuity while grounding this work on a lexicalized phrase-structure grammar. Contrarily to previous approaches, (Hall and Nivre, 2008; Versley, 2014; Fern´andez-Gonz´alez and Martins, 2015), we do not model supertagging nor spine interactions with a complex label scheme. We follow Carreras et al. (2008) but drop projectivity. We first show that our discontinuous variant of spinal TAG reduces to the Generalized Max- imum Spanning Arborescence (GMSA) problem (Myung et al., 1995). In a graph where vertices are partitioned into clusters, GMSA consists in finding the arborescence of maximum weight in- cident to exactly one vertex per cluster. This prob- lem is NP-complete even for arc-factored models. In order to bypass complexity, we resort to La- grangian relaxation and propose an efficient res- olution based on dual decomposition which com- bines a simple non-projective dependency parser on a contracted graph and a local search on each cluster to find a global consensus. We evaluated our model on the discontinuous PTB (Evang and Kallmeyer, 2011) and the Tiger (Brants et al., 2004) corpora. Moreover, we show that our algorithm is able to quickly parse the whole test sets. Section 2 presents the parsing problem. Sec- tion 3 introduces GMSA from which we derive an effective resolution method in Section 4. In Sec- tion 5 we define a parameterization of the parser which uses neural networks to model local prob- abilities and present experimental results in Sec- tion 6. We discuss related work in Section 7. 2 Joint Supertagging and Spine Parsing In this section we introduce our problem and set notation. The goal of phrase-structure parsing is to produce a derived tree by means of a se- quence of operations called a derivation. For in- stance in context-free grammars the derived tree is built from a sequence of …

Content truncated to 500 words