Pareto Ensemble Pruning

Chao Qian, Yang Yu, Zhi-Hua ZhouAAAI 2015 · OpenReview

Abstract

Ensemble learning is a powerful paradigm in machine learning, yet the resulting models often suffer from excessive size and computational overhead. Ensemble pruning addresses this by selecting a subset of base learners. We present Pareto Ensemble Pruning (PEP), which reformulates pruning as a bi-objective optimization problem to simultaneously minimize error and ensemble size. By combining evolutionary Pareto optimization with a specialized local search operator, PEP identifies superior trade-offs between performance and efficiency. Our theoretical analysis proves PEP's advantages over greedy heuristics, and extensive experiments on 30 UCI datasets and a real-world activity recognition task demonstrate that PEP consistently outperforms state-of-the-art pruning methods.

Introduction

Ensemble methods, such as Bagging and Boosting, achieve high accuracy by aggregating multiple base learners. However, large ensembles pose significant challenges for deployment in resource-constrained environments due to high memory consumption and slow inference speeds. Ensemble pruning aims to mitigate these issues by identifying a compact subset of learners that preserves or enhances the ensemble's generalization capabilities.

The primary challenge in ensemble pruning is the inherent conflict between two objectives: maximizing accuracy and minimizing model size. Traditional methods typically rely on greedy ordering or single-objective optimization, which often fail to explore the full trade-off space effectively and lack robust theoretical guarantees.

Methods: The PEP Framework

Pareto Ensemble Pruning (PEP) treats the pruning task as a bi-objective optimization problem. Instead of collapsing error and size into a single scalar value, PEP explicitly searches for the Pareto frontier—the set of solutions where no objective can be improved without degrading the other.

Evolutionary Pareto Optimization

PEP utilizes an evolutionary algorithm to maintain a population of diverse pruning solutions. The process involves:

  1. Initialization: Starting with a random subset of base learners.
  2. Mutation: Applying bit-flipping operations to explore the search space.
  3. Variable-Depth Search (VDS): A local search subroutine that refines mutated solutions by iteratively flipping bits that yield the greatest improvement in the objective space.
  4. Pareto Frontier Update: Continuously updating the set of non-dominated solutions based on their error and size.

Theoretical Foundations

A key contribution of this work is the theoretical validation of PEP. We prove that PEP can find solutions at least as good as those produced by greedy ordering methods within polynomial time. Furthermore, we identify specific problem instances where PEP finds the optimal solution while traditional heuristics require exponential time, establishing a formal basis for its superior performance.

Experimental Evaluation

We evaluated PEP against five state-of-the-art pruning methods, including Bagging, Reduce-Error (RE), and Kappa-based pruning. The evaluation spanned:

  • 30 UCI Datasets: A diverse collection of 20 binary and 10 multiclass classification tasks.
  • Mobile Human Activity Recognition (MHAR): A real-world application using smartphone sensor data to classify physical activities.

Results and Discussion

PEP demonstrated significant advantages in both accuracy and model compression across the tested datasets.

Aggregated rank on test error and size vs. original ensemble size. PEP consistently maintains the lowest (best) rank across different initial sizes.

As shown in the aggregated rank plots, PEP consistently achieves the lowest (best) rank for both test error and ensemble size, regardless of the initial ensemble size. On the 30 UCI datasets, PEP achieved the best test error or smallest size in 60% of cases.

Aggregated rank error and size across all datasets. PEP shows the best overall performance compared to other state-of-the-art methods.

In the real-world MHAR task, PEP's bi-objective approach proved particularly effective, delivering a three-fold improvement in accuracy compared to the next best method while reducing storage requirements by over 20%. These results suggest that pruning acts as a form of regularization, where removing redundant or noisy learners improves generalization.

Conclusion

Pareto Ensemble Pruning (PEP) offers a robust and theoretically grounded approach to ensemble pruning. By explicitly optimizing for both error and size, PEP identifies highly efficient models that maintain state-of-the-art accuracy. Future work will explore the integration of diversity measures as a third objective and the development of more advanced evolutionary operators to further enhance search efficiency.

Summary updated

BibTeX
@inproceedings{qian2015pareto,
  author = {Chao Qian and Yang Yu and Zhi-Hua Zhou},
  title = {{Pareto Ensemble Pruning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=vbkIUebAJV8},
}
Figure