Generalization for Explanation-Based Schema Acquisition

Paul O'RorkeAAAI 1984

Presented at AAAI in 1984, this research originates from a foundational era of artificial intelligence focused on moving beyond rigid, hand-coded systems. The goal was to develop "apprentices"—systems capable of learning by observing human experts rather than requiring exhaustive manual programming.

The Knowledge Acquisition Bottleneck

In the early 1980s, AI systems relied heavily on schemata: structured knowledge packets (similar to frames or scripts) that provided instructions for solving specific problem types. However, these systems faced a significant "knowledge acquisition bottleneck." They were unable to generate their own schemata; if a novel situation did not perfectly align with a pre-existing, hand-coded rule, the system could not proceed.

Paul O'Rorke's work addresses this through Explanation-Based Learning (EBL). The central question is: how can a system observe a human expert's solution, understand the underlying logic of why it worked, and generalize that specific instance into a reusable rule for a wide range of future problems?

The MA Apprentice System

The author introduces MA, an experimental apprentice designed for interactive theorem proving. While MA begins with basic logical axioms, it lacks high-level strategic knowledge. To acquire this knowledge, the system follows a three-step process:

  1. Observation: MA observes a human "master" complete a proof that the system cannot solve independently, such as proving the tautology $P \lor \neg P$.
  2. Explanation: The system constructs a dependency graph of the solution. This graph maps how various parameters and logical constraints support the final objective.
  3. Generalization: This is the core contribution of the paper. MA categorizes the constraints within the proof to determine which elements are essential and which are incidental.
An instance of the 'Elimination of Assumption' schema, showing the nested structure of a proof for $P \lor \neg P$.

Generalization via Constraint Taxonomy

The power of the MA system lies in its ability to distinguish "wheat from chaff"—separating essential logical requirements from irrelevant idiosyncrasies. O'Rorke proposes a taxonomy for these constraints:

  • Essential Inter-schema: Connections that link different logical steps.
  • Essential Intra-schema: Internal requirements ensuring a specific step is valid.
  • Optional: Constraints implied by essentials, retained primarily for computational efficiency.
  • Extraneous: Specific details, such as the variable $P$, which are discarded to allow for a general rule using any formula $A$.

By identifying extraneous constraints, the system realizes that a proof for $P \lor \neg P$ is actually a template for any formula $A \lor \neg A$. This allows the system to learn "inferential forms"—macro-operators that combine multiple rules into a single strategic step.

Results and Implications

The MA system successfully demonstrates that specific human-provided proofs can be transformed into general schemata. Beyond acquiring the "how-to" of a proof, the system also learns the "when-to" (heuristics) that recognize when a goal matches a newly acquired macro-rule. This significantly reduces the search space for future automated reasoning.

However, the research also highlights several limitations. The initial implementation remained somewhat rigid; for instance, it might learn to prove $A \lor \neg A$ but fail to apply the same logic if $A$ were provided as a hypothesis. Furthermore, as an "apprentice," the system is entirely dependent on the quality of human examples and cannot yet discover schemata through independent exploration. While the method is demonstrated in the domain of formal logic, extending these principles to less structured real-world domains remains a significant challenge for future research.

Summary updated

BibTeX
@inproceedings{ororke1984generalization,
  author = {Paul O'Rorke},
  title = {{Generalization for Explanation-Based Schema Acquisition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure