Cross-validation and the bias-variance trade-off, visually

The most dangerous number in machine learning is the accuracy of a model on the data you trained it on. I’ve known that since Ng’s class in 2011, in the sense that I could have said it in an interview. I didn’t really believe it until the data science certificate made me fit the same data set with a dozen models in a row and watch the training error get better every single time while the predictions got worse.

This is my attempt to draw the whole thing out, mostly for the engineers on my team who keep asking me why I’m suspicious of the 97% in their slide.

Two ways to be wrong

Say the truth is a smooth curve and your data is that curve plus noise. Fit a straight line and you’ll miss the curve no matter how much data you have. That’s bias: the model is too simple to represent the thing, so it’s wrong in the same way every time. Fit a degree-15 polynomial to 40 points and it’ll pass through nearly every one of them, noise included. Draw a new sample of 40 and you get a completely different wiggly curve. That’s variance: the model is flexible enough to memorize the particular noise in this sample, so what it learns depends a lot on which sample you happened to get.

The textbook result (it’s in ISLR, which I’ve had open next to the certificate work for most of a year) is that expected test error splits into three parts: bias squared, plus variance, plus the irreducible noise that no model can remove. As you make a model more flexible, bias goes down and variance goes up. Training error only ever goes down, because a more flexible model can always fit the training data at least as well. Test error goes down and then back up, and the bottom of that U is where you want to be.

The problem is that you don’t have the orange curve. You have the blue one, and the blue one always says “more”.

Holding data back

The obvious fix is to keep some data aside, fit on the rest, and measure on what you kept. That works, but with small data sets it’s noisy. Which 20% you happened to hold back can move the number a lot, and you’ve thrown away 20% of your training data.

k-fold cross-validation squeezes more out of the same data. Split it into k chunks. Train on k − 1 of them, test on the one you left out, and do that k times so every chunk gets a turn as the test set. Average the k errors.

In base R it’s short enough to write yourself, which I’d recommend doing once before you reach for caret:

cv_error <- function(df, degree, k = 10) {
  folds <- sample(rep(1:k, length.out = nrow(df)))
  errs <- sapply(1:k, function(i) {
    train <- df[folds != i, ]
    test  <- df[folds == i, ]
    fit   <- lm(y ~ poly(x, degree), data = train)
    mean((predict(fit, test) - test$y)^2)
  })
  mean(errs)
}

sapply(1:12, function(d) cv_error(df, d))

Run that on 40 points of a sine wave plus noise and the CV error does what the orange curve does. It drops sharply at degree 3, where the polynomial can finally bend twice like a sine, stays roughly flat for a few degrees, and then gets erratic and large at the high end, where some folds give the polynomial room to go wild at the edges of the range. Meanwhile the in-sample error just keeps creeping down. On my run the training MSE at degree 12 was the best of the lot, and the CV error was about four times worse than at degree 5.

A couple of practical things the textbook says that I’ve found to be true. Five or ten folds is the usual choice, and the difference between them rarely matters. Leave-one-out (k = n) sounds like the most thorough option, but its estimate has high variance itself, because the n fits are almost identical to each other. And when several models are within noise of each other, pick the simplest one whose CV error is within one standard error of the best, rather than the absolute minimum. The minimum is itself a noisy estimate, and you’re picking the luckiest of several noisy numbers.

The wrong way, which I’ve seen in production

This is the bit I actually wrote the post for.

Cross-validation only measures what happens inside the loop. Anything you did to the data before the loop, using all of it, is invisible to it, and leaks information from the test folds into the model.

The classic version, and it’s an example in The Elements of Statistical Learning, goes like this. You have 50 samples, two classes, and 5,000 features. You pick the 100 features most correlated with the label, then run cross-validation on a simple classifier using those 100. You get a great number. The trouble is that the features were chosen using the labels of every sample, including the ones that will later be in the test folds, so each test fold has already influenced which features got picked.

I didn’t quite believe how bad this is, so I tried it with pure noise. 50 samples, 5,000 random Gaussian features with no relationship to the labels at all, keep the top 100 by correlation, 1-nearest-neighbor, 5-fold CV. Done the wrong way, with the screening outside the loop, CV error came out between 0% and 4% across a few runs. On data that is, by construction, a coin flip. Done the right way, picking the 100 features again inside each fold using only that fold’s training data, the error came out between 44% and 54%, which is the honest answer.

The rule is that every step that looks at the labels has to be inside the loop: feature selection, choosing hyperparameters, target encoding, anything at all that uses the outcome. In practice I’d add “picking which model to report after looking at the CV numbers for twenty of them”, which is the same leak at one remove. If you’re going to do that, keep a final test set aside that nobody touches until the very end, and look at it once.

The production version I’ve seen, on our own team, was a churn model where someone had built a “customer health” feature from the full history, including events that only happened after the customer had already decided to leave. Cross-validated beautifully. It was predicting the past. Nobody had done anything wrong in the CV code; the leak was upstream, in a SQL view.

Why I care at work

Most of what my team builds isn’t machine learning, but more and more of it touches it, a scoring model here, an anomaly detector there, and the failure mode is always the same. Someone shows a great number, it ships, and three months later it’s quietly worse than the heuristic it replaced. The question I’ve started asking in reviews is “what data did that number come from, and what did the model see before it was computed?” People find it annoying, and most of the time the answer is fine. The churn model is why I keep asking anyway.

If you want to try the noise experiment yourself it’s about 25 lines of R, and I’d recommend it. Watching a coin flip score 96% or better does more for your skepticism than any amount of reading about it.