Greedy Ensemble Selection

68 concepts58 papers1 proposal

Ensemble learning operates on a simple premise: a collection of models generalizes better than any single model alone. However, a naive implementation—such as averaging the predictions of every model in a library—often runs into a fundamental bottleneck. Weak or redundant models dilute the accuracy of top-tier predictors, introducing noise instead of signal.

To build the best possible ensemble, we ideally want to find the optimal subset of models. But if you have a library of $N$ models, evaluating every possible combination requires searching through $2^N$ subsets—a combinatorial explosion that quickly becomes computationally intractable.

Greedy ensemble selection resolves this dilemma. Instead of searching the entire space or settling for a uniform average, it constructs an ensemble incrementally. By evaluating models based on their marginal contribution to a validation metric, greedy selection builds highly sparse, performant ensembles at a fraction of the computational cost.

The Forward-Stepwise Heuristic

The core mechanism of greedy ensemble selection is straightforward: start small and grow iteratively. The algorithm typically begins with an empty ensemble (or the single best-performing model on a validation set). In each subsequent stage, it evaluates every candidate model in the library by temporarily adding it to the current ensemble and measuring the resulting performance on a held-out validation set. The model that yields the highest incremental improvement is permanently added to the group.

This iterative process was formalized by Art Munson et al. in Optimizing to Arbitrary NLP Metrics using Ensemble Selection and popularized by Alexandru Niculescu-Mizil et al. in Winning the KDD Cup Orange Challenge with Ensemble Selection. A key theoretical justification for why this simple heuristic works so well is provided by Dong Dai 0004 et al. in Greedy Model Averaging. They demonstrate that as the number of selection stages increases, a greedy forward-stepwise approach eventually competes with the best possible weighted combination of all models in the library, effectively approximating the performance of the entire convex hull of the model library without the dense computational overhead.

Variations of this local search strategy exist to prevent overfitting or stagnation. For instance, Yi Zhang 0010 et al. introduce an iterative greedy swap algorithm in Concept Sampling: Towards Systematic Selection in Large-Scale Mixed Concepts in Machine Learning, which not only adds beneficial models but also removes or swaps out components that no longer contribute to error reduction. Similarly, Jacek Mańdziuk et al. utilize iterative local search operations (adding, removing, and swapping) in A Committee of Convolutional Neural Networks for Image Classification in the Concurrent Presence of Feature and Label Noise to refine neural network committees under heavy data noise.

Why It Works: Prioritizing Diversity Over Accuracy

A common point of confusion is why a greedy algorithm doesn't simply pick the single best model repeatedly. The answer lies in how the objective function is evaluated: models are judged by their joint performance with the existing ensemble, not their individual accuracy.

This mechanism naturally prioritizes functional diversity. A candidate model that is individually weaker but makes errors on entirely different data points than the current ensemble provides a massive marginal gain. Conversely, a highly accurate model that shares the exact same error patterns as the existing ensemble provides zero marginal utility.

As Behzad Shayegh et al. demonstrate in Error Diversity Matters: An Error-Resistant Ensemble Method for Unsupervised Dependency Parsing, forward-stepwise selection implicitly or explicitly optimizes a joint objective of individual accuracy and structural diversity. By focusing on how a new model contributes to the overall error diversity, the ensemble resists the influence of redundant or lower-quality models. Yijun Wang 0002 et al. leverage this property in Ensemble Pruning Based on Objection Maximization With a General Distributed Framework, using information-theoretic metrics to greedily prune large ensembles down to a highly diverse, performant subset.

This drive toward diversity can even manifest as an alternating sequence of opposing inductive biases. In Multi-Symmetry Ensembles: Improving Diversity and Generalization via Opposing Symmetries, Charlotte Loh shows that greedy selection over a pool of models with varied symmetries naturally alternates between opposing biases, proving that functional disagreement is a core driver of ensemble generalization.

Optimizing Non-Differentiable Metrics

Standard machine learning models are constrained by backpropagation; they must optimize for smooth, differentiable loss functions like cross-entropy or mean squared error. However, real-world applications are evaluated on complex, aggregate, and often non-differentiable metrics—such as BLEU scores in translation, F-measures in parsing, or Area Under the ROC Curve (AUC).

Because greedy ensemble selection operates entirely on the outputs of pre-trained models, it treats the underlying models as black boxes. This allows practitioners to optimize for any arbitrary metric directly on a validation set.

This capability is heavily exploited in state-of-the-art competitive systems. For example, in neural machine translation, Shanbo Cheng et al. (Alibaba's Neural Machine Translation Systems for WMT18) and Tanfang Chen et al. (DiDi's Machine Translation System for WMT2020) both utilized greedy selection algorithms to find optimal subsets of translation models on development sets, maximizing BLEU scores far more effectively than simple model averaging. Similarly, Chunhua Shen et al. demonstrate in Efficient Pedestrian Detection by Directly Optimizing the Partial Area under the ROC Curve that greedy selection can directly optimize the Partial Area Under the ROC Curve (pAUC), tailoring object detectors to perform best at specific, deployment-critical false-positive rates.

Modern Extensions: Weights, Augmentations, and Budgets

While originally designed for traditional classifier libraries, the intuition of greedy selection has expanded into diverse areas of modern deep learning:

By shifting the problem from "how do we train a better model?" to "how do we greedily select the most complementary models?", this paradigm provides a highly flexible, training-free mechanism to squeeze maximum performance out of existing model libraries.

Key Foundational Work

ProFusion*: Intelligent Fusion from Multiple, Distributed Search Engines (1996) — contributed 1 concept elements to this direction.
Combining Deep and Shallow Approaches in Parsing German (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_greedy_ensemble_selection_52a5e9ff,
  title = {greedy ensemble selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-ensemble-selection/rdr_52a5e9ffc2764ffca50c3d6797629faf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_greedy_ensemble_selection_52a5e9ff_v1,
  title = {greedy ensemble selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-ensemble-selection/rdr_52a5e9ffc2764ffca50c3d6797629faf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake