Overfitting and the Bias-Variance Trade-off, Derived Step by Step

Imagine a model that scores perfectly on every example it was trained on. Zero error. Flawless. Then you show it one new example, and it is badly wrong. This is not a rare bug. It is the central problem of machine learning, and today we will understand it completely, including the mathematics behind it.

• Training error: zero
• New data: disaster

In the previous episode we built our Python and data foundations, including how to split data into training, validation and test sets. Now we use those tools to answer a deeper question. Why does a model that fits the past perfectly sometimes predict the future terribly, and what can we do about it?

• Last time: Python and data
• Today: why models fail on new data

Here is the plan. First, the difference between learning and memorizing. Then polynomial fits of different degrees, so you can see underfitting and overfitting. Next, we derive the bias-variance decomposition line by line, and confirm it with a Python simulation. We finish with baselines, experimental design, and a quick recap of data leakage.

• Memorization vs learning
• Polynomial fits
• Bias-variance derivation
• Simulation and baselines

Consider a lookup table. You store every training input with its answer. Ask about a stored input and it answers perfectly. Ask about anything new and it has nothing to say. That is pure memorization, and it achieves zero training error while being useless for prediction.

• Lookup table = perfect recall
• Zero understanding

Learning means capturing the underlying pattern, the signal, while ignoring the accidental wiggles, the noise. Every real measurement is signal plus noise. A model that learns the signal will do well on new data. A model that also copies the noise has memorized, and the noise will not repeat.

• Find the pattern
• Ignore the noise
• Predict unseen inputs

Generalization is how well a model performs on data it has never seen, drawn from the same source as the training data. That is the real goal. Training error is only a means to an end. We care about the expected error on future examples, which we can never observe directly, only estimate.

• Performance on unseen data
• True goal of ML

Let us experiment. The hidden truth is a sine curve. We draw ten x values between zero and one, compute the sine, and add random noise with a standard deviation of point two. Our job is to recover the curve from those ten noisy dots, using polynomials of different degrees.

• True function: sine wave
• Ten noisy points
• Noise standard deviation 0.2

A polynomial of degree d has the form w zero plus w one x plus w two x squared, and so on up to w d times x to the d. That is d plus one parameters. Higher degree means more flexibility, so the curve can bend more. We fit each one by minimizing mean squared error on the training points.

• Degree d polynomial
• d + 1 parameters
• Higher degree = more flexible

Degree one is a straight line. It cannot bend, so it misses the sine shape. Its training error is large, around point four in a typical run, and its validation error is similar. This is underfitting: the model is too simple to capture the pattern, so it fails everywhere, even on data it has seen.

• Straight line misses the curve
• High training error
• High validation error

Degree three can make an S shape, which matches the sine over this range quite well. Training error drops to around point oh three, close to the noise variance of point oh four. The curve follows the signal and ignores most of the noise. That is the sweet spot we are looking for.

• Captures the S-shape
• Error near noise level

Degree nine has ten parameters, exactly as many as we have data points, so it can pass through every single dot. Training error is essentially zero. But between the dots the curve swings wildly, nowhere near the true sine. It has memorized the noise, and its error on new points is huge.

• Passes through every point
• Wild swings between points

There is a clean reason for this. A polynomial with n parameters can always be chosen to pass exactly through n points, as a system of n equations in n unknowns. So when the number of parameters reaches the number of data points, zero training error is guaranteed, and it tells us nothing about quality.

• Parameters vs data points
• Interpolation = zero error

To detect this, we hold out data the model never trains on. We fit on the training set and measure error on the validation set. If we generate fifty fresh validation points from the same sine plus noise, we can score every degree fairly, and see how each curve really behaves on unseen inputs.

• Fit on training set
• Score on validation set

Now plot error against polynomial degree. On the horizontal axis, complexity. On the vertical axis, mean squared error. For each degree we compute one training error and one validation error. Watch what the two curves do as complexity grows.

• x-axis: model complexity
• y-axis: error
• Two curves

The training error only goes down. A higher degree polynomial contains every lower degree polynomial as a special case, so it can always fit at least as well. Roughly, it falls from point four at degree one, to point oh three at degree three, and reaches zero at degree nine.

• More flexibility, lower training error
• Reaches zero at degree 9

The validation error tells a different story. It falls while the model gains the ability to capture the signal, reaches a minimum near degree three, then climbs sharply as the model starts fitting noise. At degree nine it might be above three. That U shape is the signature of overfitting.

• Falls, then rises
• Minimum marks best complexity

The distance between the two curves is the generalization gap. At degree three it is tiny, about point oh two. At degree nine it is enormous. A useful diagnosis: if both errors are high, you are underfitting. If training error is low but validation error is much higher, you are overfitting.

• Gap = validation minus training
• Large gap signals overfitting

