Treebank Grammar Techniques for Non-Projective Dependency Parsing

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 478–486, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Treebank Grammar Techniques for Non-Projective Dependency Parsing Marco Kuhlmann Uppsala University Uppsala, Sweden marco.kuhlmann@lingfil.uu.se Giorgio Satta University of Padua Padova, Italy satta@dei.unipd.it Abstract An open problem in dependency parsing is the accurate and efficient treatment of non-projective structures. We propose to attack this problem using chart-parsing algorithms developed for mildly context- sensitive grammar formalisms. In this pa- per, we provide two key tools for this ap- proach. First, we show how to reduce non- projective dependency parsing to parsing with Linear Context-Free Rewriting Sys- tems (LCFRS), by presenting a technique for extracting LCFRS from dependency treebanks. For efficient parsing, the ex- tracted grammars need to be transformed in order to minimize the number of nonter- minal symbols per production. Our second contribution is an algorithm that computes this transformation for a large, empirically relevant class of grammars. 1 Introduction Dependency parsing is the task of predicting the most probable dependency structure for a given sentence. One of the key choices in dependency parsing is about the class of candidate structures for this prediction. Many parsers are confined to projective structures, in which the yield of a syn- tactic head is required to be continuous. A major benefit of this choice is computational efficiency: an exhaustive search over all projective structures can be done in cubic, greedy parsing in linear time (Eisner, 1996; Nivre, 2003). A major drawback of the restriction to projective dependency structures is a potential loss in accuracy. For example, around 23% of the analyses in the Prague Dependency Treebank of Czech (Hajiˇc et al., 2001) are non- projective, and for German and Dutch treebanks, the proportion of non-projective structures is even higher (Havelka, 2007). The problem of non-projective dependency pars- ing under the joint requirement of accuracy and efficiency has only recently been addressed in the literature. Some authors propose to solve it by tech- niques for recovering non-projectivity from the out- put of a projective parser in a post-processing step (Hall and Novák, 2005; Nivre and Nilsson, 2005), others extend projective parsers by heuristics that allow at least certain non-projective constructions to be parsed (Attardi, 2006; Nivre, 2007). McDon- ald et al. (2005) formulate dependency parsing as the search for the most probable spanning tree over the full set of all possible dependencies. However, this approach is limited to probability models with strong independence assumptions. Exhaustive non- projective dependency parsing with more powerful models is intractable (McDonald and Satta, 2007), and one has to resort to approximation algorithms (McDonald and Pereira, 2006). In this paper, we propose to attack non-project- ive dependency parsing in a principled way, us- ing polynomial chart-parsing algorithms developed for mildly context-sensitive grammar formalisms. This proposal is motivated by the observation that most dependency structures required for the ana- lysis of natural language are very nearly projective, differing only minimally from the best projective approximation …

Content truncated to 500 words