Constraining Learning with Search Control

Jihie Kim, Paul S. RosenbloomICML 1993 · DOI

TL;DR

This paper tackles the "utility problem" in machine learning, where learned rules can sometimes slow down a system more than they speed it up. The authors propose a novel approach that incorporates search control knowledge directly into the learning process, bounding the cost of using learned rules by the cost of the original problem-solving effort, without sacrificing expressiveness.

What Problem Does This Paper Address?

Many learning systems, particularly those using Explanation-Based Learning (EBL) like Soar's chunking mechanism, face the "utility problem." This arises because the process of learning new rules can lead to a situation where the time taken to use these learned rules during problem-solving becomes greater than the time it would have taken without learning. This can happen in two main ways: either individual learned rules are too "expensive" to match (the "expensive chunks" problem), or the system learns so many rules that the sheer volume slows it down (the "average growth effect").

Previous work, like the "unique-attributes" restriction, addressed the expensive chunks problem by limiting the expressiveness of the rule language to guarantee polynomial bounds on matching time. However, this approach often made task encoding more difficult and could reduce the generality of learned rules. This paper focuses on the "expensive chunks" problem and proposes a method that avoids these drawbacks.

Methods

The core of the proposed solution is to make the learning mechanism sensitive to the control knowledge used during problem-solving. Instead of learning a rule based solely on the successful path to a solution, the learning process now incorporates the specific control rules that guided the search for that solution. This control knowledge is integrated into the "explanation" that forms the basis of the learned rule.

Specifically, the authors' approach involves:

  • Incorporating Control Knowledge: When a new rule is learned from a problem-solving trace, the control rules that determined the sequence of operators are included as part of the explanation.
  • Bounding Match Cost by Search Cost: By including this control knowledge, the match process for the learned rule is effectively constrained by the original problem-solving search. This means the cost of using the learned rule is bounded by the cost of the search that generated it, which is typically faster than the match process of a very general rule.
  • Eliminating Indifferent Preferences (for experimental purposes): In the context of the Soar architecture, the paper explores a specific implementation strategy that involves replacing "indifferent preferences" (which allow random choices when no clear preference exists) with explicit default orderings. This ensures that decisions are not arbitrary and leave a trace that can be used for explanation, thus making the learned rules cheaper.

This approach differs from previous methods by not imposing a priori bounds on the match process or restricting the expressiveness of the rule language. Instead, it leverages the existing problem-solving trace and control knowledge to implicitly constrain the learned rules.

Datasets

The paper evaluates its approach using two well-known benchmark problems:

  • The Grid Task: A problem involving finding a path between two points on a grid.
  • The Eight-Puzzle Task: A classic sliding tile puzzle.

These tasks are specifically chosen because they are known to produce "expensive chunks" in standard learning systems. The authors do not introduce new datasets but use these established benchmarks to demonstrate the effectiveness of their method.

Key Insights and Ideas

  • Control Knowledge is Key: The most significant insight is that the how of problem-solving (the control knowledge) is as important as the what (the successful outcome) for efficient learning.
  • Learning from the Journey, Not Just the Destination: By learning from the specific path taken and the decisions made, the system avoids learning overly general rules that might be computationally expensive.
  • Trade-off Between Generality and Efficiency: The paper highlights that while previous methods like unique-attributes achieved efficiency by sacrificing generality, their approach aims to maintain generality while improving efficiency.
  • Solving Expensive Chunks Without Sacrificing Expressiveness: The core contribution is a method that addresses the utility problem without the limitations of restricting rule language expressiveness.
  • Potential for Reduced Overgeneralization: Incorporating search control can also help prevent overgeneralization in learned rules, a subtle but important benefit.

Key Results

The paper presents experimental results on the Grid Task and the Eight-Puzzle Task, comparing their proposed "search-control" method with an "original" (unmodified) Soar system and a "unique-attribute" version.

  • Grid Task:
    • The original Soar showed a significant slowdown after learning (average CPU time increased by a factor of 4.61).
  • Both the search-control and unique-attribute versions showed substantial speedups after learning, with CPU times becoming a small constant value less than before learning. This indicates they solved the expensive chunks problem for this task.
  • The search-control version learned fewer additional rules compared to the unique-attribute version.
  • Eight-Puzzle Task:
    • The original Soar again showed a slowdown after learning.
  • The search-control and unique-attribute versions both eliminated expensive chunks, resulting in faster execution times after learning.
  • The search-control version required significantly fewer additional rules to be learned compared to the unique-attribute version (32 vs. 109), demonstrating a distinct advantage.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Lack of Knowledge Problem: Their approach doesn't fully address situations where decisions are made due to a lack of knowledge (e.g., random choices). In such cases, the learning mechanism still lacks a clear explanation, potentially leading to expensive rules.
  • Reduced Generality: While aiming to mitigate the generality loss of unique-attributes, the search-control approach can still lead to learned rules that are less general because additional conditions are incorporated. These conditions provide efficiency but might eliminate search that would otherwise allow the rules to apply in more circumstances.
  • Knowledge-Level Learning: The approach might increase the difficulty of directing the reconstruction process in knowledge-level learning, requiring new methods like "situated reconstruction."
  • Further Research Needed:
    • Extending experimental results to a wider range of tasks.
  • Quantitative analysis of speedups and generality losses.
  • Theoretical analysis of the method's potential.
  • Addressing the issue of options available at performance time vs. learning time.
  • Re-enabling the use of indifferent preferences to remove the one expressibility limitation imposed in their experimental setup.

Summary updated

BibTeX
@inproceedings{kim1993constraining,
  author = {Jihie Kim and Paul S. Rosenbloom},
  title = {{Constraining Learning with Search Control}},
  booktitle = {International Conference on Machine Learning},
  year = {1993},
  doi = {10.1016/b978-1-55860-307-3.50029-0},
}
Figure