classification
A committee of weak learners
It is the 1990s, and a startling theoretical question has just been answered yes: can a bunch of rules that are each only slightly better than a coin flip be combined into a single strong, accurate classifier? You hold exactly such weak learners. Combine hundreds of them into one powerful predictor — and, crucially, explain with theory why the combination keeps improving on test data even after it has driven training error to zero, defying the naive expectation that it must overfit. The margin explanation is the deep part. Get it wrong and you either dismiss weak rules as useless, or trust an ensemble you cannot justify — boosting's legacy is that it worked, spectacularly, for reasons that demanded new theory to understand.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
This problem is Schapire's biography. As a graduate student he answered the opening question himself: his 1990 paper The Strength of Weak Learnability proved, by explicit construction, that weak and strong PAC learnability are equivalent — the startling yes the problem cites. With Freund he then created AdaBoost (1995-1997), the adaptive reweighting algorithm that made the construction practical and spectacularly effective, winning the Godel Prize. And the deep part is his too: Schapire, Freund, Bartlett, and Lee (1998) introduced the margin distribution explanation of why boosting keeps improving test error after training error reaches zero, defending it through the subsequent debate with Breiman and the statisticians. Algorithm, theorem, and explanation are all his own published work; no historical figure fits a problem more exactly.
Freund is the co-author of this problem's answer at every layer. His 1990-1995 boost-by-majority work analyzed combining weak hypotheses through a beautiful drifting-games framework, and with Schapire he created AdaBoost (the 1995-1997 papers), whose adaptive reweighting removed the need to know weak learners' edges in advance — the practical breakthrough — earning the Godel Prize. He is likewise a co-author of the 1998 margin-distribution explanation with Schapire, Bartlett, and Lee, and of the game-theoretic reading of boosting as a minimax equilibrium between booster and weak learner, arguably the deepest single lens on why the construction works. His later work (Brownian-motion boosting, online allocation via Hedge) kept extending the theory. He sits a hair below Schapire only because the original weak-learnability equivalence theorem was Schapire's solo result.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.