∑GATE DA Atlas
GATE DA / Machine Learning

Bias–Variance Trade-off and Cross-Validation

Underfitting and overfitting, the bias–variance decomposition of expected squared error, how model complexity, regularisation and data size move bias and variance, learning curves, and estimating generalisation error — hold-out validation, k-fold cross-validation, leave-one-out cross-validation, stratification, nested CV, and avoiding data leakage.

Section 610 practice questions

Underfitting and overfitting

UnderfittingGood fitOverfitting
Training errorhighlowvery low
Test errorhighlowhigh
Gapsmallsmalllarge
Causemodel too simple / too regularised—model too flexible for the data, fits noise
model complexity →error trainingtest underfit: high biasoverfit: high variancesweet spot
Training error keeps falling with complexity; test error is U-shaped.

The bias–variance decomposition

Suppose y=f(x)+εy = f(\mathbf x) + \varepsilon with E[ε]=0E[\varepsilon] = 0, Var⁡(ε)=σ2\operatorname{Var}(\varepsilon) = \sigma^2, and f^\hat f is learned from a random training set. At a point x\mathbf x:

E[(y−f^(x))2]=(E[f^(x)]−f(x))2⏟bias2+E[(f^(x)−E[f^(x)])2]⏟variance+σ2⏟irreducible.E\big[(y - \hat f(\mathbf x))^2\big] = \underbrace{\big(E[\hat f(\mathbf x)] - f(\mathbf x)\big)^2}_{\text{bias}^2} + \underbrace{E\big[(\hat f(\mathbf x) - E[\hat f(\mathbf x)])^2\big]}_{\text{variance}} + \underbrace{\sigma^2}_{\text{irreducible}}.
  • Bias: error from wrong assumptions — how far the average model is from the truth.
  • Variance: how much the model changes with the training sample.
  • Irreducible error: noise no model can remove.
low bias, low variance low bias, high variance high bias, low variance high bias, high variance
Each dot is a model trained on a different sample; the bull's-eye is the truth.

What moves bias and variance

ChangeBiasVariance
More flexible model (higher polynomial degree, deeper tree, smaller kk in k-NN, larger CC/γ\gamma in SVM)↓↑
Stronger regularisation (larger λ\lambda)↑↓
More training data≈↓
More features↓↑
Bagging / averaging models≈↓
Boosting↓(↑ if overdone)

Learning curves (error vs training-set size) diagnose the problem: if training and validation errors converge at a high value, the model is biased (more data won't help); if a large gap remains, it has high variance (more data helps).

Estimating generalisation error

Hold-out validation

Split once into training and validation (e.g. 80/20). Cheap, but the estimate depends on the particular split and wastes data — risky for small data sets.

k-fold cross-validation

  1. Split the data into kk equal folds.
  2. For i=1,…,ki = 1, \dots, k: train on the other k−1k - 1 folds, evaluate on fold ii.
  3. Average the kk validation errors: CV(k)=1k∑iErri\text{CV}_{(k)} = \frac1k\sum_i\text{Err}_i.
run 1run 2run 3run 4run 5 → Err₁→ Err₂→ Err₃→ Err₄→ Err₅ red: validation fold · green: training folds · estimate = mean of Err₁…Err₅
5-fold CV: every example is validated exactly once.
  • k=5k = 5 or 1010 is the standard trade-off between bias (smaller training sets) and variance/computation.
  • Stratified k-fold keeps class proportions equal across folds — important for imbalanced classification.
  • Repeated CV with different shuffles reduces the variance of the estimate.
  • For time series, use forward-chaining splits (train on the past, validate on the future), never random folds.

Leave-one-out cross-validation (LOOCV)

k=nk = n: train on n−1n - 1 points, test on the one left out, nn times.

LOOCV5/10-fold CV
Training-set sizen−1n - 1 (almost all)0.8n0.8n–0.9n0.9n
Bias of the estimatevery lowslightly pessimistic
Variance of the estimatecan be high (folds nearly identical)lower
Costnn fits (closed form for linear regression: 1n∑(ei1−hii)2\frac1n\sum\left(\frac{e_i}{1 - h_{ii}}\right)^2)kk fits
Randomnessdeterministicdepends on the split

Using CV correctly

  • Model selection: compute the CV error for each hyperparameter value (e.g. λ\lambda, kk, depth) and pick the best; then retrain on all the training data.
  • Nested CV: an outer loop estimates performance while an inner loop tunes hyperparameters — otherwise the selected model's CV score is optimistically biased.
  • The test set is used once, at the very end.
  • No leakage: fit every preprocessing step (scaling, imputation, feature selection, oversampling) inside the training folds only.

Quick revision

Practice questions

GATE-style questions: 3 one-mark and 7 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.

Q1MCQ1 mark

A model has high error on both the training set and the test set, with the two errors close to each other. The model is most likely

Q2MSQ2 marks

Which statements about the bias–variance trade-off are correct?

One or more options are correct.

Q3NAT2 marks

In 5-fold cross-validation on a data set of 1000 examples, each model is trained on how many examples? ______

Q4NAT1 mark

Leave-one-out cross-validation on a data set of 50 examples requires fitting the model ______ times.

Q5MCQ2 marks

Compared with 10-fold cross-validation, leave-one-out cross-validation gives an error estimate that is

Q6NAT2 marks

At a test point, an estimator has bias 0.3 and variance 0.16, and the noise variance is 0.1. The expected squared prediction error there is ______.

Q7MCQ1 mark

Training accuracy is 99% but test accuracy is 70%. Which action is least likely to help?

Q8NAT2 marks

5-fold cross-validation gives validation errors 0.10, 0.12, 0.08, 0.11 and 0.09. The cross-validation estimate of the error is ______.

Q9MCQ2 marks

Which procedure causes data leakage in cross-validation?

Q10NAT2 marks

A 1-nearest-neighbour classifier is evaluated by leave-one-out cross-validation on four 1-D points: x=1x = 1 (A), x=2x = 2 (A), x=4x = 4 (B), x=7x = 7 (B). The LOOCV error rate is ______.