In the field of Explanation-Based Learning (EBL) during the late 1980s, a significant hurdle remained: the "generalizing to $N$" problem. While systems could generalize variables within a fixed structure, they struggled to generalize the structure itself. This 1987 paper from the AAAI proceedings introduced BAGGER, a landmark system designed to overcome this limitation by learning recursive concepts from a single example.
The Challenge of Structural Recursion
Standard EBL systems of the era were "structure-limited." If a system was shown how to unstack a three-block tower, it would generate a rule specifically for three blocks. It lacked the inductive leap to understand that the same logic applies to a tower of any height ($N$). Humans, by contrast, can observe a repetitive process once and immediately grasp the underlying iteration. BAGGER was developed to provide machines with this same "one-shot" ability to generalize number and iteration by analyzing the logical structure of a task's explanation.
The BAGGER Methodology
BAGGER operates by analyzing predicate calculus proofs—logical explanations of why a specific problem-solving trace worked. Its workflow involves several novel steps to transform a specific proof into a generalized recursive rule:
- Focus Rule Detection: The system identifies "focus rules" within the proof tree that are applied repeatedly.
- Concatenation & Augmentation: Once a repeated pattern is found, BAGGER determines how an arbitrary number of these applications can be chained together, conceptually merging them into an indefinite-length sequence.
- The "Unwinding" Technique: To ensure the learned rule is practical, BAGGER "unwinds" the logic. It traces all preconditions through intermediate states back to the initial state. This ensures that if the plan is initiated, it is guaranteed to succeed without encountering unforeseen obstacles halfway through.
- Rule Instantiation Sequence (RIS): The system uses vectors to represent how variables (such as which block is being moved) change across each of the $N$ steps.
Experimental Evaluation
BAGGER was evaluated using symbolic "toy worlds" that represented complex logical challenges. These domains demonstrated the system's ability to handle both physical and abstract reasoning tasks:
- Blocks World: The system successfully generated general plans for unstacking towers of arbitrary height and building towers to a specific goal height. It proved that a user only needs to verify the initial table setup to know if an $N$-step plan will succeed.
- Digital Circuit Design: BAGGER generalized DeMorgan’s Law from a specific two-gate implementation to a version handling $N$ cascaded gates, showing that the underlying algorithm is domain-independent.
Key Insights and Limitations
A core contribution of BAGGER is the argument that generalizing to $N$ does not require seeing $N$ examples. If a system can explain why a repetition occurs in a single case, it can mathematically extend that explanation to infinity. This creates highly efficient macro-rules where operationality is prioritized—preconditions are expressed in terms that are easy to check at the start of a task.
However, the authors noted limitations. BAGGER is a "passive" learner; it can only generalize what is explicitly present in the provided explanation. It cannot perform a new search to fill gaps if the initial proof is incomplete. For instance, the system failed to learn a general plan for clearing objects that support multiple blocks simultaneously because the training example did not provide a sufficient explanation for handling multiple supports.
Conclusion
BAGGER represented a major step forward in EBL by addressing structural recursion. By forcing all $N$ steps' preconditions to be checkable in the initial state, it created a framework for generating robust, general-purpose plans from minimal data. Future work in this area aimed to incorporate more flexible "unwindable rules" and handle more complex disjunctions within recursive steps.
Summary updated