Formal Aspects and Parsing Issues of Dependency Theory

Vincenzo Lombardo, Leonardo LesmoACL 1998

TL;DR

This paper introduces a novel lexicalized dependency grammar formalism that can handle long-distance dependencies and free word order. They then present a polynomial-time Earley-style parser for this formalism, demonstrating its practical applicability for syntactic analysis.

What Problem Does This Paper Address?

Dependency theory offers an intuitive way to represent syntactic structure, directly mapping to predicate-argument relationships and handling free word order well. However, formalizing dependency grammars and developing efficient parsers for them has been challenging. Existing formalisms often struggle with long-distance dependencies (like those found in wh-questions or relative clauses) without sacrificing projectivity (a desirable structural property) or resorting to complex, computationally expensive mechanisms. Furthermore, many existing parsers for dependency frameworks are either not formally grounded or lack efficient parsing algorithms. This paper aims to bridge this gap by providing a formal dependency grammar that can handle these complex phenomena and a practical, polynomial-time parser for it.

Methods

The authors propose a lexicalized dependency formalism where grammar rules are anchored to specific words. The core innovation lies in the use of non-lexical categories and a T-stack mechanism within the dependency rules. These elements allow the grammar to represent and manage long-distance dependencies and free word order while maintaining the projectivity of the dependency tree.

The parser is an Earley-type algorithm, adapted to handle the specific structure of dependency rules. It processes the input sentence by building sets of "items," where each item represents a partially recognized subtree of the dependency tree. The algorithm incorporates "pseudo-phases" (pseudocompleter, pseudopredictor, pseudoscanner) to manage the u-indices and u-triples used in the formalism for tracking dependencies and traces. The T-stack plays a crucial role in verifying the satisfaction of these u-triples during parsing.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Non-lexical categories are key: Introducing non-lexical categories, while seemingly a departure from pure lexicalism, is crucial for elegantly handling long-distance dependencies without violating projectivity. This allows the grammar to "skip over" intervening words.
  • T-stack for managing dependencies: The T-stack acts as a sophisticated mechanism to keep track of unsatisfied dependency constraints (u-triples). This is essential for correctly linking distant elements and ensuring the structural integrity of the dependency tree.
  • Earley's algorithm adapts well: The paper demonstrates that the general principles of Earley's parsing algorithm can be successfully adapted to the domain of dependency grammars, even with the added complexity of u-indices and u-triples.
  • Polynomial complexity is achievable: Despite the challenges posed by long-distance dependencies and free word order, the authors show that a polynomial-time parsing algorithm is feasible for their formalism, which is a significant practical advantage.

Key Results

The paper presents a formal dependency grammar that can handle long-distance dependencies and free word order. The primary result is the development of an Earley-style parser for this formalism with a polynomial time complexity of O(n⁷ + ³|D||C|), where n is the sentence length, |D| is the number of dependency relations, and |C| is the number of syntactic categories. While the exponent might seem high, the authors argue that it can be reduced in practice with linguistic constraints and that the formalism offers a significant improvement over NP-complete approaches for non-projective dependency grammars.

Limitations and Future Work

The authors acknowledge that the exponent in the complexity result can be high. They suggest that this could be reduced by using a more restrictive data structure than a set for the T-stack, similar to techniques used in constrained phrase structure formalisms. Future work could involve empirically evaluating the complexity with real-world grammars and exploring optimizations like pre-compiling parse tables for left-corner information. They also mention that the grammar factor in the complexity can be reduced by further restricting long-distance dependencies.

Summary updated

BibTeX
@inproceedings{lombardo1998formal,
  author = {Vincenzo Lombardo and Leonardo Lesmo},
  title = {{Formal Aspects and Parsing Issues of Dependency Theory}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1998},
}
Figure