A Transition-Based Parser for 2-Planar Dependency Structures

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1492–1501, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics A Transition-Based Parser for 2-Planar Dependency Structures Carlos G´omez-Rodr´ıguez Departamento de Computaci´on Universidade da Coru˜na, Spain carlos.gomez@udc.es Joakim Nivre Department of Linguistics and Philology Uppsala University, Sweden joakim.nivre@lingfil.uu.se Abstract Finding a class of structures that is rich enough for adequate linguistic represen- tation yet restricted enough for efficient computational processing is an important problem for dependency parsing. In this paper, we present a transition system for 2-planar dependency trees – trees that can be decomposed into at most two planar graphs – and show that it can be used to implement a classifier-based parser that runs in linear time and outperforms a state- of-the-art transition-based parser on four data sets from the CoNLL-X shared task. In addition, we present an efficient method for determining whether an arbitrary tree is 2-planar and show that 99% or more of the trees in existing treebanks are 2-planar. 1 Introduction Dependency-based syntactic parsing has become a widely used technique in natural language pro- cessing, and many different parsing models have been proposed in recent years (Yamada and Mat- sumoto, 2003; Nivre et al., 2004; McDonald et al., 2005a; Titov and Henderson, 2007; Martins et al., 2009). One of the unresolved issues in this area is the proper treatment of non-projective depen- dency trees, which seem to be required for an ad- equate representation of predicate-argument struc- ture, but which undermine the efficiency of depen- dency parsing (Neuhaus and Br¨oker, 1997; Buch- Kromann, 2006; McDonald and Satta, 2007). Caught between the Scylla of linguistically in- adequate projective trees and the Charybdis of computationally intractable non-projective trees, some researchers have sought a middle ground by exploring classes of mildly non-projective depen- dency structures that strike a better balance be- tween expressivity and complexity (Nivre, 2006; Kuhlmann and Nivre, 2006; Kuhlmann and M¨ohl, 2007; Havelka, 2007). Although these proposals seem to have a very good fit with linguistic data, in the sense that they often cover 99% or more of the structures found in existing treebanks, the de- velopment of efficient parsing algorithms for these classes has met with more limited success. For example, while both Kuhlmann and Satta (2009) and G´omez-Rodr´ıguez et al. (2009) have shown how well-nested dependency trees with bounded gap degree can be parsed in polynomial time, the best time complexity for lexicalized parsing of this class remains a prohibitive O(n7), which makes the practical usefulness questionable. In this paper, we explore another characteri- zation of mildly non-projective dependency trees based on the notion of multiplanarity. This was originally proposed by Yli-Jyr¨a (2003) but has so far played a marginal role in the dependency pars- ing literature, because no algorithm was known for determining whether an arbitrary tree was m- planar, and no parsing algorithm existed for any constant value of m. The contribution of this pa- per is twofold. First, we present a procedure for determining the minimal …

Content truncated to 500 words