AdaBoost weight update

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

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

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:
1. 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.
2. Let \alpha_t=\frac12\log\frac{1-\varepsilon_t}{\varepsilon_t}.
3. 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).

Article: AdaBoost →

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.

Article: The reweighted error is one half →

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.

AdaBoost weight update

Used in

See also