Incremental Non-Projective Dependency Parsing

Proceedings of NAACL HLT 2007, pages 396–403, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Incremental 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,lingfil.uu.se} Abstract An open issue in data-driven dependency parsing is how to handle non-projective dependencies, which seem to be required by linguistically adequate representations, but which pose problems in parsing with respect to both accuracy and efficiency. Using data from five different languages, we evaluate an incremental deterministic parser that derives non-projective depen- dency structures in O(n2) time, supported by SVM classifiers for predicting the next parser action. The experiments show that unrestricted non-projective parsing gives a significant improvement in accuracy, compared to a strictly projective baseline, with up to 35% error reduction, leading to state-of-the-art results for the given data sets. Moreover, by restricting the class of permissible structures to limited degrees of non-projectivity, the parsing time can be reduced by up to 50% without a significant decrease in accuracy. 1 Introduction Data-driven dependency parsing has been shown to give accurate and efficient parsing for a wide range of languages, such as Japanese (Kudo and Mat- sumoto, 2002), English (Yamada and Matsumoto, 2003), Swedish (Nivre et al., 2004), Chinese (Cheng et al., 2004), and Czech (McDonald et al., 2005). Whereas most of the early approaches were limited to strictly projective dependency structures, where the projection of a syntactic head must be contin- uous, attention has recently shifted to the analysis of non-projective structures, which are required for linguistically adequate representations, especially in languages with free or flexible word order. The most popular strategy for capturing non- projective structures in data-driven dependency parsing is to apply some kind of post-processing to the output of a strictly projective dependency parser, as in pseudo-projective parsing (Nivre and Nilsson, 2005), corrective modeling (Hall and Nov´ak, 2005), or approximate non-projective parsing (McDonald and Pereira, 2006). And it is rare to find parsers that derive non-projective structures directly, the no- table exception being the non-projective spanning tree parser proposed by McDonald et al. (2005). There are essentially two arguments that have been advanced against using parsing algorithms that derive non-projective dependency structures di- rectly. The first is that the added expressivity com- promises efficiency, since the parsing problem for a grammar that allows arbitrary non-projective depen- dency structures has been shown to be NP complete (Neuhaus and Br¨oker, 1997). On the other hand, most data-driven approaches do not rely on gram- mars, and with a suitable factorization of depen- dency structures, it is possible to achieve parsing of unrestricted non-projective structures in O(n2) time, as shown by McDonald et al. (2005). The second argument against non-projective de- pendency parsing comes from the observation that, even in languages with free or flexible word order, 396 most dependency structures are either projective or very nearly projective. This can be seen by con- sidering data from treebanks, such as the Prague Dependency Treebank of Czech (B¨ohmov´a et al., 2003), the TIGER …

Content truncated to 500 words