A Constructive View of GPSG or How to Make It Work

Stephan Busemann, Christa HauenschildCOLING 1988

TL;DR

This paper argues that the original, axiomatic formulation of Generalized Phrase Structure Grammar (GPSG) is impractical for computational implementation in Natural Language Processing (NLP) systems like machine translation. The authors propose a "constructive" view of GPSG, where syntactic structures are built incrementally rather than filtered from a vast set of possibilities, making it feasible for parsing and generation.

What Problem Does This Paper Address?

Building robust NLP systems, especially for tasks like machine translation (MT), requires highly modular and linguistically grounded grammars. Generalized Phrase Structure Grammar (GPSG) offers a promising framework due to its modularity, allowing for separate handling of universal and language-specific linguistic knowledge. However, the original, "axiomatic" definition of GPSG, as presented in Gazdar et al. (1985), leads to a combinatorial explosion of possible syntactic structures. This makes direct implementation computationally infeasible, as it would require generating and then filtering an enormous number of incorrect trees for every sentence. The paper addresses this gap by proposing a modified, "constructive" approach to GPSG that is computationally tractable for NLP applications.

Methods

The core of the paper is the proposal of a "constructive" view of GPSG, contrasting with the original "axiomatic" approach.

  • Constructive Approach: Instead of generating all possible trees and then filtering them, this approach starts with underspecified local trees derived from ID rules. Information is then incrementally added and unified through the application of GPSG's components (FCRs, FIPs, etc.) to gradually build fully specified, admissible trees. This is akin to building a structure piece by piece rather than trying to find the right piece from a massive pile.
  • Modified Feature Instantiation Principles (FIPs): The authors re-evaluate the application order and function of FIPs.
  • Head Feature Convention (HFC): The need to pre-compute "free feature specification sets" is eliminated. HFC is applied after other principles (FCRs, FFP, CAP) have done their work, ensuring that unspecified HEAD features at the mother node unify with those of the head daughter.
  • Control Agreement Principle (CAP): The original CAP's reliance on semantic types is problematic for a constructive approach. It's reformulated into a purely syntactic "Agreement Principle" (AP) that handles agreement based on feature unification, even in cases with multiple arguments. This allows for agreement to be handled without explicit semantic type distinctions.
  • Order of Application: A specific order for applying GPSG components is proposed: FFP, AP, FCRs, HFC, and finally LP statements. This order is crucial for computational efficiency and correctness.
  • Lexical Specification: The authors suggest using underspecified lexical entries (e.g., word stems) that are then enriched during the parsing/generation process.

Datasets

Not discussed in the paper. The paper focuses on the theoretical and computational aspects of implementing GPSG, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Computational Feasibility: The most significant insight is that the axiomatic GPSG is computationally intractable, but a constructive reformulation can make it practical for NLP systems. This shifts the focus from filtering to building.
  • Reordering FIPs is Crucial: The paper highlights that the order in which GPSG's principles are applied is not just a theoretical detail but a critical factor for efficient implementation. The proposed order (FFP, AP, FCRs, HFC, LP) resolves ordering dilemmas and simplifies processing.
  • Agreement as Syntactic Unification: Reformulating the CAP into a purely syntactic Agreement Principle (AP) based on feature unification is a key step. This decouples agreement from potentially complex semantic type assignments and makes it more amenable to computational handling.
  • Eliminating Combinatorial Explosion: The constructive approach directly tackles the problem of overgeneration by building structures incrementally, thus avoiding the need to generate and then discard vast numbers of invalid trees.

Key Results

The paper doesn't present quantitative results from system evaluations. Instead, its key results are theoretical and methodological:

  • Demonstration of Impracticality: The paper clearly outlines why the axiomatic GPSG is not suitable for direct implementation due to combinatorial explosion and ordering problems.
  • Proposal of a Constructive Framework: A viable alternative "constructive" view of GPSG is presented, which is argued to be suitable for parsing and generation in NLP systems.
  • Resolution of Key Implementation Dilemmas: The proposed constructive approach resolves critical issues like the ordering of CAP and HFC, and the computational burden of feature specification sets.

Limitations and Future Work

  • Loss of Generality in Control: The authors acknowledge that by reformulating the CAP into a purely syntactic AP, some of the generality in handling control phenomena (specifically, the integration of functor-argument structures with semantic types) is sacrificed.
  • Agreement Handling: While the AP handles agreement cases that the original CAP couldn't, the paper notes that the precise way agreement is specified (e.g., using different agr values like agr1, agr2) is an area of ongoing development.
  • Metarules and FSDs: The current constructive version presented does not use metarules or Feature Specification Defaults (FSDs). The authors suggest that metarules could be handled by a preprocessing component, and FSDs might be useful in a simplified form for cases where features remain unspecified even after the structure is complete.
  • Further Development of AP: A more sophisticated version of the AP is mentioned as being under development to handle agreement more comprehensively.
  • Integration with NLP Systems: The paper serves as the linguistic basis for parsing and generation in the Berlin GPSG system, implying that further work would involve the full integration and testing of this constructive approach within such systems.

Summary updated

BibTeX
@inproceedings{busemann1988constructive,
  author = {Stephan Busemann and Christa Hauenschild},
  title = {{A Constructive View of GPSG or How to Make It Work}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1988},
}
Figure