AdaBoost Decision-Region Map (2D): Stump Votes, Weights and the Product-of-Z Bound

Play AdaBoost round by round: point size is the sample weight, colour regions are the weighted vote of the stumps so far.

Switch to 3D
Controls

Presets

Parameters

Model checks

The science

Boosting. Discrete AdaBoost keeps a weight Dt(i) on every training point. Round t picks the axis-aligned decision stump ht with the smallest weighted error εt, gives it the vote αt = ½ ln((1-εt)/εt), and re-weights Dt+1(i) = Dt(i) exp(-αt yi ht(xi)) / Zt so misclassified points grow and correct ones shrink. The final classifier is sign(∑ αt ht).

Exact identities used as checks. With Zt = 2√(εt(1-εt)) the training error is bounded by (1/n)∑ exp(-yiF(xi)) = ∏ Zt (Freund and Schapire, J. Comput. Syst. Sci. 55, 1997 - formula quoted from the standard derivation, not re-fetched here). The updated weights equal exp(-y F)/(n ∏ Zt), and after the update the stump just chosen has weighted error exactly 1/2. The page verifies each of these on your data, and also checks the fast sorted prefix-sum stump search against a brute-force search over every threshold.

Simplifications. Two features, stumps only, no shrinkage or early stopping, toy data in [-1,1]². The bound can be loose and does not forecast test error: with label noise the weights pile onto the flipped points (watch the weight ratio) and the ensemble starts to memorise them.

-
-