\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML02.3 · AdaBoost

A free, illustrated module of 4 lessons and one interactive in ML02 Supervised Learning: Trees, Ensembles and Kernels: Weak learners that take turns; The AdaBoost algorithm, step by step; AdaBoost minimises exponential loss; AdaBoost in practice.

ML02.3 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of ML02 Supervised Learning: Trees, Ensembles and Kernels in the Machine Learning track.

A stump that asks one question about one feature is only a little better than guessing. AdaBoost builds a team of such stumps in turn, each trained on a reweighted copy of the data that stresses the points the team still gets wrong, and lets them vote with weights that reward accuracy. These four lessons fit a weighted stump by hand, run the algorithm round by round on the twelve points, show that it is minimising the exponential loss and prove how fast its training error falls, and then use it on real data, where label noise exposes its weak spot.

What you need first. Decision trees, impurity and splits (ML02.1), the idea of an ensemble from bagging (ML02.2), the log loss of logistic regression (ML01.6), and training, validation and test error (ML01.2, ML01.8). Natural logarithms and the exponential function, and a derivative set to zero.

Lessons

1. Weak learners that take turns ML02.3.1 25 min

   A weak learner is only a little better than guessing. Boosting trains a sequence of them, each on a reweighted copy of the data that stresses the last one’s mistakes. Learn the decision stump, weighted error and weighted Gini, and fit the best stump on the twelve points by hand.

2. The AdaBoost algorithm, step by step ML02.3.2 25 min

   The discrete AdaBoost loop: weighted error, the learner weight alpha, the multiplicative weight update and the weighted vote. Prove that the newest learner always ends up with error exactly one half, run three rounds by hand on the twelve points, and code the loop in NumPy.

3. AdaBoost minimises exponential loss ML02.3.3 25 min

   AdaBoost is forward stagewise additive modelling with the exponential loss: derive its learner weight by setting a derivative to zero, prove the training-error bound, and see from the shape of the loss why mislabelled points hurt it.

4. AdaBoost in practice ML02.3.4 25 min

   AdaBoostClassifier with stumps on the breast cancer data: the number of rounds, the learning rate as shrinkage, test error that keeps falling after training error reaches zero, what flipped labels do to the weights, and a fair comparison with a random forest.

The interactive

ML02.3-X1 · AdaBoost stepper. Step through AdaBoost on the twelve points: watch the misclassified points grow, the weighted error and learner weight of each stump fill a table, the combined vote redraw, and the training error sit beneath the exponential-loss bound. Switch to depth-2 trees to see the error reach zero. It lives in The AdaBoost algorithm, step by step.