Boosting

Boosting builds an accurate classifier from many weak ones. A weak learner returns rules that are only slightly better than chance, such as a single threshold on one feature of an image patch. Boosting calls it repeatedly, each time on a reweighted version of the training set that stresses the examples the earlier rules got wrong, and combines the rules by a weighted vote. AdaBoost (adaptive boosting), introduced by Freund and Schapire, is the classic algorithm; its training error falls exponentially with the number of rounds as long as every rule beats chance by a fixed amount, and it later turned out to fit an additive model by minimizing an exponential loss. Generalizing that view to any differentiable loss gives gradient boosting, which fits a sum of small regression trees and which scikit-learn’s user guide recommends in particular for tabular data. Boosted decision stumps, boosted trees and gradient-boosted trees are all instances.

In vision, boosting is best known from the Viola–Jones face detector, where each weak classifier is a threshold on one Haar-like feature, so that boosting also selects the few features worth computing out of more than a hundred thousand candidates. This article covers boosting as a learning method: AdaBoost, its training-error bound, the loss and margin explanations of why it works, its multiclass and gradient forms, its sensitivity to wrong labels, and its uses in vision. It assumes the ideas of machine learning (training and test error, generalization), and links to the Viola–Jones article for the detector and its cascade rather than repeating them.

Problem

Boosting began as a question in computational learning theory. In the probably approximately correct (PAC) model, a class of concepts is strongly learnable if an efficient algorithm can, with high probability, output a hypothesis with arbitrarily small error, and weakly learnable if it can only guarantee an error slightly below one half. Kearns and Valiant introduced weak learnability and left open whether the two notions are equivalent; Schapire (1990), whose account this follows, notes that the question was called the hypothesis boosting problem, because a yes answer requires a way to boost the accuracy of a weak learner.

Schapire answered yes, constructively. Train the weak learner once and call the result $h_1$. Train it again on a filtered distribution on which $h_1$ is right half of the time and wrong half of the time, giving $h_2$, and a third time only on examples where $h_1$ and $h_2$ disagree, giving $h_3$. The majority vote of the three has error at most $g(a) = 3a^2 - 2a^3$ when each has error at most $a$ on the distribution it was trained on, which is smaller than $a$ for $a < \tfrac{1}{2}$, and applying the construction recursively drives the error as low as desired. Freund’s boost-by-majority algorithm improved the efficiency, but, as Freund and Schapire (1997) point out, it needs the weak learner’s worst-case advantage to be known in advance and cannot profit from rules that are better than that. AdaBoost removed the requirement: it measures each rule’s error as it goes and sets that rule’s vote and the next reweighting from it.

In practice the problem is a supervised classification problem: given labelled images or image windows, build a classifier from a family of simple rules that are easy to fit and cheap to evaluate, but individually poor.

Inputs and Outputs

Training takes $n$ labelled examples $(\mathbf{x}_i, y_i)$, here with labels $y_i \in \{-1, +1\}$ as in the AdaBoost literature; a weak learner that accepts example weights and returns a classifier $h: \mathcal{X} \to \{-1, +1\}$, usually a decision stump (a threshold on one feature) or a small decision tree; and the number of rounds $T$. The examples are rows of a data matrix $X \in \mathbb{R}^{n \times d}$, one image or patch descriptor per row, as scikit-learn stores them.

The output is the weighted vote

$$F(\mathbf{x}) = \sum_{t=1}^{T} \alpha_t h_t(\mathbf{x}), \qquad H(\mathbf{x}) = \operatorname{sign} F(\mathbf{x}),$$

a list of $T$ weak classifiers with their votes $\alpha_t$. $F(\mathbf{x})$ is a real-valued score: its sign is the class, its magnitude a measure of confidence, and its threshold can be moved to trade false positives for misses, as the stages of a detection cascade do.

Intuition

A single threshold on one rectangle feature of a face window, such as “the band across the eyes is darker than the band below it”, is right on most faces but also fires on many non-faces. Boosting asks the next question about the cases this rule gets wrong. It raises their weights and looks for the rule with the lowest weighted error, which is a rule that does well on exactly those cases. Rules that turned out more accurate get a larger say in the final vote.

Each reweighting deliberately makes the last rule useless: after AdaBoost’s update the most recent rule has a weighted error of exactly one half under the new weights (Freund and Schapire’s footnote to the algorithm), so the next rule must find information the previous one did not provide. The weights of examples that keep being misclassified grow round after round, which is what drives the training error down and also why mislabelled examples end up dominating the weights.

Algorithm

Discrete AdaBoost for labels $y_i \in \{-1, +1\}$, in the form Schapire (2013) gives:

1. Set the weights $D_1(i) = 1/n$ for $i = 1, \dots, n$.
2. For $t = 1, \dots, T$:
   1. Train the weak learner with weights $D_t$ and get $h_t: \mathcal{X} \to \{-1, +1\}$.
   2. Compute its weighted error $\varepsilon_t = \sum_{i:\, h_t(\mathbf{x}_i) \neq y_i} D_t(i)$.
   3. Set its vote $\alpha_t = \tfrac{1}{2} \ln \frac{1 - \varepsilon_t}{\varepsilon_t}$.
   4. Update the weights $D_{t+1}(i) = D_t(i) \exp(-\alpha_t y_i h_t(\mathbf{x}_i)) / Z_t$, where $Z_t$ makes them sum to one.
3. Output $H(\mathbf{x}) = \operatorname{sign} \sum_{t=1}^{T} \alpha_t h_t(\mathbf{x})$.

