Boosting
Section of Ensembles, random forests, and boosting, part of Statistical learning
Boosting
| Type | Section |
| Taught in | Ensembles, random forests, and boosting |
| Part | Statistical learning |
| Questions using it | 1 |
A random forest draws its diversity from different samples and different candidate predictors. The members are fit separately, and none of them is told where the others failed. The diversity identity suggests a sharper use of the same idea: the members should be reasonably accurate and should be accurate in different regions, so that each compensates for the others. Boosting builds that compensation on purpose. Fit one learner. Find the training cases it gets wrong, or the residuals it leaves. Fit the next learner to those mistakes, without abandoning the cases the first one already got right. Continue, and combine the sequence. The learners are not exchangeable draws. Later ones exist because earlier ones failed somewhere.
Schapire (1990) showed that a weak learner can be improved by an ensemble built this way. The concrete algorithm is Adaptive Boosting, AdaBoost (Freund and Schapire, 1995). Bagging reduces variance by averaging unstable fits of the same problem. Boosting changes the problem at each round.
The AdaBoost weight update
Main article: AdaBoost weight update
AdaBoost needs a coding on which a correct label and a predicted label multiply to +1 when they agree and to -1 when they disagree. Record the two classes as y_i\in\{-1,+1\}. The label vector has one entry per training observation, so it lies in \{-1,+1\}^{n_{\mathrm{train}}}. The integer p is the number of predictors, not the length of y.
At iteration t the learner f_t is fit to the training cases with weights w_{t,i}. The weights are a distribution over the training sample: they are non-negative and, after the normalisation in the algorithm, they sum to 1. A case the previous learner missed has its weight increased. A case it got right has its weight decreased. The next learner is therefore aimed at the current mistakes and is not released from the rest of the sample. The size of the increase is chosen so that, under the new weights, the learner just fitted has weighted error exactly 1/2. That property is why the particular factor \alpha_t appears, rather than an arbitrary step length.
Definition 1 (AdaBoost) Training data \{x_i,y_i\}_{i=1}^{n_{\mathrm{train}}}, with x_i\in\mathbb{R}^p and y_i\in\{-1,+1\}.
- Set w_{1,i}=1/n_{\mathrm{train}} for all i.
- For t=1,\ldots,T:
- Fit a learner f_t, taking values in \{-1,+1\}, to minimise the weighted training error \varepsilon_t =\frac{\sum_i w_{t,i}\,Q[y_i,f_t(x_i)]}{\sum_i w_{t,i}}, where Q[a,b]=0 if a=b and Q[a,b]=1 otherwise.
- Let \alpha_t=\frac12\log\frac{1-\varepsilon_t}{\varepsilon_t}.
- Update the weights. A correct case is multiplied by e^{-\alpha_t} and an incorrect case by e^{\alpha_t}, which is the single factor e^{-\alpha_t y_i f_t(x_i)}: w_{t+1,i} =\frac{w_{t,i}\,e^{-\alpha_t y_i f_t(x_i)}}{Z_t}, \qquad Z_t=\sum_{i=1}^{n_{\mathrm{train}}} w_{t,i}\,e^{-\alpha_t y_i f_t(x_i)}.
The ensemble is the sign of the weighted vote,
f(x)=\operatorname{sign}\Biggl(\sum_{t=1}^T \alpha_t f_t(x)\Biggr).
Because \alpha_t=\frac12\log((1-\varepsilon_t)/\varepsilon_t), one has e^{-\alpha_t}=\sqrt{\varepsilon_t/(1-\varepsilon_t)}, the square root of the weighted odds of an error, and e^{\alpha_t}=\sqrt{(1-\varepsilon_t)/\varepsilon_t}. The ratio of the new un-normalised weight of a correct case to that of an incorrect case, relative to their old weights, is \varepsilon_t/(1-\varepsilon_t). Freund and Schapire’s original weights put \varepsilon_t/(1-\varepsilon_t) on the correct cases and 1 on the incorrect cases. After normalisation that is the same distribution. If \varepsilon_t<1/2, then \varepsilon_t/(1-\varepsilon_t)<1, and the incorrect cases gain weight. A two-class learner that cannot beat \varepsilon_t=1/2 is no better than a coin toss on the current weighted sample, so a usable round satisfies \varepsilon_t<1/2 and the update emphasises the mistakes. If a round has \varepsilon_t>1/2, its vote \alpha_t is negative, which is the algorithm voting the opposite of that learner.
Theorem 1 (The reweighted error is one half) If 0<\varepsilon_t<1 and the current weights sum to 1, the updated weights give f_t weighted error exactly 1/2. For the usual positive-vote round, require 0<\varepsilon_t<1/2. At zero error the logarithm has no finite value: stop, or handle the perfect learner explicitly.
Assume the current weights sum to 1, so the incorrect cases carry total weight \varepsilon_t and the correct cases carry 1-\varepsilon_t. From the formula for \alpha_t, e^{2\alpha_t}=(1-\varepsilon_t)/\varepsilon_t. The un-normalised weight of the incorrect cases is
\varepsilon_t\,e^{\alpha_t} =\varepsilon_t\sqrt{\frac{1-\varepsilon_t}{\varepsilon_t}} =\sqrt{\varepsilon_t(1-\varepsilon_t)},
and the un-normalised weight of the correct cases is
(1-\varepsilon_t)\,e^{-\alpha_t} =(1-\varepsilon_t)\sqrt{\frac{\varepsilon_t}{1-\varepsilon_t}} =\sqrt{\varepsilon_t(1-\varepsilon_t)}.
The two totals agree. After dividing by their sum, each group carries weight 1/2. The normaliser is Z_t=2\sqrt{\varepsilon_t(1-\varepsilon_t)}. The weighted error of f_t under the new weights is the weight of the incorrect group, which is 1/2.
What the equality establishes is a property of this particular \alpha_t, not a property of every reweighting. Under the new weights the learner just fitted is no better than guessing on the problem the next learner will see. The next learner has to use some other structure. The assumption that did the work is \alpha_t=\frac12\log((1-\varepsilon_t)/\varepsilon_t), together with a weighted error \varepsilon_t computed from weights that sum to 1. Other weight updates can also produce a useful ensemble. This one is, in addition, the stagewise step for exponential loss.
Example 1 (Three rounds of AdaBoost with stumps) 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.
Exponential loss
Main article: Exponential loss
The factor \varepsilon_t/(1-\varepsilon_t) was a choice in the original algorithm. Friedman, Hastie, and Tibshirani (2000) supplied the loss that produces it. The population criterion is the exponential loss
J(f)=\mathbb{E}\bigl[e^{-Y f(X)}\bigr],
where (X,Y) is a fresh draw, Y\in\{-1,+1\}, and f(x) is a real-valued score, positive when the classifier leans toward class +1. Exponential loss charges e^{-yf}. A negative margin yf is a mistake, and a large negative margin is punished exponentially, while a large positive margin is almost free. That emphasis on the worst mistakes is why the loss matches a procedure that keeps raising the weights of the cases it gets wrong.
With \tau_1(x)=\mathbb{P}(Y=1\mid x), the conditional expected loss is an average of two exponentials:
\mathbb{E}\bigl[e^{-Y f(x)}\bigm|x\bigr] =\tau_1(x)\,e^{-f(x)}+\bigl(1-\tau_1(x)\bigr)\,e^{f(x)}.
The score wanted minimises this conditional loss at every x. Differentiate in the scalar f=f(x):
\frac{\partial}{\partial f}\mathbb{E}\bigl[e^{-Yf}\bigm|x\bigr] =-\tau_1 e^{-f}+(1-\tau_1)e^{f}.
The second derivative is \tau_1 e^{-f}+(1-\tau_1)e^{f}>0, so the single stationary point is a minimum. Set the first derivative to zero:
(1-\tau_1)e^{f}=\tau_1 e^{-f}, \qquad e^{2f}=\frac{\tau_1}{1-\tau_1}, \qquad f^*(x)=\frac12\log\frac{\tau_1(x)}{1-\tau_1(x)}.
The minimiser is half the conditional log odds of class 1. The posterior \tau_1(x) did the work: it is the only feature of the conditional distribution of Y that enters the expected exponential loss, because Y takes only two values. When the log odds are 0, one has \tau_1(x)=1/2 and f^*(x)=0. The sign of f^* is therefore the equal-cost Bayes rule, which is why the ensemble classifies by \operatorname{sign}(f). Inverting the half-logit recovers the probability,
\tau_1(x)=\frac{1}{1+e^{-2f^*(x)}}, \qquad 1-\tau_1(x)=\frac{1}{1+e^{2f^*(x)}}.
Exponential loss does not estimate the class densities. It estimates the same posterior comparison that logistic regression writes as a logit, up to the factor 1/2.
The weight update is a stagewise step
Main article: AdaBoost as forward stagewise fitting
The population minimiser is not a finite combination of weak learners. AdaBoost builds an approximation one learner at a time. Replace the expectation by the training average
\widehat J(f)=\frac{1}{n_{\mathrm{train}}}\sum_{i=1}^{n_{\mathrm{train}}} e^{-y_i f(x_i)},
drop the outer sign, and let the ensemble score be g(x)=\sum_{t=1}^T\alpha_t f_t(x), with each f_t taking values in \{-1,+1\}. After m-1 rounds the score is g_{m-1}, and round m adds one term, g_m=\alpha_m f_m+g_{m-1}. Minimise the training exponential loss in that one new term, holding g_{m-1} fixed. Factor the loss as
\widehat J(g_m) =\frac{1}{n_{\mathrm{train}}}\sum_{i=1}^{n_{\mathrm{train}}} e^{-y_i g_{m-1}(x_i)}\,e^{-y_i\alpha_m f_m(x_i)}.
The first factor in each summand, c_{m,i}=e^{-y_i g_{m-1}(x_i)}, does not depend on the new learner. These weights are proportional to the AdaBoost weights w_{m,i}: the cases with negative margin under the ensemble so far carry larger c_{m,i}. The constant 1/n_{\mathrm{train}} does not change the minimiser. On a correct case y_i f_m(x_i)=1, so e^{-y_i\alpha_m f_m}=e^{-\alpha_m}. On an incorrect case y_i f_m(x_i)=-1, so the factor is e^{\alpha_m}. The criterion in (f_m,\alpha_m) is therefore
\begin{align*} \sum_i c_{m,i}\,e^{-y_i\alpha_m f_m(x_i)} &=e^{-\alpha_m}\sum_{y_i=f_m(x_i)}c_{m,i} +e^{\alpha_m}\sum_{y_i\ne f_m(x_i)}c_{m,i}\\ &=e^{-\alpha_m}\sum_i c_{m,i} +\bigl(e^{\alpha_m}-e^{-\alpha_m}\bigr)\sum_i c_{m,i}\,Q[y_i,f_m(x_i)]. \end{align*}
The rewriting uses \sum_{\mathrm{correct}}c=\sum_i c-\sum_{\mathrm{incorrect}}c. For \alpha_m>0 the coefficient e^{\alpha_m}-e^{-\alpha_m} is positive, so the sum is smallest, for that fixed \alpha_m, when the weighted error is smallest. The learner can therefore be chosen first:
f_m^*=\operatorname{arg\,min}_{f_m}\sum_i c_{m,i}\,Q[y_i,f_m(x_i)],
which is the weighted-error step of the algorithm. With that learner held fixed, write \varepsilon_m for the minimised weighted error, \sum_i c_{m,i}Q[y_i,f_m^*(x_i)]/\sum_i c_{m,i}. Dividing the criterion by \sum_i c_{m,i} leaves
e^{-\alpha_m}+\bigl(e^{\alpha_m}-e^{-\alpha_m}\bigr)\varepsilon_m.
Differentiate in \alpha_m and set the derivative to zero:
-e^{-\alpha_m}+\bigl(e^{\alpha_m}+e^{-\alpha_m}\bigr)\varepsilon_m=0,
which rearranges to e^{\alpha_m}\varepsilon_m=e^{-\alpha_m}(1-\varepsilon_m), hence
e^{2\alpha_m}=\frac{1-\varepsilon_m}{\varepsilon_m}, \qquad \alpha_m^*=\frac12\log\frac{1-\varepsilon_m}{\varepsilon_m}.
That is the coefficient step of the algorithm. The ensemble is updated by g_m=\alpha_m^* f_m^*+g_{m-1}. The next round’s un-normalised weights are the old ones times the new exponential factor,
c_{m+1,i}=c_{m,i}\,e^{-\alpha_m^* y_i f_m^*(x_i)}.
Because f_m^* and y_i lie in \{-1,+1\}, -y_i f_m^*(x_i)=2Q[y_i,f_m^*(x_i)]-1: the product y_i f_m^* is +1 when the learner is correct and -1 when it is wrong. Therefore
\begin{align*} e^{-\alpha_m^* y_i f_m^*(x_i)} &=e^{\alpha_m^*\bigl(2Q[y_i,f_m^*(x_i)]-1\bigr)} =e^{2\alpha_m^* Q[y_i,f_m^*(x_i)]}\,e^{-\alpha_m^*}\\ &=\Biggl(\frac{1-\varepsilon_m}{\varepsilon_m}\Biggr)^{Q[y_i,f_m^*(x_i)]}\,e^{-\alpha_m^*}. \end{align*}
The factor e^{-\alpha_m^*} multiplies every weight and cancels when the weights are normalised. Every misclassified case, where Q=1, is multiplied by (1-\varepsilon_m)/\varepsilon_m, and every correctly classified case, where Q=0, is left unchanged. After normalisation this is the original AdaBoost update.
What the stagewise argument establishes is that the algorithm is greedy minimisation of the training exponential loss, one weak learner at a time. The exponential form of the loss did the work: it factors across rounds into a weight that depends on the margin so far and a factor that depends on the new learner. A different loss would produce a different weight update. The fit is greedy. It does not go back and revise \alpha_1,\ldots,\alpha_{m-1} when round m is added.
AdaBoost adds a weighted learner to a real-valued score. Exponential loss explains the reweighting and the coefficient \alpha_t. Its unrestricted population minimiser is half the conditional log odds. The final sign is a class label and cannot estimate that real number. A finite, restricted, stagewise fit need not attain the population minimiser or produce calibrated probabilities.
Real AdaBoost, and a logistic comparison
Main article: Real AdaBoost, and a logistic comparison
AdaBoost as written asks each learner for a label in \{-1,+1\}. A probability p_t(x) carries more information than that label, and throwing it away is the step that fails when the learner is already able to say how sure it is. Real AdaBoost keeps the probability and converts it to the same half-logit that minimises exponential loss,
f_t(x)=\frac12\log\frac{p_t(x)}{1-p_t(x)}.
There is no separate vote \alpha_t, because the magnitude of f_t(x) already records the confidence at that x. The weight update is the exponential-loss factor itself,
w_{t+1,i}=\frac{w_{t,i}\,e^{-y_i f_t(x_i)}}{Z_t}, \qquad Z_t=\sum_i w_{t,i}\,e^{-y_i f_t(x_i)}.
The ensemble adds the scores and then takes the sign, f(x)=\operatorname{sign}\bigl(\sum_{t=1}^T f_t(x)\bigr).
A loss-based view lets the loss change while sequential fitting stays. With the score convention p=\sigma(2f), where \sigma is the logistic function, logistic negative log-likelihood and exponential loss have the same unrestricted population minimiser. Binomial deviance is twice the negative log-likelihood relative to a saturated model. The constant factor changes neither minimiser. The derivation below uses negative log-likelihood, without that factor two. Let p(x)=\tau_1(x) and Y'=(Y+1)/2\in\{0,1\}, so Y' is the 0/1 label used in logistic regression. The log-likelihood of one case is Y'\log p+(1-Y')\log(1-p). Substitute p=1/(1+e^{-2f}), so 1-p=1/(1+e^{2f}). Minus that log-likelihood becomes
-\ell(Y,p) =Y'\log\bigl(1+e^{-2f}\bigr)+(1-Y')\log\bigl(1+e^{2f}\bigr).
If Y'=1, then Y=1 and the expression is \log(1+e^{-2Yf}). If Y'=0, then Y=-1 and it is \log(1+e^{2f})=\log(1+e^{-2Yf}). Both cases are therefore
-\ell\bigl(Y,p(x)\bigr)=\log\bigl(1+e^{-2Y f(x)}\bigr).
The population minimisers agree. Both losses are minimised by half the conditional log odds, so with enough data a procedure that truly minimises either loss estimates the same f^*. The finite-sample paths differ, because the losses grow differently as the margin becomes more negative, and the stagewise weights follow the loss that is being minimised.
AdaBoost reweights the training cases at every round. A weak round, one with \varepsilon_t near 1/2, receives a small vote \alpha_t=\frac12\log((1-\varepsilon_t)/\varepsilon_t), and the next round faces a weighted problem on which the previous learner scores exactly 1/2.
Plot the losses against the margin yf, where y\in\{-1,+1\} is the correct label and f is the score before the threshold at 0 converts it to a label. A positive margin is a correct classification. A negative margin is a mistake, and a loss used for training should charge it. Squared error (y-f)^2 equals (1-yf)^2 when y\in\{-1,+1\}, because y^2=1. As a function of a real-valued score it is a parabola in the margin, minimised at yf=1, so a more confident correct call, with yf>1, is penalised more rather than less. Exponential loss grows exponentially as the margin falls below zero, so the fit concentrates on the worst mistakes. When the Bayes error is not near zero, some of those mistakes are unavoidable under any classifier, and concentrating on them fits noise. Binomial deviance, the logistic negative log-likelihood above, grows only linearly in the negative margin, so it is the milder penalty in that regime. Hinge loss is zero once the margin exceeds 1, and linear below that. Both exponential and logistic losses extend to more than two classes. The algorithms that minimise them by adding a weak learner, usually a tree, along the gradient of the training loss are collected under the name gradient boosting. In those programs the penalty on tree size and the limit on depth are tuning choices, selected by cross-validation or by a validation set. They are not consequences of the population minimiser.
Training classification error and training exponential loss are different criteria. A one-dimensional simulation can drive the training error to zero while the exponential loss is still moving, and the final observation weights concentrate on the points the early rounds found difficult.
Used in
- Taught in Ensembles, random forests, and boosting
- Questions that use it (1) — Why an ensemble might improve a tree
- All 7 questions on Ensembles, random forests, and boosting
See also
Decision stump · Ensemble method · Gradient boosting · Squared error of an average · Random forest · AdaBoost · The reweighted error is one half · Why averaging helps