Decision stump
Topic of Ensembles, random forests, and boosting, part of Statistical learning
Decision stump
| Type | Topic |
| Taught in | Ensembles, random forests, and boosting |
| Part | Statistical learning |
| Worked examples | 1 |
| Questions using it | 1 |
A classification tree with a single split: a threshold on one variable and a sign. A stump is a weak learner, only a little better than chance, which is what boosting combines into a strong one.
Examples
Three rounds of AdaBoost with stumps
Worked example from Ensembles, random forests, and boosting
Question. Run AdaBoost on x=1,\ldots,10 with labels
y=(+,+,+,-,-,-,+,+,+,-),
using decision stumps, a threshold on x and a sign, as learners.
Solution. Initially every w_{1,i}=0.1.
Round 1. The best stump predicts +1 for x<3.5 and -1 otherwise. It errs on x=7,8,9, so \varepsilon_1=0.3 and
\alpha_1=\tfrac12\log(0.7/0.3)=0.4236.
Correct points have their weight multiplied by e^{-\alpha_1}=\sqrt{0.3/0.7}=0.655, and wrong points by e^{\alpha_1}=1.528. The normaliser is Z_1=2\sqrt{0.3\times 0.7}=0.9165. The new weights are 0.1\times 0.655/0.9165=1/14=0.0714 on a correct point and 0.1\times 1.528/0.9165=1/6=0.1667 on a wrong point.
Round 2. The best stump on the reweighted data predicts +1 for x<9.5 and -1 otherwise. It errs on x=4,5,6, which carry weight 3/14, so \varepsilon_2=0.2143 and \alpha_2=0.6496.
Round 3. The stump that predicts -1 for x<6.5 and +1 otherwise errs on x=1,2,3 and x=10, so \varepsilon_3=0.1818 and \alpha_3=0.7520.
Weights below are the weights used in that round, listed once per observation in each group.
| x | y | w_1 | f_1 | w_2 | f_2 | w_3 | f_3 | \sum_t\alpha_t f_t | sign |
|---|---|---|---|---|---|---|---|---|---|
| 1,2,3 | + | 0.100 | + | 0.0714 | + | 0.0455 | - | 0.321 | + |
| 4,5,6 | - | 0.100 | - | 0.0714 | + | 0.1667 | - | -0.526 | - |
| 7,8,9 | + | 0.100 | - | 0.1667 | + | 0.1061 | + | 0.978 | + |
| 10 | - | 0.100 | - | 0.0714 | - | 0.0455 | + | -0.321 | - |
After three rounds the ensemble f=\operatorname{sign}(0.4236 f_1+0.6496 f_2+0.7520 f_3) classifies all ten training points correctly, although no single stump gets more than seven right. The first learner is wrong on 7,8,9. The second corrects those and is wrong on 4,5,6, which the third corrects.
Used in
- Taught in Ensembles, random forests, and boosting
- Questions that use it (1) — One round of AdaBoost
- All 7 questions on Ensembles, random forests, and boosting
See also
Decision tree · Boosting · Squared error of an average · Random forest · AdaBoost · The reweighted error is one half · Why averaging helps · Ensemble error decomposition