Compressed Rule Ensemble Learning

Malte Nalenz, Thomas AugustinAISTATS 2022 · OpenReview

Abstract

Ensembles of decision rules extracted from tree ensembles, like RuleFit, promise a good trade-off between predictive performance and model simplicity. However, they are affected by competing interests: While a sufficiently large number of binary, non-smooth rules is necessary to fit smooth, well-generalizing decision boundaries, a too high number of rules in the ensemble severely jeopardizes interpretability. As a way out of this dilemma, we propose to take an extra step in the rule extraction step and compress clusters of similar rules into ensemble rules. The outputs of the individual rules in each cluster are pooled to produce a single soft output, reflecting the original ensemble’s marginal smoothing behaviour. The final model, that we call Compressed Rule Ensemble (CRE), fits a linear combination of ensemble rules. We empirically show that CRE is both sparse and accurate on various datasets, carrying over the ensemble behaviour while remaining interpretable.

Introduction

Modern tree ensembles, such as Random Forests and Gradient Boosted Trees, are the "gold standard" for tabular data due to their high predictive accuracy. However, they are essentially black boxes; a forest of 500 deep trees is impossible for a human to audit.

To address this, researchers previously developed Rule Ensembles (like RuleFit), which extract individual paths from trees as "if-then" rules and combine them in a simple linear model. Yet, these models face a fundamental "interpretability-accuracy gap": achieving the smooth decision boundaries that make forests accurate requires hundreds of overlapping rules, which destroys interpretability. Conversely, limiting the model to just a few rules causes boundaries to become "jagged" and accuracy to plummet. CRE aims to solve this dilemma by compressing clusters of similar rules into a few "ensemble rules."

Methodology

The authors propose a novel three-step pipeline to create Compressed Rule Ensembles:

  1. Rule Extraction: Generate a standard tree ensemble (e.g., using XGBoost) and harvest all decision rules (paths) from the trees.
  2. Ensemble Compression: Instead of treating every rule as unique, CRE analyzes the "split points" for each feature. It uses a 1D clustering algorithm (Ckmeans.1d.dp) to group similar split points together. These clusters are transformed into "ensemble conditions"—soft, non-parametric functions that represent the average behavior of many similar rules.
  3. Sparse Linear Modeling: These compressed ensemble rules are fed into a Lasso (L1-regularized) linear model. This automatically selects a tiny subset of the most predictive ensemble rules to create the final, interpretable model.
Visualization of split frequencies and the resulting soft ensemble conditions $\Phi(x)$ across different features.

By using "soft" ensemble conditions rather than "hard" binary thresholds (e.g., "Age < 30"), the model captures the "marginal smoothing" effect of the original forest without needing hundreds of redundant rules.

Experimental Setup

The authors evaluated CRE on 16 binary classification datasets from the UCI Machine Learning Repository. The variety of these benchmarks provides a robust look at the algorithm's performance across different domains:

  • Medical data: Diabetes (Pima), Heart disease, Breast Cancer (WBCD), Blood Transfusion.
  • Physical/Technical data: Ionosphere, Spambase, Banknote authentication, Sonar.
  • General benchmarks: Australian credit, Haberman’s survival, and others.

Key Results and Insights

Accuracy vs. Sparsity

CRE demonstrates a superior trade-off between model complexity and performance. Specifically, the version with 4 clusters per feature ($CRE_{k:4}$) achieved AUC scores nearly identical to a fully-tuned XGBoost model, outperforming traditional rule-based competitors like SIRUS and PRE. CRE models were remarkably small; for many datasets, a model with just 5 to 20 rules was enough to reach state-of-the-art performance.

Comparison of Model Size vs. Accuracy across different datasets and models, highlighting CRE's ability to maintain high accuracy with low complexity.

Computational Efficiency

Because CRE compresses rules before the final modeling step, it significantly reduces the size of the mathematical problem. This leads to massive speedups—in tests on the "Magic" dataset ($N \approx 19,000$), RuleFit took 2,633 seconds to train, while $CRE_{k:4}$ took only 230 seconds, a more than 10x improvement.

Communicating Uncertainty

Traditional rules use a hard threshold (e.g., $x < 5.2$). CRE rules can be presented as intervals (e.g., $x \approx 5.2 \pm 0.5$), which more honestly reflects the model's uncertainty and the "grey areas" in the data, distilling the forest's wisdom into a simpler, more transparent form.

Conclusion

Compressed Rule Ensembles bridge the gap between black-box accuracy and human-readable simplicity. While the current focus is on binary classification, the authors note that the method can be extended to regression or multi-class problems. Future work includes developing stability metrics for soft rules and using ensemble compression as a general-purpose tool for interpreting the inner workings of complex forests.

Summary updated

Abstract

Ensembles of decision rules extracted from tree ensembles, like RuleFit, promise a good trade-off between predictive performance and model simplicity. However, they are affected by competing interests: While a sufficiently large number of binary, non-smooth rules is necessary to fit smooth, well generalizing decision boundaries, a too high number of rules in the ensemble severely jeopardizes interpretability. As a way out of this dilemma, we propose to take an extra step in the rule extraction step and compress clusters of similar rules into ensemble rules. The outputs of the individual rules in each cluster are pooled to produce a single soft output, reflecting the original ensemble’s marginal smoothing behaviour. The final model, that we call Compressed Rule Ensemble (CRE), fits a linear combination of ensemble rules. We empirically show that CRE is both sparse and accurate on various datasets, carrying over the ensemble behaviour while remaining interpretable.
BibTeX
@inproceedings{nalenz2022compressed,
  author = {Malte Nalenz and Thomas Augustin},
  title = {{Compressed Rule Ensemble Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=4GGTVp650t},
}

Loading related content...

Figure