IMEX: Overcoming Intractability in Explanation Based Learning

AAAI 1988

TL;DR

Explanation-Based Learning (EBL) systems struggle to generalize concepts when using compiled knowledge, leading to overly specific definitions. This paper introduces IMEX, a method to incrementally modify explanation structures derived from compiled knowledge, enabling the generation of more general and operational concept definitions.

What Problem Does This Paper Address?

Explanation-Based Learning (EBL) aims to learn general concepts from specific training examples by explaining why the example satisfies the concept. A crucial part of EBL is generalization, where the system derives a concept definition that is not only correct but also "operational" – meaning it can be efficiently applied in future situations.

The challenge arises when EBL systems use "compiled knowledge." This is pre-existing, higher-level knowledge that allows for faster reasoning by skipping intermediate steps. While compiled knowledge makes finding an explanation feasible in complex domains, it often leads to explanations that are too specific. This means the resulting concept definitions are less general than they could be, either by having constants instead of variables or by being a more specific version of a more general rule. This creates a trade-off: compiled knowledge helps with tractability (finding an explanation) but hinders generality (finding the best explanation for generalization).

Methods

The paper introduces a method called IMEX (Incrementally Modify a given Explanation) to address the problem of overly specific concept definitions arising from compiled knowledge. IMEX operates in two main phases:

  1. IMEX Implication Algorithm:
    • Find an initial explanation structure for a goal concept using the domain theory, including compiled knowledge.
  2. Determine the "boundary of operationality" for this structure. This boundary represents the highest line in the explanation tree such that removing rules below it still results in an operational concept definition.
  3. Identify rules that "straddle" this boundary (antecedents below, consequent above).
  4. Attempt to "expand" these straddling rules. Expanding a rule means replacing it with the underlying inference steps that justify it, effectively "uncompiling" it.
  5. If expansion is successful, splice the expanded rule into the explanation structure, recompute the operationality boundary, and repeat the process.
  6. Finally, retract any rules that only support nodes below the operationality boundary. The remaining structure yields a more general concept definition.
  7. IMEX Instantiation Algorithm (briefly sketched):
    • This algorithm handles overly instantiated variables in concept definitions.
  8. After running the Implication Algorithm, for each leaf node, it checks if it's more specific than its corresponding uninstantiated antecedent node.
  9. If so, it traces up the explanation structure, expands compiled rules encountered, and retracts unification constraints to generalize the leaf node. This process continues until sufficient generalization is achieved or the proof structure is fully traced.

The core idea is to use the operationality criterion not just as a filter, but to guide the modification of explanation structures, specifically targeting parts that can be expanded to achieve greater generality.

Datasets

Not discussed in the paper. The paper uses illustrative examples from the domain of "Safe-To-Stack" and plane geometry (isosceles right triangles) to demonstrate the concepts.

Key Insights and Ideas

  • The Trade-off: There's an inherent conflict between using compiled knowledge for tractability (making explanations possible) and achieving maximal generality in concept definitions.
  • Operationality as a Guide: The "boundary of operationality" is a powerful concept. Instead of generating all possible explanations and filtering them, IMEX uses this boundary to intelligently focus on which parts of an explanation structure to modify for better generality.
  • Expansion is Key: "Uncompiling" or expanding compiled rules is the mechanism by which IMEX reveals more general concept definitions that were hidden by the compiled knowledge.
  • Incremental Improvement: IMEX iteratively refines the explanation structure, making it more general with each step, rather than attempting a one-shot solution.

Key Results

The paper doesn't present quantitative results from running IMEX on large datasets. Instead, it demonstrates its effectiveness through detailed examples:

  • Safe-To-Stack Example: IMEX is shown to transform an overly specific definition derived from compiled knowledge into a more general one by expanding compiled rules.
  • Isosceles Right Triangle Example: The paper illustrates how IMEX can overcome overly specific variable instantiations by expanding compiled rules, leading to a more general geometric theorem.

The qualitative finding is that IMEX successfully generates more general and operational concept definitions by strategically expanding compiled knowledge within the explanation structure.

Limitations and Future Work

  • Dependency on Compiled Knowledge Expansion: IMEX relies on the ability to expand compiled knowledge. If justifications for compiled knowledge are not recorded, they must be redetermined, which can be inefficient.
  • Recursive Domain Rules: The presence of recursive domain rules could lead to infinite loops during rule expansion, requiring goal stack checking mechanisms.
  • Operationality Theory Properties: The efficiency and complexity of finding the operationality boundary depend on the properties of the operationality theory used. "Locality" is mentioned as a desirable property for simplifying boundary computation.
  • Multiple Explanation Structures: IMEX currently focuses on generalizing a single initial explanation structure. Future work should investigate methods for finding the most general concept definition by considering multiple distinct explanation structures for a given training instance.
  • Implementation: The authors mention they are in the process of implementing IMEX for route planning, aiming to achieve optimal levels of abstraction.

Summary updated

BibTeX
@inproceedings{1988imex,
  title = {{IMEX: Overcoming Intractability in Explanation Based Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure