Overfitting and cross-validation

Compare training accuracy with leave-one-out validation accuracy to choose k and detect memorization.

xs = list(range(1, 13))
labels = [0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1]


def predict(train_x, train_y, x, k):
    order = sorted(range(len(train_x)), key=lambda i: abs(train_x[i] - x))
    votes = [train_y[i] for i in order[:k]]
    return 1 if sum(votes) * 2 > len(votes) else 0


def train_accuracy(k):
    return sum(predict(xs, labels, x, k) == y for x, y in zip(xs, labels)) / len(xs)


def leave_one_out_accuracy(k):
    correct = 0
    for i in range(len(xs)):
        rest_x = xs[:i] + xs[i + 1:]
        rest_y = labels[:i] + labels[i + 1:]
        correct += predict(rest_x, rest_y, xs[i], k) == labels[i]
    return correct / len(xs)


for k in (1, 3, 5):
    print(k, round(train_accuracy(k), 3), round(leave_one_out_accuracy(k), 3))

1 1.0 0.75
3 0.917 0.75
5 0.833 0.833

Explanation

A model overfits when it learns the noise and quirks of its training data instead of the underlying pattern. It then does very well on the data it has seen and worse on new data. The opposite problem, underfitting, is a model too simple to capture the pattern. The gap between training and validation performance is the main warning sign.

Cross-validation estimates how well a model will generalize. In k-fold cross-validation the data are split into k parts. Each part in turn is held out for validation while the model trains on the rest, and the scores are averaged. Leave-one-out is the extreme case with one example per fold. Cross-validation is used to choose hyperparameters such as k in k-NN or the depth of a tree. A separate test set should still be kept aside for the final, unbiased estimate, and any preprocessing must be fitted inside each training fold to avoid data leakage.

In the example, a one-dimensional dataset of 12 points has a noisy label at x = 5. With k = 1 the classifier memorizes its training data and has 100 percent training accuracy, but its leave-one-out accuracy is only 0.75. As k grows the classifier smooths over the noise: the training accuracy falls, while the leave-one-out accuracy rises to 0.833 at k = 5. With only 12 points these estimates are rough, so treat the numbers as an illustration of the pattern, not a precise ranking.

—

—

—

1 1.0 0.75
3 0.917 0.75
5 0.833 0.833

Cost and common mistakes

Leave-one-out requires n evaluations of a model with prediction cost O(n log n) here, so O(n² log n) in total. k-fold with k = 5 or 10 is usually cheaper.

• Training accuracy is not a measure of quality. A perfect training score, especially with k = 1, often signals memorization.
• Do not use the validation score to pick hyperparameters and then report it as the final performance. Keep a separate test set.
• Fit scalers and other preprocessing inside each training fold. Fitting them on all the data leaks information into validation.

Try it yourself

Why is training accuracy always 1.0 for 1-nearest-neighbour when the stored points are unique?

Further reading

• scikit-learn user guide (external)
• An Introduction to Statistical Learning (James, Witten, Hastie, Tibshirani) (external)
• Stanford CS229: Machine Learning (external)