---
kind: concept
slug: adaboost
title: AdaBoost
summary: >-
  Combine many weak classifiers into one vote by reweighting the training examples each round, so later rounds focus on earlier mistakes. Multi-class variant with a weak learner that needs no training. Trade-off: each round scores every candidate feature, so cost grows with pool size. Compiled from one card; the other variants are not yet covered.
tags: [boosting, feature-selection, ensemble, classification]
papers: ["1604.03225"]
related: [dynamic-time-warping, support-vector-machine]
status: draft
updated_at: 2026-10-18
---

## Overview

AdaBoost builds a strong classifier from many weak ones. A weak classifier only
has to beat chance. Each round picks the weak classifier with the lowest
weighted error, gives it a vote weight, and then raises the weight of the
training examples it got wrong, so the next round concentrates on them
[arxiv:1604.03225 §4].

The invariant shared by the variants is the final rule: the prediction is a
weighted vote of the selected weak classifiers, and each weight comes from that
classifier's weighted error in its round [arxiv:1604.03225 §4, eq. 13, eq. 14].
What differs is the weak classifier. The only card here uses one feature per
weak learner, and that feature's "classifier" is a stored prototype rather than
a trained model [arxiv:1604.03225 §4].

This page is compiled from one card,
[Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines](/papers/1604.03225).
It uses AdaBoost as a feature selector on a pool of 1378 candidate features,
and then either votes with it or passes its output to an SVM. No other card
in this wiki covers AdaBoost, so the classical two-class formulation and other
multi-class schemes are not described here.

## Variants

### Multi-class AdaBoost with DTW weak learners

The paper extends AdaBoost to six classes. Each candidate feature is a
time series, and its weak learner labels a sequence with the class whose
median prototype is closest in dynamic time warping (DTW) distance
[arxiv:1604.03225 §4, eq. 10, eq. 11, eq. 12]. Prototypes are fixed in advance
from the training set, so the weak learner is not fitted by AdaBoost
[arxiv:1604.03225 §4]. The learner weight is
log((1 − err)/err) + log(K − 1), which is positive only when the weighted error
is below 1 − 1/K [arxiv:1604.03225 §4, eq. 13]. The paper calls the scheme
the multi-class variant of a reference it cites as [40] [arxiv:1604.03225 §4].
The card does not give the exact name used in the cited work.

The paper uses this as a standalone classifier, called AdaBoost-DTW in its
results: the selected features vote, using their learner weights
[arxiv:1604.03225 §5.2, eq. 14]. See [Dynamic time warping](/concepts/dynamic-time-warping)
for the distance used by the weak learner.

### Boosted features as input to an SVM

The same selection step can produce features for another classifier. The paper
keeps one summary value per selected feature, the maximum displacement or the
maximum change in angle or distance over the sequence, and feeds the resulting
vector to an RBF support vector machine [arxiv:1604.03225 §5.3].
See [Support vector machine](/concepts/support-vector-machine). This variant is
a choice of input representation layered on top of AdaBoost, so it is listed
here rather than as a separate boosting method.

## When to use which

| Situation | Use | Why |
|---|---|---|
| You want the boosting vote itself to be the classifier, and you have a fixed, small pool of features | Weighted vote over the selected weak learners | On CK+, the paper reports 95.17% for AdaBoost-DTW with 125 features [arxiv:1604.03225 §5.2 tab. 3]. It needs no second model. |
| Accuracy is the priority and you can tune a second model | Boosted features into an RBF SVM | The paper reports 97.35% with 400 selected features, against 95.17% for the vote [arxiv:1604.03225 §5.3 tab. 6]. The gain is from one dataset and one run, with no spread reported. |
| Weak learners are expensive to evaluate | Be cautious with the DTW weak learner | Each round scores every candidate against every training sequence. Run time and memory are not reported [arxiv:1604.03225 alg. 1 §4]. |
| Number of rounds is unknown | Pick M on held-out data, not on the curve the paper plots | The paper's choice of M is not stated. Its test-accuracy curve was read on the evaluation data [arxiv:1604.03225 §5.2 fig. 8]. |

These results are from one dataset (CK+) of posed, frontal expressions
[arxiv:1604.03225 §5.1]. They do not show how AdaBoost behaves on other tasks.

## Implementation sketch

The loop below restates the paper's Algorithm 1 for the DTW weak learner. The
names are ours. Its steps follow the paper's [arxiv:1604.03225 alg. 1 §4].

```pseudocode
# Multi-class AdaBoost with a fixed-prototype weak learner  [arxiv:1604.03225 §4]
# Input:  candidate features x[f][i] (sequence per feature f, sample i),
#         labels c[i] in K classes, class prototypes P[f][k] (median per class)
# Output: selected features and learner weights, for M rounds

def train_adaboost(x, c, P, M, K):
    # Start from uniform weights over the n training samples  [alg. 1, step 1]
    w = ones(n) / n
    for m in range(M):
        # Normalise the weights to sum to one  [alg. 1, step 2a]
        w = w / sum(w)
        # For each candidate feature, the nearest-prototype label by DTW  [eq. 12]
        # and the weighted error of that label  [alg. 1, step 2b]
        for f in features:
            pred[f] = nearest_prototype_dtw(x[f], P[f])
            err[f] = sum(w * (c != pred[f]))
        f_m = argmin(err)
        # Learner weight  [eq. 13]; the paper's sign condition is err < 1 - 1/K
        alpha[m] = log((1 - err[f_m]) / err[f_m]) + log(K - 1)
        # Upweight the samples this learner got wrong  [alg. 1, step 2e]
        w = w * exp(alpha[m] * (c != pred[f_m]))
    return selected f_1..f_M, alpha_1..alpha_M

# Final prediction: weighted vote of the selected learners  [eq. 14]
def predict(x_new):
    votes = zeros(K)
    for m in range(M):
        votes[nearest_prototype_dtw(x_new[f_m], P[f_m])] += alpha[m]
    return argmax(votes)
```

Notes for implementers:

- **Zero error.** Eq. 13 is undefined when err = 0, and the paper does not say
  how to handle it [arxiv:1604.03225 §4].
- **Learners above the threshold.** The paper states that α is positive only
  when err < 1 − 1/K, but not what happens to a round that fails this test
  [arxiv:1604.03225 §4].
- **Prototype arrangement.** Section 4 describes one prototype for the target
  class and one per other class in a one-against-all setup, while eq. 12 and
  Algorithm 1 are written over all K classes. The paper does not say which
  arrangement produced its reported numbers [arxiv:1604.03225 §4 eq. 12].
- **Distance settings.** The DTW window, step pattern and normalisation are not
  stated [arxiv:1604.03225 §4 §5.2].
- **Feature sign.** For the SVM variant, the paper takes the maximum of signed
  displacements and angle changes and does not say whether the absolute value
  is intended [arxiv:1604.03225 §5.3].

## Contradictions

None known. The card reports AdaBoost-DTW at its best with 125 features and
the SVM at its best with 400, and these are different settings rather than
conflicting results [arxiv:1604.03225 §5.2 §5.3].

## Papers

- [Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines](/papers/1604.03225): a multi-class AdaBoost that selects geometric motion features, scored by DTW to class prototypes, with an SVM on the selected features as the stronger result.