A Statistical Theory of Dependency Syntax

Christer SamuelssonCOLING 2000

TL;DR

This paper introduces a novel generative statistical model for dependency syntax, extending Tesnière's classical theory. It tackles the challenge of modeling complex syntactic phenomena like crossing dependencies and discontinuous structures by separating tree generation from surface string realization, offering a more flexible and expressive framework for natural language processing.

What Problem Does This Paper Address?

Traditional dependency grammar, while influential, often struggles to formally capture the full complexity of natural language syntax, particularly phenomena like crossing dependency links (where dependencies "cross over" each other in the linear order of words) and discontinuous nuclei (where parts of a syntactic unit are separated in the sentence). Tesnière's original work, while foundational, lacked a robust mechanism for modeling the realization of syntactic structures into actual surface strings, especially when these structures are non-projective. This paper aims to bridge this gap by proposing a statistically grounded, generative model that can handle these complex syntactic features and provide a probabilistic framework for parsing.

Methods

The core innovation is a two-part generative model:

  1. Tree Generation (P(T)): A top-down stochastic process generates the dependency tree structure. This involves defining probabilities for assigning labels (nuclei) to nodes and for determining the dependency types linking nodes. This part is framed using Gorn's notation for nodes and introduces random variables for label assignment (L), dependency type (D), and the number of children (V).
  2. String Realization (P(S|T)): A bottom-up stochastic process generates the surface string(s) given the dependency tree. This is a key departure, as it allows for non-deterministic string realization.
  3. Projective Dependency Grammars: Initially, a model is presented that generates projective trees (where dependencies don't cross). This involves variables (S) that randomly permute and concatenate child strings with the parent label.
  4. Crossing Dependency Links: To handle non-projectivity, a new variable (M) is introduced. This variable allows dependents to be realized adjacent to any dominating node, not just their immediate parent, enabling crossing dependencies. This is modeled by allowing strings to be passed up to the regent.
  5. Discontinuous Nuclei: The model is further extended to allow discontinuous nuclei by enabling the insertion of child strings anywhere within the regent's label.
  6. String Merging: A more advanced technique allows for the merging of dependent strings with their regent's label, useful for phenomena like French negation.

The overall model is framed as a probabilistic chart parser, drawing inspiration from the Cocke-Kasami-Younger (CKY) algorithm but adapted for dependency structures and probabilistic inference.

Datasets

Not discussed in the paper. The paper focuses on the theoretical framework and computational rendering, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Separation of Tree and String: The most significant insight is the explicit separation of dependency tree generation from surface string realization. This allows for greater flexibility in modeling syntax, particularly for non-projective structures and word order variations.
  • Stochastic String Realization: Treating string realization as a stochastic process, rather than a deterministic one, is crucial for capturing the variability and ambiguity in natural language. This allows for multiple surface realizations of the same underlying dependency structure.
  • Modeling Non-Projectivity: The introduction of the 'M' variable to handle string passing upwards in the tree is a novel way to model crossing dependencies, which are common in many languages.
  • Generative Framework: The paper provides a fully generative statistical model, which is essential for probabilistic parsing and for understanding the likelihood of different syntactic analyses.
  • Extending Tesnière: The work successfully extends Tesnière's classical dependency grammar by providing a formal, statistical, and computationally tractable framework that can handle more complex syntactic phenomena.

Key Results

The paper presents a theoretical framework and outlines a computational rendering as a probabilistic chart parser. While specific quantitative results (e.g., parsing accuracy, speedup) are not detailed, the key result is the development of a more expressive and flexible statistical model for dependency syntax capable of handling:

  • Crossing dependency links.
  • Discontinuous nuclei.
  • String merging.

The computational rendering is described as an agenda-driven chart parser implemented in Prolog, drawing on the CKY algorithm and utilizing set/bag operations.

Limitations and Future Work

  • Sparse Data: The paper acknowledges the issue of sparse data and mentions generalizing over actual strings to their dependency types or word classes as a strategy. However, the effectiveness of this generalization is not empirically demonstrated.
  • Computational Rendering Details: While a computational rendering is described, the paper focuses more on the theoretical underpinnings and less on the empirical performance or detailed evaluation of the parser.
  • Specific Language Phenomena: While the model is designed to handle phenomena like French negation, the paper doesn't provide extensive examples or evaluations for specific linguistic challenges beyond illustrative cases.
  • Future Work: The authors suggest that conditioning random variables on arbitrary portions of the partial tree could be explored using techniques like maximum-entropy or decision-tree models. They also note that the expressive power of the grammar depends on the string probabilities, implying that further refinement of these probabilities could lead to more powerful models. The potential for applying pruning techniques to improve parsing efficiency is also highlighted.

Summary updated

BibTeX
@inproceedings{samuelsson2000statistical,
  author = {Christer Samuelsson},
  title = {{A Statistical Theory of Dependency Syntax}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure