Practical 6: Adaboost Ensemble Learning

training rows 84, test rows 36

round  stump                            error     alpha
1      practice <= 37.0 -> Fail        0.1786    0.7630
2      attendance <= 73.5 -> Fail      0.1754    0.7740
3      practice <= 12.5 -> Fail        0.3622    0.2829
4      practice <= 49.5 -> Fail        0.3418    0.3275
5      attendance <= 53.5 -> Fail      0.3470    0.3160
6      attendance <= 72.5 -> Pass      0.4046    0.1931
7      attendance <= 77.5 -> Fail      0.3835    0.2373
8      practice <= 19.5 -> Fail        0.3624    0.2826

classifier                      train acc   test acc
stump 1 alone: practice <= 37.0 -> Fail      0.821      0.611
stump 2 alone: attendance <= 73.5 -> Fail      0.798      0.694
stump 3 alone: practice <= 12.5 -> Fail      0.524      0.694
stump 4 alone: practice <= 49.5 -> Fail      0.714      0.528
stump 5 alone: attendance <= 53.5 -> Fail      0.702      0.556
stump 6 alone: attendance <= 72.5 -> Pass      0.238      0.278
stump 7 alone: attendance <= 77.5 -> Fail      0.774      0.722
stump 8 alone: practice <= 19.5 -> Fail      0.643      0.639
ensemble of 1                       0.821      0.611
ensemble of 2                       0.798      0.694
ensemble of 3                       0.905      0.750
ensemble of 4                       0.798      0.611
ensemble of 5                       0.917      0.778
ensemble of 6                       0.917      0.778
ensemble of 7                       0.905      0.778
ensemble of 8                       0.917      0.778

the five training rows carrying the most weight at the end:
  attendance   practice   result     weight     0.5a + p
          75         46     Fail     0.1350         83.5
          54         13     Pass     0.1261         40.0
          39         48     Pass     0.0293         67.5
          41         46     Pass     0.0293         66.5
          73         38     Fail     0.0287         74.5

Reading the output: the comparison MU asks for

The weak classifiers on their own are weak. The best of the eight, the second stump, scores 0.798 on the training rows and 0.694 on the test rows. The worst, the sixth, scores 0.238 and 0.278, which is far worse than guessing. That one got a very small alpha, 0.1931, and the ensemble mostly ignores it.

The ensemble beats all of them. By round 5 it reaches 0.917 training and 0.778 test, against the best single stump's 0.798 and 0.694. Eight classifiers that cannot see more than one feature at a time have, between them, learned a boundary that needs both.

The error of each new stump rises. Round 1 finds a stump with weighted error 0.179; by round 6 the best available stump has weighted error 0.405. That is not the algorithm getting worse. It is the weights moving: the easy rows have been down-weighted almost to nothing, so what is left is hard, and a weighted error near 0.5 on a hard remainder is what you expect.

The ensemble stops improving. Rounds 5, 6, 7 and 8 all sit at 0.778 on the test set. Adding more weak classifiers does not help for ever, and the round at which it stops is worth reporting.

Where the weight ended up is the most interesting line in the output. The two heaviest rows are attendance 75 with 46 hours labelled Fail, and attendance 54 with 13 hours labelled Pass. Their scores on the rule the dataset was built from, 0.5 * attendance + practice, are 83.5 and 40.0, against a pass line of 65. Both are on the wrong side of their own labels: they are two of the rows whose labels were deliberately flipped. Adaboost found them, and it did so without being told they existed.

That is Adaboost's great strength and its known weakness in one observation. It concentrates on what is hard, which is how it learns a boundary no single stump can draw. But a wrong label is also hard, and Adaboost cannot tell the difference, so with noisy data it will spend round after round trying to get the noise right. On a dataset you suspect has bad labels, watch the weights: rows whose weight keeps climbing are either the interesting cases or the mistakes.

The same ensemble from scikit-learn

"""The same ensemble from scikit-learn."""
import csv
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

with open("admissions.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
X = [[float(r["attendance"]), float(r["practice"])] for r in rows]
y = [r["result"] for r in rows]
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)

stump = DecisionTreeClassifier(max_depth=1, random_state=0).fit(Xtr, ytr)
print("one stump alone      : train %.3f  test %.3f" % (stump.score(Xtr, ytr), stump.score(Xte, yte)))
print()
print("%-10s %10s %10s" % ("rounds", "train acc", "test acc"))
for n in (1, 2, 5, 10, 25, 50, 100):
    m = AdaBoostClassifier(estimator=DecisionTreeClassifier(max_depth=1),
                           n_estimators=n, random_state=0).fit(Xtr, ytr)
    print("%-10d %10.3f %10.3f" % (n, m.score(Xtr, ytr), m.score(Xte, yte)))

one stump alone      : train 0.798  test 0.694

rounds      train acc   test acc
1               0.798      0.694
2               0.798      0.694
5               0.810      0.833
10              0.845      0.806
25              0.857      0.806
50              0.869      0.806
100             0.893      0.806

The same story from a different implementation: one stump 0.798 and 0.694, the ensemble 0.893 and 0.806. Note that training accuracy keeps creeping up as rounds are added, from 0.798 at one round to 0.893 at a hundred, while test accuracy stops at 0.806 after five. The extra ninety-five rounds bought nothing except the appearance of progress, and a student who reports only the training figure will report the appearance.

