Constructive Induction: A Version Space-based Approach

Michèle SebagIJCAI 1999 · OpenReview

Abstract

By automatically reformulating the problem domain, constructive induction ideally overcomes the defects of the initial description. The reformulation presented here uses the Version Space primitives $D(E, F)$, defined for any pair of examples $E$ and $F$, as the set of hypotheses covering $E$ and discriminating $F$. From these primitives we derive a polynomial number of M-of-N concept. Experimentally, many of these concepts turn out to be significant and consistent. A simple learning strategy thus consists of exhaustively exploring these concepts, and retaining those with sufficient quality. Tunable complexity is achieved in the MONKEI algorithm, by considering a user-supplied number of primitives $D(E_i, F_i)$, where $E_i$ and $F_i$ are stochastically sampled in the training set. MONKEI demonstrates good performances on some benchmark problems, and obtains outstanding results on the Predictive Toxicology Evaluation challenge.

Introduction

In machine learning, the success of a learner is heavily dependent on the initial representation of the data. When attributes are poorly chosen, learners often struggle with "rare cases" or "small disjuncts"—tiny clusters of data that fail to fit general rules. Constructive induction addresses this by automatically "rewriting" the problem description to create more powerful features. However, searching for optimal features is typically computationally expensive and often requires expert domain knowledge.

This paper introduces MONKEI (M-of-N-based KonstructivE Induction), an algorithm that bridges classical Version Space (VS) theory with practical constructive induction. By utilizing stochastic sampling, MONKEI overcomes the traditional exponential complexity of Version Spaces, transforming complex problem domains into spaces where simple, robust patterns emerge.

Methodology: The MONKEI Algorithm

The core of the MONKEI approach lies in characterizing Version Spaces using Disjunctive Normal Form (DNF) primitives. The process follows several key steps:

  1. The Primitive ($D(E, F)$): For any pair of examples where $E$ is positive and $F$ is negative, the algorithm identifies "maximally discriminant selectors"—the simplest logical rules that cover $E$ while rejecting $F$.
  2. The New Attribute ($h_{E,F}$): For any new data point $U$, a new attribute $h_{E,F}(U)$ is calculated by counting how many of these selectors are satisfied. This maps the complex domain onto a simple integer scale (0 to $N$).
  3. M-of-N Concepts: These integer attributes naturally represent "M-of-N" logic (e.g., "at least $M$ of $N$ conditions are met").
  4. Stochastic Boosting: To maintain efficiency, MONKEI avoids exhaustive pairing. Instead, it stochastically samples "seed" examples that are currently difficult to classify, generating new features from them.
Calculation of the $h_{E,F}$ attribute for a new example $U$ based on training examples $E$ and $F$.

Experimental Results

The algorithm was evaluated on standard UCI benchmarks and the high-stakes Predictive Toxicology Evaluation II (PTE2) challenge.

UCI Benchmarks

On datasets such as Balance, Glass, Monks2, Vehicle, Waveform, and Tic-tac-toe, MONKEI matched or exceeded the "previous best" results. Notably, it achieved 98.3% accuracy on Monks2 and 97% on Balance. The algorithm proved efficient, finding high-quality theories using a relatively small number of dimensions (typically $d < 100$).

Predictive Toxicology Evaluation

The PTE2 challenge involves 333 chemical compounds and is notoriously difficult for both human experts and standard learners. MONKEI achieved 100% accuracy on the test set when provided with sufficient computational resources. This result is particularly significant when compared to established relational and propositional learners.

Accuracy comparison of relational and propositional learners on the Predictive Toxicology Evaluation challenge.

Discussion and Future Work

MONKEI demonstrates that DNF characterization allows for polynomial complexity and high expressiveness, capturing both "AND" and "XOR" type patterns. The most consistent rules are often found in the "tails" of the $h_{E,F}$ distribution—where $M$ is very high or very low.

Future research will focus on improving the intelligibility of the resulting DNF theories, which can be harder for humans to interpret than simple decision trees. Additionally, the author notes a promising link between MONKEI’s "seed pairs" and the "support vectors" in SVMs, suggesting potential for even more efficient sampling strategies. Efforts are also underway to extend the system to handle first-order logic and more complex relational data structures.

Summary updated

Abstract

By automatically reformulating the problem domain, constructive induction ideally overcomes the defects of the initial description. The reformulation presented here uses the Version Space primitives D(E, F), defined for any pair of examples E and F, as the set of hypotheses covering E and discriminating F. From these primitives we derive a polynomial number of M-of-N concept. Experimentally, many of these concepts turn out to be significant and consistent. A simple learning strategy thus consists of exhaustively exploring these concepts, and retaining those with sufficient quality. Tunable complexity is achieved in the MONKEI algorithm, by considering a user-supplied number of primitives D(Ei, Fi), where Ei and Fi are stochastically sampled in the training set. MONKEI demonstrates good performances on some benchmark problems, and obtains outstanding results on the Predictive Toxicology Evaluation challenge.
BibTeX
@inproceedings{sebag1999constructive,
  author = {Michèle Sebag},
  title = {{Constructive Induction: A Version Space-based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=HJWIrBfuWB},
}
Figure