The Ensemble Subset Selection Challenge

A Public Research Problem — 2026-08-31

TL;DR — we can build 10,000–30,000 weak classifiers in minutes, but we cannot reliably find the small subset whose majority vote is best. This is an NP-hard combinatorial problem. We publish the score corpora, the reference search tool and the reference results. We invite the community to supply better subset-search algorithms.

​ 1. The Problem — Exact Formulation

1.1 Input

• A library ℒ = {m₁, …, m_N} of N trained classifiers ("members"). In our corpora N ∈ {1,152; 5,760; 10,080; 30,240}.
• For every member m_i and every test sample x_t (t = 1 … 10,000 on Fashion-MNIST) a score vector s_i(x_t) ∈ ℝ^C over the C classes. The prediction is argmax_c s_i(x_t)_c.
• The true labels y_t of the test set.

1.2 Ensemble decision rule (majority vote)

For a subset S ⊆ ℒ, the ensemble prediction is the sum of the per-member argmax votes:

pred_S(x_t) = argmax_c   sum_{m_i in S}  1[ argmax_c' s_i(x_t)_{c'} == c ]

1.3 Objective and constraints

• Objective: maximize ensemble accuracy on the test set acc(S) = (1/T) · Σ_t=1..T 1[pred_S(x_t) = y_t]
• Constraint: |S| ≤ K with K typically 12–100. Every member costs DRAM bit-mass on the target chip; the accuracy-per-member efficiency acc/|S| matters.
• Generalization: the search must not overfit the test set — in practice the metric is evaluated on a hillclimbing set and checked on held-out data (see §4.4).

1.4 Complexity

Brute force over all C(N,K) subsets is infeasible: C(30,240; 12) ≈ 10⁴⁰. The problem is a special case of ensemble/feature subset selection, which is NP-hard (selecting the best subset of an ensemble; see §4.5). All practical approaches are heuristics: greedy forward selection, beam search, 2-opt exchange, bagged selection, pruning.

​ 2. What We Deliver (our current technology)

2.1 The classifiers — DRAM-native bit-logic (Otto Score)

Every member is a frozen-random-projection classifier computable with only bit-level operations (popcount, AND, OR, XOR) plus integer arithmetic — no floating point, no multiply-accumulate. This is the target architecture for an in-DRAM inference chip. Members differ by image transformation (xform), channel encoding, bit width, and seed. Because members are cheap to train (~seconds each, hundreds in parallel), we can overproduce a huge library cheaply.

2.2 The corpus format

• .ens score archives (v14/v15): int64/double scores + precision metadata, CRC64 integrity, per-member eval header.
• Public corpora on Fashion-MNIST: scores-H196-E10-OT8-INT32 (30,240 members), scores-H196-E10-OT8-M1-105-INT32 (per-m1t pools), scores-H392-E10-OT8-INT32, BV8/BV16 variants.

2.3 The search tool — merge-ensemble.c

An OpenMP-parallel C tool that already implements the standard repertoire and is fully deterministic (tiebreak fix, 2026-08-27):

Method	Flag	Result on Fashion-MNIST
Greedy forward selection (O(N²))	--greedy	91.84% (17/24,192)
Beam search (width 10–50)	--beam N	92.32% (12) @H392-OT8
Multi-try with shuffle	--tries N --tries-no-lock	91.3–91.6%
2-opt exchange	--optimal	1-swap-stable, no gain (dead end)
Library pruning / filtering	--filter ...	pruning helps (Caruana 2006 agrees)
Class exclusion	--exclude 6	94.24–94.83% (9 classes, proviso)

2.4 Reference results (Fashion-MNIST, 10k test)

Config	eval	members
Greedy full pool (24,192)	91.84%	17
Beam 30/50 + filter, H392-OT8	92.32%	12
Beam 20 + filter eval gt 20%	92.96%	12
Same, --exclude 6 (Shirt omitted)	94.24–94.83%	12–18

Key empirical findings (our search experience, fully documented in the Fashion-MNIST README):

• More members ≠ better: beam is not pool-monotone — adding 312 members to a pool worsened 6/10 corpora.
• Diversity beats strength: lower single-member accuracy with complementary errors beats uniformly strong members.
• Path-dependence: the greedy path diverges by a single early choice (the "spiral" xform decides 92.07% vs 91.58%).
• Multi-m1t pools blow up beam search: near-duplicate candidates displace good paths; hybrids ≤ single-m1t pools.

​ 3. What We Need — the Open Questions

We are looking for better subset-search algorithms — not better classifiers. Concretely, the community is invited to:

1. Beat the beam: find algorithms that reach ≥ 92.32% (Fashion, 12-member cap) reliably — across corpora, not just one lucky path — with documented improvement over beam/greedy.
2. Exploit the structure: the score vectors form an N × 10,000 matrix (30,240 × 10,000 floats ≈ 1.2 GB). Column correlation, error-covariance structure, submodularity — what is the right mathematical model of the objective?
3. Efficiency-aware selection: maximize acc/member (DRAM cost), not accuracy alone — the chip pays per member.
4. Overfitting control: demonstrate that the selected subset generalizes (hillclimb-set split protocol, §4.4), not just maximizes the reported number.
5. Theoretical guarantees: the objective is not monotone (more members can hurt). What is the approximation landscape? Is there a submodular relaxation that is provably good?

​ 4. Valid Background — What is Known in the Literature

4.1 Caruana et al. 2004 — "Ensemble Selection from Libraries of Models" (ICML)