Since $y_i h_t(\mathbf{x}_i)$ is $+1$ for a correct prediction and $-1$ for a mistake, step 4 multiplies the weight of every mistake by $e^{\alpha_t}$ and of every correct example by $e^{-\alpha_t}$ before normalizing. When $\varepsilon_t < \tfrac{1}{2}$, $\alpha_t > 0$; a rule with error exactly one half gets no vote.

Other sources write the same algorithm differently. The Elements of Statistical Learning (Algorithm 10.1, “AdaBoost.M1”) uses the vote $\log((1 - \varepsilon_t)/\varepsilon_t)$, twice the value above, and multiplies only the weights of the mistakes by its exponential; the normalized weights and the sign of the vote are the same. Freund and Schapire’s original paper uses labels $\{0, 1\}$ and a factor $\beta_t = \varepsilon_t/(1 - \varepsilon_t)$ applied to the correct examples, which is again equivalent after normalization; Viola and Jones’s version, set out in the Viola–Jones article, follows that form.

Mathematical Formulation

The training-error bound

Unrolling the weight update gives $D_{T+1}(i) = \exp(-y_i F(\mathbf{x}_i)) / (n \prod_t Z_t)$, and since the weights sum to one,

$$\frac{1}{n} \sum_{i=1}^{n} e^{-y_i F(\mathbf{x}_i)} = \prod_{t=1}^{T} Z_t .$$

A mistake has $y_i F(\mathbf{x}_i) \le 0$ and so $e^{-y_i F(\mathbf{x}_i)} \ge 1$; the training error is therefore at most $\prod_t Z_t$. Each normalizer is $Z_t = (1 - \varepsilon_t) e^{-\alpha_t} + \varepsilon_t e^{\alpha_t}$, which the vote $\alpha_t$ above minimizes, and at that minimum $Z_t = 2\sqrt{\varepsilon_t (1 - \varepsilon_t)}$ (Schapire, Freund, Bartlett and Lee, 1998, §3). Hence

$$\frac{1}{n} \left| \{ i : H(\mathbf{x}_i) \neq y_i \} \right| \;\le\; \prod_{t=1}^{T} 2\sqrt{\varepsilon_t (1 - \varepsilon_t)} \;=\; \prod_{t=1}^{T} \sqrt{1 - 4\gamma_t^2} \;\le\; \exp\!\Big(-2 \sum_{t=1}^{T} \gamma_t^2\Big),$$

with $\varepsilon_t = \tfrac{1}{2} - \gamma_t$. This is Freund and Schapire’s bound, which they state as $\epsilon \le 2^T \prod_t \sqrt{\epsilon_t (1 - \epsilon_t)}$ for the error under the initial distribution (Theorem 6 in the authors’ manuscript), together with the exponential forms. If every weak rule has an edge $\gamma_t \ge \gamma > 0$, the training error falls at least as fast as $e^{-2T\gamma^2}$ and is zero once the bound drops below $1/n$. The bound holds for any errors $\varepsilon_t$, and, as Freund and Schapire stress, it depends on the errors of all the rules, not only on the worst, which is the sense in which AdaBoost is adaptive.

Exponential loss and forward stagewise additive modelling

Friedman, Hastie and Tibshirani (2000) showed that AdaBoost fits an additive model $F(\mathbf{x}) = \sum_t \alpha_t h_t(\mathbf{x})$ in a forward stagewise way: each round adds one term and never revisits the earlier ones. The criterion is the exponential loss

$$L(y, F(\mathbf{x})) = e^{-y F(\mathbf{x})}.$$

With the current model $F_{t-1}$, the next term solves

$$(\alpha_t, h_t) = \arg\min_{\alpha, h} \sum_{i=1}^{n} w_i^{(t)} e^{-\alpha y_i h(\mathbf{x}_i)}, \qquad w_i^{(t)} = e^{-y_i F_{t-1}(\mathbf{x}_i)}.$$

Writing the sum as $(e^{\alpha} - e^{-\alpha}) \sum_i w_i^{(t)} \mathbf{1}[y_i \neq h(\mathbf{x}_i)] + e^{-\alpha} \sum_i w_i^{(t)}$ shows that for any $\alpha > 0$ the best $h$ is the one with the lowest weighted error, and minimizing over $\alpha$ then gives $\alpha_t = \tfrac{1}{2} \ln((1 - \varepsilon_t)/\varepsilon_t)$. The weights $w_i^{(t)}$ are AdaBoost’s weights before normalization (Hastie, Tibshirani and Friedman, §10.4). The training-error bound above is the same fact seen from the other side: the bound is the average exponential loss. The Elements of Statistical Learning (§10.5) notes that this equivalence was discovered about five years after AdaBoost was introduced; Schapire (2013) credits Breiman with first observing it.

What does the loss estimate? Minimizing $\mathbb{E}[e^{-yF(\mathbf{x})} \mid \mathbf{x}]$ pointwise gives (Friedman, Hastie and Tibshirani, Lemma 1)

$$F^*(\mathbf{x}) = \frac{1}{2} \ln \frac{P(y = 1 \mid \mathbf{x})}{P(y = -1 \mid \mathbf{x})}, \qquad P(y = 1 \mid \mathbf{x}) = \frac{1}{1 + e^{-2F^*(\mathbf{x})}},$$

half the log-odds, the quantity that logistic regression models linearly. The binomial deviance $\log(1 + e^{-2yF})$, the negative log-likelihood of that model, has the same population minimizer, and the two losses agree to second order around $F = 0$, up to an additive constant. They differ for badly misclassified examples: the deviance grows linearly in $-yF$, the exponential loss exponentially, which is why the exponential loss is less robust to wrong labels (Hastie, Tibshirani and Friedman, §10.6; see Properties). The loss function article covers losses in general.

The statistical view produced variants that differ in what each round fits (Friedman, Hastie and Tibshirani, Algorithms 2–4):

