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.
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.
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