Adaboost

Adaboost

1. Idea

Sequentially fit weak learners (stumps), each fixing prior mistakes. Misclassified points get higher weight; accurate learners get higher vote.

2. Algorithm

w_{i} = 1/n for all i
for m=1..M:
  fit stump f_{m} on weighted data
  err_{m} = weighted error; α_{m} = 0.5 log((1-err)/err)
  w_{i} = w_{i} exp(-α_{m} y_{i} f_{m}(x_{i})) then normalize
final: sign( sum α_{m} f_{m}(x) )

Low error → large $α$ (loud vote).

3. Properties

• Reduces bias (fits residuals of bias too).
• Sensitive to outliers / label noise (weights explode) — prefer GBM / RF on noisy data.
• Needs only stumps; $M$ by validation.

4. Worked

Stump 1: 60% acc → $α≈0.2$. Hard points upweighted ×1.5. Stump 2 fixes half of them → $α≈0.4$. Vote of 50 stumps → 90%.

5. Exam Points

• AdaBoost weight + vote update — 7 marks, very frequent.
• $α$ formula intuition — 3 marks, frequent.
• Noise sensitivity vs bagging — 3 marks, frequent.