Ensembles II: Boosting & AdaBoost

This pattern has two separate bumps of one class — a single split can only ever capture one boundary well. Dot size is each point's current weight: watch it grow on whatever the last round got wrong, and shrink on whatever it already handles. Each new round's split is chosen to serve exactly the biggest dots on the board.

This is boosting (specifically AdaBoost — short for Adaptive Boosting). Each round trains one weak learner — here, the exact single-split "stump" from Chapter 1 of this part, but scored by weighted error instead of information gain — then reweights the data before the next round:

• $\alpha_t$ — round $t$'s vote weight in the final combined prediction; a more accurate stump gets a bigger $\alpha_t$.
• $\epsilon_t$ — round $t$'s weighted error rate.
• $w_i$ — point $i$'s current weight, updated after every round.
• $y_i$ — point $i$'s true label.
• $h_t(x_i)$ — round $t$'s stump prediction on point $i$.

1. Vote weight scales with accuracy

   $\epsilon_t$ is round $t$'s weighted error; a more accurate stump gets a bigger $\alpha_t$ (more say in the final vote).

2. Reweighting re-tilts the data

   The weight update shrinks correctly-classified points and grows misclassified ones — each new stump is trained on data that's been re-tilted toward exactly what's still wrong.

Watch $\alpha$ and the combined accuracy together. A single round is stuck at 60% — genuinely weak. The final vote weights every round's opinion by its own $\alpha$, not just a plain majority, so a more confident round can outvote several less confident ones.

1. Find round 1's best stump and its weighted error

   Splitting at $x=3.5$ (predict A left, B right), it's wrong on 8 of 20 points — weighted error $\epsilon_1 = 8/20 = 0.4$, since every point starts at weight $1/20$.

2. Compute the stump's vote weight

   $$\alpha_1 = \frac{1}{2}\ln\frac{0.6}{0.4} \approx 0.203$$
3. Reweight the points

   For a point this stump got right, its new weight shrinks by $e^{-0.203} \approx 0.82$; for one it got wrong, its weight grows by $e^{0.203} \approx 1.22$.

4. Read the renormalized result

   Weights must sum to 1 again, so divide every point by the new total. With 12 correct points at $0.82/20$ each and 8 wrong points at $1.22/20$ each, that total is $12(0.82/20) + 8(1.22/20) = (9.84+9.76)/20 = 0.98$.

   Dividing each point's weight by that total gives the renormalized weight, which we compare against the average (uniform) weight of $1/20=0.05$:

   • Correct points: $(0.82/20)/0.98 \approx 0.0418$, which is $0.0418/0.05 \approx 0.83\times$ that average
   • Wrong points: $(1.22/20)/0.98 \approx 0.0624$, which is $\approx 1.25\times$ that average

   — exactly the size difference the next round's stump sees before it even starts.