Abstract
An efficient procedure for pruning regression ensembles is introduced. Starting from a bagging ensemble, pruning proceeds by ordering the regressors in the original ensemble and then selecting a subset for aggregation. Ensembles of increasing size are built by including first the regressors that perform best when aggregated. This strategy gives an approximate solution to the problem of extracting from the original ensemble the minimum error subensemble, which we prove to be NP-hard. Experiments show that pruned ensembles with only 20% of the initial regressors achieve better generalization accuracies than the complete bagging ensembles. The performance of pruned ensembles is analyzed by means of the bias-variance decomposition of the error.
Introduction
Bagging (Bootstrap Aggregating) is a cornerstone of modern ensemble learning, particularly valued for its ability to reduce variance in unstable predictors like neural networks and decision trees. By training multiple models on bootstrap replicates of the training set and averaging their outputs, bagging typically achieves lower generalization error than any single constituent model. Standard practice assumes that ensemble performance improves monotonically with size, eventually reaching a stable error floor.
However, recent research suggests that "less is often more" in the context of ensemble learning. Not all models generated through bagging contribute equally to the final prediction; some may be redundant, while others may introduce noise that degrades collective performance. This paper addresses the problem of ensemble pruning: identifying the optimal subset of models to maximize accuracy. The authors prove that finding the absolute minimum error subensemble is an NP-hard problem, making exhaustive search infeasible for ensembles of practical size. Consequently, they propose a greedy heuristic called "Ordered Bagging" to efficiently approximate the optimal solution.
Methodology: Ordered Bagging
The core of the proposed approach is an ordering algorithm that builds a subensemble incrementally. Instead of aggregating models in their training order, the algorithm employs a greedy selection strategy:
- Iterative Selection: Starting with an empty ensemble, the algorithm searches the pool of available models and adds the one that results in the greatest reduction of the current subensemble's training error.
- Efficiency: This greedy approach provides a polynomial-time approximation for the subset selection problem, making it computationally viable for large model pools.
- Pruning via Early Stopping: By monitoring the error as models are added, a characteristic "U-shaped" curve often emerges in the test error. The ensemble is pruned by selecting the subensemble at the point where this error is minimized, typically well before all models are included.
Experimental Setup and Results
The effectiveness of Ordered Bagging was validated across 14 regression datasets, including four synthetic benchmarks (Friedman1, Friedman2, Friedman3, and Peak) and ten real-world datasets from the UCI and Weka repositories.
Performance Gains
The experimental results consistently demonstrate that pruned ensembles outperform full bagging ensembles. In nearly every dataset, a subensemble consisting of approximately the first 20% of the ordered models achieved a lower Mean Square Error (MSE) than the complete 100% ensemble. These improvements were found to be statistically significant through paired t-tests, often with p-values below 0.01.
For example, on the Boston Housing dataset, the MSE was reduced from 12.05 (complete ensemble) to 10.38 (pruned ensemble) using a pool of 100 neural networks. Beyond accuracy, the 80% reduction in ensemble size offers substantial benefits in terms of memory efficiency and inference speed, which are critical for deployment in resource-constrained environments.
Analysis of the Pruning Mechanism
To understand why pruning improves performance, the authors analyze the error using bias-variance decomposition. A key insight is that the greedy algorithm does not simply pick the best individual models; rather, it prioritizes models that exhibit negative correlation with the existing subensemble. This allows the errors of individual models to cancel out, effectively reducing the collective bias.
As shown in the decomposition analysis, the ordering process significantly reduces the bias of the ensemble members included early on. While the selection is performed on training data, the "minimum error" region on the test curve is generally broad enough that the gains translate effectively to unseen data without significant overfitting.
Conclusion
This research demonstrates that strategic pruning of bagging ensembles can lead to models that are both more accurate and more efficient. The proposed Ordered Bagging algorithm provides a practical solution to the NP-hard problem of subset selection. While the "20% heuristic" serves as a robust starting point, future research could explore automated methods for determining the optimal pruning point and extend the analysis to a broader range of base learners beyond neural networks.
Summary updated