Pseudo-Projective Dependency Parsing

Proceedings of the 43rd Annual Meeting of the ACL, pages 99–106, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Pseudo-Projective Dependency Parsing Joakim Nivre and Jens Nilsson School of Mathematics and Systems Engineering V¨axj¨o University SE-35195 V¨axj¨o, Sweden {nivre,jni}@msi.vxu.se Abstract In order to realize the full potential of dependency-based syntactic parsing, it is desirable to allow non-projective depen- dency structures. We show how a data- driven deterministic dependency parser, in itself restricted to projective structures, can be combined with graph transforma- tion techniques to produce non-projective structures. Experiments using data from the Prague Dependency Treebank show that the combined system can handle non- projective constructions with a precision sufficient to yield a significant improve- ment in overall parsing accuracy. This leads to the best reported performance for robust non-projective parsing of Czech. 1 Introduction It is sometimes claimed that one of the advantages of dependency grammar over approaches based on constituency is that it allows a more adequate treat- ment of languages with variable word order, where discontinuous syntactic constructions are more com- mon than in languages like English (Mel’ˇcuk, 1988; Covington, 1990). However, this argument is only plausible if the formal framework allows non-projective dependency structures, i.e. structures where a head and its dependents may correspond to a discontinuous constituent. From the point of view of computational implementation this can be problematic, since the inclusion of non-projective structures makes the parsing problem more com- plex and therefore compromises efficiency and in practice also accuracy and robustness. Thus, most broad-coverage parsers based on dependency gram- mar have been restricted to projective structures. This is true of the widely used link grammar parser for English (Sleator and Temperley, 1993), which uses a dependency grammar of sorts, the probabilis- tic dependency parser of Eisner (1996), and more recently proposed deterministic dependency parsers (Yamada and Matsumoto, 2003; Nivre et al., 2004). It is also true of the adaptation of the Collins parser for Czech (Collins et al., 1999) and the finite-state dependency parser for Turkish by Oflazer (2003). This is in contrast to dependency treebanks, e.g. Prague Dependency Treebank (Hajiˇc et al., 2001b), Danish Dependency Treebank (Kromann, 2003), and the METU Treebank of Turkish (Oflazer et al., 2003), which generally allow annotations with non- projective dependency structures. The fact that pro- jective dependency parsers can never exactly repro- duce the analyses found in non-projective treebanks is often neglected because of the relative scarcity of problematic constructions. While the proportion of sentences containing non-projective dependencies is often 15–25%, the total proportion of non-projective arcs is normally only 1–2%. As long as the main evaluation metric is dependency accuracy per word, with state-of-the-art accuracy mostly below 90%, the penalty for not handling non-projective construc- tions is almost negligible. Still, from a theoretical point of view, projective parsing of non-projective structures has the drawback that it rules out perfect accuracy even as an asymptotic goal. 99 (“Only one of them concerns quality.”) ZR (Out-of � � ? AuxP P nich them � � ? Atr …

Content truncated to 500 words