• Real AdaBoost. The weak learner returns a weighted class-probability estimate $p_t(\mathbf{x})$, and the round adds $\tfrac{1}{2} \ln(p_t(\mathbf{x}) / (1 - p_t(\mathbf{x})))$, a real-valued, confidence-rated vote.
• Gentle AdaBoost. Each round fits a regression function to the labels by weighted least squares and adds it, a Newton step on the exponential loss; its updates stay in $[-1, 1]$, avoiding the log-ratios of Real AdaBoost, which the authors note can be numerically unstable.
• LogitBoost. Newton steps on the binomial log-likelihood instead: each round fits a weighted least-squares regression to a working response $z_i = (y_i^* - p_i)/(p_i(1 - p_i))$ with weights $p_i(1 - p_i)$, where $y_i^* \in \{0, 1\}$, and adds half of it.

For a decision stump as the weak learner, Real and Gentle AdaBoost fit a separate real value on each side of the threshold, where Discrete AdaBoost has only $\pm\alpha_t$.

Margins

Training error stops changing once it reaches zero, yet AdaBoost often keeps improving on test data after that point; the example below shows it. Schapire, Freund, Bartlett and Lee (1998) explained this with the margin of an example under the normalized vote $f(\mathbf{x}) = \sum_t \alpha_t h_t(\mathbf{x}) / \sum_t \alpha_t$:

$$\text{margin}(\mathbf{x}_i, y_i) = y_i f(\mathbf{x}_i) \in [-1, 1],$$

the weighted fraction of votes for the correct label minus the fraction for the wrong one. It is positive exactly when the example is classified correctly, and a large value is a confident vote. Their Theorem 1 says that, for a finite class $\mathcal{H}$ of weak classifiers and $m$ training examples drawn from a distribution $\mathcal{D}$, with probability at least $1 - \delta$ every such vote satisfies, for all $\theta > 0$,

$$P_{\mathcal{D}}[y f(\mathbf{x}) \le 0] \;\le\; P_S[y f(\mathbf{x}) \le \theta] + O\!\left( \frac{1}{\sqrt{m}} \left( \frac{\log m \, \log |\mathcal{H}|}{\theta^2} + \log(1/\delta) \right)^{1/2} \right),$$

where $P_S$ is the fraction of training examples. The bound does not depend on the number of rounds $T$, and their Theorem 2 gives a similar result for a class of VC dimension $d$, with $d \log^2(m/d)$ in place of $\log m \log |\mathcal{H}|$. Their Theorem 5 bounds the fraction of training margins at most $\theta$ for AdaBoost, $P_S[y f(\mathbf{x}) \le \theta] \le 2^T \prod_t \sqrt{\varepsilon_t^{1 - \theta} (1 - \varepsilon_t)^{1 + \theta}}$, and the bound falls exponentially with $T$ when every $\varepsilon_t \le \tfrac{1}{2} - \gamma$ and $\theta < \gamma$. Together: if the weak rules are good enough to produce large margins and simple relative to the amount of data, a long run need not overfit. The authors relate this margin to that of the support vector machine: both are margins of a linear classifier in a high-dimensional space, measured with the $L^1$ norm of the vote weights for boosting and the Euclidean norm for the SVM.

The authors call their bounds loose, and the theory is incomplete: algorithms that maximize the smallest margin directly, such as Breiman’s arc-gv, produced larger minimum margins but slightly worse test error, which Reyzin and Schapire, as Schapire (2013) reports, attributed to more complex weak hypotheses and to a margin distribution that is lower overall even when its minimum is higher.

Multiclass AdaBoost: SAMME

With $K$ classes, a weak classifier that is better than chance may still have error above one half, and then AdaBoost’s $\alpha_t$ is negative and the reweighting goes the wrong way. Zhu, Zou, Rosset and Hastie’s SAMME (stagewise additive modelling using a multi-class exponential loss) changes only the vote:

$$\alpha_t = \ln \frac{1 - \varepsilon_t}{\varepsilon_t} + \ln(K - 1),$$

so that $\alpha_t > 0$ whenever the accuracy $1 - \varepsilon_t$ exceeds $1/K$; the weights of mistakes are multiplied by $e^{\alpha_t}$, and the prediction is the class with the largest total vote. For $K = 2$ it is AdaBoost in the form with $\ln$ rather than $\tfrac{1}{2}\ln$. The authors derive it as forward stagewise fitting of a multiclass exponential loss.

Parameters

• Weak learner. Its capacity sets how much each round can do. Stumps give an additive model in the features, with no interactions between them; trees with $J$ leaves allow interactions of up to $J - 1$ features (Hastie, Tibshirani and Friedman, §10.11). For boosted trees the book reports that $4 \le J \le 8$ works well and that tuning rarely improves much on $J \approx 6$. In detection, stumps on single features also make boosting a feature selector, since each round evaluates one feature.
• Number of rounds $T$. More rounds fit the training set more closely. AdaBoost often tolerates a long run, but not always (see Properties), so $T$ is best chosen on a validation set or by cross-validation, the method Freund and Schapire themselves suggest as an alternative to bounds.
• Learning rate (shrinkage) $\nu$. Multiplying each new term by $0 < \nu \le 1$ slows the fit. Friedman (2001) introduced this for gradient boosting and found that smaller $\nu$ gives better results at the price of more rounds; the Elements of Statistical Learning recommends $\nu < 0.1$ with $T$ chosen by early stopping (§10.12.1).
• Initial weights. Uniform by default. Unequal initial weights change the problem being solved: Viola and Jones gave each class equal total weight, and their asymmetric AdaBoost spread an extra cost on missed faces over all rounds, as the Viola–Jones article describes.

