A Parser for Portable NL Interfaces Using Graph-Unification-Based Grammars

Kent WittenburgAAAI 1986

Introduction

In the mid-1980s, the development of natural language (NL) interfaces was hindered by a fundamental trade-off: portability versus sophistication. Developers typically chose between semantically-based grammars—which are easy to build for specific domains but difficult to port—and syntactically-based grammars, which offer portability but suffer from massive syntactic ambiguity. General-purpose English grammars can produce hundreds or even thousands of valid parses for a single sentence, leading to a "combinatorial explosion" that makes exhaustive search impractical for interactive systems.

This paper introduces Astro, a best-first chart parser designed for the "Lingo" NL interface project. Astro navigates this complexity by combining Combinatory Categorial Grammars (CCG) with a heuristic, agenda-driven search, demonstrating that a linguistically principled parser can be fast enough for real-world applications.

The Astro Architecture

The Astro parser is built on several key technical pillars designed to balance linguistic power with computational efficiency.

Combinatory Categorial Grammar (CCG)

Unlike standard phrase-structure grammars, CCG handles complex linguistic phenomena—such as coordination and "wh-questions"—elegantly using a small set of rules. This allows the grammar to remain compact while maintaining high expressive power.

Figure 1: A structural representation of syntactic categories and their relations within the CCG framework used by Astro.

Best-First Chart Parsing

To avoid the pitfalls of exhaustive search, Astro employs a prioritized agenda. Instead of exploring every possible rule application (breadth-first) or following a single path to completion (depth-first), the system always executes the "best" action first based on a heuristic score. This allows the parser to focus on the most likely interpretations while suspending less promising paths.

Efficient Graph Unification

Astro represents linguistic features as graphs. Since full graph unification is computationally expensive, the system uses a "porous," non-destructive check function. This preliminary test determines if a rule might succeed before committing to the resource-intensive process of full unification.

Optimization Techniques

Beyond its core architecture, Astro introduces specific mechanisms to prune the search space and improve performance.

Heuristic Scoring

The agenda is ordered by a heuristic function that incorporates several factors:

  • Span Length: Favoring longer phrases that cover more of the input.
  • Rule Priorities: Intrinsic weights assigned to specific grammar rules.
  • Statistical Likelihood: Incorporating the probability of certain word senses.

Extended Sister Relation

Unary rules (rules with a single child) are a common source of inefficiency because they can trigger in many contexts. Astro utilizes a novel "extended sister relation" to prune these "promiscuous" rules. By pre-calculating which types of phrases are permitted to appear adjacent to one another, the system can discard useless unary rule applications before they clutter the chart.

Evaluation and Insights

While the paper predates modern benchmarks like the Penn Treebank, it validates its approach through internal testing within the MCC Lingo project and references to earlier "Wizard-of-Oz" experiments that highlighted the extreme ambiguity of natural language.

The author reports an "overwhelming performance improvement" when transitioning from a non-selective, bottom-up design to the best-first approach. Furthermore, the parser's flexibility allows it to be "toggled" between finding a single "best" parse for end-users and exhaustive enumeration for grammar developers.

Conclusion and Future Work

Astro demonstrates that the agenda-driven control structure is a critical component for practical NL interfaces. However, several challenges remain. The current heuristic functions are hand-tuned through trial and error, suggesting a need for automated "credit assignment" schemes where the system learns to adjust its weights based on performance. Additionally, future work will explore better integration of local versus global context and real-time "cascading" designs that feed parsing results directly into semantic and pragmatic components.

Summary updated

BibTeX
@inproceedings{wittenburg1986parser,
  author = {Kent Wittenburg},
  title = {{A Parser for Portable NL Interfaces Using Graph-Unification-Based Grammars}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure