AdaBoost as forward stagewise fitting

Section of Ensembles, random forests, and boosting, part of Statistical learning

Type	Section
Taught in	Ensembles, random forests, and boosting
Part	Statistical learning

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.

AdaBoost as forward stagewise fitting

Used in

See also