Fast Parsing Using Pruning and Grammar Specialization

Manny Rayner, David M. CarterACL 1996 · DOI

Abstract

General-purpose natural language parsers often struggle with efficiency when applied to specific domains due to the vast search space of theoretically valid but contextually irrelevant interpretations. This paper describes a hybrid approach developed at SRI International that combines statistical constituent pruning with Explanation-Based Learning (EBL) to specialize general grammars. By selectively creating domain-specific macro-rules and pruning unlikely phrasal constituents, the system achieves a 9x speedup in parsing time while maintaining high accuracy, reducing coverage loss to approximately 5%.

Introduction

In computational linguistics, a fundamental trade-off exists between grammar generality and parsing efficiency. While general grammars provide broad linguistic coverage, they often generate numerous "garden path" interpretations in specific contexts, leading to significant computational waste. Traditionally, this was addressed by manually authoring narrow, domain-specific grammars—a process that is both labor-intensive and lacks scalability. This research explores automated methods to adapt massive, general-purpose grammars for efficient use in specialized domains, such as the Air Travel Information System (ATIS).

Methodology

The proposed solution employs two complementary techniques:

1. Statistical Constituent Pruning

This bottom-up approach filters out unlikely phrases (edges in a parsing chart) before they can propagate through the parser. Using statistical scores from a training corpus, the system calculates the probability that a constituent belongs in the final correct parse. A key innovation is the "minimum score" heuristic, which assumes maximal dependence among features; if any single feature indicates a low probability, the constituent is pruned. Path connectivity is also used to eliminate constituents that cannot form part of a complete sentence span.

2. Grammar Specialization via EBL

Explanation-Based Learning (EBL) is used to analyze training parses and "chunk" frequently occurring rule sequences into single macro-rules. The authors introduced a refined "New scheme" that distinguishes between simple phrasal rules (e.g., basic noun phrases) and complex non-phrasal rules. By only specializing the latter, the system avoids the rule explosion seen in previous EBL attempts.

Comparison of rule count and coverage loss between the old and new EBL schemes.

As shown in the figure above, the "New scheme" significantly reduces the number of specialized rules while simultaneously lowering the coverage loss compared to the "Old scheme."

Experimental Results

The system was evaluated on the ATIS corpus, consisting of 16,000 utterances. A linguistics student provided a gold-standard set of parses over a 2.5-month period to facilitate training.

The combination of pruning and specialization resulted in a multiplicative performance gain. While pruning and EBL each provided a roughly 3x speedup independently, their combined application yielded a 9x improvement over the baseline general parser.

Breakdown of parsing time (in seconds) for different system configurations.

The timing breakdown illustrates the dramatic reduction in total parsing time, particularly in the "Full parsing" stage, when both EBL (E+) and pruning (P+) are active. The total time drops from 16.85 seconds in the baseline (E-/P-) to just 1.86 seconds in the fully optimized configuration. Furthermore, the "New scheme" for EBL reduced coverage loss to 5%, a significant improvement over the 10–12% loss observed in earlier methods.

Conclusion

By integrating top-down grammar specialization with bottom-up statistical pruning, researchers have demonstrated that general-purpose grammars can be made highly efficient for domain-specific tasks. Future work aims to further interleave pruning into the parsing process and develop robust parsing techniques to handle ungrammatical or out-of-vocabulary inputs.

Summary updated

BibTeX
@inproceedings{rayner1996fast,
  author = {Manny Rayner and David M. Carter},
  title = {{Fast Parsing Using Pruning and Grammar Specialization}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1996},
  doi = {10.3115/981863.981893},
}
Figure