Overfitting, Bias-Variance & Cross-Validation

A single decision tree, grown deep enough, will classify every training point perfectly. It can also be useless on new data. That gap between "perfect on what it has seen" and "poor on what it has not" is the single most important idea in machine learning, and it is exactly the weakness that random forests and boosting exist to fix. This lesson gives you the vocabulary and the tools to name that gap precisely: bias, variance, irreducible noise, and the honest measuring stick of cross-validation.

We build it on three pillars at once. The math decomposes expected test error into three terms you can reason about. The intuition comes from a dartboard and an animated k-fold split. And the code lets you watch the U-shaped error curve appear, and lets you cross-validate a real tree in your browser.

Underfitting versus overfitting

Every supervised model sits somewhere on a spectrum of capacity, its freedom to bend to the data.

• Underfitting (too little capacity). The model is too simple to capture the real pattern. A depth-1 stump splitting a spiral, or a straight line through a curve. Training error is high, and test error is high too, because there is genuine structure the model never learned.
• Overfitting (too much capacity). The model is flexible enough to trace not just the signal but the noise in the training sample. A depth-20 tree that carves out a private rectangle around every point. Training error falls toward zero, but test error climbs, because the memorized quirks do not repeat on new data.

The tell is the gap between training error and validation error. When both are high, you are underfitting. When training error is low but validation error is much higher, you are overfitting. Train the network below and watch the two curves: as capacity or training time grows, the red validation curve stops tracking the green training curve and turns back upward. That divergence is overfitting, made visible.

Crank the capacity slider up, or shrink the training set size, and the gap widens. Add data, weight decay, dropout, or early stopping, and it narrows. Trees have their own version of every one of those knobs (max_depth, min_samples_leaf, pruning), but the phenomenon is identical. To fix it deliberately rather than by trial and error, we need to name where the error comes from.

The bias-variance decomposition

Fix a single input $x$. Assume the true label is a deterministic function plus noise:

Here $f(x)$ is the best possible answer and $\varepsilon$ is irreducible measurement noise: two houses with identical features still sell for slightly different prices. Now let $\hat f$ be a model trained on a random training set $\mathcal{D}$. Because $\mathcal{D}$ is random, $\hat f(x)$ is itself a random quantity: retrain on a fresh sample and the prediction shifts. Taking expectations over both the noise and the draw of the training set, the expected squared error at $x$ splits into three clean pieces:

In the compact form you should memorize:

Read each term:

• Bias² is how far the average model (averaged over all possible training sets) lands from the truth $f(x)$. High bias means the model class is systematically wrong no matter which sample you train on. A linear model on a curve, or a shallow stump: they miss the target the same way every time.
• Variance is how much a single trained model bounces around that average as the training set changes. High variance means the model is chasing the sample. A deep unpruned tree: two trees grown on two samples from the same source can look wildly different.
• σ² (irreducible noise) is the floor. No model, however perfect, can beat it, because the labels themselves carry randomness. It is why chasing zero test error is a mistake.

Only the first two terms are under your control. This is why we say error is a trade-off: simplifying a model (shallower tree, more pruning) lowers variance but usually raises bias; enriching it (deeper tree) lowers bias but raises variance. The art is finding the capacity where their sum is smallest.

Seeing it on a dartboard

Picture the bullseye as the truth $f(x)$, and each dart as one model trained on one random dataset. Bias is how far the cluster of darts sits from the bullseye. Variance is how spread out the darts are. Toggle the two knobs below and throw again.

The four corners map onto four kinds of model:

• Low bias, low variance is the goal: a tight cluster on the bullseye. Rare, and usually the result of the right capacity plus plenty of data.
• Low bias, high variance is the lone deep tree: centered on the truth on average, but any single tree scatters far. This is precisely the case bagging (random forests) attacks, by averaging many high-variance trees to shrink the spread.
• High bias, low variance is the stump: consistent, but consistently off. Boosting attacks this by adding weak learners to reduce bias.
• High bias, high variance is the worst case: wrong and unstable.

Hold onto that second corner. The whole reason random forests work is that a deep tree is a low-bias, high-variance machine, and variance is the one component you can cancel by averaging.

The U-shaped test-error curve

Now sweep capacity from low to high and plot the error. Training error only ever falls: more capacity can always fit the training set better. Test (validation) error tells a different story. It starts high (underfit, bias-dominated), falls to a minimum, then rises again (overfit, variance-dominated). That is the famous U.

The bottom of the U is the sweet spot, the capacity where bias² + variance is minimized. Everything to the left is too simple; everything to the right is memorizing noise. Below, we make the U appear for real: validation_curve trains a DecisionTreeClassifier at every max_depth from 1 to 17, with 5-fold cross-validation at each depth, and plots training error against validation error. Press Run.

The left arm of the U is high bias, the right arm is high variance, and the dashed line marks the depth where their sum bottoms out. Try widening flip_y to 0.2 and watch the right arm climb harder: more label noise means more for a deep tree to overfit.

k-fold cross-validation

The U-curve above needed a validation error at every depth. Where did it come from? Not from the test set, which we must never touch until the very end, and not from a single train/validation split either, because one split is a coin flip: get an easy validation slice and you look great, get a hard one and you look terrible. The estimate wobbles.

k-fold cross-validation removes the luck. Split the training data into $k$ equal folds. Then, $k$ times over, hold out one fold as validation, train on the other $k-1$, and score on the held-out fold. Every point is validated exactly once, and every point is trained on $k-1$ times. Average the $k$ scores:

where $\operatorname{err}(\text{fold}_i)$ is the error of the model trained on every fold except $i$, evaluated on fold $i$. The mean is a low-variance estimate of generalization error, and the standard deviation across folds tells you how much you can trust it. Step through the mechanics below: each fold takes its turn in red as the held-out validation set, and the scores accumulate into the CV estimate on the right.

Notice two things. First, the locked test set on the side is never involved: cross-validation squeezes an honest estimate out of the training pool alone, which is what lets you compare models and tune hyperparameters without ever peeking at the final exam. Second, larger $k$ means each model trains on more data (so less bias in the estimate) but costs $k$ full fits and gives correlated folds. $k = 5$ and $k = 10$ are the standard compromises; $k = n$ is leave-one-out, maximally thorough and maximally expensive.

Now run it for real. Below, cross_val_score with an explicit KFold object evaluates a depth-5 tree across 5 shuffled folds and reports the mean plus or minus the standard deviation, then contrasts that with the jumpy accuracy of eight different single splits.

The single-split accuracies swing noticeably from seed to seed. The cross-validated estimate averages that luck away, which is why CV, not one split, is the honest way to choose max_depth, compare a tree against a forest, or report a number you would stake a decision on.

Test yourself

Interview readiness