scikit-learn 1.7.2. AdaBoostClassifier has estimator=None, which means a DecisionTreeClassifier(max_depth=1), n_estimators=50 and learning_rate=1.0, and it implements SAMME, multiplying its vote by learning_rate. Boosting stops early if a weak classifier fits the weighted training set perfectly, and the last classifier is dropped if its error reaches $1 - 1/K$. The SAMME.R option (“R for Real”, the multiclass analogue of Real AdaBoost in the 2006 preprint of Zhu and colleagues’ paper; the published version only mentions that they derived one) was deprecated in version 1.4; in 1.7.2 only "SAMME" is accepted, and the algorithm parameter itself, deprecated in 1.6 and due to be removed in 1.8, has no effect apart from a FutureWarning. The default stump is chosen by the tree’s Gini impurity criterion, not by weighted error, which can select a different stump from the one AdaBoost’s derivation calls for; the second example shows how often.

Complexity

Training. For stumps over $K$ features and $n$ examples, sorting each feature once costs $O(Kn \log n)$; after that, one pass over each sorted feature with running sums of the positive and negative weight finds every threshold’s weighted error, so a round costs $O(Kn)$ and $T$ rounds $O(TKn)$. Deeper trees or a library tree learner that re-sorts at every node cost more per round. Each round depends on the previous one’s weights, so rounds cannot run in parallel; the search within a round can.

Prediction. $T$ weak-classifier evaluations and a sum, or fewer if evaluation stops early, as in a detection cascade.

Memory. The weights ($n$ numbers) during training; the $T$ rules and votes at test time.

Implementation

The three examples classify synthetic $24 \times 24$ grayscale patches with exactly known labels: a bright disc (label $+1$) or a bright ring, the same disc with a hole of half its radius (label $-1$), with random radius from 5 to 8 pixels, centre shifted by up to 3 pixels, random background and contrast, and Gaussian noise of standard deviation 0.1. Each patch is described by 400 random two- and three-rectangle Haar-like features computed from its integral image. Because the shape moves, no single rectangle feature separates the classes: in the first run the best first stump has a training error of 0.25. The weak learner is the exhaustive stump search described under Complexity. The outputs come from NumPy 2.3.5 and scikit-learn 1.7.2 with OMP_NUM_THREADS=1; each block runs in about 20 seconds.

AdaBoost from scratch: training error, bound, test error and margins

The first block trains discrete AdaBoost for 400 rounds on 2,000 patches, tests on 4,000 new ones, and tracks the bound, the average exponential loss and the normalized margins. It repeats the run for five seeds.

import numpy as np

S = 24                                        # patch size (pixels)
yy, xx = np.mgrid[0:S, 0:S] + 0.5             # pixel-centre coordinates

def patch(disc, rng, noise=0.1):
    """A 24x24 grayscale patch: a bright disc (label +1) or a bright ring (label -1)
    of random radius, position, brightness and contrast, plus Gaussian noise."""
    b, c = rng.uniform(0.3, 0.7), rng.uniform(0.15, 0.35)
    r, (cy, cx) = rng.uniform(5, 8), S / 2 + rng.uniform(-3, 3, 2)
    d2 = (yy - cy) ** 2 + (xx - cx) ** 2
    shape = d2 <= r * r
    if not disc:
        shape &= d2 > (r / 2) ** 2            # ring: the disc with a hole of half its radius
    img = np.full((S, S), b)
    img[shape] += c
    return img + rng.normal(0, noise, (S, S))

def dataset(n, rng):
    y = np.where(rng.random(n) < 0.5, 1, -1)
    return np.array([patch(label == 1, rng) for label in y]), y

