Bounding the Cost of Learned Rules: A Transformational Approach

AAAI 1996

TL;DR

This paper tackles the "utility problem" in machine learning, where learned rules can sometimes be slower than the original problem-solving process. The authors propose a transformational analysis of the learning process to identify and eliminate sources of this increased cost, aiming to guarantee that learned rules are always at least as efficient as the original problem-solving method.

What Problem Does This Paper Address?

Many machine learning systems, particularly those focused on speed-up learning, face a critical issue known as the "utility problem." This means that after learning new rules or knowledge, the system might actually take longer to solve problems than it did before learning. This defeats the primary goal of learning, which is to improve efficiency. The paper's authors are interested in understanding why this happens and, more importantly, how to guarantee that learned knowledge always speeds up problem-solving, or at least doesn't make it slower. They propose that by analyzing the learning process itself and identifying the specific "costs" introduced, these can be mitigated.

Methods

The core of the paper's approach is a "transformational analysis" of the learning process. The authors decompose learning into a sequence of transformations, starting from a problem-solving episode and ending with a learned rule. This detailed breakdown allows them to pinpoint specific points where computational cost can increase. They identify three primary sources of this increased cost:

  1. Ignoring Search-Control Rules: When learning systems simplify by discarding rules that guide the search through problem spaces, the resulting learned rules can become overly general and perform much more search than necessary, even exponentially more than the original, guided search.
  2. Mismatch between Problem-Solving and Matching Structures: If the way a problem is solved (often hierarchical) is flattened into a linear sequence of conditions for matching a learned rule, the matching process can become inefficient.
  3. Ignoring Optimization in Problem Solving: Systems like Soar use optimizations (e.g., merging equivalent working memory elements). If learning ignores these optimizations, the learned rules can become less efficient.

The paper suggests that by incorporating search control into the explanation structure, making learning sensitive to problem-solving structure, and preprocessing partial instantiations, these sources of expensiveness can be avoided.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Learning isn't always faster: The utility problem is a fundamental challenge in speed-up learning, not just a minor bug.
  • Decomposition is key: Analyzing the learning process as a series of transformations is crucial for understanding where costs are introduced.
  • Three main culprits: The paper clearly articulates three distinct reasons why learned rules can be more expensive: over-generalization due to lost search control, structural mismatches between problem-solving and rule matching, and failure to preserve problem-solving optimizations.
  • Guaranteed efficiency is possible: By addressing these identified sources of expensiveness, it's possible to guarantee that learned rules will not be slower than the original problem-solving process.

Key Results

The paper reports that modifications based on their analysis have successfully eliminated the identified sources of expensiveness in known expensive-rule-learning tasks. While specific quantitative results (e.g., percentage speedup) are not detailed, the qualitative finding is that their approach effectively mitigates the cost increases.

Limitations and Future Work

The authors acknowledge that their work is based on analysis and initial experimental results. Future work includes:

  • Extending experimental validation to a wider range of tasks, including both traditionally expensive and non-expensive rule-learning scenarios.
  • Testing the approach on practical, real-world domains rather than simplified "toy" domains to assess its applicability and allow for more realistic analysis.
  • Identifying any other potential sources of expensiveness that may exist, aiming for a complete set of factors to address.

The ultimate goal is to ensure that the cost of using learned rules is always bounded by the cost of the original problem-solving episode from which they were learned.

Summary updated

BibTeX
@inproceedings{1996bounding,
  title = {{Bounding the Cost of Learned Rules: A Transformational Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure