Machine Learning (13) — AdaBoost

Preface: Another ensemble idea—boosting. Boosting builds weak predictors (e.g. decision trees) stepwise and adds them with weights. If each weak model follows the loss gradient, it is gradient boosting (GBT/GBDT/GBRT). Boosting turns weak models into strong ones. Common algorithms: AdaBoost, Gradient Boosting.

AdaBoost

Adaptive Boosting iterates: each round trains a learner on weighted data; misclassified samples get higher weight, easy ones lower—hard examples matter more. Stop when error is small enough or max rounds reached. Sample reweighting:

Algorithm

AdaBoost combines base classifiers linearly; lower error → larger classifier weight α:

Final classifier applies sign to the combination:

Sign converts continuous score to class labels.

Sign function:

Loss counts misclassifications via indicator I:

Learner form:

Substitute into loss:

Minimize loss; partial derivatives give weights:

Solution:

e = weighted error in round k.

Final model:

Training procedure

• Training set T = {(X₁,Y₁), …, (Xₙ,Yₙ)}

• Initialize uniform sample weights

• Train base classifier on weighted data

• Compute weighted error of Gₘ(x)

• Classifier weight αₘ from error e

• Update sample weights:

Zₘ normalizes weights:

• Linear combination:

• Final classifier:

Summary

Two weight types: classifier weight α and sample weight (upweight misclassified points after normalization).

Example:

#-*- conding:utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles
## Chinese display (original)
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
## Data
X1, y1 = make_gaussian_quantiles(cov=2.,
                                 n_samples=200, n_features=2,
                                 n_classes=2, random_state=1)
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,
                                 n_samples=300, n_features=2,
                                 n_classes=2, random_state=1)

X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))
plot_step = 0.02
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
                     np.arange(y_min, y_max, plot_step))
bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1),
                         algorithm="SAMME.R",
                         n_estimators=200)
# max_depth 10–100 for large data; small data: shallow trees or fewer estimators
# n_estimators: weak learners (200 here)
# base_estimator: default CART
# algorithm: SAMME vs SAMME.R (probability-based weights, faster)
# learning_rate: 0

Bagging vs Boosting

• Sampling: Bagging bootstrap with replacement; Boosting same set, sample weights change by round from prior errors;

• Sample weights: Bagging equal per draw; Boosting increases weight on mistakes;

• Prediction: Bagging equal vote; Boosting weighted vote—accurate weak learners count more;

• Parallelism: Bagging parallel; Boosting sequential (needs prior model);

• Variance vs bias: Bagging reduces variance (strong base learners, overfitting); Boosting reduces bias (weak learners, underfitting).