Paper: Optimizing Grammars for Minimum Dependency Length

ACL ID P07-1024
Title Optimizing Grammars for Minimum Dependency Length
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2007

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.