Learning Decision Lists Using Homogeneous Rules

Richard B. Segal, Oren EtzioniAAAI 1994

Abstract

Traditional decision list learning algorithms often suffer from "greedy myopia" and the "rule overlap problem," where the quality of a rule depends heavily on its position in the list. This paper introduces BRUTEDL, an algorithm that leverages homogeneous rules—rules whose accuracy remains statistically stable regardless of their position. By focusing on these position-independent rules, BRUTEDL reduces the task of building an optimal classifier to finding the best individual rules independently. Experimental results on UCI and MONK datasets demonstrate that BRUTEDL is highly effective, particularly in solving complex logical patterns like XOR, while remaining computationally feasible.

Introduction

Decision lists are ordered sets of "if-then" rules used for classification. Most existing algorithms, such as CN2 or AQ, learn these lists greedily: they identify one rule, remove the covered data, and repeat. This approach introduces two significant challenges. First, the Rule Overlap Problem means a rule's accuracy is contingent on preceding rules, making isolated evaluation difficult. Second, Greedy Myopia can lead to suboptimal models if an early rule choice skews the remaining dataset.

To address these issues, this research proposes a framework based on Homogeneous Rules. A rule is considered homogeneous if its accuracy does not change when more specific conditions are added to it. This property allows rules to be evaluated and selected independently of their eventual position in a decision list.

The BRUTEDL Algorithm

The BRUTEDL (Brute-force Decision List) algorithm implements this framework through a systematic, depth-bounded search of the rule space. Key components include:

  • Systematic Search: Unlike greedy learners, BRUTEDL performs an exhaustive search of conjunctive rules up to a specified depth.
  • Homogeneity Testing: A $\chi^2$ (chi-squared) test is employed to ensure statistical stability. If a specialized version of a rule significantly alters its accuracy, the original rule is rejected as non-homogeneous.
  • Laplace Accuracy: The algorithm uses the Laplace heuristic to estimate rule accuracy, mitigating overfitting on rules with low coverage.
  • Sound Pruning: To maintain efficiency, the authors developed pruning axioms. For instance, if a rule achieves 100% accuracy, its descendants are pruned as they cannot offer further improvement.

The theoretical foundation of BRUTEDL rests on the "Expressive Equivalence" theorem, which states that for every decision list, there exists a logically equivalent homogeneous decision list. This ensures that restricting the search to homogeneous rules does not sacrifice predictive power.

Experimental Evaluation

The algorithm was benchmarked against the popular C4 decision tree algorithm using real-world datasets from the UCI Repository and synthetic MONK’s problems.

Accuracy comparison between BRUTEDL and C4 across various benchmark datasets.

As shown in Figure 2, BRUTEDL achieved 100% accuracy on the MONK #1 problem, which involves an XOR relationship that typically challenges decision tree learners like C4 (which scored 80.6%). BRUTEDL's ability to search for specific attribute combinations allows it to handle such disjunctive patterns naturally. On real-world datasets, BRUTEDL remained competitive, notably outperforming C4 on the Lymphography dataset (82.0% vs 69.6%).

Computational performance and search depth of BRUTEDL across different domains.

Despite the "brute force" moniker, BRUTEDL is remarkably efficient. By processing approximately 100,000 rules per second and utilizing sound pruning, most benchmarks completed in under a minute (Figure 1). The longest run, for the Chess endgame dataset, took roughly 16 minutes on 1994-era hardware.

Discussion and Conclusion

While BRUTEDL offers a robust alternative to greedy learning, it has limitations. The $\chi^2$ test for homogeneity can be sensitive, sometimes leading to "false alarms" that discard valid rules, as seen in the Voting and Breast Cancer results. Additionally, the exhaustive search is depth-bounded; in domains like "Glass" where rules are inherently deep, BRUTEDL may be outperformed by algorithms capable of deeper heuristic searches.

Future work could involve exploring more stable statistical tests for homogeneity or integrating homogeneous rule principles into heuristic search methods like beam search. Overall, BRUTEDL demonstrates that moving beyond greedy approaches to focus on position-independent rules can yield powerful, interpretable, and computationally viable classification models.

Summary updated

BibTeX
@inproceedings{segal1994learning,
  author = {Richard B. Segal and Oren Etzioni},
  title = {{Learning Decision Lists Using Homogeneous Rules}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure