Statistical learning

1What learning is for

Two students prepare for an exam using past papers. One memorises every answer word for word. The other works out why each answer is right. On the past papers they both score 100%. On the real exam, with new questions, only one of them does well.

That is the central problem of machine learning. A learner is shown examples, but the examples are not the point. The point is to do well on new cases it has never seen. Doing well on new cases is called generalisation. Doing well only on the examples you were shown is memorisation.

You have already seen this problem twice. In Week 1 we always tested the umbrella learner on new days, never on the days it learned from. In Week 4 a learner that remembered exact 14-day weather patterns scored worse than one that only counted rainy days, because most new situations were ones it had never seen. This week we study the problem directly, with a new task and a new learner.

2The mango problem

A market trader wants a machine to sort mangoes into ripe and not ripe. For each mango it measures two things:

• Colour, from 0 (fully green) to 1 (fully yellow);
• Firmness, from 0 (very soft) to 1 (very hard).

Experienced sorters have labelled some mangoes "ripe" or "not ripe". In our simulation, the true rule is a curved boundary: mangoes that are yellow and soft are ripe. But the sorters make mistakes, and 10% of the labels are wrong.

Those mistakes matter. Even a machine that knew the true rule perfectly would disagree with the wrong labels. On our test set of 2,000 mangoes, knowing the true rule scores 0.913. That is the best possible accuracy; no learner can reliably do better. At the other end, a lazy machine that always says "not ripe" scores 0.600, because 60% of the mangoes are not ripe. Any learner worth having should land between those two numbers.

3Ask the neighbours

Here is perhaps the simplest learner there is. To decide about a new mango, find the k mangoes in the training data that are most similar to it, meaning closest in colour and firmness, and go with the majority. This is called k nearest neighbours.

def knn_predict(train, colour, firmness, k):
    # the k training mangoes closest to this one
    nearest = heapq.nsmallest(k, train,
        key=lambda m: (m[0] - colour) ** 2 + (m[1] - firmness) ** 2)
    # majority vote: are more than half of them ripe?
    return 2 * sum(m[2] for m in nearest) > k

"Learning" here is just storing the training mangoes. All the work happens when a new mango arrives. The one setting you choose is k, how many neighbours to ask:

• k = 1: copy the single most similar mango. If that one was mislabelled, so is your answer.
• Large k: ask many neighbours. Individual mistakes get outvoted, but neighbours from further away, which may be quite different, get a vote too.
• k = all of them: every mango gets the same answer, the overall majority. That is the lazy "always not ripe" machine.

A setting like k, chosen by you rather than learned from the data, is called a hyperparameter.

4Memorising and smoothing

Part A of the code trains on 200 mangoes and measures accuracy twice: on the 200 training mangoes themselves, and on 2,000 new test mangoes. It repeats this with 10 different training sets and averages, so that the luck of one particular set does not dominate.

Read the two columns separately:

• Training accuracy only goes down as k grows. With k = 1, every training mango's nearest neighbour is itself, so it scores a perfect 1.000, including on the 10% of labels that are wrong. It has memorised the mistakes along with everything else.
• Test accuracy rises, then falls. It is worst at the extremes and best in the middle, around k = 7 to 15, where it reaches 0.884, close to the best possible 0.913.

From k = 7 onwards the gap is slightly negative: the learner does a little better on new mangoes than on the ones it trained on. That is not an error. Once it stops memorising, training mangoes are just more mangoes, about 10% of them mislabelled, and our particular test set happens to have fewer wrong labels (8.7%).

The two ends of the table fail in opposite ways:

Overfitting (k too small)

The learner follows every detail of the training data, including the noise. It looks perfect on what it has seen and does worse on what it has not. The generalisation gap, training minus test accuracy, is large: 0.195 at k = 1.

Underfitting (k too large)

The learner smooths so much that it misses the real pattern. At k = 199 it says the same thing for every mango. Training and test accuracy are both poor.

A useful word for where a learner sits between these is capacity: how complicated a pattern it can follow. Small k means high capacity, able to draw a boundary that weaves around every single mango. Large k means low capacity. The right capacity depends on how much data you have and how noisy it is.

5Fitting nonsense

Here is a stranger experiment. Take the 200 training mangoes and shuffle the labels: deal out the same number of "ripe" and "not ripe" labels at random, so that labels no longer have anything to do with colour or firmness. There is now nothing to learn. Then train the same 1-nearest-neighbour learner.

Both score a perfect 1.000 on their training data. One has learned something real about mangoes; the other has learned nothing at all, and does no better than tossing a slightly biased coin on new mangoes. From the training score alone you cannot tell which is which.

This is not a quirk of nearest neighbours. In 2017, Zhang and colleagues showed that large neural networks of the kind used in modern AI could also fit completely random labels on image datasets perfectly. Yet the same networks, trained on real labels, generalise well. Why they generalise when they clearly could just memorise is still not fully understood.

Replicated finding Large neural networks can perfectly fit random labels, and they generalise when trained on real ones. This has been reproduced many times since Zhang et al. (2017).

Open question Why some learners that are able to memorise nonetheless generalise is one of the main unsolved questions in learning theory. It is the course's research question Q4.

6More data, and choosing fairly

More data

The simplest cure for overfitting is more examples. Part C trains on more and more mangoes and measures test accuracy, averaged over 5 training sets of each size.