The canonical formulation. Given a library of thousands of models, forward stepwise selection adds the model that maximizes ensemble performance on a held-out hillclimbing set. The method is optimizable to any metric (accuracy, cross-entropy, precision, ROC area). Two overfitting countermeasures are introduced: sorted ensemble initialization (start with the N best single models) and bagged ensemble selection (select from random subsets of the library and average). DOI 10.1145/1015330.1015432.

4.2 Caruana et al. 2006 — "Getting the Most Out of Ensemble Selection" (ICDM)

Four findings that directly guide our setup:

• Calibration of base models does not help much — benefit comes from base-model quality, not ensemble building.
• Hillclimb-set size matters: with ~5,000 points, overfitting becomes negligible; with 100 points, bagging is crucial.
• Optimize the true target metric — but RMS/MXE are competitive proxies if the metric is expensive.
• Library pruning is usually beneficial: keeping only the top 10–20% of models (by hillclimb performance) rarely hurts, often improves, and always speeds up the search. "Using 100% of the models is never worthwhile."

4.3 Caruana/Niculescu-Mizil et al. 2009 — KDD Cup Orange Challenge winner

Ensemble Selection won the KDD Cup Orange Challenge (average AUC 0.8457) using greedy forward selection on a library of classifiers built by many team members. Key practice: use a large hillclimbing set (they moved from two to four CV folds = 20,000 instances), and stop early when the ensemble starts overfitting the hillclimb set.

4.4 Overfitting protocol (community standard)

• Split test data: hillclimbing set (search) + validation set (final check). Our corpora use the full 10k test as the metric set; we recommend a 5k/5k or CV-embedded protocol for submissions.
• Auto-sklearn (Feurer et al. 2015) popularized greedy ensemble selection as the post-processing step of AutoML; it explicitly selects on a validation set and returns the full model as ensemble.

4.5 NP-hardness and pruning theory

• Selecting the best subset of an ensemble is NP-hard — Born-Again Tree Ensembles (Vidal 2020) prove it via reduction from 3-SAT; all practical methods are heuristics.
• Ensemble pruning literature (Margineantu & Dietterich 1997 — pruning AdaBoost; Martínez-Muñoz & Suárez 2006 — ordered bagging pruning) treats selection as a post-processing step and confirms greedy families as the workhorse; Partalas et al. 2012 give a unified greedy-pruning framework.
• Diversity measures (Kuncheva & Whitaker 2003) quantify error-complementarity — the quantity our "diversity beats strength" observation points to.

​ 5. Effort We Can Support

We can contribute the following to any collaboration:

• Data: full .ens score corpora (Fashion-MNIST; MNIST and CIFAR-10 corpora exist as well), publicly accessible on request / via the repository.
• Tooling: merge-ensemble.c (deterministic, OpenMP), extract-best-m1t.py, the full sweep + merge recipes documented in the README.
• Compute: local 12–16 thread machines for benchmark runs; sweep of a 10,080-member pool takes ~1–2 h, a merge search 3–60 s.
• Evaluation: independent re-run of every submitted algorithm on all corpora; we publish the results table and update the public leaderboard.
• Reference implementations: greedy, beam, tries, 2-opt, filtering — all present in the open tool for direct comparison.

​ 6. Submission Protocol

1. Format: any language/algorithm, but the result must be a subset of member indices (or a ranking) reproducible from the .ens corpus alone.
2. Metrics reported: accuracy, #members, wall-time, hillclimb/test split used, determinism, and the exact command line.
3. Constraints: |S| ≤ 12 is the standard cap; report also the best result at |S| ≤ 100.
4. Contact: via the GitHub repository aotto1968/forward-prop (issues/PRs). We maintain a public leaderboard.

​ 7. References

1. R. Caruana, A. Niculescu-Mizil, G. Crew, A. Ksikes. Ensemble Selection from Libraries of Models. ICML 2004. doi:10.1145/1015330.1015432.
2. R. Caruana, A. Munson, A. Niculescu-Mizil. Getting the Most Out of Ensemble Selection. ICDM 2006. doi:10.1109/ICDM.2006.76.
3. A. Niculescu-Mizil, C. Perlich, G. Póczos, L. Wu, P. Melville. Winning the KDD Cup Orange Challenge with Ensemble Selection. JMLR W&CP 7 (2009).
4. M. Feurer, A. Klein, K. Eggensperger, J. Springenberg, M. Blum, F. Hutter. Efficient and Robust Automated Machine Learning. NeurIPS 2015 (auto-sklearn).
5. T. Vidal, M. Schiffer. Born-Again Tree Ensembles. ICML 2020 (NP-hardness of optimal tree-subset selection).
6. I. Partalas, G. Tsoumakas, I. Vlahavas. A Study on Greedy Algorithms for Ensemble Pruning. 2012.
7. D. D. Margineantu, T. G. Dietterich. Pruning Adaptive Boosting. ICML 1997.
8. A. Martínez-Muñoz, A. Suárez. Pruning in Ordered Bagging Ensembles. ICML 2006.
9. L. I. Kuncheva, C. J. Whitaker. Measures of Diversity in Classifier Ensembles and their Relationship with the Ensemble Accuracy. Machine Learning 51(2), 2003.

Forward-Prop Research — DRAM-native bit-logic classification. Challenge published 2026-08-31. Reference results INT32 bit-exact, reproducible via run-grep --date-start 2026-08-30 | run-sort eval.