estimator=DecisionTreeClassifier(max_depth=1) is what makes the weak learner a stump; that is scikit-learn's default for this class, and saying it explicitly is better than relying on it.

Procedure

1. Write the Stump class: one feature, one threshold, one polarity, and a predict that returns +1 or -1.
2. Write best_stump: try every feature, every threshold midway between two neighbouring values, and both polarities, and keep the one with the smallest weighted error.
3. Write the Adaboost loop: compute alpha from the error, update every weight by exp(-alpha y prediction), and normalise.
4. Run it for eight rounds and print each stump, its weighted error and its alpha.
5. Measure each stump on its own, on both the training and the test rows.
6. Measure the ensemble of the first k stumps for every k, and find where it stops improving.
7. List the training rows carrying the most weight at the end, and say what they have in common.
8. Run AdaBoostClassifier for several numbers of rounds and compare.

Observations

The five heaviest training rows at the end.

Result

Adaboost was implemented over decision stumps and trained for eight rounds on a 120-row dataset split 84 to 36. The best individual stump scored 0.821 on the training rows and 0.722 on the test rows; the ensemble reached 0.917 and 0.778 by round 5 and did not improve after it. The weighted error of each successive stump rose from 0.179 to 0.405 as the easy rows lost their weight. The two rows carrying by far the most weight at the end, 0.1350 and 0.1261 against a starting weight of 0.0119, were two of the rows whose labels had been deliberately flipped when the dataset was built. scikit-learn's AdaBoostClassifier reproduced the pattern, improving a single stump's 0.798 and 0.694 to 0.893 and 0.806.

Where marks are lost

Not comparing with the individual weak classifiers. It is the third sentence of MU's exercise. Print each stump's own accuracy beside the ensemble's.

Forgetting to normalise the weights. They must add to 1 after every round, or alpha stops meaning anything.

Using error instead of weighted error. The whole algorithm is in the word weighted.

Labels 0 and 1. exp(-alpha y prediction) needs +1 and -1: with 0 and 1 the update does nothing for one class.

An error of exactly 0. ln((1-0)/0) is undefined. Clamp the error away from 0 and 1, as the program does.

Reporting the training accuracy over many rounds. It rises for ever. Test accuracy stopped at round 5 here.

Using a full decision tree as the weak learner. Then it is not boosting weak classifiers, and one member can already do the whole job. Depth 1.

Running Adaboost on data you know is mislabelled and not saying so. It will put all its weight on the bad labels, which the observation table above shows happening.

For the journal

Aim; what a weak classifier is and what a decision stump is; the four steps of Adaboost with the alpha formula; the dataset and why the easier one was not used; the Stump class and best_stump; the boosting loop; the round-by-round table of stump, error and alpha; the accuracy of each stump alone against the ensemble at each size; the heaviest rows at the end with their scores on the underlying rule; the scikit-learn comparison; both observation tables; the result.

Quick revision

• A weak classifier is barely better than chance. A decision stump is a one-level tree.
• Every training row has a weight; they start equal and add to 1.
• Each round picks the stump with the smallest weighted error.
• alpha = 0.5 * ln((1 - error) / error). Low error, loud voice; error 0.5, no voice; error above 0.5, negative voice.
• Weights are multiplied by exp(-alpha y prediction) and then normalised, so wrong rows get heavier.
• The ensemble answers by the sign of the sum of alpha * prediction.
• Successive stumps have higher weighted error, because what is left is hard.
• Measured here: best stump 0.722 on test, ensemble 0.778, and no gain after round 5.
• Adaboost concentrates on hard rows, and a mislabelled row is hard, so it is sensitive to noise.

Questions you must be able to answer

1. What is a weak classifier, and which one did you use? One only a little better than guessing. A decision stump: one feature, one threshold, one answer each side.

2. How does the next round know what the last one got wrong? Through the weights. Every row the chosen stump got wrong has its weight multiplied up, so the next round's weighted error is dominated by those rows and the next stump is chosen to fix them.

3. What is alpha and where does it come from? The weight of a stump's vote in the final ensemble, computed from its weighted error as 0.5 * ln((1 - error) / error).

4. What alpha does a stump with error 0.5 get, and why is that right? Zero, because ln(1) is 0. A classifier that is right half the time carries no information, so it gets no vote.

5. What happens to a stump whose error is above 0.5? Its alpha is negative, so the ensemble uses the opposite of its answer. A classifier that is reliably wrong is as useful as one that is reliably right.

6. Why does the weighted error of each new stump keep rising? Because the rows the earlier stumps handle well have lost almost all their weight, so the remaining weight sits on the hard rows and any stump scores badly on them.

7. What did your ensemble gain over the best single stump? Training accuracy from 0.821 to 0.917 and test accuracy from 0.722 to 0.778, using classifiers that can each see only one feature.

8. Should you keep adding rounds? No. Training accuracy keeps rising, but test accuracy stopped at round 5 here and scikit-learn's stopped at 0.806 after five rounds out of a hundred. Choose the number of rounds by measuring on held-out data.

9. Why is Adaboost sensitive to noisy labels? Because a mislabelled row is permanently wrong, so its weight grows every round and the algorithm spends its later rounds on it. In this run the two heaviest rows at the end were two of the deliberately flipped labels.

10. Your ensemble and one of its stumps give different answers on a row. Which is used? The ensemble's, which is the sign of the sum of alpha * prediction over every stump. An individual stump's answer only ever enters through that sum.