AdaBoost

AdaBoost combines many weak learners, usually one-split trees, into a strong classifier. Each new learner pays extra attention to the points the previous ones got wrong.

The idea

Think of revising for an exam with flashcards. After each round you move the cards you missed to the front, so the next round focuses on them. You only stop worrying about a card once you keep getting it right.

AdaBoost does this with point weights. Misclassified points get heavier, so the next learner is pushed to fix them. Each learner also gets a say in the final vote that grows with its accuracy.

How it learns

  1. Give every point the same weight.
  2. Fit a small tree that minimises the weighted error.
  3. Compute its weighted error ε\varepsilon and its voting power α\alpha (scaled by the learning rate).
  4. Increase the weights of misclassified points, decrease the rest, and renormalise.
  5. Repeat for the chosen number of learners; predict with a weighted vote.

Reading the picture

With Size points by weight on, each point's size shows how much the current round cares about it. Watch the hard points near the boundary swell while easy ones shrink.

The background shows the sign of the weighted vote, shaded by its strength. Because each learner is a stump or a shallow tree, the boundary is built from axis-aligned steps that become finer as learners are added.

Try this

  1. On Circles with Learner depth 1, press step a few times. Each stump is a single straight cut, yet together they start to enclose the ring.
  2. Keep Size points by weight on and play to the end. The biggest points are the ones the ensemble still finds hardest.
  3. Set Learning rate to 0.1. Learners get a smaller say, so you need many more of them to reach the same boundary.
  4. Try XOR with Learner depth 1 and then 2. A single stump has weighted error near 50% here, so depth 2 helps a lot.

The maths

Weighted error

εm=∑iwi⋅1[hm(xi)≠yi]\varepsilon_m = \sum_i w_i \cdot \mathbf{1}[h_m(x_i) \ne y_i]

Learner weight

αm=η⋅12ln⁡(1−εmεm)\alpha_m = \eta \cdot \frac{1}{2} \ln\left(\frac{1 - \varepsilon_m}{\varepsilon_m}\right)

Reweight

wi←wi⋅exp⁡(αm1[miss]−αm1[hit]),then normalisew_i \leftarrow w_i \cdot \exp\big(\alpha_m \mathbf{1}[\text{miss}] - \alpha_m \mathbf{1}[\text{hit}]\big), \quad \text{then normalise}

Final vote

H(x)=sign⁡(∑mαmhm(x)),hm(x)∈{−1,+1}H(x) = \operatorname{sign}\Big(\sum_m \alpha_m h_m(x)\Big), \quad h_m(x) \in \{-1, +1\}

Strengths and weaknesses

Good at

  • Turns very weak learners into a strong classifier.
  • Few hyperparameters and no feature scaling.
  • Point weights reveal which examples are hard.

Struggles with

  • Very sensitive to label noise and outliers.
  • Learners are sequential, so it is hard to parallelise.
  • This version handles two classes only.