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:
- Model Merging (Weight Soups): Instead of ensembling models at the prediction level (which increases inference costs), recent techniques merge models directly in the parameter space. Arjun Seshadri et al. introduce this in Diffusion Soup: Model Merging for Text-to-Image Diffusion Models, using greedy selection to iteratively add or remove specific expert weights based on validation metrics to maximize text-to-image alignment without extra inference overhead.
- Test-Time Augmentation (TTA): Finding the best set of image transformations to average at test time can be viewed as an ensemble problem. Both the multi-author work of Alexander Lyzhov et al. (Greedy Policy Search: A Simple Baseline for Learnable Test-Time Augmentation) and the single-author work of Andrew G. Howard (Some Improvements on Deep Convolutional Neural Network Based Image Classification) employ greedy selection to iteratively discover the most impactful subset of data transformations, drastically reducing the number of forward passes needed during inference.
- Resource-Constrained Budgets: When computational time is unpredictable, greedy selection can order models by their marginal utility. As explored by Christian Gomes et al. in On the Cost-Effectiveness of Stacking of Neural and Non-Neural Methods for Text Classification: Scenarios and Performance Prediction and Ying Yang et al. in Classifying under computational resource constraints: anytime classification using probabilistic estimators, ordering estimators by their forward sequential addition ensures that the most impactful refinements are executed first, maximizing accuracy if computation is suddenly interrupted.
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.