AdaBoost

AdaBoost constructs an additive classifier by repeatedly fitting a base classifier to exponentially reweighted observations. Misclassified observations receive greater weight at the next iteration, and the final score is a nonnegative weighted sum of the base classifiers.

At score $F$, the exponential classification risk weights observation $i$ proportionally to $e^{-y_{i}F(x_i)}$. A stage $\alpha G$ multiplies this weight by $e^{-\alpha y_{i}G(x_i)}$. For weighted error $ϵ$, the loss multiplier is $(1-ϵ)e^{-\alpha }+ϵe^{\alpha }$, minimized at the displayed value. Its minimum is $2\sqrt{ϵ(1-ϵ)}$. Thus errors gain weight relative to correct observations in the next stage.

// Target: foundations-of-mathematics.bigb

For AdaBoost with initial uniform weights, labels and base predictions in $\{-1,1\}$, and edges ${\gamma }_m=1/2-{ϵ}_m>0$, the training exponential classification risk equals the product of stage normalizers. A wrongly classified point has exponential loss at least one, so empirical classification error is bounded by this product. The final inequality uses $\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$. The result concerns training error, not a guarantee against overfitting or mislabeled observations.

// Target: probability-and-statistics.bigb

For weighted binary data, a weak learner supplies a classifier whose weighted error is below one half. A uniform edge $\gamma >0$ for every weighting permits a quantitative AdaBoost training error bound. This training-weight condition is a separate assumption from merely having error below one half on the initial unweighted sample.

// Target: foundations-of-mathematics.bigb

For labels $Y\in \{-1,1\}$ and a real-valued score $f$, the exponential loss is $\varphi (Yf(X))=e^{-Yf(X)}$. Its population and empirical risks are