Constraints on Non-Projective Dependency Parsing

Constraints on Non-Projective Dependency Parsing Joakim Nivre V¨axj¨o University, School of Mathematics and Systems Engineering Uppsala University, Department of Linguistics and Philology joakim.nivre@msi.vxu.se Abstract We investigate a series of graph-theoretic constraints on non-projective dependency parsing and their effect on expressivity, i.e. whether they allow naturally occurring syntactic constructions to be adequately represented, and efficiency, i.e. whether they reduce the search space for the parser. In particular, we define a new measure for the degree of non-projectivity in an acyclic dependency graph obeying the single-head constraint. The constraints are evaluated experimentally using data from the Prague Dependency Treebank and the Danish Dependency Treebank. The results indicate that, whereas complete linguistic coverage in principle requires unrestricted non-projective dependency graphs, limit- ing the degree of non-projectivity to at most 2 can reduce average running time from quadratic to linear, while excluding less than 0.5% of the dependency graphs found in the two treebanks. This is a sub- stantial improvement over the commonly used projective approximation (degree 0), which excludes 15–25% of the graphs. 1 Introduction Data-driven approaches to syntactic parsing has until quite recently been limited to representations that do not capture non-local dependencies. This is true regardless of whether representations are based on constituency, where such dependencies are traditionally represented by empty categories and coindexation to avoid explicitly discontinuous constituents, or on dependency, where it is more common to use a direct encoding of so-called non- projective dependencies. While this “surface dependency approximation” (Levy and Manning, 2004) may be acceptable for certain applications of syntactic parsing, it is clearly not adequate as a basis for deep semantic interpretation, which explains the growing body of research devoted to different methods for correct- ing this approximation. Most of this work has so far focused either on post-processing to recover non-local dependencies from context-free parse trees (Johnson, 2002; Jijkoun and De Rijke, 2004; Levy and Manning, 2004; Campbell, 2004), or on incorporating nonlocal dependency information in nonterminal categories in constituency represen- tations (Dienes and Dubey, 2003; Hockenmaier, 2003; Cahill et al., 2004) or in the categories used to label arcs in dependency representations (Nivre and Nilsson, 2005). By contrast, there is very little work on parsing methods that allow discontinuous constructions to be represented directly in the syntactic structure, whether by discontinuous constituent structures or by non-projective dependency structures. No- table exceptions are Plaehn (2000), where discon- tinuous phrase structure grammar parsing is ex- plored, and McDonald et al. (2005b), where non- projective dependency structures are derived using spanning tree algorithms from graph theory. One question that arises if we want to pursue the structure-based approach is how to constrain the class of permissible structures. On the one hand, we want to capture all the constructions that are found in natural languages, or at least to provide a much better approximation than before. On the other hand, it must still be possible for the parser not only to search the space of permissible struc- tures in an efficient way but also to learn to select …

Content truncated to 500 words