Minimal Cost Complexity Pruning of Meta-Classifiers

AAAI 1999

TL;DR

This paper introduces a novel pruning technique for meta-classifiers, which are ensembles of multiple machine learning models. By adapting the CART algorithm's "minimal cost-complexity pruning," they effectively reduce the size of meta-classifiers without sacrificing predictive accuracy, leading to significant improvements in computational efficiency. This is crucial for real-time applications where speed is paramount.

What Problem Does This Paper Address?

Modern machine learning often leverages ensembles of classifiers to improve accuracy and robustness. When these ensembles, known as meta-classifiers, are built from a large number of individual "base" classifiers, they can become computationally expensive. This is particularly problematic for real-time systems like intrusion detection or e-commerce, where rapid predictions are essential. The challenge is to reduce the size and computational demands of these meta-classifiers without compromising their predictive power. Existing methods might prune base classifiers, but this paper focuses on pruning the structure of the meta-classifier itself.

Methods

The core contribution is a three-stage pruning algorithm for meta-classifiers.

  1. Initial Model Construction: A decision tree is built to model the input/output behavior of the original meta-classifier. This tree essentially represents the meta-classifier's decision-making process, with base classifiers acting as nodes.
  2. Tree Pruning: The algorithm then applies the "minimal cost-complexity pruning" technique, borrowed from the CART (Classification and Regression Trees) algorithm. This method associates a complexity parameter with the number of terminal nodes in a decision tree. By adjusting this parameter, the algorithm prunes the decision tree, effectively removing redundant base classifiers that don't significantly contribute to the meta-classifier's performance. This is analogous to how CART prunes decision trees to find an optimal balance between tree size and misclassification error.
  3. Reconstruction: Finally, the original combining scheme is reapplied to the remaining, pruned set of base classifiers to form the new, smaller meta-classifier.

The paper also mentions alternative pruning methods like Rissanen's minimum description length (MDL) principle, but focuses on the cost-complexity approach.

Datasets

The authors evaluated their pruning technique on two real-world credit card transaction datasets provided by Chase and First Union bank. They used 12 disjoint subsets of these datasets and combined 60 base classifiers using weighted voting and stacking schemes, evaluated through 6-fold cross-validation. No new benchmarks were introduced; existing datasets were used for evaluation.

Key Insights and Ideas

  • Meta-classifier pruning is feasible and effective: The paper demonstrates that it's possible to significantly reduce the complexity of meta-classifiers without a substantial loss in accuracy.
  • Cost-complexity pruning adapts well: The adaptation of the CART algorithm's cost-complexity pruning to the meta-classifier structure proves to be a powerful tool for identifying and removing redundant base classifiers.
  • Throughput gains are substantial: The primary benefit of pruning is not just a smaller model, but a dramatic increase in prediction speed (throughput), which is critical for real-time applications.
  • Accuracy-efficiency trade-off is manageable: The results suggest that a considerable portion of base classifiers can be removed while maintaining near-original accuracy levels.

Key Results

The pruned meta-classifiers achieved remarkable results:

  • Chase Data:
    • Retained 100% of the original meta-classifier's performance even when up to 60% of base classifiers were pruned.
  • Achieved 230% and 638% higher throughput with 60% and 90% pruning, respectively.
  • First Union Data:
    • Showed no significant accuracy reduction with 80% pruning.
  • Maintained 80% of the original performance with 90% pruning.
  • Achieved 5.08 and 9.92 times better throughput with 80% and 90% pruning, respectively.

Limitations and Future Work

  • Limitations: The paper focuses on pruning the structure of the meta-classifier using a decision tree representation. It doesn't explicitly discuss pruning individual base classifiers themselves, which might be another avenue for optimization. The evaluation is limited to two specific datasets and a fixed set of combining schemes.
  • Future Work: The authors suggest that this approach can be extended to other types of meta-classifiers and combining schemes. Further research could explore optimal pruning strategies for different application domains and investigate the interplay between pruning individual base classifiers and pruning the meta-classifier structure.

Summary updated

BibTeX
@inproceedings{1999minimal,
  title = {{Minimal Cost Complexity Pruning of Meta-Classifiers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure