Minimal-length linearizations for mildly context-sensitive dependency trees

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 335–343, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Minimal-length linearizations for mildly context-sensitive dependency trees Y. Albert Park Department of Computer Science and Engineering 9500 Gilman Drive La Jolla, CA 92037-404, USA yapark@ucsd.edu Roger Levy Department of Linguistics 9500 Gilman Drive La Jolla, CA 92037-108, USA rlevy@ling.ucsd.edu Abstract The extent to which the organization of nat- ural language grammars reflects a drive to minimize dependency length remains little explored. We present the first algorithm polynomial-time in sentence length for obtain- ing the minimal-length linearization of a de- pendency tree subject to constraints of mild context sensitivity. For the minimally context- sensitive case of gap-degree 1 dependency trees, we prove several properties of minimal- length linearizations which allow us to im- prove the efficiency of our algorithm to the point that it can be used on most naturally- occurring sentences. We use the algorithm to compare optimal, observed, and random sentence dependency length for both surface and deep dependencies in English and Ger- man. We find in both languages that anal- yses of surface and deep dependencies yield highly similar results, and that mild context- sensitivity affords very little reduction in min- imal dependency length over fully projective linearizations; but that observed linearizations in German are much closer to random and far- ther from minimal-length linearizations than in English. 1 Introduction This paper takes up the relationship between two hallmarks of natural language dependency structure. First, there seem to be qualitative constraints on the relationship between the dependency structure of the words in a sentence and their linear ordering. In par- ticular, this relationship seems to be such that any natural language sentence, together with its depen- dency structure, should be generable by a mildly context-sensitivity formalism (Joshi, 1985), in par- ticular a linear context-free rewrite system in which the right-hand side of each rule has a distinguished head (Pollard, 1984; Vijay-Shanker et al., 1987; Kuhlmann, 2007). This condition places strong con- straints on the linear contiguity of word-word de- pendency relations, such that only limited classes of crossing context-free dependency structures may be admitted. The second constraint is a softer preference for words in a dependency relation to occur in close proximity to one another. This constraint is perhaps best documented in psycholinguistic work suggest- ing that large distances between governors and de- pendents induce processing difficulty in both com- prehension and production (Hawkins, 1994, 2004; Gibson, 1998; Jaeger, 2006). Intuitively there is a relationship between these two constraints: con- sistently large dependency distances in a sentence would require many crossing dependencies. How- ever, it is not the case that crossing dependencies always mean longer dependency distances. For ex- ample, (1) below has no crossing dependencies, but the distance between arrived and its dependent Yes- terday is large. The overall dependency length of the sentence can be reduced by extraposing the relative clause who was wearing a hat, resulting in (2), in …

Content truncated to 500 words