Minimal-length linearizations for mildly context-sensitive dependency trees

Y. Albert Park, Roger LevyNAACL 2009 · OpenReview

TL;DR

This paper introduces the first polynomial-time algorithm for finding the shortest possible linearizations of dependency trees, even when they allow for "mildly context-sensitive" structures (like crossing dependencies). They show that while mild context-sensitivity offers little benefit over purely projective structures for minimizing dependency length, German word order is significantly further from optimal than English, suggesting deeper morphological or processing differences.

What Problem Does This Paper Address?

Natural language sentences have a hierarchical dependency structure (which word modifies which) and a linear word order. The relationship between these two is not arbitrary; linguistic theories suggest constraints on how dependency structures can be linearized. One key constraint is "mild context-sensitivity," which allows for a limited number of "crossing" dependencies (where a modifier appears outside the span of its head). Another is the psycholinguistic observation that shorter dependency lengths (the distance between a head and its dependent) are generally preferred, likely due to processing ease.

The challenge is to find the absolute shortest possible linearizations of a dependency tree, considering these mild context-sensitivity constraints. Previous work either focused on purely projective (non-crossing) trees or didn't efficiently handle the complexity introduced by mild context-sensitivity. This paper aims to bridge that gap by developing an efficient algorithm and exploring the implications for real-world languages.

Methods

The core contribution is a novel dynamic programming algorithm designed to find minimal-length linearizations of dependency trees under mild context-sensitivity constraints.

  • Factorization of Dependency Length: The authors develop a new way to break down the total dependency length of a sentence. For projective trees, this is relatively straightforward. For mildly context-sensitive trees, they introduce a more complex factorization that accounts for the "gaps" created by crossing dependencies. This factorization is crucial for making the problem computationally tractable.
  • Dynamic Programming: Building on this factorization, they employ dynamic programming. This involves recursively computing optimal linearizations for subtrees and combining them to find the overall optimal linearization for the entire sentence.
  • Algorithmic Optimizations: The paper details several key optimizations to their initial dynamic programming approach:
  • Constraint on Component Placement: They prove that for optimal linearizations, the components of a split dependent must lie on opposite sides of their head. This significantly prunes the search space.
  • Status Set Reduction: They refine the information that needs to be stored at each node during dynamic programming, reducing the number of "status sets" (combinations of dependency information) that need to be considered.
  • Rank-Based Ordering: They introduce a "rank value" for components and prove that within a component, they must be ordered by increasing rank value. This replaces a factorial search with a sorting step.

These optimizations transform an algorithm that was computationally infeasible for even moderately sized sentences into one that is efficient enough for practical use on typical treebank data.

Datasets

The authors evaluated their algorithm on:

  • English: Sentences from the Wall Street Journal (WSJ) portion of the Penn Treebank.
  • German: Sentences from the NEGRA corpus.

They extracted two types of dependency trees for each sentence:

  • Surface Trees: These are inherently projective (no crossing dependencies).
  • Deep Trees: These account for discontinuous dependents (e.g., fronted elements like "who" in relative clauses) and can exhibit crossing dependencies.

Key Insights and Ideas

  • The Power of Factorization: The ability to decompose the complex problem of minimizing dependency length in mildly context-sensitive trees into manageable subproblems via a novel factorization is a key theoretical contribution.
  • Mild Context-Sensitivity's Limited Benefit: Surprisingly, the optimal dependency length for gap-degree 1 (a common form of mild context-sensitivity) is very close to, and often indistinguishable from, the optimal length for purely projective trees, even for longer sentences. This suggests that projectivity might be sufficient for achieving near-optimal dependency length in many cases.
  • German vs. English Word Order: The most striking empirical finding is the significant difference between English and German. German observed linearizations are much closer to random orderings and further from optimal than English linearizations. This highlights potential differences in morphological richness, word order flexibility, or processing strategies between the two languages.
  • Psycholinguistic Resonance: The finding that English speakers' word order is closer to optimal (and thus potentially less effortful) aligns with psycholinguistic theories suggesting that long-distance dependencies are more taxing in English.

Key Results

  • Efficient Algorithm: The optimized algorithm achieves polynomial time complexity (specifically, O(nm² log m(2m²)m)), making it feasible to compute minimal dependency lengths for typical sentences. Figure 7 shows a dramatic speedup compared to the unoptimized version.
  • English vs. German Comparison:
    • Observed dependency lengths are consistently lower than random orderings (even with projectivity constraints) for both languages.
  • Relaxing the projectivity constraint (allowing crossing dependencies) leads to slightly lower optimal dependency lengths.
  • English observed linearizations are significantly closer to optimal and further from random than German observed linearizations.
  • Surface vs. Deep Dependencies: Analyses using surface and deep dependency trees yield generally similar conclusions, though minimal lengths for deep dependencies are slightly higher for English and slightly lower for German.

Limitations and Future Work

  • Computational Complexity: While polynomial, the complexity is still exponential in the arity (maximum number of dependencies per word). However, the authors note that most sentences in treebanks have low arity, making the algorithm practical.
  • Gap Degree: The paper focuses on gap-degree 1. Generalizing the algorithm to higher gap degrees would be a natural extension, though it would increase complexity.
  • Cross-Lingual Differences: The significant difference between English and German observed linearizations warrants further investigation into the underlying linguistic and psycholinguistic factors. The authors suggest this might be related to German's richer morphology and greater word order variability.
  • Future Work: The authors suggest exploring the implications of their findings for language acquisition, processing models, and the design of natural language processing systems.

Summary updated

Abstract

The extent to which the organization of natural language grammars reflects a drive to minimize dependency length remains little explored. We present the first algorithm polynomial-time in sentence length for obtaining the minimal-length linearization of a dependency 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 improve 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 German. We find in both languages that analyses of surface and deep dependencies yield highly similar results, and that mild context-sensitivity affords very little reduction in minimal dependency length over fully projective linearizations; but that observed linearizations in German are much closer to random and farther from minimal-length linearizations than in English.
BibTeX
@inproceedings{park2009minimal,
  author = {Y. Albert Park and Roger Levy},
  title = {{Minimal-length linearizations for mildly context-sensitive dependency trees}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=r1WeTMZdWH},
}
Figure