Turn a pile of barely-better-than-random classifiers into one strong one. Keep a weight on every example; each round, train a weak learner (a one-split “stump”) on the weighted data, give it a vote α = ½ ln((1−e)/e), then push weight onto the examples it got wrong. The next round is forced onto them. “Ada” = adaptive: α is read off the error each round — the first booster that needs no advance knowledge of the weak learner’s edge.
THE TECHNIQUE three stumps beat a task no stump can do
Three points on a line, labels +,−,+ — a 1-D parity that no single stump can separate (any threshold gets at most 2 of 3). Boost three rounds: each stump trains on the current weights, earns a vote from its error, and hands the hard point to the next round. The weighted vote separates all three. live demo
HISTORY & CREDIT the name is adaptive, not first
“AdaBoost invented boosting” — no; that is theirsSchapire’s (1990). AdaBoost made it adaptive. cited
1988–89 · Michael Kearns (unpublished note) poses “can a weak learner be boosted to strong?” and coins the word; Kearns & Valiant leave it formally open. 1990 · Robert Schapire answers yes with the first boosting algorithm (a recursive majority-of-three) — this, not AdaBoost, is the first booster. Freund’s boost-by-majority (1990/95) follows, still needing the edge γ up front. 1995 · Freund & Schapire publish AdaBoost (EuroCOLT) — the novelty is adaptivity: αt is set from the observed error, no advance γ. The famous ½ ln((1−e)/e), H=sign(Σαh) form is later still (Schapire & Singer, 1999). 2003 / 2010 · Godel Prize for the 1997 paper; Long & Servedio prove any convex-potential booster (AdaBoost included) can be broken by any label-noise rate — the hard limit behind its noise sensitivity.
Learner-agnostic by definition; “AdaBoost = boosted trees” is only a convention. Freund & Schapire, 1995/1997
RECOMMEND FOR I-13 weights in an array, one ln per round
The alphas need a logarithm; the votes and margins are f64 sums — and the three grounded margins carry the correct signs:
$ i13 run ada.i13 # +,-,+ parity, 3 stumps, ln via series
a1=0.3466 a2=0.5493 a3=0.8047 (0.5*ln2, 0.5*ln3, 0.5*ln5)
margins = +0.6020, -0.0912, +1.0074 -> signs +,-,+ ALL CORRECT
Recommend:nothing new — example weights live in an f64 array; each round is a weighted-error sum, one vote α = ½ ln((1−e)/e) (the corpus’s ln series, dart 106’s exp inverse), and a reweight Dₖ ← Dₖ e−α y h; the final vote is sign(Σ αt ht) (verified margins +0.6020, −0.0912, +1.0074 — signs +,−,+, all correct on a task one stump provably cannot do). Note: the samples × features design matrix a real weak learner scans is a 2-D array (PS-004); the 1-D stump above sidesteps it. Pairs with random forest (dart 125): boosting reweights sequentially, bagging resamples in parallel.