Q(D)O-ES: Population-based Quality (Diversity) Optimisation for Post Hoc Ensemble Selection in AutoML

Lennart Purucker, Lennart Schneider, Marie Anastacio, Joeran Beel, Bernd Bischl, Holger H. Hoos

Introduction

In Automated Machine Learning (AutoML), the final performance of a system often hinges on "post hoc ensembling." This process involves selecting and combining a subset of the models discovered during the search phase to maximize predictive accuracy. For nearly two decades, the industry standard for this task has been Greedy Ensemble Selection (GES). While efficient, GES is a deterministic greedy search that is susceptible to local optima and often fails to account for complex, non-linear interactions between models that do not yield immediate incremental improvements.

Presented at AutoML 2023, the work by Purucker et al. introduces QO-ES and QDO-ES, two population-based alternatives designed to move beyond the limitations of greedy search. By leveraging Quality Diversity (QD) optimization, these methods aim to maintain a diverse archive of high-performing ensembles, offering a more robust exploration of the ensemble search space.

Methodology

The researchers developed two evolutionary-based algorithms to optimize ensemble selection:

1. Quality Optimisation Ensemble Selection (QO-ES)

QO-ES is a population-based search that maintains an archive of the $a$ best-performing ensembles found during the search. It utilizes stochastic operators—specifically mutation (randomly adding a model to an ensemble) and crossover (combining components of two different ensembles)—to explore the search space more thoroughly than a single-path greedy search.

2. Quality Diversity Optimisation Ensemble Selection (QDO-ES)

QDO-ES extends the population-based approach by prioritizing not just performance, but also diversity. It maps candidate ensembles into a "behavior space" defined by two key metrics:

  • Average Loss Correlation (ALC): A measure of output-space diversity, calculating how differently the models within an ensemble make errors.
  • Configuration Space Similarity (CSS): A measure of input-space diversity, assessing the structural differences between the underlying algorithms and hyperparameters of the models.

By utilizing a sliding boundaries archive (implemented via the pyribs library), QDO-ES prevents the search from converging prematurely on a single type of ensemble, potentially discovering combinations that are more robust to noise.

Experimental Design

The study represents one of the most extensive evaluations in the field of post hoc ensembling:

  • Benchmark: 71 classification datasets from the OpenML AutoML Benchmark (AMLB).
  • Base Models: Generated using Auto-Sklearn 1 with a 4-hour time limit per fold.
  • Evaluation: 10-fold cross-validation, totaling over 620,000 individual ensemble runs to evaluate various hyperparameter configurations.

Key Insights and Results

The Overfitting Wall

The most significant finding of the study is the disparity between validation and test performance. While QDO-ES and QO-ES significantly outperformed GES on validation data across all scenarios (ROC AUC and Balanced Accuracy), much of this advantage diminished on hidden test sets. This suggests a critical bottleneck in AutoML: as search algorithms become more powerful, they face an increased risk of "memorizing" the noise in the validation split, leading to overfitting during the ensembling phase.

The Importance of Preprocessing

Interestingly, the method used to prune the initial pool of models proved more impactful than the choice of search algorithm. The researchers compared TopN (selecting the $N$ best models) with SiloTopN (ensuring representation from different algorithm families like XGBoost, Random Forest, and SVM). SiloTopN consistently led to superior final performance, highlighting that a diverse starting pool is a prerequisite for effective ensembling.

Comparative Performance

  • Ensembling vs. Single Best: All ensembling methods (GES, QO-ES, QDO-ES) statistically significantly outperformed the single best model found during the search.
  • Validation Performance: Population-based methods (QO-ES and QDO-ES) were statistically superior to GES on validation sets.
  • Generalization: On test data, while population-based methods generally achieved higher rankings than GES, the difference was not statistically significant at the $\alpha = 0.05$ level.
  • Computational Efficiency: Despite their complexity, these methods remain practical. QDO-ES typically runs in approximately 3 minutes, a negligible fraction of the total AutoML pipeline time.

Conclusion and Future Work

Q(D)O-ES demonstrates that population-based and diversity-aware search can find superior ensemble configurations compared to traditional greedy methods. However, the "overfitting wall" remains a primary hurdle.

Future research directions include:

  • Robust Validation: Testing these methods with n-repeated k-fold cross-validation to provide a more stable signal for the optimizer.
  • Behavior Space Refinement: Exploring alternative diversity metrics to better capture the nuances of ensemble robustness.
  • Implementation Optimization: Reducing the computational overhead associated with maintaining large diversity archives.

Summary updated

BibTeX
@inproceedings{purucker2023q,
  author = {Lennart Purucker and Lennart Schneider and Marie Anastacio and Joeran Beel and Bernd Bischl and Holger H. Hoos},
  title = {{Q(D)O-ES: Population-based Quality (Diversity) Optimisation for Post Hoc Ensemble Selection in AutoML}},
  booktitle = {AutoML MainTrack},
  year = {2023},
  url = {https://openreview.net/forum?id=zvV7hemQmtLl},
}
Figure