Data changes the picture. With the same degree nine polynomial but one hundred points instead of ten, there are far more constraints than parameters, so the curve cannot chase individual noisy dots. The gap shrinks. Overfitting depends on complexity relative to the amount of data, not on complexity alone.

• Same degree 9, more points
• Gap shrinks

Complexity is not just degree. It also includes the number of features, the depth of a tree, the number of neighbors in a nearest neighbor model, and how strongly we penalize large weights. In general, complexity is how rich the family of functions is that the model can choose from.

• Number of parameters
• Allowed flexibility
• Regularization strength

Recall the difference between parameters and hyperparameters. The weights are learned from training data. The degree is a hyperparameter that we choose. And we choose it using validation error, never training error, because training error will always vote for the most complex model.

• Parameters: learned
• Hyperparameters: chosen by us

Now the deeper question. Why does the U shape happen? We can answer it exactly for squared error. We will split the expected error at a point into three pieces: bias, variance, and irreducible noise. This is the bias-variance decomposition, and we will derive every step.

• Why does the U-shape happen?
• Split error into parts

Setup. The true relationship is y equals f of x plus epsilon, where epsilon is noise with mean zero and variance sigma squared. We train a model on a random training set D, giving a prediction f hat of x. The training set is random, so f hat is a random quantity. We analyze a fixed point x zero, and the new noise epsilon is independent of the training set.

• y = f(x) + noise
• Noise mean 0, variance sigma squared
• Model f-hat trained on random dataset

We want the expected squared error at x zero: E of y minus f hat of x zero, all squared. The expectation averages over every possible training set and every possible noise value. To simplify, write f for f of x zero, and let f bar be the average prediction, the expectation of f hat over all training sets.

• Expected squared error at x0
• Average over datasets and noise

Step one: rewrite y minus f hat. Since y equals f plus epsilon, we get epsilon plus f minus f hat. Now add and subtract f bar. This gives three terms: epsilon, plus the quantity f minus f bar, plus the quantity f bar minus f hat. Adding and subtracting the same number changes nothing, but it separates the pieces.

• y - f-hat = noise + (f - f-bar) + (f-bar - f-hat)
• Three terms

Step two: square the sum. Call the three terms A, B and C. The square of A plus B plus C is A squared, plus B squared, plus C squared, plus two A B, plus two A C, plus two B C. We now take the expectation of each piece. The three squares will give us the answer, so the question is what happens to the cross terms.

• Three squares
• Three cross terms

Cross terms. A times B: B is a constant, and the expectation of epsilon is zero, so it vanishes. A times C: epsilon is independent of the training set, so the expectation factors into the expectation of epsilon times the expectation of C, which is zero. B times C: B is constant, and the expectation of f bar minus f hat is f bar minus f bar, which is zero. All three cross terms disappear.

• E[A] = 0, A independent of C
• B is a constant
• E[C] = 0

What remains. The expectation of epsilon squared is sigma squared, the noise variance. The expectation of B squared is just B squared, since B is constant: f minus f bar, squared. That is the squared bias. And the expectation of f bar minus f hat, squared, is the definition of the variance of f hat. So the error equals sigma squared plus bias squared plus variance.

• E[A squared] = sigma squared
• E[B squared] = bias squared
• E[C squared] = variance

A tiny numeric check. Suppose the true value f at x zero is two, and the noise standard deviation is point five. Five models trained on five datasets predict two point five, three point five, three, two, and four. Their mean is three. So the bias is two minus three, which is minus one, and the squared bias is one.

• True f = 2, sigma = 0.5
• Predictions: 2.5, 3.5, 3.0, 2.0, 4.0
• Mean 3.0

Variance: the deviations from the mean are minus point five, point five, zero, minus one and one. Squares: point two five, point two five, zero, one and one, summing to two point five. Divide by five to get a variance of point five. Noise is point five squared, which is point two five. Total expected squared error: point two five plus one plus point five, which equals one point seven five.

• Deviations: -0.5, 0.5, 0, -1, 1
• Variance = 2.5 / 5 = 0.5
• Total = 0.25 + 1 + 0.5 = 1.75

Read the pieces in plain language. Bias is how far the average model is from the truth: a systematic miss caused by wrong assumptions, like forcing a line onto a curve. Variance is how much the prediction jumps around when the training set changes: sensitivity to the particular sample. Noise is the floor that no model can beat.

• Bias: systematic miss
• Variance: sensitivity to the dataset

Now the U shape makes sense. A degree one line is stable across datasets, so variance is low, but it can never match a sine, so bias is high. A degree nine polynomial can match anything on average, so bias is low, but it reshapes itself around every noisy sample, so variance is huge. Total error is minimized in between.

• Simple: high bias, low variance
• Complex: low bias, high variance

We can see variance directly. Draw many different training sets of ten points, fit a model to each, and overlay all the curves. Lines form a tight bundle, but miss the sine. Degree nine curves spray everywhere, though their average is close to the sine. The bundle width is variance, and the gap between the average and the truth is bias.

