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₁, …, mN} of N trained classifiers ("members"). In our corpora N ∈ {1,152; 5,760; 10,080; 30,240}.
• For every member mi and every test sample xt (t = 1 … 10,000 on Fashion-MNIST) a score vector si(xt) ∈ ℝ^C over the C classes. The prediction is argmaxc si(xt)c.
• The true labels yt 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[predS(xt) = yt]
• 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.

​ … read more at: https://forward-prop.nhi1.de/papers/ensemble-selection-challenge.html