AdaBoost

Definition

Start with $D^{(1)}=(\frac{1}{m},\dots ,\frac{1}{m})$. In round $t$: $h_t=\mathrm{WL}(D^{(t)})$, ${\epsilon }_t={\sum }_i{D}_i^{(t)}1[y_i\ne h_t(x_i)]$, $w_t=\frac{1}{2}\log (\frac{1}{{\epsilon }_t}-1)$, $D_i^{(t+1)}\propto D_i^{(t)}{e}^{-w_t{y}_i{h}_t(x_i)}$ (normalized). Output $\mathrm{sign}({\sum }_t{w}_t{h}_t(x))$. A weak learner has error $\le \frac{1}{2}-\gamma$.

Formula

$$\text{training error}\le Z_T=\prod _{t}2\sqrt{{\epsilon }_t(1-{\epsilon }_t)}\le \exp (-2{\gamma }^{2}T)$$

• By hand: wrong points get $D_i/(2{\epsilon }_t)$, correct points $D_i/(2(1-{\epsilon }_t))$; the mistakes always carry weight $\frac{1}{2}$ afterwards.
• ${\epsilon }_t=\frac{1}{2}$ gives $w_t=0$ and no progress (stumps on XOR).
• Test error: VC bound with $\mathrm{VC}({\mathcal{H}}_T)\lesssim T{d}_{\mathcal{B}}\log (T{d}_{\mathcal{B}})$, or the margin bound without $T$.
• AdaBoost = stagewise additive modeling with the exponential loss. Weak and strong PAC learnability are equivalent.

Appears in

• Lecture 6, weak and strong (PAC) learners
• Lecture 6, algorithm and update by hand
• Lecture 6, exam-style task
• Lecture 6, Theorem 1 (training error of AdaBoost) and proof
• Lecture 6, VC bound
• Lecture 6, margin bound
• Lecture 1.1, the exponential loss

Related concepts

• Gradient Boosting
• Surrogate Loss
• Margin