• Fit many models on many datasets
• Overlay the curves

Let us confirm all this in Python. The plan: repeat two hundred times. Each time, draw ten fresh noisy points from the sine, fit a polynomial of a given degree, and record its prediction at x zero equals point five. Afterwards, compute the mean prediction, the bias, and the variance across the two hundred predictions.

• Repeat 200 times
• Fit on fresh data
• Predict at x0 = 0.5

The code is short. Define the true function with numpy sine. Inside a loop, sample x uniformly, add normal noise with standard deviation point two, call numpy polyfit with the chosen degree, then numpy polyval at x zero. Store the results in an array. Then bias squared is the squared difference between true value and mean of the array, and variance is the array's variance.

• numpy polyfit and polyval
• Fresh sample each trial

The results follow the theory. For degree one, bias squared is large and variance small. For degree three, both are small, so the total sits near the noise floor of point oh four. For degree nine, bias squared is nearly zero, but the variance is enormous. The numbers depend on the random seed, but the pattern is stable.

• Degree 1: bias high, variance low
• Degree 3: both small
• Degree 9: variance explodes

As a final check, also measure the expected squared error directly. Generate fresh noisy targets at x zero, compare them with each model's prediction, and average the squared differences. The result matches noise plus bias squared plus variance, up to small simulation error. The decomposition is an identity, not an approximation.

• Measure error directly
• Compare with sum of three parts

Two honest caveats. This clean three-part split is exact for squared error; other losses like classification error have no equally tidy decomposition. And in real projects we never know the true function, so we cannot compute bias and variance directly. We simulate them in toy problems to build intuition, and use validation error in practice.

• Exact for squared error only
• Needs the true f, which we never know

Before any fancy model, build a baseline: the simplest sensible predictor. For regression, always predict the training mean. For classification, always predict the most common class. A baseline gives context. A validation error of point five means nothing until you learn that the baseline scores point five one.

• Simplest sensible predictor
• Gives a number to beat

Baselines expose a classic trap. Suppose ninety five percent of patients in a dataset are healthy. A model that always says healthy scores ninety five percent accuracy while detecting no sick patient at all. If your fancy model reports ninety six percent, it barely beats a trivial rule. We will fix this with better metrics in a later episode.

• 95 percent healthy patients
• Always say healthy: 95 percent accuracy

Experimental design starts with three roles. The training set fits parameters. The validation set chooses hyperparameters, like the degree. The test set gives the final, honest estimate and is used once. If you peek at the test set repeatedly while tuning, it silently turns into a second validation set, and your final number becomes optimistic.

• Train: fit parameters
• Validation: choose hyperparameters
• Test: final report, once

A single random split can mislead. With only ten or twenty validation points, the score could swing a lot depending on which points landed there. Better to repeat with several random seeds, or use cross validation, and report the mean and the spread. If two models differ by less than that spread, you cannot claim one is better.

• Random split changes the score
• Repeat and report mean and spread

Putting it together as a recipe. For each candidate degree, fit on the training set and score on validation. Pick the degree with the lowest validation error. Optionally retrain on training plus validation. Then evaluate once on the test set and report that number, next to the baseline. Cross validation, which we cover in a later episode, makes the selection step more reliable.

• Fit each degree on train
• Pick lowest validation error
• Report test error once

We covered data leakage in the Python and data episode, so here is just the reminder. Leakage means information from validation or test data sneaks into training, for example by scaling the whole dataset before splitting. It makes validation error look better than reality, which is a different way of fooling yourself than overfitting, but with the same disappointing result.

• Test information leaks into training
• Scores look great, then collapse

Three common mistakes. First, choosing a model by training error, which always favors complexity. Second, tuning on the test set until it looks good. Third, chasing zero error on noisy data: if the noise standard deviation is point two, no honest model can get below a mean squared error of about point oh four on new data. Zero is a warning sign, not a goal.

• Choosing by training error
• Tuning on the test set
• Ignoring noise level

If you are overfitting, you have levers. Get more data. Use a simpler model. Add regularization, which penalizes large weights and which we study soon. Or average many models, as ensembles do. If you are underfitting, do the opposite: add features, use a more flexible model, or reduce regularization. The diagnosis from the error curves tells you which way to move.

• More data
• Simpler model
• Regularization
• Averaging models

Recap. A model that learns generalizes; one that memorizes does not. Training error always falls with complexity, but validation error is U-shaped. For squared error, the expected error splits into noise, squared bias and variance, and we derived this by adding and subtracting the average prediction and watching the cross terms vanish. Always compare against a baseline, split your data properly, and touch the test set once.

• Learning generalizes
• Error = noise + bias squared + variance
• Validate, baseline, test once

Next time, in episode fourteen, we put these ideas to work on our first real algorithm: linear regression. We will derive the normal equation, solve it by hand, and compare it with gradient descent.

• Normal equation
• Gradient descent
• Subscribe for episode 14