Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 14

AdaBoost with decision stumps

Each base learner is a decision stump: a single threshold on one input, so its boundary is a line parallel to an axis. AdaBoost trains the stumps one after another; before each new stump it raises the weight of the points the committee so far gets wrong. In the left panel every circle's radius is the weight w_n^(m) used to train the latest stump (dashed white line), and the green line is the boundary of the whole committee sign(∑ α_l y_l(x)). The right panels follow the training error and the exponential error that AdaBoost minimises, and place every training point on the error functions of Figure 14.3 at its margin z_n = t_n f_m(x_n).

Data

Number of stumps m

Shading

Scoreboard

Try these

With α_m = ln((1 − ε_m)/ε_m), the exponential error (1/N)∑_n exp(−t_nf_m(x_n)) equals ∏_l 2√(ε_l(1 − ε_l)) exactly; it bounds the training error because exp(−z) ≥ 1 whenever z ≤ 0 (Freund and Schapire 1997).

In the lecture notes

Chapter 14 notes: Section 14.3 (the AdaBoost algorithm, (14.15) to (14.19), and Figure 14.2), Section 14.3.1 (AdaBoost as sequential minimisation of the exponential error, (14.20) to (14.26)) and Section 14.3.2 (error functions for boosting, Figure 14.3, half the log odds (14.28)).
Python code: code/ch14_combining_models.py (functions fit_stump, adaboost, adaboost_curves, fig14_2, fig14_3); checks in code/checks_ch14.py.