• With k = 15, more data steadily helps, and by 1,600 mangoes the learner is within a percentage point of the best possible.
• With k = 1, it levels off around 0.83 and stays there. However much data you give it, it still copies one neighbour, and 10% of neighbours are mislabelled. There is a classic result here: with unlimited data, the 1-nearest-neighbour learner's error rate approaches at most twice the best possible error rate.
• With only 25 mangoes, k = 15 is the worse choice: asking 15 neighbours out of 25 means asking mangoes that are not similar at all. The right k depends on how much data you have.

Established result As training data grows without limit, the 1-nearest-neighbour error rate is at most twice the best possible error rate (Cover & Hart, 1967). Here, twice the 8.7% best possible error is about 17%, an accuracy of 0.83, which is where the k = 1 column settles.

Choosing k without cheating

Table 1 says k = 7 or 15 is best. But we only know that because we looked at the test set. In real life the test set stands for the future, and you cannot look at the future. If you try twenty settings and keep the one that does best on the test set, your test score is no longer an honest estimate. You have, in a small way, fitted the test set.

The fix is to split the data you do have. Part D takes one training set of 200 mangoes, learns from 150 of them, and checks each k on the other 50, called the validation set. It picks the best k there, then retrains on all 200 and is tested once, at the very end.

Validation picks k = 31, which scores 0.885 on the test set: as good as the best in Table 1, found without peeking. Notice how bumpy the validation scores are, though. With only 50 mangoes, one mango more or less right moves the score by 0.02. Small validation sets give noisy choices; seminar exercise 3 shows a standard way to make them steadier.

7Summary

• Learning is for generalisation: doing well on new cases, not on the examples you were shown.
• Noisy labels set a ceiling on accuracy. Here no learner can reliably beat 0.913.
• The nearest-neighbour learner labels a new case by a vote among the k most similar training cases.
• Small k overfits: perfect on training data, worse on test data. Very large k underfits: poor on both. The best test accuracy (0.884) came in between.
• A learner can fit shuffled, meaningless labels perfectly. Training accuracy alone cannot distinguish learning from memorising.
• More data helps learners that smooth, but a learner that copies one neighbour levels off, as theory predicts.
• Choose settings on a validation set. Use the test set once, at the end.

·Key terms

Generalisation

Doing well on new cases the learner was not trained on.

Memorisation

Doing well only on the training cases, by storing them rather than learning a pattern.

Label noise

Training labels that are wrong.

Best possible accuracy

The accuracy of the true rule. No learner can reliably beat it. Also called the Bayes rate.

k nearest neighbours

Label a new case by majority vote among the k most similar training cases.

Hyperparameter

A setting chosen by the designer, such as k, rather than learned from data.

Overfitting

Following the training data so closely, noise included, that performance on new data suffers.

Underfitting

Being too simple to capture the real pattern.

Generalisation gap

Training accuracy minus test accuracy.

Capacity

How complicated a pattern a learner is able to follow.

Validation set

Data held back from training and used to make choices such as hyperparameters.

Test set

Data locked away until the end and used once to report final performance.

·Check your understanding

Try each question before opening the answer.

1. Why does the 1-nearest-neighbour learner always score 1.000 on its own training data?
   Show answer

   Each training mango's nearest neighbour is itself, at distance zero. So it always "predicts" the label it was given, right or wrong.

2. A learner scores 0.99 on its training data and 0.70 on new data. Overfitting or underfitting? What would you try first?
   Show answer

   Overfitting: a large generalisation gap. Reduce its capacity (for nearest neighbours, increase k) or give it more training data.

3. Why can no learner reliably beat 0.913 on the mango test set?
   Show answer

   About 9% of the test labels are wrong. A learner that predicted those wrong labels would have to predict the sorters' random mistakes, which have nothing to do with colour or firmness.

4. With shuffled labels, the learner scored 0.521 on the test set. Why not exactly 0.5?
   Show answer

   Two reasons. The labels are not 50/50 (about 60% "not ripe"), so random guesses with the same mix are right a bit more than half the time by chance. And with only 2,000 test mangoes, any score wobbles a little.

5. A classmate tries 50 settings and reports the best test-set score. Why is that score probably too optimistic?
   Show answer

   By keeping whichever setting happened to do best on the test set, they partly fitted the test set itself, including its luck. The honest way is to choose on a validation set and test once.

·Seminar exercises

As always, write your prediction before you run anything.

1. Cleaner labels. Set LABEL_NOISE to 0 and rerun Part A. Predict first: what happens to the best k, and to the gap at k = 1? Then try 0.3.
2. Half shuffled. Shuffle only half of the training labels. What test accuracy do you expect with k = 1, and with k = 31? Which learner is hurt more by bad labels, and why?
3. Steadier choices. Instead of one validation set of 50, split the 200 mangoes into 5 groups of 40. For each k, train on 4 groups and validate on the fifth, rotating 5 times, and average. This is called 5-fold cross-validation. Is the chosen k more stable across different training sets than in Table 4?
4. A third measurement. Add a third feature to each mango that is pure noise, such as a random number for the day of the week it was picked, scaled to the same range. Rerun Part A. Why does a useless feature hurt nearest neighbours? Link your answer to Week 4's curse of dimensionality.

·Readings

• Core. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). An introduction to statistical learning (2nd ed.). Springer. Sections 2.1–2.2, on assessing accuracy, overfitting and nearest neighbours. The book is freely available online from its authors.
• Core. Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. ICLR. Read the introduction and Section 2, the random-labels experiment. This is the basis for Laboratory 5.1.
• Further. Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press. Chapter 2, for a precise statement of when learning from examples is possible.