TL;DR
This paper introduces Duce, a machine learning system that assists domain experts in building knowledge bases by suggesting high-level domain features. Duce uses a set of six transformation operators to generalize and compress example data, guided by an "oracle" (human expert) to ensure the validity and meaningfulness of newly generated concepts. This approach aims to alleviate the bottleneck of knowledge acquisition in expert system development.
What Problem Does This Paper Address?
Developing expert systems often faces a significant bottleneck: acquiring and structuring expert knowledge. While previous work has shown that generalizing low-level data into high-level rules can ease this burden, a substantial portion of the knowledge still needs to be provided by the expert in structuring the knowledge hierarchy. This paper addresses the challenge of "constructive induction," the process of originating new, meaningful terms or concepts within a domain. The goal is to automate more of the knowledge structuring process, reducing the expert's workload and potentially leading to more efficient and transparent knowledge bases.
Methods
Duce employs a set of six transformation operators to progressively restructure a rule base derived from example data. These operators perform generalizations and feature constructions. The key innovation is the integration of a human "oracle" who validates each proposed transformation. This oracle's agreement ensures that the generated concepts are not only valid but also semantically meaningful, sidestepping the philosophical difficulties of defining "meaningful" computationally.
The six operators are:
- Inter-construction: Combines commonalities from multiple rules to form a new, more general concept.
- Intra-construction: A distributive law for Boolean equations, simplifying rule structures.
- Absorption: Generalizes rules by identifying when the body of one rule is contained within another.
- Identification: Identifies a new concept based on a unique symbol appearing in one rule's body compared to others.
- Dichotomisation: Handles mixed positive and negative examples to create new concepts, similar to decision tree node creation.
- Truncation: Generalizes by dropping conditions from rules, with a precondition that the resulting rule must not be inconsistent with the rest of the rule base.
Duce uses a search algorithm that prioritizes operator applications leading to the largest "symbol reduction" (a measure of rule base compactness), embodying Occam's Razor. This search is guided by the oracle's feedback.
Datasets
The paper demonstrates Duce's capabilities on three distinct domains:
- Simple Animal Taxonomy: Illustrated with a set of animal descriptions (Figure 1).
- Even-Parity Checker: Using examples of 8-variable even-parity (Figure 4).
- King-and-Pawn-on-a7 vs. King-and-Rook (KPa7KR) Chess Endgame: A substantial dataset of around 200,000 positions, reduced to 3196 distinct examples based on 36 primitive board features. This is a real-world expert system domain.
Key Insights and Ideas
- The Oracle as a Meaningfulness Filter: The core idea is that an oracle can effectively guide constructive induction by validating not just the logical correctness but also the semantic relevance of newly generated concepts. This bypasses the need for complex computational definitions of "meaningfulness."
- Transformation-Based Induction: Duce's approach is framed as a form of "deductive transformational programming" applied to inductive inference. Each inductive step is a truth-preserving transformation, validated by the oracle.
- Symbol Reduction as a Guiding Principle: Using symbol reduction as the primary search criterion for operator application effectively applies Occam's Razor, leading to more compact and potentially more understandable rule bases.
- Hierarchical Knowledge Discovery: Duce naturally generates hierarchical knowledge structures, which are crucial for managing complex domains and improving the transparency of expert systems.
- Illustrative Examples are Crucial: For complex domains like chess, presenting illustrative board positions alongside new concepts was indispensable for the oracle to understand and name them.
Key Results
- Animal Taxonomy: Duce successfully generated a more compact and conceptually transparent animal taxonomy, introducing meaningful concepts like "primate" and "bird."
- Even-Parity: Duce was able to learn a hierarchical solution for the even-parity problem, demonstrating its ability to handle functions that are difficult for simpler algorithms.
- KPa7KR Chess Endgame: This was the most significant test. Duce, guided by human experts, transformed a large rule base (118,252 symbols) into a much smaller one (553 rules, 9050 symbols) in a single day, involving 41 oracle-agreed transformations. This is a dramatic reduction compared to the estimated 6 man-months effort for a manually created structure. Duce's solution used a deeper hierarchy (13 levels vs. 9) than the human expert's.
Limitations and Future Work
- Oracle Dependence: The system's effectiveness is heavily reliant on the quality and availability of the oracle. The paper notes that a sparse set of examples led to more oracle rejections, suggesting that the oracle's workload might be inversely related to the completeness of the training data.
- Representation: Duce currently works with propositional logic. The authors suggest extending the techniques to first-order logic and potentially to learning hierarchically definable context-free grammars.
- Search Space: While symbol reduction guides the search, the initial search space can be enormous (e.g., 2^3196 for KPa7KR). Further research is needed to explore more efficient search strategies or pruning techniques.
- Concept Naming: While the oracle names concepts, the process of naming could potentially be further automated or supported.
The paper concludes that Duce offers a promising approach to constructive induction by explicitly integrating human expertise through an oracle, leading to more efficient knowledge acquisition and more transparent, hierarchical knowledge bases.
Summary updated