A Transformational Analysis of the EBL Utility Problem

AAAI 1996

TL;DR

This paper tackles the "utility problem" in Explanation-Based Learning (EBL), where the cost of using learned knowledge can outweigh its benefits. The authors propose analyzing the EBL chunking process as a sequence of transformations to pinpoint the sources of this increased cost, offering a path towards more efficient learning systems.

What Problem Does This Paper Address?

Explanation-Based Learning (EBL) is a powerful machine learning paradigm that learns from experience by explaining why a particular solution worked. The goal is to generalize this explanation into a reusable piece of knowledge, often in the form of a learned rule or "chunk." However, a significant challenge known as the "utility problem" arises: the computational cost of applying these learned chunks can sometimes be higher than the cost of re-deriving the solution from scratch. This paper investigates the root causes of this utility problem specifically within the context of the Soar architecture, which employs a variant of EBL called chunking. The authors aim to understand how the process of transforming a problem-solving episode into a learned chunk can introduce inefficiencies.

Methods

The core of the paper's methodology is a transformational analysis of the chunking process in Soar. Instead of viewing chunking as a monolithic operation, the authors decompose it into a sequence of distinct transformations. By examining each transformation individually, they can identify specific points where computational cost might be introduced. They then propose potential solutions for each identified source of inefficiency.

The key transformations and their associated problems/solutions discussed are:

  • Removing Search Control: When learning rules, Soar (and other EBL systems like PRODIGY/EBL) often ignores search control information from the original problem-solving trace. This can lead to overly general rules that explore vast, inefficient search spaces. The proposed solution is to incorporate search control back into the explanation structure, guiding the learned rule's match process.
  • Eliminating Intermediate Rule Firing (Unifying): In Soar, equivalent working memory elements generated by different rule firings are merged. If this merging process is eliminated during learning, it can lead to a proliferation of redundant partial instantiations, increasing cost. The solution is to preprocess and merge equivalent instantiations during learning.
  • Totally Ordering the Conditions (Linearize): Simplifying the learned rule's structure without preserving the original problem-solving structure can also increase cost. The authors suggest making the learning mechanism sensitive to the problem-solving structure, reflecting it in the learned rule's match algorithm.

Datasets

Not discussed in the paper. The analysis is theoretical and based on the internal workings of the Soar architecture.

Key Insights and Ideas

  • Decomposition is Key: The utility problem isn't a single issue but a collection of inefficiencies arising from specific steps in the learning process. Breaking down chunking into transformations is crucial for pinpointing these issues.
  • Generality vs. Efficiency Trade-off: The pursuit of generality in learned rules, a hallmark of EBL, can directly lead to computational overhead if not managed carefully.
  • Search Control is Vital: Ignoring how a solution was found (i.e., the search path) during learning can result in learned rules that are far less efficient than the original problem-solving trace.
  • Structure Matters: Preserving the structural relationships from the problem-solving episode within the learned rule is important for efficient matching.

Key Results

The paper doesn't present quantitative results from experiments. Instead, it offers a qualitative analysis and proposes potential solutions. The "key results" are the identification of three primary sources of cost increase in EBL chunking: ignoring search control, eliminating intermediate rule firings, and linearizing conditions. For each, they provide a clear explanation of why it increases cost and a conceptual solution. The paper concludes by stating they are working on implementing a variant of chunking that addresses these issues, aiming for learned chunks whose usage cost is bounded by the original problem-solving cost.

Limitations and Future Work

The primary limitation is that the analysis is theoretical and not empirically validated within the paper itself. The authors acknowledge this by stating they are "currently working towards the specification and implementation of a variant of chunking which avoids any of these sources of extra cost." Future work will involve testing this new chunking mechanism to empirically demonstrate its effectiveness in mitigating the utility problem. They also suggest that this transformational analysis approach could be applied to other EBL systems.

Summary updated

BibTeX
@inproceedings{1996transformational,
  title = {{A Transformational Analysis of the EBL Utility Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure