"Learning by Failing to Explain" presents a paradigm shift for machine learning systems that encounter examples they cannot fully explain. Rather than discarding these failures or falling back on purely statistical methods, the system leverages existing knowledge to "prune" understood components, isolating the specific "mysterious" elements to synthesize new, targeted rules.
The Challenge of Incomplete Theories
In the mid-1980s, Explanation-Based Generalization (EBG) was the dominant paradigm. EBG posits that if a system understands a domain's underlying theory, it can explain a single example and generalize that explanation into a rule. However, EBG requires a "complete" theory. If knowledge is incomplete or the problem (e.g., a VLSI circuit) is computationally intractable, EBG fails entirely. Robert J. Hall argues that a failure to explain is a wasted opportunity. An efficient learner should isolate the unknown—saying, "I understand everything except Step 5"—and extract knowledge from that specific gap.
Methodology: Precedent and Re-analysis
The framework utilizes Design Grammars, representing rules as "Structure X implements Functional Block Y." Two primary techniques are employed to evolve the knowledge base:
- Precedent Analysis: When faced with an unexplainable precedent, the system performs a "maximal partial parse." Using a greedy, hill-climbing algorithm, it matches as much of the example as possible to its current rule library. The remaining unmatched subgraphs are then paired to form a new rule.
- Rule Re-analysis: Learning is recursive. After acquiring a new rule, the system re-examines older, complex rules to see if they can be simplified. This "bootstrapping" allows the system to decompose specific rules into more general ones, even if examples are presented in a sub-optimal order.
Key Insights: The "Mysterious" Remainder
The core philosophy is focusing on the gap between known theory and observed reality. By isolating the "mysterious" part of a circuit, the system avoids the complexity of the entire device and focuses its learning power on the novel sub-component.
The paper also introduces a formal distinction between a role (a mapping of inputs to a set of allowable outputs) and a behavior (a unique mapping). A conjectured rule is guaranteed to be valid in all contexts if the "hole" it fills in a circuit is a behavior, providing a theoretical foundation for rule validation.
Results and Domain Flexibility
The system was tested primarily on digital circuit designs involving multipliers, XOR gates, and multiplexers. It was also successfully applied to a simplified gear domain, where it learned structural rules for gear assemblies based on shaft speed relationships. These qualitative results demonstrate the system's ability to evolve its knowledge base and its flexibility across different functional domains with only minor modifications.
Limitations and Future Work
Despite its successes, the system faces scaling challenges. The current greedy hill-climbing algorithm may miss optimal parses by committing to early matches. Additionally, tracking all paths from the initial graph leads to search-space explosions in large designs. Future work aims to improve search control and expand Design Grammars to handle parameterized structures, such as n-bit adders.
Summary updated