Boosting & AdaBoost

Source: Unit 3 §3

Boosting: the core idea

Boosting trains learners sequentially, each one learning from the mistakes of the previous one, and combines them with weights derived from accuracy or variance.

≡FactsThe mechanics in four lines

• Let a hypothesis $h_1$ misclassify some instances. The next learner $h_2$ is told "get $h_1$'s misclassified instances right" - by increasing the weights of the misclassified samples and decreasing the weights of the correctly classified ones.
• All sample weights must sum to 1.
• The weak learner is often a decision stump: one node, a single binary split. Boosting learns slowly and incrementally.
• The final classifier is a weighted summation of all the individual classifiers.

Each round re-weights the training set so the next stump is forced to look at what the last one got wrong. The points literally grow. The six points are schematic: each ε shown is the source's own value for that round, not a count of the red rings.

Boosting vs bagging

	Bagging	Boosting
Sampling	Every element has an equal probability	Observations are weighted, so some appear more often
Learners	Parallel, independent	Sequential, each learns from the previous
Goal	Reduce variance	Reduce bias (and variance)
Popular example	Random Forest	AdaBoost

AdaBoost: the algorithm

AdaBoost uses two sets of weights: instance weights (one per data point) and hypothesis weights $\alpha$ (one per learner).

→StepsThe AdaBoost loop

1. Start from ONE dataset. Initialize every instance weight to $w = 1/N$, where $N$ is the number of instances.
2. For a binary classifier, encode the labels as +1 (true) and −1 (false).
3. Build many decision stumps and choose the one with the lowest error rate; call it $h_1(x)$.
4. Compute the error rate $\varepsilon_m$, the weighted percentage of misclassified examples.
5. Compute the hypothesis weight $\alpha_m$.
6. Update the instance weights: up-weight the misclassified, down-weight the correct, then normalize so they sum to 1.
7. Repeat, so the next stump focuses on the previous stump's errors.
8. Finish with a weighted vote of all the hypotheses.

The formulas

Error of the $m$-th classifier, where $I(a,b) = 1$ if $a \neq b$ and 0 otherwise:

$$\varepsilon_m = \sum_n w_n^{(m)} \cdot I(\text{prediction}, \text{actual})$$

Hypothesis weight, also called the stump weight:

$$\alpha_m = \frac{1}{2} \ln\!\left( \frac{1 - \varepsilon_m}{\varepsilon_m} \right)$$

Instance weight update, then normalize by $N$ so the weights sum to 1:

$$w_{i+1} = w_i \cdot \exp\!\left( -\alpha \cdot \text{actual}_i \cdot \text{prediction}_i \right)$$

≡FactsWhich way the exponent pushes

• Correctly classified - $\text{actual} \cdot \text{prediction} = +1$, so multiply by $e^{-\alpha}$ and the weight decreases.
• Misclassified - $\text{actual} \cdot \text{prediction} = -1$, so multiply by $e^{+\alpha}$ and the weight increases.

Final hypothesis:

$$H(x) = \operatorname{sign}\!\left( \sum_m \alpha_m \cdot h_m(x) \right)$$

Worked arithmetic

→StepsTurning an error rate into a stump weight

1. Suppose the total weighted error is $\varepsilon = 0.3$.
2. $\alpha = \tfrac{1}{2} \ln\!\left[ (1 - 0.3) / 0.3 \right]$.
3. $(1 - 0.3)/0.3 = 2.333$.
4. $\tfrac{1}{2} \ln(2.333) = \tfrac{1}{2} \times 0.847 = \mathbf{0.42}$.
5. The next round from the slides: $\varepsilon = 0.21 \Rightarrow \alpha = \mathbf{0.65}$.

⚠GotchaThe slide rounds the second alpha down

The slide gives $\varepsilon = 0.21 \Rightarrow \alpha = 0.65$, but the formula gives $\tfrac{1}{2}\ln(0.79 / 0.21) = \tfrac{1}{2} \times 1.3250 = \mathbf{0.6625}$, which is 0.66. The method is unaffected and the four-round example below still comes out positive either way - $1.2375$ instead of $1.25$ - but quote 0.66 if you are asked to compute it yourself. The slide's 0.65 is kept below only because that is the number its worked example carries.

→StepsThe final prediction over 4 rounds

1. The four hypothesis weights are $\alpha = 0.42,\ 0.65,\ 0.38,\ 1.1$.
2. The four stumps vote $+1,\ -1,\ +1,\ +1$ on this instance.
3. Weighted sum: $0.42 \times 1 + 0.65 \times (-1) + 0.38 \times 1 + 1.1 \times 1 = 1.25$.
4. $\operatorname{sign}(1.25) = +1$, so the instance is labelled true and is correctly classified.

Alpha versus error

A perfect stump gets infinite weight, a coin-toss stump gets none, and a consistently wrong stump gets a negative weight so its vote is flipped.

Error rate ε	Stump weight α	What it means
0	+∞	A perfect classifier gets a huge weight
0.5	0	A coin toss is useless, so it gets zero weight
1	−∞	Always wrong, so its vote is strongly negated

◎Exam cueWhere α comes from

The stump weight $\alpha$ is derived by taking the partial derivative of the error with respect to the error. The shape that falls out is the one plotted above: better classifiers, meaning lower $\varepsilon$, get higher weight.

⚠GotchaBoosting can overfit; bagging does not

Unlike bagging, boosting can overfit. That is exactly why the hypothesis weights $\alpha_1, \alpha_2, \alpha_3, \ldots$ exist: they temper how much each learner is allowed to contribute to the final vote.