Non-Projective Dependency Parsing in Expected Linear Time

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 351–359, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Non-Projective Dependency Parsing in Expected Linear Time Joakim Nivre Uppsala University, Department of Linguistics and Philology, SE-75126 Uppsala V¨axj¨o University, School of Mathematics and Systems Engineering, SE-35195 V¨axj¨o E-mail: joakim.nivre@lingfil.uu.se Abstract We present a novel transition system for dependency parsing, which constructs arcs only between adjacent words but can parse arbitrary non-projective trees by swapping the order of words in the input. Adding the swapping operation changes the time complexity for deterministic parsing from linear to quadratic in the worst case, but empirical estimates based on treebank data show that the expected running time is in fact linear for the range of data attested in the corpora. Evaluation on data from five languages shows state-of-the-art accuracy, with especially good results for the labeled exact match score. 1 Introduction Syntactic parsing using dependency structures has become a standard technique in natural language processing with many different parsing models, in particular data-driven models that can be trained on syntactically annotated corpora (Yamada and Matsumoto, 2003; Nivre et al., 2004; McDonald et al., 2005a; Attardi, 2006; Titov and Henderson, 2007). A hallmark of many of these models is that they can be implemented very efficiently. Thus, transition-based parsers normally run in linear or quadratic time, using greedy deterministic search or fixed-width beam search (Nivre et al., 2004; At- tardi, 2006; Johansson and Nugues, 2007; Titov and Henderson, 2007), and graph-based models support exact inference in at most cubic time, which is efficient enough to make global discrim- inative training practically feasible (McDonald et al., 2005a; McDonald et al., 2005b). However, one problem that still has not found a satisfactory solution in data-driven dependency parsing is the treatment of discontinuous syntactic constructions, usually modeled by non-projective dependency trees, as illustrated in Figure 1. In a projective dependency tree, the yield of every sub- tree is a contiguous substring of the sentence. This is not the case for the tree in Figure 1, where the subtrees rooted at node 2 (hearing) and node 4 (scheduled) both have discontinuous yields. Allowing non-projective trees generally makes parsing computationally harder. Exact inference for parsing models that allow non-projective trees is NP hard, except under very restricted indepen- dence assumptions (Neuhaus and Br¨oker, 1997; McDonald and Pereira, 2006; McDonald and Satta, 2007). There is recent work on algorithms that can cope with important subsets of all non- projective trees in polynomial time (Kuhlmann and Satta, 2009; G´omez-Rodr´ıguez et al., 2009), but the time complexity is at best O(n6), which can be problematic in practical applications. Even the best algorithms for deterministic parsing run in quadratic time, rather than linear (Nivre, 2008a), unless restricted to a subset of non-projective structures as in Attardi (2006) and Nivre (2007). But allowing non-projective dependency trees also makes parsing empirically harder, because it requires that we model relations between non- adjacent structures over potentially unbounded distances, which …

Content truncated to 500 words