Efficient Parsing for Head-Split Dependency Trees

Transactions of the Association for Computational Linguistics, 1 (2013) 267–278. Action Editor: Brian Roark. Submitted 3/2013; Published 7/2013. c⃝2013 Association for Computational Linguistics. Efficient Parsing for Head-Split Dependency Trees Giorgio Satta Dept. of Information Engineering University of Padua, Italy satta@dei.unipd.it Marco Kuhlmann Dept. of Linguistics and Philology Uppsala University, Sweden marco.kuhlmann@lingfil.uu.se Abstract Head splitting techniques have been success- fully exploited to improve the asymptotic runtime of parsing algorithms for project- ive dependency trees, under the arc-factored model. In this article we extend these tech- niques to a class of non-projective dependency trees, called well-nested dependency trees with block-degree at most 2, which has been previ- ously investigated in the literature. We define a structural property that allows head splitting for these trees, and present two algorithms that im- prove over the runtime of existing algorithms at no significant loss in coverage. 1 Introduction Much of the recent work on dependency parsing has been aimed at finding a good balance between ac- curacy and efficiency. For one end of the spectrum, Eisner (1997) showed that the highest-scoring pro- jective dependency tree under an arc-factored model can be computed in time O.n3/, where n is the length of the input string. Later work has focused on mak- ing projective parsing viable under more expressive models (Carreras, 2007; Koo and Collins, 2010). At the same time, it has been observed that for many standard data sets, the coverage of projective trees is far from complete (Kuhlmann and Nivre, 2006), which has led to an interest in parsing al- gorithms for non-projective trees. While non-project- ive parsing under an arc-factored model can be done in time O.n2/ (McDonald et al., 2005), parsing with more informed models is intractable (McDonald and Satta, 2007). This has led several authors to investig- ate ‘mildly non-projective’ classes of trees, with the goal of achieving a balance between expressiveness and complexity (Kuhlmann and Nivre, 2006). In this article we focus on a class of mildly non- projective dependency structures called well-nested dependency trees with block-degree at most 2. This class was first introduced by Bodirsky et al. (2005), who showed that it corresponds, in a natural way, to the class of derivation trees of lexicalized tree-adjoin- ing grammars (Joshi and Schabes, 1997). While there are linguistic arguments against the restriction to this class (Maier and Lichte, 2011; Chen-Main and Joshi, 2010), Kuhlmann and Nivre (2006) found that it has excellent coverage on standard data sets. Assum- ing an arc-factored model, well-nested dependency trees with block-degree � 2 can be parsed in time O.n7/ using the algorithm of G´omez-Rodr´ıguez et al. (2011). Recently, Pitler et al. (2012) have shown that if an additional restriction called 1-inherit is im- posed, parsing can be done in time O.n6/, without any additional loss in coverage on standard data sets. Standard context-free parsing methods, when adap- ted to the parsing of projective trees, provide O.n5/ time complexity. The O.n3/ time result reported by Eisner (1997) has been obtained by exploiting more sophisticated dynamic programming …

Content truncated to 500 words