Derivational Analogy and Its Role in Problem Solving

Jaime G. CarbonellAAAI 1983

Introduction

In his seminal 1983 paper, Jaime G. Carbonell introduced Derivational Analogy, a concept that fundamentally reshaped Case-Based Reasoning (CBR). Carbonell argued that for an artificial intelligence to truly learn from experience, it must move beyond merely storing the final solutions to past problems. Instead, it should record and "replay" the underlying reasoning process—the derivation—that led to those solutions.

The Problem of Solution Transformation

Prior to this work, AI problem solving typically oscillated between two extremes: "weak methods" like heuristic search, which start from scratch for every new task, and "plan instantiation," which relies on rigid, pre-defined templates. Carbonell’s earlier research explored "solution transformation," where a system attempts to adapt a completed past solution to a new problem.

However, solution transformation suffers from a critical flaw: it ignores the "why." Without understanding the justifications for specific steps, a system cannot intelligently modify them when the environment changes. For instance, while the final code for a Quicksort algorithm in PASCAL and LISP looks entirely different, the underlying logic—the derivation—is nearly identical. Derivational analogy seeks to capture this shared logic.

The Derivational Analogy Framework

Derivational analogy stores the "derivation history" of a problem-solving episode. A complete derivation includes:

  1. Subgoal Structure: The hierarchy of goals pursued.
  2. Decisions and Justifications: Every choice made, including the reasons for selecting one path and rejecting alternatives.
  3. Failed Paths: A record of unsuccessful attempts and their causes, providing "negative expertise" to prune future search spaces.
  4. Dependencies: Links showing how decisions rely on specific problem facts or prior choices.

When faced with a new problem, the system employs a "Replay" Algorithm. It walks through the old reasoning, checking if the original justifications still hold. If they do, the step is copied; if not, the system explores alternatives or initiates a new search, effectively "fixing" the analogy at the point of divergence.

Integrating Problem-Solving Strategies

Carbonell posits that a robust general inference engine should not rely on a single method but rather integrate multiple strategies. Derivational analogy serves as a powerful bridge between general plans and specific historical cases.

Figure 1: A conceptual model of the relationship between various problem-solving methods and a new problem.

As shown in Figure 1, a new problem can be addressed through a spectrum of techniques ranging from general abstractions to specific past experiences:

  • (a) Specific Plans: Direct application of specialized templates.
  • (b) Old Problems Solved: Direct analogy to previous solutions.
  • (c) General Plans: High-level abstractions.
  • (d) Weak Methods: General-purpose search when no specific experience is available.

Derivational analogy enhances this ecosystem by allowing the system to re-evaluate decision points across these different levels of abstraction, making the problem solver more robust and efficient than systems relying on search or rigid templates alone.

Conclusion

By focusing on the reasoning process rather than the final artifact, derivational analogy provides a more accurate model of human expertise. It allows for cross-domain transfer and efficient learning from both success and failure. While it introduces bookkeeping overhead, the resulting system is far more capable of handling novel, complex problems by intelligently leveraging its past "thought processes."

Summary updated

BibTeX
@inproceedings{carbonell1983derivational,
  author = {Jaime G. Carbonell},
  title = {{Derivational Analogy and Its Role in Problem Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure