Introduction
In the field of Artificial Intelligence, the mid-1980s marked a significant shift toward Explanation-Based Learning (EBL). Unlike modern data-intensive approaches, EBL aims to enable systems to learn robust, general rules from a single training example. This is achieved by "explaining" why an example satisfies a concept using existing domain knowledge and then generalizing that explanation. This paper introduces EGGS (Explanation Generalization using Global Substitution), a domain-independent algorithm designed to streamline this process. By treating generalization as a global constraint-satisfaction problem, EGGS offers superior efficiency and flexibility compared to contemporary methods like STRIPS or EBG.
The Challenge of Explanation-Based Learning
Early methods for generalizing explanations faced significant computational hurdles. The STRIPS robot planner used an ad-hoc, domain-specific approach. In contrast, the EBG (Explanation-Based Generalization) method proposed by Mitchell et al. relied on a two-pass process: a "regression" step to move constraints backward from the goal, followed by a forward propagation step to determine the generalized result. This redundancy made the process computationally expensive. Mooney and Bennett sought a cleaner, more efficient, and truly domain-independent pipeline to transform specific explanations into reusable general rules.
The EGGS Algorithm: Global Substitution
The core innovation of EGGS lies in its handling of substitutions—the process of replacing specific constants (e.g., Object1) with general variables (e.g., ?x).
Instead of the incremental or two-pass updates seen in previous systems, EGGS treats an explanation as a graph of inference units. It identifies all points where patterns must match (equalities), computes the Most General Unifier (MGU) for each pair, and composes these into a single Global Substitution ($\gamma$). This global mapping is then applied to the entire structure in a single sweep.
This approach is inherently order-independent. EGGS views generalization as "posting and propagating constraints" in all directions simultaneously, ensuring that the structural validity of the proof is maintained while stripping away unnecessary specifics.
Evaluation across Diverse Domains
To validate its domain independence, EGGS was tested on several symbolic logic problems:
- The Cup Example: A benchmark for learning functional requirements (stability, liftability, and being an open vessel).
- LEAP (VLSI Design): Generalizing circuit designs for logical functions.
- STRIPS Robot Planning: Learning macro-operators for robot navigation and object manipulation.
- GENESIS (Narrative Understanding): Learning complex schemas, such as insurance fraud, from short stories.
Key Results and Efficiency
The primary contribution of EGGS is its algorithmic superiority. A complexity analysis reveals that EGGS requires significantly fewer operations than its predecessors:
- STRIPS requires $e \times p$ substitutions (where $e$ is the number of equalities and $p$ is the number of patterns).
- EBG requires $2e$ unifications and $2p$ substitutions.
- EGGS requires only $e$ unifications and $p$ substitutions, plus the one-time cost of composing the global mapping.
Furthermore, the paper demonstrates that the same underlying algorithm can successfully generalize explanations across wildly different fields—from hardware design to human-centric storytelling—proving its robust domain independence.
Conclusion and Future Work
While EGGS represents a major step forward, it operates under the "Perfect Theory" assumption, requiring a complete and correct domain theory. It does not natively handle noisy or incomplete rules. Additionally, the "operationality" problem—deciding the optimal level of generalization (e.g., generalizing "warehouse" to "inanimate object" rather than "building")—remains an area for future research. Nevertheless, EGGS provides a foundational framework for efficient, domain-independent explanation-based learning.
Summary updated