AdaBoost Derivation

AdaBoost fits the additive model $f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)$ by forward stagewise additive modeling under exponential loss $L_{\exp}(f) = \sum_{i=1}^{n} e^{-y_i f(x_i)}$. At round $m$, fixing $f_{m-1}$ and writing $w_i^{(m)} = e^{-y_i f_{m-1}(x_i)}$, we minimize $\sum_{i=1}^{n} w_i^{(m)} e^{-\alpha_m y_i G_m(x_i)}$. Splitting samples by correctness — correctly classified ($y_i G_m(x_i) = +1$) contribute $e^{-\alpha_m} w_i$, misclassified ($y_i G_m(x_i) = -1$) contribute $e^{\alpha_m} w_i$ — the objective becomes $e^{-\alpha_m}\left(W_m - \text{err}_m\right) + e^{\alpha_m} \text{err}_m$ with $W_m = \sum_{i=1}^{n} w_i^{(m)}$ and weighted misclassified mass $\text{err}_m = \sum_{y_i \neq G_m(x_i)} w_i^{(m)}$. Setting the derivative w.r.t. $\alpha_m$ to zero: $-e^{-\alpha_m}\left(W_m - \text{err}_m\right) + e^{\alpha_m} \text{err}_m = 0$, so $e^{2\alpha_m} = \frac{W_m - \text{err}_m}{\text{err}_m}$; with the weighted error rate $e_m = \frac{\text{err}_m}{W_m}$ we get $\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$ — more accurate weak learners ($e_m \to 0$) get larger weights, random guessing ($e_m = 0.5$) gets weight 0, worse-than-random ($e_m > 0.5$) gets a negative weight (flip the prediction). For fixed $\alpha_m > 0$ the objective in $G_m$ reduces to $\sum_{i=1}^{n} w_i^{(m)} \mathbb{1}\left[y_i \neq G_m(x_i)\right]$ — the weighted classification error, which justifies training the weak learner on weighted data each round. Weight update: $w_i^{(m+1)} = w_i^{(m)} e^{-\alpha_m y_i G_m(x_i)}$, i.e. multiply correct samples by $e^{-\alpha_m} = \sqrt{\frac{e_m}{1 - e_m}} < 1$ and misclassified samples by $e^{\alpha_m} = \sqrt{\frac{1 - e_m}{e_m}} > 1$, then renormalize by $W_{m+1}$. Final classifier: $G(x) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)$. Exponential loss is a convex upper bound of 0-1 loss ($e^{-yf} \geq \mathbb{1}[yf < 0]$) and is smooth, aligning weighted training with gradient descent in function space.

deriving the AdaBoost weights is a whiteboard classic — follow-ups include where the objective comes from, why we differentiate w.r.t. $\alpha_m$, why the weight update is multiplicative, why normalization is required, and the link to GBDT.

a single weak learner (e.g. depth-1 stump) is barely better than random — AdaBoost's iterative reweighting focuses training on misclassified samples and drives the training error down exponentially fast with the bound $\prod_{m=1}^{M} 2\sqrt{e_m(1 - e_m)}$: as long as $e_m < 0.5$ (the weak-learner condition), error goes to zero as $M$ grows, boosting weak learners into an arbitrarily accurate strong classifier; the cost is that exponential loss is overly sensitive to noise/outliers (misclassified weights explode), which motivated LogitBoost's log-likelihood loss and GBDT's negative-gradient framework.

Test Your Knowledge: Practice Questions for "AdaBoost Derivation"

Single choice pitfall questions with instant feedback and mistake tracking.