def haar_pool(K, rng):
    """K random two- and three-rectangle features: lists of (top, left, h, w, sign)."""
    pool = []
    for _ in range(K):
        nx, ny = [(2, 1), (1, 2), (3, 1), (1, 3)][rng.integers(4)]
        w, h = rng.integers(2, S // nx + 1), rng.integers(2, S // ny + 1)
        x, y = rng.integers(0, S - nx * w + 1), rng.integers(0, S - ny * h + 1)
        pool.append([(y + j * h, x + i * w, h, w, (-1) ** (i + j)) for i in range(nx) for j in range(ny)])
    return pool

def features(imgs, pool):
    """Feature values from integral images: signed mean intensities of the rectangles."""
    I = np.pad(imgs, ((0, 0), (1, 0), (1, 0))).cumsum(1).cumsum(2)
    F = np.zeros((len(imgs), len(pool)))
    for k, rects in enumerate(pool):
        for y0, x0, h, w, s in rects:
            F[:, k] += s * (I[:, y0 + h, x0 + w] - I[:, y0, x0 + w] - I[:, y0 + h, x0] + I[:, y0, x0]) / (h * w)
    return F

class Stumps:
    """Exhaustive weak learner: the stump h(x) = s * sign(x_k - thr) with the lowest
    weighted error over all features k, thresholds thr and polarities s = +1 or -1."""
    def __init__(self, F):
        self.order = np.argsort(F, 0)
        self.Fs = np.take_along_axis(F, self.order, 0)
        self.cut_ok = np.vstack([self.Fs[1:] > self.Fs[:-1], np.zeros((1, F.shape[1]), bool)])

    def fit(self, y, w):
        wy = (w * y)[self.order]                                  # sorted, per feature
        pos_below = np.cumsum(np.maximum(wy, 0), 0)
        neg_below = np.cumsum(np.maximum(-wy, 0), 0)
        err_up = pos_below + neg_below[-1] - neg_below            # error if +1 above the cut
        err = np.where(self.cut_ok, np.minimum(err_up, 1 - err_up), np.inf)
        i, k = np.unravel_index(np.argmin(err), err.shape)
        thr = (self.Fs[i, k] + self.Fs[i + 1, k]) / 2
        s = 1 if err_up[i, k] <= 0.5 else -1
        return k, thr, -s, s                                      # labels left and right of thr

def stump_predict(F, k, thr, left, right):
    return np.where(F[:, k] > thr, right, left)

def adaboost(F, y, T, learner, nu=1.0):
    """Discrete AdaBoost, labels in {-1, +1}, with the votes scaled by a learning rate nu
    (nu = 1 is AdaBoost itself). Returns the stumps, their votes alpha_t, their
    errors eps_t and the final weights."""
    n = len(y)
    w = np.full(n, 1 / n)
    stumps, alphas, epss = [], [], []
    for t in range(T):
        stump = learner.fit(y, w)
        h = stump_predict(F, *stump)
        eps = w[h != y].sum()                                     # weighted error
        alpha = nu * 0.5 * np.log((1 - eps) / eps)
        w = w * np.exp(-alpha * y * h)                            # up-weight the mistakes
        w /= w.sum()
        stumps.append(stump); alphas.append(alpha); epss.append(eps)
    return stumps, np.array(alphas), np.array(epss), w

def staged_scores(F, stumps, alphas):
    """F_t(x) = sum_{s <= t} alpha_s h_s(x) for every t (rows) and patch (columns)."""
    H = np.array([stump_predict(F, *st) for st in stumps])
    return np.cumsum(alphas[:, None] * H, 0)

def error(G, y):
    """Error rate of sign(F_t), with a score of exactly 0 assigned to -1 as scikit-learn does."""
    return (np.where(G > 0, 1, -1) != y).mean(-1)

T, report = 400, [1, 2, 5, 10, 20, 50, 100, 200, 400]
for seed in range(5):
    rng = np.random.default_rng(seed)
    X_tr, y_tr = dataset(2000, rng)
    X_te, y_te = dataset(4000, rng)
    pool = haar_pool(400, rng)
    F_tr, F_te = features(X_tr, pool), features(X_te, pool)
    stumps, alphas, epss, w = adaboost(F_tr, y_tr, T, Stumps(F_tr))
    G_tr, G_te = staged_scores(F_tr, stumps, alphas), staged_scores(F_te, stumps, alphas)
    train_err = error(G_tr, y_tr)
    test_err = error(G_te, y_te)
    bound = np.cumprod(2 * np.sqrt(epss * (1 - epss)))
    exp_loss = np.exp(-y_tr * G_tr).mean(1)
    margin = y_tr * G_tr / np.cumsum(alphas)[:, None]               # normalized margins in [-1, 1]
    if seed == 0:
        print("seed 0: 2,000 training and 4,000 test patches, 400 Haar-like features")
        print("    t   eps_t  alpha_t  train err  bound = mean exp loss  test err  min margin  median margin")
        for t in report:
            print(f"{t:5d}  {epss[t-1]:.3f}  {alphas[t-1]:6.3f}   {train_err[t-1]:.4f}      "
                  f"{bound[t-1]:.2e} = {exp_loss[t-1]:.2e}      {test_err[t-1]:.4f}   {margin[t-1].min():+.3f}"
                  f"      {np.median(margin[t-1]):+.3f}")
        print("\nseed  first t with zero train err  test err there  test err at t=400  min margin there -> at 400")
    t0 = np.argmax(train_err == 0)
    print(f"{seed:4d}  {t0 + 1:27d}  {test_err[t0]:14.4f}  {test_err[-1]:17.4f}"
          f"      {margin[t0].min():+.3f} -> {margin[-1].min():+.3f}")

Output:

seed 0: 2,000 training and 4,000 test patches, 400 Haar-like features
    t   eps_t  alpha_t  train err  bound = mean exp loss  test err  min margin  median margin
    1  0.250   0.551   0.2495      8.65e-01 = 8.65e-01      0.2380   -1.000      +1.000
    2  0.225   0.618   0.2775      7.23e-01 = 7.23e-01      0.2973   -1.000      +1.000
    5  0.274   0.487   0.1125      5.21e-01 = 5.21e-01      0.1325   -0.641      +0.524
   10  0.305   0.412   0.0805      3.48e-01 = 3.48e-01      0.0875   -0.455      +0.391
   20  0.371   0.264   0.0490      2.12e-01 = 2.12e-01      0.0565   -0.258      +0.367
   50  0.370   0.266   0.0080      7.39e-02 = 7.39e-02      0.0330   -0.051      +0.288
  100  0.387   0.230   0.0000      2.03e-02 = 2.03e-02      0.0230   +0.015      +0.238
  200  0.396   0.211   0.0000      2.46e-03 = 2.46e-03      0.0203   +0.050      +0.209
  400  0.412   0.178   0.0000      5.84e-05 = 5.84e-05      0.0177   +0.071      +0.187

seed  first t with zero train err  test err there  test err at t=400  min margin there -> at 400
   0                           75          0.0285             0.0177      +0.001 -> +0.071
   1                           78          0.0243             0.0118      +0.007 -> +0.083
   2                           74          0.0283             0.0175      +0.002 -> +0.078
   3                           68          0.0253             0.0147      +0.005 -> +0.081
   4                           71          0.0255             0.0150      +0.010 -> +0.078

The weak rules get weaker as boosting proceeds: the weighted error climbs from 0.25 towards 0.41 and the votes shrink with it, because each reweighting concentrates on the patches the vote so far gets wrong. The bound and the average exponential loss agree to every printed digit, as the identity $\frac{1}{n}\sum_i e^{-y_i F(\mathbf{x}_i)} = \prod_t Z_t$ requires, and both decrease every round. The training error itself need not: it rises from round 1 to round 2, while the bound falls. The bound is also loose. It falls below $1/2000$, which forces zero training error, only after round 200, while the training error actually reaches zero at round 75.

The second table is the phenomenon the margin theory addresses. In all five runs the training error reaches zero between rounds 68 and 78, yet the test error is lower at round 400 in every run, 0.0118–0.0177 against 0.0243–0.0285 at that point, and in seed 0 it falls at every printed round after 50. Over the same rounds the smallest training margin grows from about zero (0.001 to 0.010) to 0.071–0.083. In seed 0 the median margin falls (0.238 at round 100, 0.187 at round 400) while the minimum rises: AdaBoost concentrates on the examples whose margins are small, as Schapire, Freund, Bartlett and Lee describe, and on these data its later rounds raise the smallest margins while the median falls.

Cross-check with scikit-learn

The second block continues the first (it reuses its functions) on the seed-0 data. It prints AdaBoostClassifier’s defaults, runs the same AdaBoost loop with scikit-learn’s own depth-1 tree as the weak learner and compares the result with AdaBoostClassifier round by round, and then compares the trees with the exhaustive minimum-error stumps.

import warnings
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

rng = np.random.default_rng(0)                       # the seed-0 data of the first block
X_tr, y_tr = dataset(2000, rng)
X_te, y_te = dataset(4000, rng)
pool = haar_pool(400, rng)
F_tr, F_te = features(X_tr, pool), features(X_te, pool)
F_tr, F_te = (F.astype(np.float32).astype(np.float64) for F in (F_tr, F_te))   # trees store X as float32

p = AdaBoostClassifier().get_params()
print("defaults:", {k: p[k] for k in ("estimator", "n_estimators", "learning_rate", "algorithm")})
with warnings.catch_warnings(record=True) as caught:
    warnings.simplefilter("always")
    AdaBoostClassifier(algorithm="SAMME").fit(F_tr[:50], y_tr[:50])
print("algorithm='SAMME' ->", caught[0].category.__name__)

T = 200
clf = AdaBoostClassifier(n_estimators=T, random_state=0).fit(F_tr, y_tr)
print("default weak learner:", clf.estimators_[0])

class TreeStump:
    """scikit-learn's depth-1 tree as the weak learner of our own loop."""
    def __init__(self, F):
        self.F = F
    def fit(self, y, w):
        tree = DecisionTreeClassifier(max_depth=1, random_state=0).fit(self.F, y, sample_weight=w)
        k, thr = tree.tree_.feature[0], tree.tree_.threshold[0]
        left, right = (int(tree.classes_[tree.tree_.value[c, 0].argmax()])
                       for c in (tree.tree_.children_left[0], tree.tree_.children_right[0]))
        return k, thr, left, right                                # the two leaves may agree

for name, learner in (("our loop, sklearn's stumps", TreeStump(F_tr)), ("our loop, min-error stumps", Stumps(F_tr))):
    stumps, alphas, epss, w = adaboost(F_tr, y_tr, T, learner)
    G_te = staged_scores(F_te, stumps, alphas)
    print(f"\n{name}: test error at t = 50, 200: {error(G_te[49], y_te):.4f}, "
          f"{error(G_te[-1], y_te):.4f}")
    if name.startswith("our loop, sklearn"):
        same = [k for (k, *_), e in zip(stumps, clf.estimators_) if k == e.tree_.feature[0]]
        print(f"  same feature as AdaBoostClassifier in {len(same)} of {T} rounds")
        print(f"  max |eps_t - estimator_errors_|       = {np.abs(epss - clf.estimator_errors_).max():.1e}")
        print(f"  max |2 alpha_t - estimator_weights_|  = {np.abs(2 * alphas - clf.estimator_weights_).max():.1e}")
        margin_te = G_te[-1] / alphas.sum()
        print(f"  max |2 margin - decision_function|    = {np.abs(2 * margin_te - clf.decision_function(F_te)).max():.1e}")
        staged = list(clf.staged_predict(F_te))
        print(f"  AdaBoostClassifier test error at t = 50, 200: "
              f"{(staged[49] != y_te).mean():.4f}, {(staged[-1] != y_te).mean():.4f}")
    else:
        print("  features of the first 8 stumps:", [int(st[0]) for st in stumps[:8]])
        print("  sklearn's first 8 stumps:      ", [int(e.tree_.feature[0]) for e in clf.estimators_[:8]])

Output:

defaults: {'estimator': None, 'n_estimators': 50, 'learning_rate': 1.0, 'algorithm': 'deprecated'}
algorithm='SAMME' -> FutureWarning
default weak learner: DecisionTreeClassifier(max_depth=1, random_state=209652396)

our loop, sklearn's stumps: test error at t = 50, 200: 0.0325, 0.0163
  same feature as AdaBoostClassifier in 200 of 200 rounds
  max |eps_t - estimator_errors_|       = 2.8e-16
  max |2 alpha_t - estimator_weights_|  = 1.2e-15
  max |2 margin - decision_function|    = 1.1e-15
  AdaBoostClassifier test error at t = 50, 200: 0.0325, 0.0163

our loop, min-error stumps: test error at t = 50, 200: 0.0330, 0.0203
  features of the first 8 stumps: [268, 200, 317, 40, 380, 144, 206, 157]
  sklearn's first 8 stumps:       [268, 200, 317, 40, 245, 206, 157, 339]

Given the same weak learner, the NumPy loop and AdaBoostClassifier agree to rounding error in every round. The library’s votes are exactly twice ours because SAMME with $K = 2$ uses $\ln((1 - \varepsilon_t)/\varepsilon_t)$ rather than half of it, which changes neither the weights after normalization nor the sign of the vote; its two-class decision_function is twice the normalized margin defined above. The features are rounded to single precision first because scikit-learn’s trees store their input as float32, so that both loops compare the same numbers with each threshold; on these data the printed results are the same without the rounding.

The weak learner is where the two implementations part. scikit-learn’s stump minimizes the weighted Gini impurity of its two leaves, and from round 5 on its sequence of features differs from that of the minimum-error stump that the exponential-loss derivation calls for; the code also has to allow a stump whose two leaves predict the same class, which the Gini criterion can produce. On this dataset the Gini stumps happened to do slightly better after 200 rounds; a single dataset says nothing general about which criterion is better.

Label noise

The third block continues the first. It flips the labels of a random 10% of the training patches of seeds 0 to 2, keeps the test labels clean, and tracks the share of AdaBoost’s weight held by the flipped patches. It also reruns AdaBoost with a learning rate $\nu = 0.1$.

T, report = 400, [10, 50, 200, 400]
print("10% of training labels flipped; test labels clean")
print("seed  weight share of flipped patches at t = 10, 50, 200, 400   test err nu=1 (t=50, 400)   nu=0.1 (t=50, 400)")
for seed in range(3):
    rng = np.random.default_rng(seed)                    # the same data as the first block
    X_tr, y_tr = dataset(2000, rng)
    X_te, y_te = dataset(4000, rng)
    pool = haar_pool(400, rng)
    F_tr, F_te = features(X_tr, pool), features(X_te, pool)
    flip = np.random.default_rng(100 + seed).random(len(y_tr)) < 0.1
    y_noisy = np.where(flip, -y_tr, y_tr)
    learner, share, err = Stumps(F_tr), [], {}
    for nu in (1.0, 0.1):
        stumps, alphas, epss, w = adaboost(F_tr, y_noisy, T, learner, nu)
        G_tr, G_te = staged_scores(F_tr, stumps, alphas), staged_scores(F_te, stumps, alphas)
        err[nu] = error(G_te, y_te)
        if nu == 1.0:                                     # weights before round t+1, from F_t
            W = np.exp(-y_noisy * G_tr)
            share = (W[:, flip].sum(1) / W.sum(1))[[t - 1 for t in report]]
    print(f"{seed:4d}  {flip.mean():.3f} -> " + "  ".join(f"{v:.3f}" for v in share) +
          f"          {err[1.0][49]:.4f}  {err[1.0][-1]:.4f}          {err[0.1][49]:.4f}  {err[0.1][-1]:.4f}")

Output:

10% of training labels flipped; test labels clean
seed  weight share of flipped patches at t = 10, 50, 200, 400   test err nu=1 (t=50, 400)   nu=0.1 (t=50, 400)
   0  0.096 -> 0.287  0.370  0.396  0.395          0.0690  0.0650          0.0950  0.0465
   1  0.106 -> 0.335  0.386  0.405  0.407          0.0673  0.0658          0.0885  0.0350
   2  0.100 -> 0.345  0.382  0.410  0.412          0.0645  0.0530          0.0690  0.0403

The mislabelled patches are about 10% of the training set but hold 29–35% of the weight after 10 rounds and about 40% (0.395–0.412) after 400: a ring labelled as a disc stays misclassified by any sensible rule, so its weight is multiplied up round after round, and the weak learner spends more and more of its effort trying to fit labels that are wrong. The cost shows on the clean test set. With the same patches, the three noise-free runs of the first block reached test errors of 0.0118–0.0177 after 400 rounds; with the flipped labels AdaBoost reaches 0.053–0.066, and gains at most 1.2 points between rounds 50 and 400. Shrinking the votes to a tenth makes the first 50 rounds worse (0.069–0.095) but ends lower after 400 rounds (0.035–0.047), in line with the gains from shrinkage that Friedman (2001) reported; this run does not show whether $\nu = 0.1$ would also degrade if continued far longer.

Properties and Behavior

• Training error falls exponentially while the weak learner keeps an edge over chance, by the bound above; it reaches zero once the bound drops below $1/n$, and no bound on the weak learner’s edge needs to be known in advance.
• Test error often keeps falling after the training error reaches zero. Schapire and colleagues reported this for boosted C4.5 decision trees on the letter dataset, where the test error fell from 8.4% at round 5, when the training error first reached zero, to 3.1% at round 1,000, and the first example above shows the same pattern. The margin theory explains it by the growth of the training margins.
• AdaBoost can overfit. A VC-dimension analysis based on Freund and Schapire’s bound on the complexity of the vote predicts that test error eventually rises with $T$ (Schapire, Freund, Bartlett and Lee, 1998), and Schapire (2013) shows a benchmark (the Cleveland heart-disease data) where it does. The margin bound protects only when the weak classifiers are simple relative to the data and the margins become large.
• Loss minimization is not the whole story. In an experiment of Schapire and Freund’s described by Schapire (2013), plain gradient descent and a version of AdaBoost that picks its weak rules at random drove the exponential loss as low as standard AdaBoost but stayed near 40% test error, while standard AdaBoost reached 0%. The exponential loss is convex but its minimum is often not unique or not attained, so how it is minimized matters.
• Early stopping acts like regularization. A variant of AdaBoost with a tiny constant vote can trace practically the same path as minimization of the exponential loss under a bound on the $L^1$ norm of the votes, a correspondence Hastie, Tibshirani and Friedman observed and later work showed to hold under some but not all conditions (Schapire, 2013); stopping early then corresponds to a tighter bound. Schapire notes that this explains only early-stopped runs of the variant, not long runs of AdaBoost itself. See regularization for penalties in general.
• Consistency. Bartlett and Traskin proved, as Schapire (2013) summarizes, that AdaBoost stopped after a suitable number of rounds converges to the Bayes error as the data grow, if the weak classifiers are sufficiently rich; this holds even with noisy labels and without the weak-learning condition.
• Sensitivity to wrong labels. The exponential loss gives misclassified examples exponentially growing influence, and the Elements of Statistical Learning (§10.6) reports that AdaBoost’s performance has been observed to degrade dramatically when training labels are wrong; the binomial deviance, which grows only linearly, is far more robust in noisy settings. Long and Servedio constructed a problem, summarized by Schapire (2013), in which flipping 1% of the labels makes AdaBoost produce error above 50%, even with unlimited data, although a classifier of the same form reaches 1%; the result applies to most methods that minimize a convex loss, support vector machines and logistic regression among them, with or without regularization. Dietterich and others observed the susceptibility in practice. The third example shows the mechanism, mislabelled examples taking a growing share of the weight.

Limitations

• Noisy labels and outliers draw a growing share of the weights, as above. Remedies include losses that grow more slowly (LogitBoost, gradient boosting with the deviance), shrinkage, early stopping, and boosting algorithms that can give up on very hard examples, such as Freund’s BrownBoost, which Schapire (2013) reports as more resistant to noise in preliminary experiments.
• A weak learner that is too weak or too strong. If no rule beats chance on the reweighted data, AdaBoost stops making progress; with $K > 2$ classes this happens early unless SAMME or a similar form is used. Rules that are too complex make the vote overfit, and the margin bound then no longer protects.
• Sequential training. Rounds depend on each other, and with an exhaustive feature search each round touches every feature of every example, which makes training on large feature pools slow (the Viola–Jones face detector took weeks to train, as its article describes).
• Scores, not probabilities. The vote estimates half the log-odds only in the population limit (Friedman, Hastie and Tibshirani, Lemma 1). In our reading, the scores of a finite run are no more trustworthy as probabilities than those of other margin-based classifiers and need calibrating before use as such; logistic regression covers calibration.
• Fixed features. Boosting selects and combines given features. In vision it has been displaced, for most recognition tasks, by convolutional neural networks that learn their features from pixels.

Variants

• Real AdaBoost, Gentle AdaBoost and LogitBoost, described above (Friedman, Hastie and Tibshirani, 2000). In Schapire and Singer’s confidence-rated boosting, weak rules output real values; Friedman, Hastie and Tibshirani note that one form of it coincides with Real AdaBoost when the weak learner is a decision tree.
• SAMME for multiclass problems, above. Freund and Schapire’s own multiclass extensions were AdaBoost.M1, which still requires each weak rule’s error to be below one half, and AdaBoost.M2, which lets weak rules output a degree of belief for each label and measures them by a pseudo-loss.
• Gradient boosting. Friedman (2001) treated boosting as steepest descent in function space. For any differentiable loss $L$, each round computes the negative gradient at the training points, the pseudo-residuals $r_i = -\partial L(y_i, F(\mathbf{x}_i)) / \partial F(\mathbf{x}_i)$ at $F = F_{t-1}$, fits a regression tree to them by least squares, sets each leaf’s value by a line search on $L$, and adds the tree scaled by the learning rate $\nu$. For squared error the pseudo-residuals are the ordinary residuals; for the binomial deviance one tree per round (or one per class for $K$ classes) fits $y_i^* - p(\mathbf{x}_i)$ (Hastie, Tibshirani and Friedman, §10.10). Stochastic gradient boosting fits each tree on a random subsample, typically half the data (§10.12.2). scikit-learn 1.7.2’s GradientBoostingClassifier defaults to the log-loss, learning_rate=0.1, n_estimators=100 and trees of max_depth=3; with loss="exponential" it fits AdaBoost’s loss, which its user guide notes is less robust to mislabelled examples than the log-loss. Its HistGradientBoostingClassifier bins each feature (into at most 255 bins by default) and builds histograms instead of sorting at each node; the user guide says it was inspired by LightGBM (Ke et al.) and relates its $L^2$ leaf penalty to the regularized objective of XGBoost (Chen and Guestrin), two other gradient-boosting libraries.
• Asymmetric AdaBoost and boosted cascades for detection, in which early stages must almost never reject the object, and soft cascades and WaldBoost, which let rejection happen after any weak classifier; the Viola–Jones article covers them.
• JointBoost, which shares weak learners between classes (below).

Uses in Computer Vision

Face detection and feature selection. Viola and Jones (2001, 2004) restricted each weak classifier to a threshold on a single Haar-like feature, so that each AdaBoost round selects one feature from a pool of over a hundred thousand, and chained boosted classifiers into an attentional cascade whose early stages reject most background windows with a handful of features. The Viola–Jones article covers the detector, its cascade training and its reported results, and the paper article the 2001 publication. The same article reports Lienhart, Kuranov and Pisarevsky’s comparison of Discrete, Real and Gentle AdaBoost for face cascades, in which Gentle AdaBoost detected the most faces at a fixed false-alarm rate, and notes that OpenCV’s cascade trainer uses Gentle AdaBoost by default.

Other detectors. Zhu, Avidan, Yeh and Cheng used AdaBoost to select HOG blocks of variable size for the stages of a cascade, as the HOG article describes. Torralba, Murphy and Freeman (2007) trained detectors for many object classes jointly with JointBoost, a variant of Gentle AdaBoost with regression stumps in which each round chooses a feature and the subset of classes that share it. On 21 object classes, the number of features needed for a given performance grew roughly logarithmically with the number of classes when training jointly, against linearly for independent detectors, and the shared features were generic edge-like patterns rather than object-specific templates.

In these systems boosting does two jobs at once: it learns the classifier and decides which of a very large set of cheap image features to compute. Together with the cascade, this is what let Viola and Jones run face detection at 15 frames per second on a 700 MHz Pentium III.