Duce, An Oracle-based Approach to Constructive Induction

Stephen H. Muggleton

Abstract

Constructive induction—the discovery of new, high-level descriptors from primitive data—is a critical component of automated knowledge acquisition. This paper describes Duce, a system that employs six logical transformation operators to restructure propositional rule sets. By utilizing a human "oracle" to validate and name newly generated concepts, Duce bridges the gap between mathematical compression and human-understandable semantics. Experimental results in domains such as chess endgames demonstrate that Duce can achieve massive symbol reduction, producing hierarchies comparable to those manually crafted by experts.

Introduction

In the development of expert systems, the "knowledge acquisition bottleneck" refers to the difficulty experts face when articulating the underlying structure of their domain knowledge. While experts are proficient in their tasks, they often lack the meta-knowledge required to design the sub-problem hierarchies necessary for machine learning. Duce addresses this challenge by automating the discovery of these hierarchies. Unlike previous statistical clustering methods that often produced unintuitive groupings, Duce prioritizes "conceptual transparency," ensuring that discovered terms are both mathematically efficient and humanly meaningful.

Methodology

Duce operates on rule sets expressed in propositional logic. The system's search algorithm is guided by the principle of Occam’s Razor, specifically seeking transformations that maximize "symbol reduction" to create the most compact representation possible.

The core of the system consists of six transformation operators:

  1. Inter-construction: Identifies common features across different rules to create new intermediate concepts.
  2. Intra-construction: Simplifies rules with the same head using the distributive law.
  3. Absorption: Identifies when one rule is a subset of another.
  4. Identification: Generalizes terms based on shared symbols.
  5. Dichotomisation: Creates decision-tree-like structures from mixed positive and negative examples.
  6. Truncation: Generalizes by removing unnecessary conditions.

Crucially, Duce is an oracle-based system. When the machine identifies a potential new concept through these transformations, it queries a human expert. The oracle must either name the concept (validating its semantic utility) or reject it. This division of labor allows the machine to handle the syntax of compression while the human provides the semantic grounding.

Interactive session showing Duce's induction process and oracle queries.

Experimental Evaluation

Duce was evaluated across three distinct domains to test its versatility and efficiency:

  • Animal Taxonomy: Duce successfully "discovered" biological concepts like "bird" and "primate" from raw physical descriptions, demonstrating its ability to align with existing human knowledge.
  • 8-Variable Even-Parity: In this synthetic dataset, Duce's hierarchical approach efficiently solved parity problems that are typically difficult for "flat" learning algorithms, proving the power of multi-level descriptions.
  • Chess Endgame (KPa7KR): In a real-world benchmark involving ~200,000 positions, Duce compressed a rule set of 118,252 symbols down to just 9,050 symbols within a single day.
Example of rule transformation leading to symbol reduction via truncation.

Key Insights and Results

The results from the chess endgame task are particularly notable. The structure Duce generated was comparable to a solution manually crafted by experts Shapiro and Kopec, which had originally taken six man-months of effort. Duce achieved human-level parity in structure in a fraction of the time, highlighting the efficiency gains of automated constructive induction.

The system demonstrates that symbol reduction often aligns with the most "natural" way for humans to organize information. By engaging in an interactive session, Duce acts as a collaborator rather than a black-box learner, helping the user refine the knowledge base in real-time.

Limitations and Future Work

While effective, Duce is currently restricted to propositional logic. Extending these transformation techniques to first-order calculus (predicate logic) is a necessary step for addressing more complex relational domains. Additionally, the system's reliance on a human oracle introduces the risk of "oracle fatigue" if the training data is sparse or noisy, leading to a high rate of rejected concept suggestions. Future research may also explore adapting these techniques for grammar induction in natural language processing.

Summary updated

BibTeX
@inproceedings{muggleton1987duce,
  author = {Stephen H. Muggleton},
  title = {{Duce, An Oracle-based Approach to Constructive Induction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure