Rule Induction and Instance-Based Learning: A Unified Approach

Pedro M. DomingosIJCAI 1995

Abstract

The RISE algorithm bridges the gap between two classic machine learning paradigms: Rule Induction and Instance-Based Learning (k-Nearest Neighbor). By starting with specific examples as rules and generalizing them only when it improves global accuracy, RISE achieves significantly higher predictive performance than state-of-the-art decision trees and rule learners across a wide variety of real-world datasets.

Introduction

In the mid-90s, machine learning was characterized by the "selective superiority problem": different algorithms excelled in different domains, but no single approach dominated. Two popular but flawed paradigms were Rule Induction (RI) and Instance-Based Learning (IBL/k-NN). RI is effective at finding highly predictive features but struggles with "small disjuncts" (rare exceptions) and "splintering" (data depletion during partitioning). Conversely, IBL handles complex boundaries and exceptions well but is highly sensitive to irrelevant features and noise.

Pedro Domingos argues that these two are ends of a spectrum. This paper introduces RISE (Rule Induction from a Set of Exemplars), a unified algorithm designed to capture the strengths of both paradigms while mitigating their individual weaknesses.

Methods

RISE operates on a "specific-to-general" search strategy:

  1. Initialization: Every training example starts as its own specific rule.
  2. Generalization: For each rule, the algorithm identifies the nearest example of the same class not yet covered and attempts to "stretch" the rule to include it.
  3. Global Evaluation: Unlike traditional "separate-and-conquer" learners, RISE evaluates every potential generalization against the entire training set. A generalization is only kept if it maintains or improves the global accuracy of the entire rule set.
  4. Classification: New instances are classified using a "best-match" strategy. Distance is calculated using a hybrid metric (Euclidean for numeric data and Value Difference Metric for symbolic data), with ties broken by Laplace-corrected accuracy.

This mechanism allows the system to behave like a nearest-neighbor classifier when rules are specific and like a traditional rule system as they generalize.

Experimental Setup

The author evaluated RISE using 30 datasets from the UCI repository. These domains spanned medical diagnosis, physical phenomena, social/economic data, and biological data. To ensure unbiased results, 15 domains were used for development and tuning, while the remaining 15 were reserved for the final comparative study.

Results and Discussion

The empirical results were strikingly favorable for RISE. As shown in the detailed performance breakdown across the 15 test domains, RISE consistently outperformed its parent paradigms and industry standards.

Detailed accuracy comparison across 15 test domains for RISE and competing algorithms.

Key observations from the experimental results include:

  • Outperforming the "Parents": RISE consistently achieved higher accuracy than PEBLS (an advanced IBL) and CN2 (a state-of-the-art rule learner).
  • Beating Decision Trees: RISE outperformed C4.5 in 13 out of 15 test domains. In 10 of those cases, the improvement was statistically significant at a 95% confidence level.
  • Consistency: RISE achieved the highest average accuracy across all domains and the highest overall "score" when ranking algorithms by performance per dataset.
Summary of performance measures comparing RISE against PEBLS, CN2, and C4.5.

Key Insights

  • Conquering Without Separating: By avoiding the "splintering" effect of traditional rule induction, RISE maintains statistical strength by always referencing the full training set.
  • Preserving Small Disjuncts: Starting with specific instances allows RISE to preserve rare exceptions that top-down learners often prune as noise.
  • Context-Sensitive Feature Selection: RISE can drop irrelevant features for specific rules, recognizing that feature importance can vary across the instance space.

Limitations and Future Work

The primary drawback of RISE is its computational complexity. Evaluating every generalization against the entire dataset makes it significantly slower than decision trees or simple k-NN. For example, while small datasets processed in seconds, the "hypothyroid" domain required nearly two hours. Future work focuses on optimization through windowing or sampling, improving the interpretability of the resulting rule sets, and incorporating domain knowledge into the search process.

Summary updated

BibTeX
@inproceedings{domingos1995rule,
  author = {Pedro M. Domingos},
  title = {{Rule Induction and Instance-Based Learning: A Unified Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure