In the pursuit of more intelligent systems, a natural assumption is that more knowledge leads to better performance. However, research in automated planning and reasoning has repeatedly uncovered a paradox: as a system learns more "shortcuts" or rules to speed up its search, it often becomes slower.
This phenomenon, known as the utility problem, describes the point where the computational cost of managing and matching learned knowledge outweighs the time saved by using it.
The Paradox of Knowledge Acquisition
Traditional AI systems, such as those described by Andrew R. Golding and Paul S. Rosenbloom in Improving Rule-Based Systems Through Case-Based Reasoning, often use Explanation-Based Learning (EBL) to turn a complex problem-solving experience into a reusable rule or "macro-operator."
Intuitively, these rules should act as "short-circuits." If a system knows a 10-step sequence to achieve a goal, it can save that sequence as a single macro-step. However, Steven Minton and Jaime G. Carbonell noted in Strategies for Learning Search Control Rules: An Explanation-based Approach that every new rule adds to the system's "match cost." Before taking any action, the solver must check its entire library of rules to see which ones apply. When the library grows large, this checking process—the "match phase"—becomes a massive computational bottleneck.
The Match Cost and the Swamping Problem
The utility problem is essentially a trade-off between search reduction and overhead. As Lawrence Holder demonstrated in Empirical Analysis of the General Utility Problem in Machine Learning, performance typically follows a "response curve": it improves as the first few high-value rules are learned, reaches a peak, and then steadily declines as the system is "swamped" by low-utility knowledge.
This "swamping problem" is particularly acute in Case-Based Reasoning (CBR). Barry Smyth and Mark T. Keane argued in Remembering To Forget that a system’s "competence" (the range of problems it can solve) must be balanced against its "efficiency." If a system remembers every single case it encounters, the time spent searching the case library eventually exceeds the time it would take to solve the problem from scratch.
Strategies for Selective Learning
To solve the utility problem, researchers moved away from "learning everything" toward "selective learning." Several mechanisms have been proposed to ensure only high-utility knowledge is retained:
- Utility Filtering: Shaul Markovitch and Paul D. Scott introduced utilization filtering, which uses heuristics to predict whether a learned rule will actually lead to a solution or just cause redundant work.
- Statistical Rigor: The COMPOSER system, developed by Jonathan Gratch and Gerald DeJong, treats the addition of a rule as a statistical hypothesis. In COMPOSER: A Probabilistic Solution to the Utility Problem in Speed-Up Learning, they show that by monitoring a rule's performance over time, a system can mathematically guarantee that a new rule provides a net speedup before committing it to long-term memory.
- Forgetting and Deletion: Systems like FAILSAFE-2 and the work of Yoshiyuki Koseki emphasize "forgetting" strategies. By periodically pruning rules that are rarely used or that have high match costs, the system keeps its knowledge base lean and efficient.
Structural Consolidation
Another approach involves changing the structure of the knowledge itself to reduce the match cost. Instead of a flat list of thousands of specific rules, systems can organize knowledge into hierarchies or recursive structures.
Jude W. Shavlik demonstrated in Acquiring Recursive Concepts with Explanation-Based Learning that a single recursive rule can replace an infinite number of specific rules (e.g., a rule for a 3-step task, a 4-step task, etc.). This consolidation prevents the knowledge base from bloating while maintaining the system's ability to handle complex, multi-step problems. Similarly, James Wogulis and Pat Langley argued in Improving Efficiency by Learning Intermediate Concepts that building a hierarchy of intermediate concepts is often more efficient than "flattening" knowledge into direct but numerous rules.
By shifting the focus from the quantity of learned knowledge to the utility of that knowledge, this research direction ensures that learning remains a tool for acceleration rather than a source of degradation.