Introduction
In the development of expert systems, knowledge acquisition often involves formalizing human expertise into a logical "theory"—a set of rules used for reasoning. However, these initial theories are frequently "approximate," suffering from over-generality or over-specificity. The challenge of Theory Refinement lies in efficiently correcting these flaws. While pure induction ignores existing knowledge and requires vast amounts of data, and Explanation-Based Learning (EBL) struggles with fundamentally broken theories, there is a need for a hybrid approach. This paper introduces EITHER (Explanation-based and Inductive THeory Extension and Revision), a system designed to surgically identify and repair multiple errors within complex logic-based theories.
Methodology
EITHER treats theory refinement as a diagnostic and repair task, utilizing a combination of deduction, abduction, and induction. The process follows several key stages:
- Deduction and Abduction: The system attempts to prove examples using the existing propositional Horn clause logic. For failed positive examples, EITHER employs "most specific abduction" to identify the minimal set of assumptions required to complete a proof.
- Fault Localization: Instead of broad revisions, EITHER uses failed proofs to pinpoint specific rules or intermediate concepts that are likely erroneous.
- Inductive Repair: Once a failing portion of the theory is isolated, EITHER invokes the ID3 inductive learning algorithm to suggest a fix. To address over-specificity, it may learn new rules or remove constraints. To address over-generality, it adds constraints to existing rules to exclude negative examples.
- Structure Preservation: A primary goal is maintaining the original structure of the expert's knowledge, ensuring that modifications to intermediate concepts do not unnecessarily disrupt the broader reasoning chain.
Experimental Evaluation
The system was evaluated on a real-world biological dataset: DNA Promoter Recognition. The task involves identifying "promoters"—DNA sequences that initiate gene transcription—based on 57 sequential nucleotides. The dataset consists of 106 examples (53 positive, 53 negative). The initial theory provided to EITHER was a modified biological theory that was significantly over-specific, correctly identifying only 4 out of 53 positive examples.
Results and Discussion
The DNA promoter experiments demonstrated the clear advantages of the EITHER system over purely inductive methods.
As shown in the figure above, EITHER consistently outperformed the ID3 algorithm across all training set sizes. With 80 training examples, EITHER achieved an accuracy approximately 5.8% to 10.0% higher than ID3. This "head start" advantage highlights that even an imperfect theory provides a structured search space that focuses the learner on relevant features, drastically improving data efficiency. Statistical analysis using a Student t-test confirmed that EITHER’s performance advantage was significant at the 1% level.
Furthermore, EITHER's ability to perform "surgical" repairs on intermediate concepts proved vital. By fixing specific sub-routines without discarding entire branches of the logic tree, the system preserves the interpretability and integrity of the original expert knowledge.
Conclusion
EITHER represents a significant step forward in theory refinement by successfully integrating EBL and inductive reasoning. While currently limited to propositional logic and sensitive to noise, the system demonstrates that leveraging approximate domain knowledge allows for faster and more accurate learning than starting from a blank slate. Future work will focus on extending the system to predicate calculus and improving its robustness to noisy data.
Summary updated