Optimizing Grammars for Minimum Dependency Length

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 184–191, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Optimizing Grammars for Minimum Dependency Length Daniel Gildea Computer Science Dept. University of Rochester Rochester, NY 14627 David Temperley Eastman School of Music University of Rochester Rochester, NY 14604 Abstract We examine the problem of choosing word order for a set of dependency trees so as to minimize total dependency length. We present an algorithm for computing the op- timal layout of a single tree as well as a numerical method for optimizing a gram- mar of orderings over a set of dependency types. A grammar generated by minimizing dependency length in unordered trees from the Penn Treebank is found to agree surpris- ingly well with English word order, suggest- ing that dependency length minimization has influenced the evolution of English. 1 Introduction Dependency approaches to language assume that ev- ery word in a sentence is the dependent of one other word (except for one word, which is the global head of the sentence), so that the words of a sentence form an acyclic directed graph. An important principle of language, supported by a wide range of evidence, is that there is preference for dependencies to be short. This has been offered as an explanation for numer- ous psycholinguistic phenomena, such as the greater processing difficulty of object relative clauses ver- sus subject relative clauses (Gibson, 1998). Depen- dency length minimization is also a factor in ambi- guity resolution: listeners prefer the interpretation with shorter dependencies. Statistical parsers make use of features that capture dependency length (e.g. an adjacency feature in Collins (1999), more explicit length features in McDonald et al. (2005) and Eisner and Smith (2005)) and thus learn to favor parses with shorter dependencies. In this paper we attempt to measure the extent to which basic English word order chooses to minimize dependency length, as compared to average depen- dency lengths under other possible grammars. We first present a linear-time algorithm for finding the ordering of a single dependency tree with shortest total dependency length. Then, given that word or- der must also be determined by grammatical rela- tions, we turn to the problem of specifying a gram- mar in terms of constraints over such relations. We wish to find the set of ordering constraints on depen- dency types that minimizes a corpus’s total depen- dency length. Even assuming that dependency trees must be projective, this problem is NP-complete,1 but we find that numerical optimization techniques work well in practice. We reorder unordered depen- dency trees extracted from corpora and compare the results to English in terms of both the resulting de- pendency length and the strings that are produced. The optimized order constraints show a high degree of similarity to English, suggesting that dependency length minimization has influenced the word order choices of basic English grammar. 2 The Dependency Length Principle This idea that dependency length minimization may be a general principle in …

Content truncated to 500 words