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.

Whiteboard the AdaBoost weight: start from exponential loss, split samples into correct/misclassified, differentiate w.r.t. $\alpha_m$ to get $\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$

Derive the multiplicative update $w_i \leftarrow w_i e^{-\alpha_m y_i G_m(x_i)}$: multiply by $e^{-\alpha_m}$ (correct) vs $e^{\alpha_m}$ (wrong); why must weights be renormalized? What is the ratio of the two factors?

Why train the weak learner on weighted data? Why does the objective reduce to the weighted error rate for fixed $\alpha_m$?

Why exponential loss? Its surrogate relationship with 0-1 loss and log loss (LogitBoost), and the tradeoffs

Meaning of the training error bound $\prod_m 2\sqrt{e_m(1 - e_m)}$; the relationship between AdaBoost and additive models / GBDT