Classifiers: A Theoretical and Empirical Study

Wray L. BuntineIJCAI 1991 · OpenReview

Abstract

This paper describes how a competitive tree learning algorithm can be derived from first principles. The algorithm approximates the Bayesian decision theoretic solution to the learning task. Comparative experiments with the algorithm and several mature AI and statistical families of tree learning algorithms currently in use show the derived Bayesian algorithm is consistently as good or better, although sometimes at computational cost. Using the same strategy, we can design algorithms for many other supervised and model learning tasks given just a probabilistic representation for the kind of knowledge to be learned. As an illustration, a second learning algorithm is derived for learning Bayesian networks from data. Implications to incremental learning and the use of multiple models are also discussed.

Introduction

By the early 1990s, classification tree systems such as Quinlan’s ID3/C4.5 and Breiman’s CART were widely successful but had reached a performance plateau. Most improvements remained incremental, and the field lacked a unified theoretical framework to compare disparate learning theories, such as classical statistics versus minimum encoding approaches.

A central challenge in this domain is overfitting: balancing model complexity with accuracy when data is limited. Traditional systems often relied on heuristics to find a single "best" tree. However, this "winner-take-all" approach ignores valuable information contained in alternative model structures, particularly when the top-ranked tree is only marginally superior to its competitors.

Bayesian Algorithm Design

Buntine proposes a general six-step algorithm design strategy rooted in Bayesian decision theory. Rather than searching for a single optimal tree, the objective is to approximate the posterior average of class probabilities across the entire space of possible tree structures.

The derivation for classification trees involves defining the structure, likelihood, prior, and posterior, as summarized in the table below:

Summary of the Bayesian derivation for classification trees.

Key techniques in this approach include:

  • Bayesian Smoothing: Instead of binary pruning, this method averages class probabilities at a leaf with those of its parent nodes, blending specific local data with general global trends.
  • Option Trees (Averaging): The algorithm utilizes an AND-OR representation to store multiple high-performing tree structures simultaneously. Predictions for new instances are generated by averaging across all stored structures.
  • Lookahead Heuristics: The system employs one-ply or two-ply lookahead, evaluating split quality using a Bayesian posterior measure rather than standard information gain.

Extension to Bayesian Networks

To demonstrate the generality of this six-step strategy, Buntine applies it to the task of learning the structure of Bayesian networks from data. This involves moving from tree structures to more complex directed acyclic graphs that represent conditional dependencies between variables.

An example Bayesian network structure for medical diagnosis.

Experimental Evaluation

The Bayesian approach was evaluated against CART, C4.5, and minimum encoding methods across 12 diverse datasets from the UCI Machine Learning Repository and various medical domains (e.g., Glass, Hepatitis, Mushrooms, and Hypothyroid data). Testing involved 20 random trials per dataset across four different training set sizes to ensure statistical significance.

Key Results

  • Superior Accuracy: The Bayesian averaging approach, utilizing a uniform prior, was the only method to consistently produce the best predictions across all 12 datasets.
  • Statistical Significance: In most cases, the Bayesian approach was pairwise significantly better than non-Bayesian methods at the 5% level.
  • Performance Gains: Averaging with a two-ply lookahead yielded improvements in predictive accuracy of 2–3% over standard single-tree methods.
  • Robustness: The advantage of Bayesian methods was most pronounced on smaller datasets, where smoothing and model averaging effectively prevented the "over-pruning" common in heuristic systems.

Discussion and Conclusion

The study highlights that the traditional search for a single "best" model is essentially a first-order approximation of the full Bayesian solution. By making prior assumptions explicit and averaging over multiple models, the proposed framework provides a more theoretically sound and empirically accurate foundation for learning.

While powerful, these methods come with increased computational complexity; growing option trees can require significantly more time and space than building a single tree. Future work involves optimizing search heuristics and developing more flexible, domain-specific priors to further enhance performance in information-poor environments.

Summary updated

Abstract

This paper describes how a competitive tree learning algorithm can be derived from first principles. The algorithm approximates the Bayesian decision theoretic solution to the learning task. Comparative experiments with the algorithm and the several mature AI and statistical families of tree learning algorithms currently in use show the derived Bayesian algorithm is consistently as good or better, although sometimes at computational cost. Using the same strategy, we can design algorithms for many other supervised and model learning tasks given just a probabilistic representation for the kind of knowledge to be learned. As an illustration, a second learning algorithm is derived for learning Bayesian networks from data. Implications to incremental learning and the use of multiple models are also discussed.
BibTeX
@inproceedings{buntine1991classifiers,
  author = {Wray L. Buntine},
  title = {{Classifiers: A Theoretical and Empirical Study}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
  url = {https://openreview.net/forum?id=H1WjeBGO-H},
}
Figure