Quantitative Evaluation of Explanation-Based Learning as an Optimisation Tool for a Large-Scale Natural Language System

Christer Samuelsson, Manny RaynerIJCAI 1991

Introduction

Natural Language Processing (NLP) systems are computationally demanding, often performing exhaustive morphological, syntactic, and semantic analyses for every input. However, human-computer interaction is frequently repetitive, characterized by a limited set of "idioms" or phrasing patterns. This paper explores the use of Explanation-Based Learning (EBL) to optimize the SRI Core Language Engine by "short-circuiting" complex processing for common sentence structures.

Methodology: Explanation-Based Learning

The authors implement EBL as a form of "example-guided partial evaluation." The process involves several key stages:

  1. Rule Extraction: When the system successfully processes a sentence, a "Generalizer" examines the derivation tree—the formal explanation of the sentence's validity—to create a generalized rule.
  2. Multi-Level Operationality: Unlike traditional EBL systems that operate at a single level, this approach learns at three distinct granularities: sentences, noun phrases (NPs), and words. This modularity allows the system to recombine learned "chunks" of language to handle novel but structurally similar inputs.
The EBL rule extraction process, showing how derivation traces are generalized and compiled into learned rules.

Solving the Utility Problem

A significant risk in EBL is the "utility problem": as the library of learned rules grows, the time required to search for a matching rule can exceed the time saved by bypassing standard analysis. To mitigate this, the authors developed specialized indexing schemes:

  • Decision-Tree Indexing: For sentences and NPs, the system uses a decision tree to navigate to the correct rule based on the sequence of lexical categories in the input. This turns a potentially exponential search space into a linear, high-speed dispatch.
  • Key Indexing: A simpler mapping is used for morphological rules.
Decision-tree indexing used to navigate learned rules efficiently based on lexical categories.

Experimental Evaluation

The system was tested using the ATIS (Air Travel Information System) corpus, a standard 1990s benchmark for flight information queries. The training set comprised 1,563 sentences, while a separate, randomly selected set of 100 sentences was used for testing.

Key Results

  • Coverage: From the training set, 680 rules were derived, which successfully covered 90% of the unseen test sentences.
  • Performance Gains: The system achieved a 3x overall speedup with the full rule set. Median "bypass" time using a learned rule was 15 times faster than standard processing.
  • Efficiency: Even when a rule lookup failed, the overhead was minimal (approximately 5%), demonstrating the effectiveness of the indexing strategy.

Conclusion and Future Directions

The study demonstrates that EBL can significantly optimize large-scale NLP systems by exploiting the predictable nature of user interaction. Future work suggests deeper integration of morphology, rule compression techniques, and the potential for incremental, background learning during live interactions. Integrating these symbolic learned rules with modern probabilistic models remains a promising avenue for hybrid NLP architectures.

Summary updated

BibTeX
@inproceedings{samuelsson1991quantitative,
  author = {Christer Samuelsson and Manny Rayner},
  title = {{Quantitative Evaluation of Explanation-Based Learning as an Optimisation Tool for a Large-Scale Natural Language System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure