Quantitative Evaluation of Explanation-Based Learning as an Optimization Tool

IJCAI 1991

TL;DR

This paper explores how Explanation-Based Learning (EBL) can be used to create personalized, faster natural language processing (NLP) systems. By learning from a user's typical phrases, EBL creates specialized rules that bypass much of the standard processing, leading to significant speedups. The authors demonstrate this on a large-scale NLP system, showing a 50% speedup with just 250 learned rules and a 3x speedup with 680 rules.

What Problem Does This Paper Address?

Interacting with natural language systems can be frustratingly slow and rigid. Users often adapt their language to fit the system's limitations, using "typical phrases" that they know the system can handle. This paper tackles the problem of optimizing these large-scale NLP systems to be much faster for these common user inputs. The core challenge is that general-purpose NLP systems perform extensive processing (morphological, syntactic, semantic) for every sentence, even simple ones. This paper proposes a way to bypass much of this overhead for frequently used sentence structures by learning personalized rules.

Methods

The paper applies Explanation-Based Learning (EBL), a machine learning technique, to optimize the SRI Core Language Engine (CLE). The EBL process works as follows:

  • Learning from Examples: Users provide sample sentences. The system analyzes these sentences and their derivations to create "learned rules."
  • Bypassing Normal Processing: These learned rules are designed to directly handle common sentence patterns, skipping the usual, more computationally expensive, morphological, syntactic, and semantic analysis steps.
  • Generalization: EBL generalizes from specific examples to create broader rules. The paper details a multi-level operationality approach, where rules can define sentences in terms of phrases, phrases in terms of words, and words in terms of morphemes.
  • Efficient Indexing: A crucial aspect is ensuring quick access to these learned rules. The paper discusses two indexing methods:
  • Decision-tree indexing: Used for sentence and noun phrase rules, it dispatches on lexical categories.
  • Key indexing: Used for morphological rules, it maps lexical constraints to a sequence of key letters.
  • "Utility Problem" Solution: The paper addresses the "utility problem" (Minton, 1988) – the challenge of efficiently selecting the most useful learned rules – by using domain-specific indexing.

Datasets

  • ATIS Corpus: This large corpus, extracted from real user interactions, was used for both training and testing.
  • Training Set: 1563 sentences.
  • Test Set: 100 sentences.

Key Insights and Ideas

  • Personalization is Key: The most significant speedups come from learning rules tailored to a specific user's typical phrasing. This highlights the value of adaptive NLP systems.
  • EBL as an Optimization Tool: EBL isn't just for learning new knowledge; it's a powerful technique for optimizing existing systems by creating shortcuts.
  • Indexing is Crucial for Speed: The effectiveness of learned rules hinges on how quickly they can be retrieved. The paper's focus on decision-tree and key indexing demonstrates this.
  • Trade-off: Space for Time: EBL trades increased storage space for learned rules for significant reductions in processing time. This is presented as an "economical compromise."
  • "Typical Phrases" Dominate: The observation that users tend to repeat common phrases is the foundation for this optimization strategy.

Key Results

  • Coverage: 680 learned rules derived from the training set covered 90% of the test sentences.
  • Processing Time Reduction:
    • With 680 learned rules, the total processing time was reduced to one-third (a 3x speedup).
  • An overall speedup of 50% was achieved with just 250 learned rules.
  • Look-up Time: Median bypass time for learned rules was 15 times less than normal processing.
  • Overhead: The median overhead for using learned rules was only 5%.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the "utility problem" (selecting the best rules) is complex and relies on effective indexing.
  • The current implementation did not bypass morphological analysis due to the specific architecture of the SRI Menlo Park CLE version.
  • Future Work:
    • Integrating EBL more closely with the target system, allowing normal analysis to use EBL partial results and vice versa.
  • Allowing incremental adaptation of the system by running the learning component as a background process.
  • Incorporating learned rules into probabilistic language models for speech recognition systems.
  • Exploring using learned rules "backwards" for paraphrasing by indexing logical forms.

Summary updated

BibTeX
@inproceedings{1991quantitative,
  title = {{Quantitative Evaluation of Explanation-Based Learning as an Optimization Tool}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure