Methods for Obtaining Corresponding Phrase Structure and Dependency Grammars

Jane J. RobinsonCOLING 1967

TL;DR

This paper introduces novel methods for converting between phrase structure grammars (PSGs) and dependency grammars (DGs), enabling researchers to leverage the strengths of both formalisms. The work addresses the need for systematic correspondences between these grammar types, facilitating experimentation and theoretical exploration in computational linguistics.

What Problem Does This Paper Address?

Linguists and computer scientists often work with different grammatical formalisms, primarily phrase structure grammars (PSGs) and dependency grammars (DGs). While both can represent the structure of sentences, they do so in fundamentally different ways. PSGs, like those formalized by Chomsky, represent hierarchical constituent structures, while DGs represent relationships between words as directed links. This difference can make it challenging to translate insights or algorithms developed in one framework to the other. The paper addresses the gap by providing concrete methods for converting a PSG into a corresponding DG and vice versa, ensuring that the generated sentences and their structural representations remain systematically related. This allows for greater flexibility in choosing the most appropriate grammar formalism for a given task or for exploring theoretical questions about linguistic structure.

Methods

The paper presents two primary methods for converting between grammars:

  • PSG to DG Conversion: This method takes a simple, context-free PSG (SPG) and converts it into a corresponding dependency grammar (DG). The process involves augmenting the SPG rules by "starring" categories on the right-hand side, which helps to identify key elements for dependency relations. A Table of Substitutes (TS) and an Intermediate Rule List (IRL) are constructed to map PSG categories to DG elements. The core of the conversion involves systematically transforming the augmented SPG rules into dependency rules, often involving the assignment of coefficients to represent the strength or order of dependencies.
  • DG to SPG Conversion: This method converts a DG into a corresponding SPG. It begins with an augmentation step for the DG rules, assigning coefficients and subscripts to dependents to distinguish them. This augmented DG is then transformed into an Intermediate Rule List (IRL), which is subsequently used to construct the SPG's rewriting rules. The process aims to create an SPG that is "strongly equivalent" to the original DG, meaning they generate the same language and assign corresponding structures.

A key aspect of both methods is the concept of "augmentation," where rules are modified (e.g., by starring categories or assigning coefficients) to facilitate the conversion process. The paper also discusses the importance of constraints on these augmentations to avoid issues like "structure sensitivity" in the resulting grammars.

Datasets

Not discussed in the paper. The paper focuses on theoretical methods and demonstrates them with abstract grammar examples (SPG1, DG1, SPG2, DG2, etc.) rather than real-world datasets.

Key Insights and Ideas

  • Systematic Correspondence: The paper establishes that it's possible to create systematically corresponding grammars in both PSG and DG formalisms. This means that the structures assigned to a string by one grammar will have a predictable relationship to the structures assigned by its converted counterpart.
  • Asymmetrical Relationship: The correspondence between PSG and DG structures is often asymmetrical. A complete subtree in a DG might correspond to a complete subtree in a PSG, but a complete PSG subtree might only correspond to a connected (potentially incomplete) DG subtree.
  • Structure Sensitivity: A crucial concept introduced is "structure sensitivity" in DGs. This occurs when a DG's rules are so restrictive or overlapping that conflating them into a single rule would lead to generating incorrect strings or losing essential structural information. This property can arise from the choices made during the conversion process.
  • Linguistic Motivation for Constraints: The paper argues for imposing constraints on grammars (both SPG and DG) to avoid structure sensitivity and ensure cleaner conversions. These constraints are motivated by linguistic considerations and aim to simplify the resulting grammars.
  • Weak Equivalence: Both PSG and DG systems are shown to be weakly equivalent, meaning they can generate the same set of context-free languages. This theoretical foundation underpins the possibility of conversion.

Key Results

The paper successfully demonstrates methods for converting between phrase structure and dependency grammars. It provides detailed step-by-step procedures for both PSG-to-DG and DG-to-SPG conversions, illustrated with abstract grammar examples. The authors show how these methods can produce grammars that are systematically related, and under certain constraints, even "substantively equivalent" or "strongly equivalent." The work highlights the potential for "structure sensitivity" in DGs and discusses how to manage or avoid it through careful augmentation and rule design.

Limitations and Future Work

  • Structure Sensitivity: The paper acknowledges that structure sensitivity can arise in the derived DG, which might be linguistically undesirable. While methods are proposed to manage this, it remains a complex issue.
  • Augmentation Complexity: Augmenting SPGs, in particular, is noted as a more difficult case, with potential for infinite loops or loss of essential information if not handled carefully. The paper suggests restrictions on augmentation policies.
  • "Head" Categories: The concept of "head" categories in SPGs is introduced as a way to simplify DG generation and avoid structure sensitivity. This suggests that identifying and utilizing head categories is a promising direction for cleaner conversions.
  • Linguistic Justification: While the methods are presented, the paper hints at the broader linguistic implications and the need for criteria for establishing categories, which is a significant open question. The authors suggest that the ability to avoid structure sensitivity could be a criterion for assigning government in dependency analysis.
  • Transformational Grammars: The work is framed within the context of transformational grammars, suggesting that these conversion methods are relevant for building base components of such systems. Future work could explore how these conversions interact with transformational rules themselves.

Summary updated

BibTeX
@inproceedings{robinson1967methods,
  author = {Jane J. Robinson},
  title = {{Methods for Obtaining Corresponding Phrase Structure and Dependency Grammars}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1967},
}
Figure