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:
- Observation: MA observes a human "master" complete a proof that the system cannot solve independently, such as proving the tautology $P \lor \neg P$.
- Explanation: The system constructs a dependency graph of the solution. This graph maps how various parameters and logical constraints support the final objective.
- 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.
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