tailieunhanh - Báo cáo khoa học: "Optimizing Grammars for Minimum Dependency Length"

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 optimal layout of a single tree as well as a numerical method for optimizing a grammar 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 surprisingly well with English word order, suggesting that dependency length minimization has influenced the evolution of English. . | 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 optimal layout of a single tree as well as a numerical method for optimizing a grammar 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 surprisingly well with English word order suggesting that dependency length minimization has influenced the evolution of English. 1 Introduction Dependency approaches to language assume that every 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 numerous psycholinguistic phenomena such as the greater processing difficulty of object relative clauses versus subject relative clauses Gibson 1998 . Dependency length minimization is also a factor in ambiguity resolution listeners prefer the interpretation with shorter dependencies. Statistical parsers make use of features that capture dependency length . an adjacency feature in Collins 1999 more explicit length features in McDonald et al. 2005 and Eisner 184 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 dependency lengths under other possible grammars. We first present a linear-time algorithm for finding the ordering of a single .