Beyond Projectivity: Multilingual Evaluation of Constraints and Measures on Non-Projective Structures

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 608–615, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Beyond Projectivity: Multilingual Evaluation of Constraints and Measures on Non-Projective Structures Jiˇr´ı Havelka Institute of Formal and Applied Linguistics Charles University in Prague Czech Republic havelka@ufal.mff.cuni.cz Abstract Dependency analysis of natural language has gained importance for its applicability to NLP tasks. Non-projective structures are common in dependency analysis, there- fore we need fine-grained means of describ- ing them, especially for the purposes of machine-learning oriented approaches like parsing. We present an evaluation on twelve languages which explores several constraints and measures on non-projective structures. We pursue an edge-based ap- proach concentrating on properties of in- dividual edges as opposed to properties of whole trees. In our evaluation, we include previously unreported measures taking into account levels of nodes in dependency trees. Our empirical results corroborate theoreti- cal results and show that an edge-based ap- proach using levels of nodes provides an accurate and at the same time expressive means for capturing non-projective struc- tures in natural language. 1 Introduction Dependency analysis of natural language has been gaining an ever increasing interest thanks to its ap- plicability in many tasks of NLP—a recent example is the dependency parsing work of McDonald et al. (2005), which introduces an approach based on the search for maximum spanning trees, capable of han- dling non-projective structures naturally. The study of dependency structures occurring in natural language can be approached from two sides: by trying to delimit permissible dependency struc- tures through formal constraints (for a recent review paper, see Kuhlmann and Nivre (2006)), or by pro- viding their linguistic description (see e.g. Vesel´a et al. (2004) and Hajiˇcov´a et al. (2004) for a linguistic analysis of non-projective constructions in Czech.1) We think that it is worth bearing in mind that neither syntactic structures in dependency tree- banks, nor structures arising in machine-learning ap- proaches, such as MST dependency parsing, need a priori fall into any formal subclass of dependency trees. We should therefore aim at formal means ca- pable of describing all non-projective structures that are both expressive and fine-grained enough to be useful in statistical approaches, and at the same time suitable for an adequate linguistic description.2 Holan et al. (1998) first defined an infinite hierar- chy of classes of dependency trees, going from pro- jective to unrestricted dependency trees, based on the notion of gap degree for subtrees (cf. Section 3). Holan et al. (2000) present linguistic considerations concerning Czech and English with respect to this hierarchy (cf. also Section 6). In this paper, we consider all constraints and mea- sures evaluated by Kuhlmann and Nivre (2006)— with some minor variations, cf. Section 4.2. Ad- 1These two papers contain an error concerning an alternative condition of projectivity, which is rectified in Havelka (2005). 2The importance of such means becomes more evident from the asymptotically negligible proportion of projective trees to all dependency trees; there are super-exponentially many unre- stricted …

Content truncated to 500 words