AdaBoost

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 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 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 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. 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 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 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 1604.03225 §4, eq. 13. The paper calls the scheme the multi-class variant of a reference it cites as [40] 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 1604.03225 §5.2, eq. 14. See 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 1604.03225 §5.3. See 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

These results are from one dataset (CK+) of posed, frontal expressions 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 1604.03225 alg. 1 §4.

# 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 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 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 1604.03225 §4 eq. 12.
• Distance settings. The DTW window, step pattern and normalisation are not stated 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 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 1604.03225 §5.2 §5.3.

Papers

• Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines: 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.