AdaBoost

Definition

The AdaBoost (Adaptive Boosting) is the weighted sum of weak learners that are robust to outliers and noise.

Algorithm

Consider a 2-class problem with $Y\in \{-1,1\}$

1. Initialize the weights $w_i=\frac{1}{n},i=1,2,\dots ,n$
2. Repeat for $m=1,2,\dots ,M$:
   1. Fit a weak classifier $\delta$ that minimizes the weighted error rate $\text{err}=\sum _{i=1}^n{w}_{i}I(y_i\ne \delta (x_i))$ and call the fitted classifier $f_m$, and its corresponding error rate ${\text{err}}_m$
   2. Compute $c_m=\ln \left(\frac{1-{\text{err}}_m}{{\text{err}}_m}\right)=\mathrm{logit}(1-{\text{err}}_m)$
   3. Update the weights $w_i$ by $w_i=\frac{w_i\exp [c_{m}I(y_i\ne f_m(X_i))]}{\sum _{j=1}^n{w}_j\exp [c_{m}I(y_j\ne f_m(X_j))]}$
3. Output the classifier $f(x)=\mathrm{sgn}\left(\sum _{m=1}^M{c}_m{f}_m(x)\right)$

Facts

AdaBoost is equivalent to Gradient Boosting using the exponential loss $L(y,f(x))=\exp (-yf(x))$