The first figure of this section shows a zero training error next to the largest in the plot.
Answer $$\boxed{\text{nothing follows; }\mathrm{MSE}_{\mathrm{test}}\ \text{may be large}}$$
Check
In the same figure the degree-$3$ fit has a positive training MSE, $0.181$, and a test MSE of $0.190$, about eleven times smaller than the interpolating fit's, so a zero training error does not even rank models.
Keep this question in mind: the whole section is about what to measure instead.
A student calibrating a light sensor takes three readings: $1$, $3$ and $2$ volts at light levels $0$, $1$ and $2$. A parabola through the three points reproduces every reading exactly; the best straight line misses them with an average squared error of $0.5$. On three new readings, the parabola's average squared error is almost four times the line's.
By the end you can explain that result as against variance, and choose between such models from the readings alone with leave-one-out or .
In 60 seconds
A model is judged on data it has not seen: its expected test error splits into bias², variance and noise, and estimates that error from the training data alone by holding points out in turn.
choosing a degree or a tuning constant with $k$ fits per candidate
Three most common mistakes
Choosing the model with the lowest training MSE: it always favours the most flexible model, which can post a training error of $0$ and a large test error.
Averaging the gaps before squaring: bias² averages $(\bar f(x)-\bar y(x))^2$ over the inputs, so gaps of $+0.5$ and $-0.5$ give $0.25$, not $0$.
Scoring a point with a model that was fitted on it: in leave-one-out and k-fold CV, the model that predicts a point must be fitted without it.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The syllabus assesses the outcome 'train and test machine learning algorithms on a given dataset' through the problem sets and quizzes and through the term project.
How much time do you have?
10 minutes
The decomposition that explains every error curve in this section, and the cross-validation recipe that chooses a model without a test set.
The 60-second card · The bias-variance decomposition · k-fold cross-validation · Formula card
45 minutes
Every definition and method once, each with a worked example, then the bias-variance calculation from a full solution down to a bare problem.
The 60-second card · Training MSE and test MSE · The training set is random · The bias-variance decomposition · The tradeoff · The validation set approach · Leave-one-out cross-validation · k-fold cross-validation · Scaffolding comes off · Formula card
full read
Adds the proofs, the look-alike pairs and enough mixed practice to decide the method yourself.
The opening pages · Recall first · Training MSE and test MSE · The training set is random · The bias-variance decomposition · The tradeoff · The validation set approach · Leave-one-out cross-validation · k-fold cross-validation · Look-alike pairs · Method boxes · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Compute the training and test MSE of a fitted model, and explain why the training MSE can neither estimate the test error nor choose a model.
Define the expected label and the average model, and compute the average model and the prediction variance of simple algorithms, including a least squares line.
Derive the bias-variance decomposition and compute its three terms for a given algorithm and data model.
Diagnose and from bias and variance or from error curves, and state which terms an algorithm can change.
Estimate test error with a validation set, and quantify its two weaknesses: dependence on the split and training on less data.
Compute the leave-one-out error CV(n), by refitting or through the mean predictor's shortcut.
Run k-fold cross-validation to choose between models, count its fits, and refit the winner.
Syllabus coverage
covered
Measuring performance — covered
training MSE against test MSE
why a training error of zero is always available and proves nothing
training and test error as the flexibility grows
The official weekly list has no line of its own for this chapter; the lecturer teaches it as a separate chapter between least squares and regularized regression, and this section follows that chapter's order.
covered
bias-variance — covered
The random training set, the expected label and the average model
the decomposition of the expected squared test error into bias², variance and noise
which terms an algorithm controls
underfitting and overfitting
Spread over three blocks: the setup, the decomposition and the tradeoff.
covered
cross-validation — covered
The validation set approach and its two weaknesses
leave-one-out cross-validation
the k-fold version and its cost in fits
The validation set approach comes first, because both cross-validation methods are built to fix its weaknesses.
covered
model selection — covered
Choosing a polynomial degree or a tuning constant by validation or cross-validation error.
Named in the weekly line next to bias-variance and cross-validation; it runs through the last three blocks.
off syllabus
leave-one-out shortcut for least squares — off syllabus
The identity $y_i-\hat f_{D_i}(x_i)=(y_i-\hat y_i)/(1-h_{ii})$, which gives $\mathrm{CV}(n)$ for a least squares line from a single fit.
Further reading, not on the lecture slides. It appears once, in a worked example, and is checked there against two refits by hand.
off syllabus
refitting the winner and an honest final error — off syllabus
After choosing, refit the winner on all of the data; the smallest validation score is optimistic, so an honest error needs data that took no part in fitting or choosing.
Further reading: standard practice that the slides do not spell out.
Recall first
Least squares and RSS
For data $D=\{(x_i,y_i)\}_{i=1}^n$, least squares picks $\hat\beta$ to minimize $\mathrm{RSS}(\beta)=\sum_i(y_i-x_i^T\beta)^2$; with full column rank, $\hat\beta=(\mathbf X^T\mathbf X)^{-1}\mathbf X^T\mathbf y$.
Every fitted model on this page is a least squares fit, and an MSE is an RSS divided by the number of points.
Simple linear regression
$\hat\beta_1=\dfrac{\sum_i(x_i-\bar x)(y_i-\bar y)}{\sum_i(x_i-\bar x)^2}$ and $\hat\beta_0=\bar y-\hat\beta_1\bar x$, where $\bar y$ is the mean of the labels. With fixed inputs and uncorrelated noise of variance $\sigma^2$: $E[\hat\beta_j]=\beta_j^{\mathrm{true}}$, $\mathrm{Var}(\hat\beta_1)=\sigma^2/\sum_i(x_i-\bar x)^2$, and $\mathrm{Var}(\hat\beta_0)=\sigma^2/n$ when $\bar x=0$.
They give the bias and the variance of a fitted line exactly, without simulation.
Polynomial regression
Fitting $Y=\beta_0+\beta_1X+\dots+\beta_pX^p+\varepsilon$ is least squares on the columns $1,x,\dots,x^p$; the fit is unique when at least $p+1$ of the $x_i$ are distinct.
The degree is the flexibility knob in most examples, and with $n$ distinct inputs the degree $n-1$ passes through every point.
Mean and variance rules
$E[aZ+b]=aE[Z]+b$ and $\mathrm{Var}(aZ+b)=a^2\mathrm{Var}(Z)$. For independent $Z_i$: $\mathrm{Var}\big(\sum_ia_iZ_i\big)=\sum_ia_i^2\mathrm{Var}(Z_i)$ and $\mathrm{Cov}\big(\sum_ia_iZ_i,\sum_ib_iZ_i\big)=\sum_ia_ib_i\mathrm{Var}(Z_i)$. Also $\mathrm{Var}(Z)=E[Z^2]-(E[Z])^2$.
The variances of an average, a shrunken average and a fitted line all come from these lines.
Conditional expectation
$E[Y\mid X=x]$ is the mean of $Y$ among pairs with input $x$, $\mathrm{Var}(Y\mid X=x)$ is the spread around it, and $E[Y]=E_X\big[E[Y\mid X]\big]$.
The expected label $\bar y(x)$ and the noise term are exactly these objects.
Independence
If $D$ and $(X,Y)$ are independent, then $E\big[g(D)\,h(X,Y)\big]=E[g(D)]\,E[h(X,Y)]$, and conditioning on $X=x$ leaves the distribution of $D$ unchanged.
It is what makes the cross terms of the decomposition vanish.
Try it yourself first (2 questions)
1§04.3 — the expected square of a shifted variable
A random variable $Z$ has mean $3$ and variance $4$. Before reading on, compute one expected square.
Find(a) What is $E\big[(Z-5)^2\big]$?
Given
$E[Z]=3$
$\mathrm{Var}(Z)=4$
Hint 1/4
Split $Z-5$ into the part that moves around the mean and the fixed distance from the mean to $5$.
Hint 2/4
For any constant $c$: $E\big[(Z-c)^2\big]=\mathrm{Var}(Z)+\big(E[Z]-c\big)^2$.
Hint 3/4
Here $\mathrm{Var}(Z)=4$, $E[Z]=3$ and $c=5$.
Hint 4/4
$E\big[(Z-5)^2\big]=4+(3-5)^2=8$.
Show solution
Centring at the mean makes the cross term vanish, which is quicker than going through $E[Z^2]$.
Centre at the mean
$$Z-5=(Z-3)+(3-5)$$
The first piece has mean $0$, the second is a constant.
Second route: $E[Z^2]=\mathrm{Var}(Z)+E[Z]^2=13$, so $E[(Z-5)^2]=E[Z^2]-10E[Z]+25=13-30+25=8$.
This identity, used twice, is the whole proof of the bias-variance decomposition later in this section.
2§04.1 — adding a term to a least squares fit
A least squares quadratic $\beta_0+\beta_1x+\beta_2x^2$ is fitted to $30$ points. A classmate refits with an extra $x^3$ term and warns that the training RSS might go up.
Find(a) True or false: adding the $x^3$ term can make the training RSS larger.
Given
the same $30$ points both times
second model: $\beta_0+\beta_1x+\beta_2x^2+\beta_3x^3$, fitted by least squares
Hint 1/4
Compare the sets of curves the two models are allowed to choose from.
Hint 2/4
Least squares picks the curve with the smallest RSS in its model, and a minimum over a larger set is never larger.
Hint 3/4
Every quadratic $\beta_0+\beta_1x+\beta_2x^2$ is the cubic with $\beta_3=0$, fitted to the same $30$ points.
Hint 4/4
The cubic's training RSS is at most the quadratic's, so the statement is false.
Show solution
Nesting answers the question for every data set at once, so there is nothing to compute.
Nesting
$$\{\text{quadratics}\}\subset\{\text{cubics}\}$$
Setting $\beta_3=0$ turns a cubic into any quadratic we like.
the two parts of a random split, and the size of the validation part
No point may sit in both parts.
$D_i,\ \hat f_{D_i}$
D i, f hat sub D i
the data without point $i$ (leave-one-out) or without fold $i$ ($k$-fold), and the model fitted on it
The index says what was left out.
$F_1,\dots,F_k,\ \lvert F_i\rvert$
folds F one to F k, size of F i
the $k$ random parts of $D$ and their sizes
Sizes may differ by one when k does not divide n.
$\mathrm{CV}(n),\ \mathrm{CV}(k)$
CV of n, CV of k
the leave-one-out and the k-fold estimates of test error
$\mathrm{CV}(n)$ is $\mathrm{CV}(k)$ with $k=n$.
$m,\ m_{-i}$
m, m minus i
the mean of the training labels, and the same mean with label $i$ left out
Used for the mean predictor; it is a random number, unlike $\bar y(x)$.
$h_{ii}$
h i i, the of point i
$\frac1n+\frac{(x_i-\bar x)^2}{\sum_j(x_j-\bar x)^2}$ for a least squares line
Further reading; used only in the leave-one-out shortcut.
Conventions used here
Fixed or random inputs.
The lecture draws every pair $(x_i,y_i)$ at random. Many examples here fix the training inputs, as in a sweep, so only the labels are random and $J$ is their distribution. The decomposition holds either way, because it needs only $D$ to be independent of the test pair.
Fixed inputs keep the arithmetic short, and the results carry over.
Which average.
Subscripts name what is random: $E_D$ averages over training sets, $E_X$ over test inputs, $E_{X,Y}$ over test pairs. When the test input takes a few equally likely values, $E_X$ is a plain average over them.
Most wrong answers average over the wrong thing, or over nothing.
The noise symbol.
The noise is written $\varepsilon$, as in the regression chapters; the probability review wrote the same zero-mean noise as $\omega$. When its variance does not depend on $x$ it is $\sigma^2$, and then the noise term equals $\sigma^2$.
Two letters for one object is a notation clash, not two ideas.
Sums and averages.
An RSS is a sum of squared misses and an MSE is that sum divided by the number of points. $\mathrm{CV}(k)$ averages the $k$ fold MSEs, each already divided by its fold size.
Mixing sums and averages is the most common arithmetic slip in this chapter.
Degree and coefficients.
A polynomial of degree $d$ has $d+1$ coefficients, so $n$ points with distinct inputs allow an exact at degree $n-1$.
Counting coefficients tells you when a training error of $0$ is guaranteed.
Rounding.
Intermediate steps keep at least four significant figures; final answers are rounded to three decimals unless an exact fraction is asked for.
Rounding a variance early can move a total in the second decimal.
4.1Training MSE and test MSE: why a perfect fit proves nothing
Separates how well a model fits its own training points from how well it predicts new ones; only the second counts.
Least squares gave us the fit with the smallest RSS on the data; now we ask what that number says about data the fit has never seen.
Solvable with what we have
Fit a least squares line or polynomial to $n$ points and compute its RSS.
Rank two fits of the same data by their RSS.
Hit $n$ points with distinct inputs exactly, using a polynomial of degree $n-1$.
Not solvable yet
Say which of two fits will predict the next reading better.
Choose a polynomial degree without always landing on the largest one.
Attach a number to a model that describes its error on data it has not seen.
Rank the models by their error on the data they were fitted to. For the three sensor readings the parabola scores $0$ and the line scores $0.5$, so we keep the parabola.
Why it fails
On three new readings the parabola's average squared miss is $0.889$ and the line's is $0.228$. A score that an interpolating polynomial can always drive to $0$ cannot rank models; it rewards copying the noise in the readings.
DefinitionTraining MSE and test MSE
Conditions
$\hat f$ is fitted on $D_{\mathrm{train}}$ and then held fixed
$D_{\mathrm{test}}$ comes from the same source as $D_{\mathrm{train}}$ and plays no part in the fitting
Both lines average the squared miss of the same fixed model. The first averages over the points the model was fitted to, the second over points it never saw; only the second measures , how the model does on new data.
One simulated training set: $12$ inputs evenly spaced on $[0,2]$, labels $\sin 3x$ plus noise with standard deviation $0.4$, and $5000$ new pairs for the test MSE. The $\textcolor{#1f6feb}{\text{training MSE}}$ falls with every extra degree; the $\textcolor{#d1690a}{\text{test MSE}}$ is lowest at degree $3$ and passes $2$ at degree $11$, where the curve goes through all $12$ points.
Looks like this, but is not
A model whose training MSE is $0.05$ against a rival's $0.40$ looks like the better predictor.
Training MSE falls every time we add flexibility, whether the extra flexibility follows the signal or the noise. A memorizing model and a good model both post small training errors; only points held out from the fit tell them apart.
degree
training MSE
test MSE
0
0.526
0.688
1
0.341
0.374
2
0.315
0.371
3
0.181
0.190
4
0.157
0.208
5
0.134
0.209
6
0.111
0.236
7
0.109
0.239
8
0.105
0.254
9
0.041
0.611
10
0.0003
1.544
11
0
2.058
The training column only goes down and is exactly $0$ at degree $11$. The test column bottoms out at $0.190$ at degree $3$ and ends about $11$ times higher.
Three sensor readings: a parabola through all of them against the least squares line
A light sensor reads $1$, $3$ and $2$ volts at light levels $0$, $1$ and $2$. Fit the parabola through the three points and the least squares line, and score both on those readings. Then score both on three new readings: $2.2$ V at level $0.5$, $1.4$ V at level $1.0$ and $2.6$ V at level $1.5$.
Find$\mathrm{MSE}_{\mathrm{train}}$ and $\mathrm{MSE}_{\mathrm{test}}$ for both fits.
Given
training readings: $(0,1),\ (1,3),\ (2,2)$
new readings: $(0.5,\,2.2),\ (1.0,\,1.4),\ (1.5,\,2.6)$
Solution
We fit on the three old readings only and keep the new ones sealed until both models are fixed, because a reading used for fitting cannot also judge the fit.
Two checks by other routes: $q(1)=1+3.5-1.5=3$ and $q(2)=1+7-6=2$ reproduce the readings, and the line's training residuals add up to $-0.5+1-0.5=0$, as least squares with an intercept requires.
This is the opening puzzle: the parabola earned its $0$ on the readings it was built from, including a reading of $3$ at level $1$ that the new $1.4$ shows was mostly noise.
Degrees 0, 1 and 2 on the same readings: why the training column can only fall
Add a third candidate to the sensor example: the constant model, which predicts the mean of the three training labels. Compute its training and test MSE on the same readings, set it next to the line and the parabola, and explain why the training MSE cannot rise with the degree.
FindThe two MSEs of the constant model and the reason behind the training trend.
Given
training readings: $(0,1),\ (1,3),\ (2,2)$
new readings: $(0.5,\,2.2),\ (1.0,\,1.4),\ (1.5,\,2.6)$
line: $0.5$ and $0.228$; parabola: $0$ and $0.889$ (training, test)
Solution
Nesting settles the training trend in one line, so we compute only the new model and then argue, instead of refitting a ladder of degrees.
Fit and score the constant model
$$\hat f(x)=\tfrac13(1+3+2)=2$$
Degree $0$ least squares is the mean of the training labels.
Edge case: with $11$ points a degree-$9$ fit could not, in general, hit every label, and the training MSE would be positive. The zero here comes from counting coefficients, not from a good model.
A training MSE of $0$ describes the fitted points only; to learn anything about new points, score the model on points it did not see.
⚠ Choosing the model with the smallest training MSE
it is the one error we can compute without extra data, and it looks like a quality score
wrong$$\hat d=\arg\min_d\,\mathrm{MSE}_{\mathrm{train}}(d)=11\ \ \text{in the figure}$$
right$$\hat d=\arg\min_d\,\mathrm{MSE}_{\mathrm{test}}(d)=3\ \ \text{in the figure}$$
⚠ Computing the test MSE on the training points
both errors use the same formula, so the data set behind the sum is easy to swap
4.2The training set is random: the expected label and the average model
Treats the fitted model as random, because the training set is, and defines the best possible prediction and the average fit.
In the sensor example one noisy reading dragged the parabola far away; to judge an algorithm rather than one lucky or unlucky fit, we average over the training sets it could have received.
DefinitionExpected label, average model, expected test error
Conditions
$(x_i,y_i)\sim p(X,Y)$ i.i.d. for $i=1,\dots,n$, so the data set is random: $D\sim J$ with $J=\prod_{i=1}^n p(X_i,Y_i)$
an algorithm $A$ turns a data set into a function, $\hat f_D=A(D)$, and $\hat y=\hat f_D(x)$ is its prediction at $x$
the test pair $(X,Y)\sim p$ is drawn independently of $D$
The expected label $\bar y(x)$ is the mean of the labels that input $x$ produces, the best single prediction at $x$ under squared error. The average model $\bar f(x)$ is what the algorithm predicts at $x$, averaged over every training set it might get. The expected test error scores the algorithm, not one fit.
The $12$ fixed inputs of the first figure, each thin line fitted to a fresh draw of the noisy labels. The thick line is the exact average model $\textcolor{#1f6feb}{\bar f}$ of this algorithm; it is itself a straight line, and no averaging bends it onto $\textcolor{#8250df}{\sin 3x}$.
Looks like this, but is not
The mean of the training labels, $\bar y=\frac1n\sum_i y_i$ in the least squares formulas, looks like the expected label $\bar y(x)$.
The first is one random number computed from $D$, the same at every input. The second is a fixed function of $x$ set by $p(X,Y)$: for the sensor it changes with the light level, and no data set changes it.
Two ways to predict a packet count from two past minutes: average model and spread
A network link loses either $0$ or $2$ packets in a minute, each with probability $\tfrac12$, independently from minute to minute and of anything we can measure. From two past minutes, algorithm $A_1$ predicts their average and $A_2$ predicts the larger of the two. Find $\bar f$ and the spread $E_D[(\hat f_D-\bar f)^2]$ for each, and compare $\bar f$ with $\bar y$.
Find$\bar f$ and $E_D[(\hat f_D-\bar f)^2]$ for $A_1$ and for $A_2$.
Given
$Y\in\{0,2\}$, each with probability $\tfrac12$, so $\bar y=1$
training set $D=(y_1,y_2)$: two independent minutes
$A_1(D)=\tfrac12(y_1+y_2)$ and $A_2(D)=\max(y_1,y_2)$
Solution
Only four training sets are possible, so listing them is exact and shorter than any formula. It also handles the maximum, where the rules for sums do not apply.
For $A_1$ the spread must be $\mathrm{Var}(Y)/2$, the variance of an average of two. Since $\mathrm{Var}(Y)=E[Y^2]-1=2-1=1$, that is $0.5$, found without the list.
The maximum is off by $0.5$ on average and also wobbles more, so it loses on both counts. The next block shows that these two numbers are exactly the pieces of its test error.
A least squares line through five fixed inputs: right on average, less sure at the ends
The inputs are fixed at $x=-2,-1,0,1,2$, one label each, with $Y=4+0.5x+\varepsilon$ and independent noise of variance $\sigma^2=1$. For the least squares line, find $\bar f(x)$ and the variance of the prediction at $x=0$, $x=2$ and $x=4$.
Find$\bar f(x)$, and $\mathrm{Var}_D\big(\hat f_D(x)\big)$ at $x=0,2,4$.
Given
$x_i=-2,-1,0,1,2$, so $\bar x=0$ and $\sum_i x_i^2=10$
At $x=0$ the prediction is the plain average of five independent labels of variance $1$, so its variance must be $1/5=0.2$, as found.
The fit is unbiased everywhere, but its variance grows with the squared distance from the centre of the inputs: at $x=4$, outside the data, it is nine times the variance at the centre.
Checkpoint
§04.2 — an algorithm that ignores its data
A lazy algorithm ignores its training set and always outputs the prediction $5$, whatever the input.
Find(a) What are its average model $\bar f(x)$ and its spread $E_D\big[(\hat f_D(x)-\bar f(x))^2\big]$?
Given
$\hat f_D(x)=5$ for every data set $D$ and every input $x$
the labels have expected value $\bar y(x)$ and $\mathrm{Var}(Y\mid X=x)>0$
Hint 1/4
Ask what changes when the training set changes, and what the average of something that never changes is.
Hint 2/4
$\bar f(x)=E_D[\hat f_D(x)]$, and the spread is $E_D\big[(\hat f_D(x)-\bar f(x))^2\big]$.
Hint 3/4
Here $\hat f_D(x)=5$ for every $D$, so both expectations are over a quantity that is always $5$.
Hint 4/4
$\bar f(x)=5$ and the spread is $0$, so all of this algorithm's error will be bias and noise.
Show solution
Both definitions are expectations over $D$ of something that does not depend on $D$, so we can evaluate them on sight.
Average model
$$\bar f(x)=E_D[5]=5$$
The expectation of a constant is the constant.
Spread
$$E_D\big[(5-5)^2\big]=0$$
Every training set gives the same prediction, so nothing varies.
Direct check at one input: $E\big[(5-Y)^2\mid X=x\big]=\mathrm{Var}(Y\mid X=x)+(\bar y(x)-5)^2$, which is noise plus bias² with nothing left over for variance.
Ignoring the data removes all variance and leaves all the error to bias: one extreme of the tradeoff met later in this section.
⚠ Feeding the averaged data to the algorithm
for a mean or a least squares fit the two orders agree, so the shortcut looks safe
the least squares formulas use the same letter for the average of the training labels
wrong$$\bar y(x)=\frac1n\sum_{i=1}^n y_i$$
right$$\bar y(x)=E[Y\mid X=x],\ \ \text{a fixed function of }x$$
4.3The bias-variance decomposition: three sources of test error
Splits the expected test error exactly into bias squared, variance and noise, three numbers with three different causes.
With $\bar y$ and $\bar f$ in hand, the miss from a prediction to a new label breaks into three gaps: prediction to average model, average model to expected label, expected label to the label itself.
TheoremThe bias-variance decomposition
Conditions
$D\sim J$, $\hat f_D=A(D)$, and the test pair $(X,Y)\sim p$ is independent of $D$
$\bar y(x)=E[Y\mid X=x]$ and $\bar f(x)=E_D[\hat f_D(x)]$
Averaged over training sets and new pairs, the squared miss equals the squared gap between the average model and the expected label (bias squared), plus how far one fit strays from the average model (variance), plus how far a real label strays from its expected value (noise). No cross terms survive.
Proof: one identity, used twice
The subscripts make this look harder than it is: one identity does all the work. For any random $Z$ and constant $c$, $E[(Z-c)^2]=\mathrm{Var}(Z)+(E[Z]-c)^2$; write $Z-c=(Z-E[Z])+(E[Z]-c)$ and expand, and the cross term carries the factor $E[Z-E[Z]]=0$.
Fix the input $X=x$ and the training set $D$, so $a=\hat f_D(x)$ is a number. Because $D$ is independent of the test pair, $Y$ given $X=x$ still has mean $\bar y(x)$, and the identity with $Z=Y$ gives $$E\big[(a-Y)^2\mid X=x\big]=\mathrm{Var}(Y\mid X=x)+\big(\bar y(x)-a\big)^2.$$
Now let $D$ vary with $x$ fixed. The identity with $Z=\hat f_D(x)$ and $c=\bar y(x)$ gives $$E_D\big[(\hat f_D(x)-\bar y(x))^2\big]=E_D\big[(\hat f_D(x)-\bar f(x))^2\big]+\big(\bar f(x)-\bar y(x)\big)^2.$$
Put the two lines together and average over $X$. The three pieces become variance, bias squared and noise, since $E_X[\mathrm{Var}(Y\mid X)]=E_{X,Y}[(\bar y(X)-Y)^2]$.
The two algorithms of the first worked example below: inputs $0,1,2$, noise variance $1$. Each bar is the expected test error, stacked as $\textcolor{#8250df}{\text{bias}^2}$, $\textcolor{#1f6feb}{\text{variance}}$ and noise; the $\textcolor{#d1690a}{\text{totals}}$ are $4$ and $1.67$.
Looks like this, but is not
Bias sounds like a property of the data set, something a larger training set should cure.
Bias compares the average model with the expected label, so it belongs to the algorithm and its model class. The constant predictor below keeps a bias squared of $8/3$ however many labels it averages at those three inputs; more data shrinks its variance, not that gap.
Mean of the labels against the least squares line, split into bias², variance and noise
Training inputs are fixed at $0$, $1$ and $2$, one label each, with $\bar y(x)=2x$ and independent noise of variance $1$. The test input is equally likely to be $0$, $1$ or $2$. Compute the three terms and the expected test error for the constant predictor (the mean of the labels) and for the least squares line.
FindBias², variance, noise and their sum for both algorithms.
Given
$\bar y(x)=2x$ and $\mathrm{Var}(Y\mid X=x)=1$
training inputs $0,1,2$; test input uniform on $\{0,1,2\}$
Solution
Both predictors are weighted sums of independent labels, so each term follows from means and variances of sums; the constant predictor's total then gets a second, independent route.
Second route for the constant: $\hat f_D-Y=(2-2X)+(\bar\varepsilon-\varepsilon)$ is a sum of independent zero-mean pieces, so $E[(\hat f_D-Y)^2]=\tfrac83+\tfrac13+1=4$ without naming bias or variance.
The line pays twice the constant's variance and buys back all of its bias. When $\bar y$ really is a line, that trade wins by a wide margin.
The two packet-count predictors, split into three parts and checked by listing every case
Continue the packet example: $Y\in\{0,2\}$ with equal probability, a training set of two independent minutes, $A_1$ the average and $A_2$ the larger value. Split each expected test error into bias², variance and noise, then check the totals by averaging $(\hat f_D-Y)^2$ over every case.
FindThe three terms and the total for each algorithm.
The pieces are already known from the listing, so the decomposition is one line per algorithm; listing the cases a second time gives a check that does not use the theorem.
Decompose
$$A_1:\ (1-1)^2+0.5+1=1.5$$
Bias² is $0$ because the average model sits on $\bar y$.
No algorithm beats the noise: it is the error of the best possible predictor $\bar y(x)$, and equality needs zero bias and zero variance at once. What we choose, the model class, its degree, the amount of data, acts on bias² and variance, and more flexibility usually lowers the first while raising the second.
Why the floor holds
Bias² and variance are averages of squares, so neither is negative. Dropping them from the decomposition can only make the right side smaller, which is the inequality; equality needs both to vanish.
Exact $\textcolor{#8250df}{\text{bias}^2}$, $\textcolor{#1f6feb}{\text{variance}}$ and $\textcolor{#d1690a}{\text{expected test error}}$ of least squares polynomials of degree $0$ to $10$ on the $12$ evenly spaced inputs of the first figure, noise variance $0.16$. The orange curve is the sum of the other two plus the dashed noise floor.
Looks like this, but is not
An unbiased estimator looks like the safest choice: on average it is exactly right.
Squared error also charges for spread. In the first example below, multiplying the average of four labels by $0.8$ adds $0.16$ of bias² but removes $0.36$ of variance, so the expected error drops from $5$ to $4.8$.
degree
bias²
variance
expected test error
0
0.5225
0.0133
0.6958
1
0.1871
0.0246
0.3717
2
0.1782
0.0348
0.3730
3
0.0048
0.0448
0.2096
4
0.0041
0.0557
0.2198
5
below 0.0001
0.0681
0.2281
6
below 0.0001
0.0829
0.2429
7
below 0.0001
0.1023
0.2623
8
below 0.0001
0.1336
0.2936
9
below 0.0001
0.2106
0.3706
10
below 0.0001
0.5891
0.7491
Bias² collapses between degrees $2$ and $3$, when the polynomial can finally bend like $\sin 3x$. Variance grows at every step, slowly at first and fast after degree $8$.
Shrinking an average: buying bias to sell variance
A label $Y$ does not depend on the input; it has mean $\mu=2$ and variance $\sigma^2=4$. We predict a new label by $\alpha m$, where $m$ is the average of $n=4$ independent training labels and $\alpha$ is a number we pick. Find the expected test error as a function of $\alpha$, the best $\alpha$, and the error there.
Find$E\big[(\alpha m-Y)^2\big]$, the minimizing $\alpha$, and the error at $\alpha=1$ and at the best $\alpha$.
Given
$\mu=2$, $\sigma^2=4$, $n=4$
$\hat f_D=\alpha m$ with $m=\tfrac14\sum_{i=1}^4 y_i$
Solution
The decomposition turns the error into a quadratic in $\alpha$ that one derivative minimizes; expanding $(\alpha m-Y)^2$ directly reaches the same quadratic with more algebra.
General form: $\alpha^\ast=\mu^2/(\mu^2+\sigma^2/n)=4/(4+1)=0.8$, the same value. At the other extreme $\alpha=0$ the error is $4+0+4=8$, pure bias.
The best $\alpha$ needs $\mu$ and $\sigma^2$, which we never know. Choosing a knob like this from the data is exactly the job of validation.
Degree 1 and degree 9: the same test error for opposite reasons
For least squares polynomials on $12$ inputs evenly spaced on $[0,2]$, with $\bar y(x)=\sin 3x$ and noise variance $0.16$, the exact bias² and variance are: degree $1$, $0.187$ and $0.025$; degree $3$, $0.005$ and $0.045$; degree $9$, below $0.0001$ and $0.211$. Compute the three expected test errors, diagnose degrees $1$ and $9$, and say what would help each.
FindThe three totals and a diagnosis of degrees $1$ and $9$.
Scale check on the source table: at degree $0$ the fit is the mean of $12$ labels, whose variance must be $0.16/12\approx 0.0133$, and that is the table's first variance entry.
Two models with equal test error can need opposite repairs, so read which term dominates before adding or removing flexibility.
Checkpoint
§04.4 — what can lower the noise term
A team predicts a house's yearly energy use from its floor area alone. Their expected test error is well above what they hoped, and they list four possible changes.
Find(a) Which change can lower the noise term itself?
Given
noise term $E_{X,Y}\big[(\bar y(X)-Y)^2\big]$, with $X$ the floor area
the four candidate changes are the choices below
Hint 1/4
The noise term is built from the joint distribution of $X$ and $Y$ only, so look for the change that alters that distribution.
Hint 2/4
$\text{noise}=E_{X,Y}\big[(\bar y(X)-Y)^2\big]=E_X\big[\mathrm{Var}(Y\mid X)\big]$, with no $\hat f$ inside.
Hint 3/4
The changes are: a more flexible model, twice as many houses, an extra recorded input (the insulation class), and averaging many fits. Only one of them changes what $X$ is.
Hint 4/4
Recording the insulation class changes $X$ itself, and only that can lower the noise term.
Show solution
Instead of estimating each change's effect, we check which quantities each change can touch; a term without $\hat f$ is out of reach of anything that only changes $\hat f$.
Houses of equal area but different insulation no longer share one $\bar y(x)$, so the spread left around $\bar y$ can shrink.
Answer $$\boxed{\text{record the insulation class}}$$
Check
Law of total variance: $E[\mathrm{Var}(Y\mid X_1,X_2)]\le E[\mathrm{Var}(Y\mid X_1)]$, so an extra input can lower the noise term or leave it unchanged, never raise it.
To get below a noise floor, measure something new; modelling cannot squeeze more out of the same inputs than $\bar y(x)$ already does.
⚠ Calling a high training error overfitting
both words describe a bad model, and it is easy to attach the wrong one
right$$\begin{aligned}&n\to\infty\ \Rightarrow\ \text{variance shrinks}\\ &\text{bias}^2\ \text{stays if the model class cannot express }\bar y\end{aligned}$$
4.5The validation set approach: hold data out, fit on the rest
Estimates test error without a test set by fitting on one random part of the data and scoring on the held-out part.
The degree and the shrinkage factor are , set before the fit, and their best values depend on $\bar y$ and the noise, which we never see; what we can always compute is the error on points a model did not train on.
MethodThe validation set approach
Conditions
$D$ is split at random into $D_{\mathrm{train}}$ and $D_{\mathrm{validation}}$, with no point in both
every candidate model is fitted on $D_{\mathrm{train}}$ only
$D_{\mathrm{validation}}$ is used only for scoring
Score each candidate by its average squared miss on the held-out points and keep the one with the smallest score. Two weaknesses come with it: the score depends on which points landed where, and each candidate trains on fewer points than we have, so it looks worse than the model we finally use.
One data set of $40$ points (inputs evenly spaced on $[0,2]$, $\sin 3x$ plus noise with standard deviation $0.4$) halved at random eight times. Each orange curve is one split's validation MSE; the dots mark the degree each split would choose.
Looks like this, but is not
After picking the degree with the smallest validation MSE, that smallest score looks like an honest estimate of the chosen model's test error, since no validation point was used for fitting.
The validation points were used for choosing. The smallest of several noisy scores is pulled down by luck, so it is optimistic; an honest number needs points that took no part in fitting or choosing, such as a separate test set.
split
degree chosen
validation MSE there
validation MSE at degree 3
1
3
0.173
0.173
2
8
0.191
0.201
3
6
0.209
0.219
4
3
0.191
0.191
5
3
0.148
0.148
6
3
0.183
0.183
7
3
0.175
0.175
8
5
0.169
0.171
Five splits choose degree $3$ and three choose $5$, $6$ or $8$. Even at the same degree the score moves from $0.148$ to $0.219$ with nothing changed but the split.
Line or constant? Scoring both on three held-out readings out of seven
Seven readings at inputs $-3,\dots,3$ are split at random. Training part: inputs $-3,-1,1,3$ with labels $2.5,\ \allowbreak 4.5,\ \allowbreak 5.5,\ \allowbreak 7.5$. Validation part: inputs $-2,0,2$ with labels $3.0,\ 5.5,\ 6.5$. Choose between the constant model and the least squares line, then refit the winner on all seven readings.
Find$\mathrm{MSE}_{\mathrm{val}}$ of both candidates, the choice, and the refitted model.
The training inputs are symmetric about $0$, so each fit needs only a mean and one weighted sum; the validation readings are touched only after both fits are fixed.
The line's training MSE on its own four readings is $\tfrac14(0.01+0.09+0.09+0.01)=0.05$, below its validation MSE of $0.14$, as a score on unseen points usually is.
Fit on the training part, score on the held-out part, and only then refit the winner on everything: the held-out score chose the model, the refit uses all the data.
What half the data costs: how much a validation estimate overstates
Labels ignore the input and have variance $\sigma^2=1$; the model predicts the mean of its training labels. With $n=10$ points in all, compare the expected test error of the model trained on all $10$ labels with the models trained on $5$ (a half split) and on $8$ (an 80/20 split).
FindThe expected test error for each $m$, and how much each split overstates the full model's error.
Given
$\mathrm{Var}(Y)=\sigma^2=1$, labels independent
training sizes $m=10$, $5$ and $8$
Solution
The decomposition gives the error of a mean of $m$ labels in one line, so we can read off exactly what training on fewer points costs.
Edge check: as $m\to\infty$ the error tends to $\sigma^2=1$, the noise floor, and at $m=1$ it is $2$; all three values sit between these ends in the right order.
Giving the training part more points makes the estimate less pessimistic but leaves fewer points to score on, which is why the lecture's 80/20 rule of thumb is a compromise rather than a law.
Checkpoint
§04.5 — scoring a fitted line on held-out points
A line fitted on the training part of a data set is $\hat f(x)=1+2x$. Four validation points were held out from that fit.
⚠ Reporting the winning validation score as the test error
the winner's score was computed on held-out points, which sounds like a test
wrong$$\text{test error of the winner}\approx\min_d\,\mathrm{MSE}_{\mathrm{val}}(d)$$
right$$\begin{aligned}&\min_d\,\mathrm{MSE}_{\mathrm{val}}(d)\ \text{is optimistic}\\ &\text{score the winner on untouched data}\end{aligned}$$
4.6Leave-one-out cross-validation: n fits, each point held out once
Fits n models, each on all points but one, and averages the n squared misses on the left-out points; no random split.
The validation set wastes training data and depends on the split; leave-one-out uses every point for training in all but one fit and for validation exactly once.
MethodLeave-one-out cross-validation (LOOCV)
Conditions
$D_i=D\setminus\{(x_i,y_i)\}$ has $n-1$ points
$\hat f_{D_i}$ is fitted on $D_i$ with the same algorithm for every $i$
Leave point $i$ out, fit on the other $n-1$, predict the point you left out and square the miss; do this for every point and average. Each term is an honest test error of a model trained on $n-1$ points, and nothing is random: the same data always give the same $\mathrm{CV}(n)$.
Leave-one-out with $n=5$: five fits, each trained on four points ($\textcolor{#1f6feb}{\text{blue}}$) and each predicting the one point it did not see ($\textcolor{#d1690a}{\text{orange}}$).
Looks like this, but is not
Fitting once on all of $D$, taking the $n$ residuals $y_i-\hat f_D(x_i)$ and averaging their squares also gives every point a squared error.
That is the training MSE: each point helped fit the model that predicts it. For the least squares line on five points in the second example below it is $0.54$, while leave-one-out gives $1.67$.
Leave-one-out for the mean predictor: each held-out miss is the residual times n/(n − 1)
The model predicts the mean of its training labels. For the labels $4,\ 7,\ 5,\ 8$, compute $\mathrm{CV}(4)$ through a shortcut, then check the shortcut with one refit.
Find$\mathrm{CV}(4)$, and the training MSE for comparison.
Given
labels $4,7,5,8$, so $n=4$ and the mean is $m=6$
$\hat f_{D_i}=m_{-i}$, the mean of the other three labels
Solution
Removing one label changes the mean in a predictable way, so one line of algebra replaces four refits; a single refit then checks the algebra.
All four held-out squares by direct refits: $\tfrac{64}{9},\ \tfrac{16}{9},\ \tfrac{16}{9},\ \tfrac{64}{9}$, whose average is $\tfrac{160}{36}=\tfrac{40}{9}\approx 4.44$.
The factor $(n/(n-1))^2$ is the price of predicting a point the mean did not include; it fades as $n$ grows but never reaches $1$.
Leave-one-out for a least squares line from a single fit (further reading)
A shortcut that is not on the lecture slides: for simple least squares the held-out miss equals the ordinary residual divided by $1-h_{ii}$, where $h_{ii}=\frac1n+\frac{(x_i-\bar x)^2}{\sum_j(x_j-\bar x)^2}$. Use it for the points $(-2,2),\ \allowbreak (-1,2),\ \allowbreak (0,5),\ \allowbreak (1,5),\ \allowbreak (2,8)$, and check one term by refitting.
Find$\mathrm{CV}(5)$ for the line, and its training MSE.
A second refit, without $(-2,2)$: the line through the other four points is $4.1+1.8x$, which predicts $0.5$ at $x=-2$, a miss of $1.5=0.6/0.4$, as the shortcut says.
The two end points, with leverage $0.6$, have their misses multiplied by $2.5$: leave-one-out punishes a fit that leans on a few influential points.
Checkpoint
§04.6 — one held-out miss for the mean predictor
The model predicts the mean of its training labels. The data are five labels, and we compute one term of leave-one-out cross-validation.
Find(a) What is $\mathrm{MSE}_i$ for the point with label $10$?
Given
labels $3,\ 5,\ 10,\ 6,\ 6$
the term for the point whose label is $10$
Hint 1/4
Leave the label $10$ out, predict it from the rest, and square the miss.
Hint 2/4
$\mathrm{MSE}_i=(y_i-m_{-i})^2$, where $m_{-i}$ is the mean of the other $n-1$ labels.
Hint 3/4
The other labels are $3,\ 5,\ 6,\ 6$, with sum $20$; the left-out label is $10$.
Hint 4/4
$m_{-i}=5$, so $\mathrm{MSE}_i=(10-5)^2=25$.
Show solution
The mean predictor refits in one addition, so we refit directly rather than use the shortcut, and keep the shortcut as the check.
Leave out and refit
$$m_{-i}=\tfrac14(3+5+6+6)=5$$
The model is refitted on the four remaining labels.
Square the miss
$$(10-5)^2=25$$
The refitted model never saw the label it now predicts.
Answer $$\boxed{\mathrm{MSE}_i=25}$$
Check
Shortcut check: the full mean is $6$, the ordinary residual is $4$, and $\tfrac54\times 4=5$, the same held-out miss.
A point far from the others is predicted badly once it is left out, and that is exactly the kind of point leave-one-out is designed to expose.
⚠ Scoring each point with the full-data fit
the full fit is already computed, and refitting $n$ times feels wasteful
4.7k-fold cross-validation: k fits, each fold held out once
Splits the data into $k$ folds, fits $k$ models with one fold held out each, and averages their fold MSEs.
Leave-one-out needs $n$ fits, which hurts when one fit takes minutes; $k$-fold keeps its core idea, every point held out exactly once, with only $k$ fits.
Methodk-fold cross-validation
Conditions
$D$ is split at random into $k$ folds $F_1,\dots,F_k$ of equal size, or sizes differing by one when $k$ does not divide $n$
$D_i=D\setminus F_i$, and $\hat f_{D_i}$ is fitted on $D_i$
Each fold takes one turn as the validation set while the other $k-1$ folds train the model. Every point is predicted once by a model that did not see it, and $\mathrm{CV}(k)$ averages the $k$ fold scores; with $k=n$ each fold is one point and $\mathrm{CV}(k)$ is $\mathrm{CV}(n)$.
The same $40$ points as the validation figure. Thick: leave-one-out, $40$ fits per degree. Thin: eight different random 5-fold splits, $5$ fits per degree each. All nine curves choose degree $3$.
Looks like this, but is not
Two-fold cross-validation looks like the validation set approach with a 50/50 split.
The validation approach fits once and scores one half. Two-fold CV fits twice with the roles swapped, so every point is scored once and the two scores are averaged; the answer no longer hangs on which half did the training.
method
fits per degree
fits in total
training points per fit
validation set, 80/20
1
6
400
5-fold CV
5
30
400
10-fold CV
10
60
450
leave-one-out
500
3000
499
Five-fold CV gives every fit the same $400$ points as an 80/20 split and still scores all $500$; leave-one-out needs $100$ times as many fits as 5-fold.
Three-fold cross-validation by hand: constant or line on six readings
Six readings $(x,y)$: $(0,1),\ \allowbreak (1,2),\ \allowbreak (2,3),\ \allowbreak (3,4),\ \allowbreak (4,4),\ \allowbreak (5,6)$. A random assignment puts inputs $\{0,3\}$ in $F_1$, $\{1,4\}$ in $F_2$ and $\{2,5\}$ in $F_3$. Compute $\mathrm{CV}(3)$ for the constant model and for the least squares line, choose one, and refit it on all six readings.
Find$\mathrm{CV}(3)$ for both candidates, the choice, and the final model.
candidates: the mean of the training labels, and the least squares line
Solution
The same three folds serve both candidates, so the comparison is not muddied by different splits; each fit uses four points, few enough for the formulas by hand.
The refitted line's residuals, $-0.048,\ \allowbreak 0.038,\ \allowbreak 0.124,\ \allowbreak 0.210,\ \allowbreak -0.705,\ \allowbreak 0.381$, add up to $0$, as least squares with an intercept requires.
Six fits in all, three folds for each of two candidates. By hand this is tedious, which is why $k$-fold CV is always run in code outside an exam.
Use one set of folds for every candidate, fit on the other folds, score on the held-out fold, and refit the winner on everything.
Checkpoint
§04.7 — counting fits and training points
A data set has $n=12$ points, and we run $4$-fold cross-validation for one candidate model.
Find(a) How many points does each fit use, and how many fits are there?
Given
$n=12$
$k=4$ folds of equal size
Hint 1/4
Picture one round: which points train the model, and which are scored?
Hint 2/4
Each fold holds $n/k$ points, each fit trains on the other $n-n/k$, and there is one fit per fold.
Hint 3/4
With $n=12$ and $k=4$, each fold holds $12/4=3$ points, and each fit trains on $12-3$ points.
Hint 4/4
Each fit uses $9$ points, and there are $4$ fits.
Show solution
Counting one round and multiplying by $k$ avoids mixing up the fold that is scored with the folds that train.
splitting a table sorted by $x$ into consecutive blocks is the easiest split to code, but then every fit must extrapolate to its fold
wrong$$F_1=\{\text{the }n/k\ \text{smallest inputs}\},\ F_2=\{\text{the next }n/k\},\ \dots$$
right$$\text{assign points to folds at random, then cut}$$
Bias², variance and noise for a given algorithm
A question gives the data model and an algorithm and asks for the expected test error or one of its parts.
Read off the target
Write $\bar y(x)$ and $\mathrm{Var}(Y\mid X=x)$ from the data model; the average of the variance over $X$ is the noise.
Write the fit in the labels
For example $\hat f_D=m$, or $\hat\beta_0+\hat\beta_1x$ with the least squares formulas.
Average model
$\bar f(x)=E_D[\hat f_D(x)]$; when the fit is linear in the labels, replace each label by its mean.
Bias²
Average $(\bar f(x)-\bar y(x))^2$ over the test inputs: square first, then average.
Variance
Average $\mathrm{Var}_D(\hat f_D(x))$ over the test inputs, with $\mathrm{Var}\big(\sum a_iY_i\big)=\sum a_i^2\mathrm{Var}(Y_i)$ for independent labels.
Add and check
Total = bias² + variance + noise, and the total must be at least the noise.
Where it goes wrong
Averaging signed gaps before squaring, so that a model too high at one input and too low at another looks unbiased.
Using $\mathrm{Var}(Y)$ as the variance of a fit that averages several labels.
Leaving out the noise, which every algorithm pays.
Choosing a model by k-fold cross-validation
Several candidate models or tuning values, no separate test set, and one of them must be picked.
Split once
Shuffle $D$ and cut it into $k$ folds of nearly equal size; use the same folds for every candidate.
Fit and score
For each candidate and each $i$, fit on $D\setminus F_i$ and compute $\mathrm{MSE}_i$ on $F_i$.
Average
$\mathrm{CV}(k)=\frac1k\sum_i\mathrm{MSE}_i$ for each candidate.
Choose
Keep the candidate with the smallest $\mathrm{CV}(k)$.
Refit
Fit the chosen candidate on all of $D$; that is the model you use.
Where it goes wrong
Fitting once on all of D and scoring that fit on each fold, which is the training error in disguise.
Drawing new folds for each candidate, which adds split noise to the comparison.
Quoting the winner's CV score as its test error after it has won a contest on the same folds.
Leave-one-out by hand
Small n and a model you can refit quickly, or the mean predictor, which has a shortcut.
$y_i-m_{-i}=\frac{n}{n-1}(y_i-m)$, so $\mathrm{CV}(n)=\big(\frac{n}{n-1}\big)^2\cdot\frac1n\sum_i(y_i-m)^2$.
Where it goes wrong
Predicting $y_i$ with the fit on all of $D$.
Dividing by $n-1$ in the final average.
Forgetting that the left-out mean $m_{-i}$ divides by $n-1$.
When the expected label is the line 2x: line against interpolating parabola
Inputs are fixed at $0,1,2$, one label each, with noise variance $1$ and the test input uniform on $\{0,1,2\}$. Here $\bar y(x)=2x$. Compare the expected test error of the least squares line with that of the parabola through the three points.
FindBoth expected test errors.
Given
$\bar y(x)=2x$, noise variance $1$
line: prediction variances $\tfrac56,\ \tfrac13,\ \tfrac56$ at $0,1,2$
parabola through the three points: its prediction at each input is that input's label
Solution
Both fits are unbiased here, so only their variances differ, and the parabola's variance at each input is the variance of one label.
The parabola copies one label at each input, so its variance there is exactly one label's variance, $1$; the line mixes three labels and at $x=1$ its variance is only $\tfrac13$.
When $\bar y$ is a line, extra flexibility buys no bias reduction and only adds variance.
When the expected label bends to 0, 3, 0: line against interpolating parabola
Inputs are fixed at $0,1,2$, one label each, with noise variance $1$ and the test input uniform on $\{0,1,2\}$, but now $\bar y(0)=0$, $\bar y(1)=3$ and $\bar y(2)=0$. Compare the least squares line with the parabola through the three points.
The variances did not change from the linear case; only the line's bias² did, from $0$ to $2$, and that alone flips the verdict.
Flexibility pays exactly when the simpler model's bias costs more than the extra variance it saves.
Same inputs, noise and algorithms; only $\bar y$ changes, and the winner flips because the line's bias² goes from $0$ to $2$ while every variance stays put.
How to tell them apart
Neither model is better in general: compare bias² plus variance, and since $\bar y$ is unknown in practice, compare cross-validation errors instead.
One 50/50 validation split of six labels
Six labels are split at random into halves $H_1=\{2,6,4\}$ and $H_2=\{3,7,8\}$. The model predicts the mean of its training labels. Estimate its test error with the validation set approach, training on $H_1$.
Find$\mathrm{MSE}_{\mathrm{val}}$.
Given$H_1=\{2,6,4\}$ for training, $H_2=\{3,7,8\}$ for validation
Solution
One fit on $H_1$ and one score on $H_2$ is the whole method.
Had the split made $H_2$ the training half, the same method would report $\tfrac13[(2-6)^2+0^2+(4-6)^2]=\tfrac{20}{3}\approx 6.67$; the answer depends on the draw.
One split gives one number, and a different split gives a different number.
Two-fold cross-validation on the same two halves
Same six labels, same halves and the same mean predictor. Estimate the test error with two-fold cross-validation, using $H_1$ and $H_2$ as the folds.
Find$\mathrm{CV}(2)$.
Given$F_1=\{2,6,4\}$, $F_2=\{3,7,8\}$
Solution
Two-fold CV runs the validation approach in both directions and averages, so every label is scored once.
Fold 2 held out
$$\text{train on }F_1:\ m=4,\ \ \mathrm{MSE}_2=\tfrac{26}{3}$$
This is the validation split of pair A.
Fold 1 held out
$$\text{train on }F_2:\ m=6,\ \ \mathrm{MSE}_1=\tfrac13\big[16+0+4\big]=\tfrac{20}{3}$$
The answer lies between the two single-split answers, $6.67$ and $8.67$, as an average must, and it no longer depends on which half was drawn first.
Swapping the roles and averaging is the whole difference between a split and a fold.
Both fit the mean on three labels and score it on the other three; the validation approach stops after one direction, while two-fold CV runs both and averages.
How to tell them apart
Count the fits: one fit and one scored half is the validation set approach; one fit per fold, with every fold scored once, is k-fold CV.
Scaffolding comes off
The common skeleton
Noise: read $\bar y(x)$ and $\mathrm{Var}(Y\mid X=x)$ off the data model.
Average model: write $\hat f_D(x)$ in terms of the labels and take $\bar f(x)=E_D[\hat f_D(x)]$.
Bias²: average $(\bar f(x)-\bar y(x))^2$ over the test inputs, squaring before averaging.
Variance: average $\mathrm{Var}_D(\hat f_D(x))$ over the test inputs.
Add the three terms and check that the total is at least the noise.
1 · fully worked
Mean of four labels on a two-level input: the three terms
The test input is $0$ or $2$ with equal probability, $\bar y(x)=1+x$ and the noise variance is $1$. The training inputs are fixed at $0,0,2,2$, one label each. The algorithm predicts the mean of the four labels at every input. Find bias², variance, noise and the expected test error.
Direct route: $\hat f_D-Y=(2-\bar y(X))+(\bar\varepsilon-\varepsilon)$, with $E[(2-\bar y(X))^2]=1$, $\mathrm{Var}(\bar\varepsilon)=0.25$ and $\mathrm{Var}(\varepsilon)=1$, so the total is $2.25$ again.
A constant predictor on a sloped $\bar y$ is dominated by bias; with four labels its variance is already small.
2 · you write the reasoning
An easier one, and this time you write the reasons. Same setting: the test input is $0$ or $2$ with equal probability, $\bar y(x)=1+x$, noise variance $1$. The algorithm ignores its data and always predicts $2$. For each line, write why it is allowed.
$E_X\big[\mathrm{Var}(Y\mid X)\big]=1$
reasoning
The noise comes from the data model alone: the variance of $Y$ at each input is $1$.
$\bar f(x)=E_D[2]=2$
reasoning
The prediction does not depend on $D$, so its average over training sets is the prediction itself.
Square the gap at each of the two equally likely test inputs, then average.
$\text{variance}=E_D\big[(2-2)^2\big]=0$
reasoning
Every training set gives the same prediction, so nothing varies.
$\text{total}=1+0+1=2$
reasoning
Bias² plus variance plus noise; the total is at least the noise, as it must be. It even beats the mean of four labels, $2.25$: same bias, no variance.
3 · find the buried error
Harder, with two errors buried in the worked solution. The test input is $0$ or $2$ with equal probability, $\bar y(x)=1+x$, noise variance $1$, training inputs $0,0,2,2$; $m_0$ and $m_2$ are the means of the two labels at $0$ and at $2$. At each input the rule predicts half the mean there plus half the mean of all four labels. Find the expected test error.
Step 1.$\bar y(0)=1,\ \bar y(2)=3$, noise $=1$. Read off the data model.
Step 2.$\hat f_D(0)=0.75\,m_0+0.25\,m_2$, so $\bar f(0)=1.5$; likewise $\bar f(2)=2.5$. Average model at each input.
Step 3.$\text{bias}^2=\Big(\tfrac12\big[(1.5-1)+(2.5-3)\big]\Big)^2=0$. The gaps at the two inputs cancel.
Step 4.$\mathrm{Var}\big(0.75\,m_0+0.25\,m_2\big)=0.75\cdot\tfrac12+0.25\cdot\tfrac12=0.5$. Variance at each input, since $m_0$ and $m_2$ each average two labels.
Step 5. Total $=0+0.5+1=1.5$, the same as the plain per-input mean, so the mixing costs nothing.
the two buried errors (2)
⚠ step 3
Bias² squares the gap at each input before averaging over $X$. The gaps $+0.5$ and $-0.5$ cancel only if the average is taken first.
The formula $E_X\big[(\bar f(X)-\bar y(X))^2\big]$ has the square inside the expectation, and habit moves it outside.
Weights enter a variance squared: $\mathrm{Var}(aU+bV)=a^2\mathrm{Var}(U)+b^2\mathrm{Var}(V)$ for independent $U$ and $V$.
Expectations use the weights as they are, and the habit carries over to variances.
right
$0.75^2\cdot\tfrac12+0.25^2\cdot\tfrac12=0.3125$, so the total is $0.25+0.3125+1=1.5625$.
4 · the bare problem
§04.3 — overall mean or per-input mean on a two-level input
The test input is $0$ or $2$ with equal probability, $\bar y(x)=1+x$ and the noise variance is $1$. The training inputs are fixed at $0,0,0,2,2,2$, one label each.
Find
(a) Find the expected test error of rule A.
(b) Find the expected test error of rule B, and say which rule wins.
rule A: predict the mean of all six labels; rule B: predict the mean of the three labels at the test input
Hint 1/4
Run the skeleton twice: noise, average model, bias², variance, total.
Hint 2/4
Bias² $=E_X\big[(\bar f(X)-\bar y(X))^2\big]$, variance $=E_X\big[\mathrm{Var}_D(\hat f_D(X))\big]$, and a mean of $k$ independent labels of variance $1$ has variance $1/k$.
Hint 3/4
Rule A averages all $6$ labels, so $\bar f=\tfrac16(3\cdot 1+3\cdot 3)=2$; rule B averages the $3$ labels at the test input, so $\bar f(x)=\bar y(x)$. The noise is $1$.
Hint 4/4
Rule A: $1+\tfrac16+1\approx 2.17$; rule B: $0+\tfrac13+1\approx 1.33$, so rule B wins.
Show solution
Both rules are averages of independent labels, so the skeleton's five steps apply unchanged.
Compare with the four-label versions on the ladder: rule A went from $2.25$ to $2.17$, only its variance shrinking, and rule B from $1.5$ to $1.33$; more data never touched rule A's bias of $1$.
Averaging only the relevant labels removes the bias for a little variance; the overall mean keeps its bias however many labels it gets.
Full exam-style question
Exam-style: local averaging with m neighbours, from bias and variance to a choice of mexam format
Inputs are fixed at $x=1,2,\dots,9$, one label each, with $Y=(x-5)^2+\varepsilon$ and independent noise of variance $\sigma^2=9$. To predict at $x_0=5$, the algorithm averages the labels at the $m$ inputs closest to $5$, for $m=1,3,5$ or $9$, a window centred at $5$.
(a) Find $\bar f(5)$ and the bias² at $x_0=5$ for each $m$.
(b) Find the variance of the prediction for each $m$.
(c) Give the expected squared error for a new label at $x_0=5$, and the best $m$.
(d) In practice $\bar y$ is unknown. How would you choose $m$ from the data alone?
FindBias², variance and expected squared error at $x_0=5$ for each $m$; the best $m$; a way to pick $m$ from data.
Given
$\bar y(x)=(x-5)^2$, so $\bar y(5)=0$
$\sigma^2=9$
windows $W_m$: $\{5\}$, $\{4,5,6\}$, $\{3,\dots,7\}$, $\{1,\dots,9\}$
Solution
The prediction is an average of $m$ independent labels, so its mean and variance come from the rules for sums; the decomposition at the single input $x_0$ then needs no average over $X$.
Edge cases: $m=1$ is unbiased with the full label variance, $0+9+9=18$, and $m=9$ has the smallest variance, $1$, but the largest bias; the best $m$ lies strictly between them, as the tradeoff predicts.
The window size is a flexibility knob like the polynomial degree, turned the other way: a small window means low bias and high variance.
Practice
A · concept 4 questions
1§04.3 — does zero bias leave only the noise?
A classmate claims that an algorithm with no bias at any input has an expected test error equal to the noise. You test the claim on a small case.
Find(a) Is the claim true or false?
Given
Claim: if $\bar f(x)=\bar y(x)$ for every $x$, the expected test error equals $E_{X,Y}\big[(\bar y(X)-Y)^2\big]$.
Test case: training inputs $0,1,2$ with one label each, $\bar y(x)=2x$, noise variance $1$, test input uniform on $\{0,1,2\}$. The least squares line is unbiased here, with prediction variances $\tfrac56,\ \tfrac13,\ \tfrac56$ at $0,1,2$.
Hint 1/4
The claim drops one term of the decomposition; check whether that term is zero in the test case.
Hint 2/4
Expected test error $=\text{bias}^2+\text{variance}+\text{noise}$.
Hint 3/4
In the test case bias² is $0$, the variance is the average of $\tfrac56,\ \tfrac13,\ \tfrac56$ over three equally likely inputs, and the noise is $1$.
Hint 4/4
The expected test error is $0+\tfrac23+1=\tfrac53>1$, so the claim is false.
Show solution
One counterexample refutes a claim about every algorithm, so we evaluate the test case instead of arguing in general.
Average the prediction variance over the three equally likely test inputs.
Total
$$0+\tfrac23+1=\tfrac53\neq 1$$
The bias term is zero, but the variance term is not.
Answer $$\boxed{\text{False: expected test error }\tfrac53\ \text{against noise }1}$$
Check
Direct check at $x=1$, where the line's prediction is the mean of the three labels: $E\big[(\hat f_D(1)-Y)^2\big]=\tfrac13+1$, already above the noise at that single input.
Every fit made from noisy labels carries variance, and it is paid on top of the noise.
2§04.6 — running leave-one-out twice
Two teammates run leave-one-out cross-validation on the same $50$ points with the same least squares model, on different days and different computers.
Find(a) True or false: their two $\mathrm{CV}(n)$ values must be equal.
Given
the same data set of $50$ points
the same algorithm: least squares with a fixed degree, full column rank
Hint 1/4
Ask whether any step of leave-one-out involves a random choice.
Hint 2/4
$\mathrm{CV}(n)=\frac1n\sum_i\big(y_i-\hat f_{D_i}(x_i)\big)^2$ with $D_i=D\setminus\{(x_i,y_i)\}$.
Hint 3/4
With the same $50$ points, each $D_i$ is the same set on both days, and least squares on the same $D_i$ gives the same fit.
Hint 4/4
Every term is identical, so the two values are equal: true.
Show solution
We walk through the recipe looking for a random choice, since a deterministic recipe on the same input gives the same output.
Where randomness could enter
$$D_i=D\setminus\{(x_i,y_i)\}\ \ \text{is determined by }D$$
The line really is the least squares fit of the training points: its residuals $0.2,-0.4,0.2$ sum to $0$, and $\sum_i x_ir_i=0-0.4+0.4=0$, the two normal equations.
Always say which points an MSE was computed on; the same line has two different errors.
2§04.3 — bias², variance and noise from four training sets
An algorithm is run on the four equally likely training sets of a small experiment, and its prediction at the input $x_0$ is recorded each time.
Find
(a) Find $\bar f(x_0)$, the bias² and the variance at $x_0$.
(b) Find the expected squared error for a new label at $x_0$.
Given
predictions at $x_0$: $1.0,\ \allowbreak 1.4,\ \allowbreak 1.8,\ \allowbreak 2.2$, each with probability $\tfrac14$
$\bar y(x_0)=1.2$
$\mathrm{Var}(Y\mid X=x_0)=0.3$
Hint 1/4
Average the four predictions first, then measure the gap to $\bar y(x_0)$ and the spread around the average.
Direct refits: the held-out misses are $-3.75,\ \allowbreak -1.25,\ \allowbreak 5,\ \allowbreak 0,\ \allowbreak 0$, with squares $14.0625,\ \allowbreak 1.5625,\ \allowbreak 25,\ \allowbreak 0,\ \allowbreak 0$ whose average is $8.125$.
With five labels the held-out error is more than one and a half times the training error; the gap shrinks as $n$ grows.
5§04.7 — four folds of two labels
Eight labels are split at random into four folds of two, and the mean predictor is scored by $4$-fold cross-validation.
Find
(a) Compute the four fold MSEs.
(b) Compute $\mathrm{CV}(4)$ and compare it with the leave-one-out value $\big(\tfrac87\big)^2\times 4.5\approx 5.88$.
Given
folds of labels: $F_1=\{1,5\}$, $F_2=\{4,8\}$, $F_3=\{2,4\}$, $F_4=\{6,6\}$
the model predicts the mean of the labels it was trained on
Hint 1/4
For each fold, the model is the mean of the six labels outside it.
Hint 2/4
$\mathrm{MSE}_i=\frac12\sum_{y\in F_i}\big(y-m_{-F_i}\big)^2$ and $\mathrm{CV}(4)=\frac14\sum_i\mathrm{MSE}_i$.
Hint 3/4
Folds $\{1,5\}, \allowbreak \{4,8\}, \allowbreak \{2,4\}, \allowbreak \{6,6\}$ with total $36$, so the outside means are $\tfrac{36-6}{6}=5$, $\tfrac{36-12}{6}=4$, $5$ and $4$.
Hint 4/4
The fold MSEs are $8,\ 8,\ 5,\ 4$, so $\mathrm{CV}(4)=6.25$, a little above the leave-one-out $5.88$.
Show solution
Each outside mean is the total minus the fold, divided by six, which is quicker than adding six labels four times.
Models trained on fewer labels score slightly worse.
Answer $$\boxed{\mathrm{CV}(4)=6.25}$$
Check
Direction check: a mean of $6$ labels is expected to predict a little worse than a mean of $7$, since its error is $\sigma^2(1+1/m)$, and $6.25>5.88$ points the same way.
Fewer folds mean smaller training sets and a slightly more pessimistic estimate; that is the price of fewer fits.
6§04.5 — how pessimistic a half split is
Labels ignore the input and have variance $\sigma^2=4$; the model predicts the mean of its training labels. There are $n=20$ labelled points.
Find
(a) Find the expected test error of the model trained on all $20$ points, on $10$ (a half split) and on $16$ (an 80/20 split).
(b) By what factor does each split overstate the error of the model trained on all $20$?
Given
$\sigma^2=4$, labels independent
$n=20$
expected test error of a mean of $m$ labels $=$ bias² $+$ variance $+$ noise
Hint 1/4
The only thing that changes between the three models is how many labels they average.
Hint 2/4
A mean of $m$ labels has bias² $0$, variance $\sigma^2/m$ and noise $\sigma^2$, so its expected test error is $\sigma^2(1+1/m)$.
Hint 3/4
With $\sigma^2=4$, the training sizes are $m=20$, $10$ and $16$.
Hint 4/4
The errors are $4.2$, $4.4$ and $4.25$; the half split overstates by a factor $1.048$ and the 80/20 split by $1.012$.
Show solution
The decomposition gives the whole curve $\sigma^2(1+1/m)$ at once, so each training size is one substitution.
Formula
$$\sigma^2\Big(1+\frac1m\Big)$$
An unbiased mean with variance $\sigma^2/m$, plus the noise.
Ratio check: leave-one-out costs $n/k=100$ times as many fits as $10$-fold, and $4000/40=100$.
Leave-one-out is cheap only when $n$ is small or a shortcut exists; otherwise $5$ or $10$ folds keep the idea at a fraction of the cost.
8§04.4 — the best shrinkage factor for a noisy average
A label does not depend on the input; it has mean $\mu=3$ and variance $\sigma^2=18$. We predict a new label by $\alpha m$, where $m$ is the mean of $n=2$ independent training labels.
Find
(a) Write the expected test error as a function of $\alpha$.
(b) Find the best $\alpha$ and compare its error with the error at $\alpha=1$.
Given
$\mu=3$, $\sigma^2=18$, $n=2$
$\hat f_D=\alpha m$
Hint 1/4
Split the error into bias², variance and noise, each as a function of $\alpha$.
Hint 2/4
$\text{bias}^2=(\alpha-1)^2\mu^2$, $\text{variance}=\alpha^2\sigma^2/n$, noise $=\sigma^2$; the minimizer is $\alpha^\ast=\mu^2/(\mu^2+\sigma^2/n)$.
Hint 3/4
Here $\mu^2=9$, $\sigma^2/n=18/2=9$ and $\sigma^2=18$.
Hint 4/4
$\alpha^\ast=9/18=0.5$, with error $22.5$ against $27$ at $\alpha=1$.
Show solution
The decomposition gives a quadratic in $\alpha$, so one derivative finds the minimum.
Because $\mu^2=\sigma^2/n$ here, the formula puts $\alpha^\ast$ exactly halfway, and at that point bias² and variance come out equal, $2.25$ each.
When the noise in the average is as large as the signal, halving the estimate beats using it as it is; with little noise, $\alpha^\ast$ moves toward $1$.
C · exam level 5 questions
1§04.4 — reading a table of training and validation errors
Polynomials of degree $1$ to $6$ are fitted to the same training part and scored on the same validation part.
Find(a) Which degree do you choose, and how do you describe the two ends of the table?
Given
training MSE for degrees $1$ to $6$: $2.10,\ \allowbreak 0.95,\ \allowbreak 0.60,\ \allowbreak 0.52,\ \allowbreak 0.40,\ \allowbreak 0.31$
validation MSE for degrees $1$ to $6$: $2.18,\ \allowbreak 1.10,\ \allowbreak 0.75,\ \allowbreak 0.80,\ \allowbreak 1.05,\ \allowbreak 1.60$
Hint 1/4
Choose with the validation column; diagnose with both columns together.
Hint 2/4
Underfitting: both errors high. Overfitting: training error low, validation error high.
The gap between validation and training error grows from $0.08$ at degree $1$ to $1.29$ at degree $6$, the mark of rising variance.
A small gap is good news only when both errors are small; at degree $1$ it just means the model is equally bad everywhere.
2§04.3 — a prediction pulled toward a fixed guess
Labels ignore the input, with mean $\mu=5$ and variance $\sigma^2=3$. From two independent training labels, an analyst predicts $\hat f_D=\tfrac13(y_1+y_2+4)$, pulling the average toward the guess $4$.
Find(a) What is the expected test error $E\big[(\hat f_D-Y)^2\big]$?
Given
$\mu=5$, $\sigma^2=3$
$\hat f_D=\tfrac13(y_1+y_2+4)$
a new label $Y$, independent of $y_1$ and $y_2$
Hint 1/4
Find the average model first; the fixed guess moves it away from $\mu$.
The plain average of two has no bias but variance $\tfrac32$.
Answer $$\boxed{\tfrac{34}{9}\approx 3.78}$$
Check
Direct route: $\hat f_D-Y$ has mean $\tfrac{14}{3}-5=-\tfrac13$ and variance $\tfrac23+3=\tfrac{11}{3}$, so $E[(\hat f_D-Y)^2]=\tfrac{11}{3}+\tfrac19=\tfrac{34}{9}$.
A fixed guess pays in bias and saves in variance; here the guess $4$ is close to $\mu=5$, so it saves more than it costs.
3§04.7 — find the flaw in a cross-validation routine
A student writes up how they chose a polynomial degree for $100$ points with $5$-fold cross-validation. The four steps are below.
Find(a) Which step contains the error?
Given
Step 1: shuffle the $100$ points and cut them into $5$ folds of $20$.
Step 2: for each degree $d$, fit the polynomial once, on all $100$ points.
Step 3: for each fold, compute the MSE of that fit on the fold's $20$ points.
Step 4: average the five fold MSEs to get $\mathrm{CV}(5)$ for degree $d$, and keep the degree with the smallest value.
Hint 1/4
For each step, ask whether the points being scored were kept away from the fit.
Hint 2/4
In $k$-fold CV, fold $F_i$ is scored by $\hat f_{D_i}$ with $D_i=D\setminus F_i$.
Hint 3/4
Here $n=100$ and $k=5$: each fold's model should be fitted on the other $80$ points, one fit per fold, $5$ fits per degree.
Hint 4/4
Step 2 fits once on all $100$ points, so every fold is scored by a model that saw it: Step 2 is the error.
Show solution
Checking each step against the recipe is quicker than rerunning the whole routine.
Steps 1, 3 and 4
$$\text{shuffle and cut};\ \ \text{score each fold};\ \ \text{average and pick}$$
These three match the recipe.
Step 2
$$\hat f\ \text{fitted on all }100\ \Rightarrow\ \text{every fold was in the fit}$$
The fold MSEs become pieces of the training error.
Five equal folds of one fit average back to its training MSE, which always prefers the most flexible model.
Answer $$\boxed{\text{Step 2}}$$
Check
Symptom check: with this flaw the chosen degree is always the largest one tried, because training MSE never rises with the degree.
Write the fit inside the loop over folds, never before it.
4§04.6 — leave-one-out against a single validation split
A student compares leave-one-out cross-validation with one random 50/50 validation split, on the same $n$ points and with the same least squares model.
Find(a) Which statement about leave-one-out is correct?
Given
same data, same model
validation split: one random 50/50 split
Hint 1/4
Recall how many fits leave-one-out makes and what each one is trained on.
Hint 2/4
Leave-one-out: for each $i$, fit on $D\setminus\{(x_i,y_i)\}$ and score on $(x_i,y_i)$.
Hint 3/4
With $n$ points that is $n$ fits, each on $n-1$ points, with held-out sets fixed by the data; the split makes one fit on $n/2$ points.
Hint 4/4
The correct statement: it fits $n$ models, and no random split affects its value.
Show solution
Counting fits and looking for random steps settles all four options at once.
Count
$$n\ \text{fits, each on }n-1\ \text{points}$$
One fit per left-out point.
Randomness
$$D_i=D\setminus\{(x_i,y_i)\}\ \ \text{is fixed by }D$$
Nothing is shuffled, so the value is the same on every run.
Answer $$\boxed{n\ \text{fits; no random split}}$$
Check
Contrast with the split: one fit on $n/2$ points, and a new shuffle gives a new score, as the eight curves of the validation figure show.
Leave-one-out fixes both weaknesses of the single split, randomness and small training sets, at the cost of $n$ fits.
5§04.1 — why the training error is optimistic, in one formula
Labels ignore the input and are independent with mean $\mu$ and variance $\sigma^2$. The model predicts the mean $m$ of its $n$ training labels.
Find
(a) Show that $E\big[(y_i-m)^2\big]=\sigma^2\,\frac{n-1}{n}$ for each training label.
(b) Show that $E\big[(Y-m)^2\big]=\sigma^2\,\frac{n+1}{n}$.
(c) Evaluate both for $n=5$ and $\sigma^2=10$, and give the gap.
Given
$y_1,\dots,y_n$ independent, with mean $\mu$ and variance $\sigma^2$
$m=\frac1n\sum_{j=1}^n y_j$
a new label $Y$, independent of the training labels
Hint 1/4
Both are expected squares of a difference whose mean is $0$, so each equals the variance of that difference.
Hint 2/4
$\mathrm{Var}\big(\sum_ja_jy_j\big)=\sigma^2\sum_ja_j^2$ for independent labels, and $\mathrm{Var}(U-V)=\mathrm{Var}(U)+\mathrm{Var}(V)$ for independent $U$, $V$.
Hint 3/4
Write $y_i-m=\big(1-\tfrac1n\big)y_i-\tfrac1n\sum_{j\ne i}y_j$, and use that $Y$ is independent of $m$; then put $n=5$, $\sigma^2=10$.
Hint 4/4
$E[(y_i-m)^2]=8$ and $E[(Y-m)^2]=12$: a gap of $2\sigma^2/n=4$.
Show solution
Both differences have mean $0$, so each expectation is a variance, and variances of weighted sums of independent labels are routine.
Edge case $n=1$: the training residual is $y_1-y_1=0$, and the formula gives $\sigma^2\cdot 0=0$; the new-label error is $2\sigma^2$, the variance of a difference of two independent labels.
The training error is optimistic by $2\sigma^2/n$ even for the simplest model: the fit has already seen, and partly absorbed, the noise it is scored on.
D · interleaved 5 questions
1§04.5 — a spam filter's error on 400 held-out emails
A spam filter, frozen after training, is scored on $400$ held-out emails and misclassifies $36$ of them. You want an interval for its true error rate and a plan to narrow it.
Find
(a) Give the 95% interval for the true error rate.
(b) How many held-out emails would halve the interval's half-width, if the error rate stayed near the same value?
a 95% interval for a proportion: $\bar\theta\pm 2\sqrt{\bar\theta(1-\bar\theta)/n}$
Hint 1/4
The held-out emails are a sample of yes/no outcomes with one unknown rate.
Hint 2/4
$\mathrm{SE}=\sqrt{\bar\theta(1-\bar\theta)/n}$, which shrinks like $1/\sqrt n$.
Hint 3/4
Here $\bar\theta=36/400=0.09$ and $n=400$, so $\mathrm{SE}=\sqrt{0.09\times 0.91/400}$.
Hint 4/4
The interval is $0.09\pm 0.029=[0.061,\,0.119]$, and $1600$ emails would halve its half-width.
Show solution
The filter is fixed and the emails were held out, so the error indicators are independent draws with the true error rate as mean, and the interval for a proportion applies.
Check the halving: $\sqrt{0.09\times 0.91/1600}\approx 0.00715$, half of $0.0143$.
A held-out error rate is an estimate with its own error bar, which is why the validation scores of close candidates can swap places between splits.
2§04.5 — how many held-out images are enough
An image classifier has been trained and frozen. We want its error rate on held-out images to be within $0.05$ of its true error rate with probability at least $0.95$.
Find
(a) How many held-out images does this bound require?
(b) Why may the same bound not be applied to the classifier's error rate on its own training images?
Given
for independent $Z_i\in[0,1]$ with average $\bar Z$: $\Pr\big(\vert\bar Z-E[\bar Z]\vert\ge\varepsilon\big)\le 2e^{-2n\varepsilon^2}$
$\varepsilon=0.05$ and failure probability $\delta=0.05$
Hint 1/4
Each held-out image gives an error indicator in $\{0,1\}$; the bound controls how far their average strays from its mean.
Hint 2/4
Set $2e^{-2n\varepsilon^2}\le\delta$ and solve: $n\ge\frac{\ln(2/\delta)}{2\varepsilon^2}$.
Hint 3/4
With $\varepsilon=0.05$ and $\delta=0.05$: $n\ge\frac{\ln 40}{2\times 0.0025}=\frac{3.689}{0.005}$.
Hint 4/4
$n\ge 737.8$, so $738$ images; on training images the indicators depend on the fit, so their mean is not the true error rate.
Show solution
Solving the inequality for $n$ is one logarithm; the harder half of the question is whether its assumptions hold.
Guarantees about error rates need points the model was never fitted to; held-out data is what makes the probability statement true.
3§04.4 — a click rate estimated with and without a prior
A click rate $\theta$ is estimated from $N=10$ independent views. The MLE is $N_1/N$; with a flat $\mathrm{Beta}(1,1)$ prior the posterior mean is $(N_1+1)/(N+2)$. Judge both as estimators of $\theta$ by squared error.
Find
(a) For $\theta=0.2$, find the bias², variance and expected squared error of each estimator.
(b) Repeat for $\theta=0.05$. Which estimator wins each time?
Given
$N_1\sim\mathrm{Binomial}(10,\theta)$: mean $10\theta$, variance $10\theta(1-\theta)$
MLE $N_1/10$; posterior mean $(N_1+1)/12$
Hint 1/4
Each estimator is a fixed function of the count $N_1$, so its bias and variance follow from the binomial mean and variance.
Hint 2/4
For $aN_1+b$: mean $a\cdot 10\theta+b$ and variance $a^2\cdot 10\theta(1-\theta)$; expected squared error $=$ bias² $+$ variance.
Hint 3/4
MLE: $a=\tfrac1{10}$, $b=0$. Posterior mean: $a=\tfrac1{12}$, $b=\tfrac1{12}$. Use $\theta=0.2$, then $\theta=0.05$.
Hint 4/4
At $\theta=0.2$ the errors are $0.016$ and $0.0136$, so the posterior mean wins; at $\theta=0.05$ they are $0.00475$ and $0.0089$, so the MLE wins.
Show solution
Both estimators are linear in $N_1$, so the rules $E[aN_1+b]$ and $\mathrm{Var}(aN_1+b)$ give everything without listing the eleven values of $N_1$.
The pull toward $\tfrac12$ now costs more bias than it saves in variance.
Answer $$\boxed{\theta=0.2:\ \text{posterior mean wins};\qquad \theta=0.05:\ \text{MLE wins}}$$
Check
The posterior mean pulls every estimate toward $0.5$; that pull helps when $\theta$ is near the middle and hurts near an edge, which matches the two verdicts.
Like the shrunken average, the prior trades bias for variance, and whether the trade pays depends on the unknown $\theta$.
4§04.2 — a fitted line's error at a new input
A least squares line is fitted with the inputs fixed at $-1,0,1$, each used twice, so $n=6$. The model form is right.
Find
(a) Find $\mathrm{Var}(\hat\beta_0)$ and $\mathrm{Var}(\hat\beta_1)$.
(b) Find the variance of the prediction at $x=2$.
(c) Find the expected squared error for a new label at $x=2$.
Given
$Y=1+2x+\varepsilon$, independent noise with $\sigma^2=4$
inputs $-1,-1,0,0,1,1$
$\mathrm{Var}(\hat\beta_1)=\sigma^2/\sum_i(x_i-\bar x)^2$; with $\bar x=0$, $\mathrm{Var}(\hat\beta_0)=\sigma^2/n$ and the two are uncorrelated
Hint 1/4
The line is unbiased, so the error at the new input is the prediction variance plus the new label's noise.
Hint 2/4
When the two coefficients are uncorrelated, $$\mathrm{Var}\big(\hat\beta_0+\hat\beta_1x\big)=\mathrm{Var}(\hat\beta_0)+x^2\,\mathrm{Var}(\hat\beta_1).$$
Hint 3/4
Here $\sigma^2=4$, $n=6$ and $\sum_i x_i^2=4$, with $x=2$.
Hint 4/4
$\mathrm{Var}(\hat\beta_0)=\tfrac23$, $\mathrm{Var}(\hat\beta_1)=1$, the prediction variance is $\tfrac{14}{3}\approx 4.67$, and the expected squared error is $\tfrac{26}{3}\approx 8.67$.
Show solution
The least squares formulas from the previous section give the coefficient variances directly, and the decomposition adds the rest.
At the centre $x=0$ the prediction variance would be $\tfrac23$, the variance of an average of six labels of variance $4$; at $x=2$ it is seven times that.
Even a correct model pays for distance from its data: the variance term grows with $(x-\bar x)^2$.
5§04.5 — how noisy a validation score is
A fixed model's squared errors on held-out points are independent, each with mean $0.8$ and standard deviation $1.2$. The validation MSE is their average.
Find
(a) Find the standard deviation of the validation MSE, and the range that holds it with probability about $0.95$.
(b) How many held-out points would bring the standard deviation down to $0.05$?
Given
per squared error: mean $0.8$, standard deviation $1.2$
$n_{\mathrm{val}}=36$
an average of $n$ i.i.d. terms has standard deviation $\sigma/\sqrt n$ and is roughly normal for large $n$
Hint 1/4
The validation MSE is a sample mean, so the tools for averages apply.
Hint 2/4
$\mathrm{sd}\big(\mathrm{MSE}_{\mathrm{val}}\big)=\sigma/\sqrt{n_{\mathrm{val}}}$, and about $0.95$ of a normal lies within two standard deviations of its mean.
Hint 3/4
Here $\sigma=1.2$, $n_{\mathrm{val}}=36$ and the mean is $0.8$; for (b), solve $1.2/\sqrt n=0.05$.
Hint 4/4
The standard deviation is $0.2$, the range is $[0.4,\ 1.2]$, and $576$ points give $0.05$.
Show solution
The central limit theorem turns the question into one square root and one inversion.
With a few dozen held-out points a validation MSE can land anywhere from half to one and a half times its mean, enough for two close candidates to swap places.
Mistake ledger (14 entries)
⚠ Choosing the model with the smallest training MSE
It is the one error we can compute without extra data, and it looks like a quality score.
wrong$$\hat d=\arg\min_d\,\mathrm{MSE}_{\mathrm{train}}(d)=11\ \ \text{in the figure}$$
right$$\hat d=\arg\min_d\,\mathrm{MSE}_{\mathrm{test}}(d)=3\ \ \text{in the figure}$$
⚠ Computing the test MSE on the training points
Both errors use the same formula, so the data set behind the sum is easy to swap.
right$$\begin{aligned}&n\to\infty\ \Rightarrow\ \text{variance shrinks}\\ &\text{bias}^2\ \text{stays if the model class cannot express }\bar y\end{aligned}$$
⚠ Fitting on all of the data and then scoring on the validation part
The full fit looks like the model we will use, so scoring it seems natural.
The identity that splits the expected squared test error into bias squared, variance and noise.
yanlılık varyans ikilemi
The pattern that making a model more flexible usually lowers its bias and raises its variance.
overfittingaşırı öğrenme
Fitting the noise of the training set along with its signal: low training error, high test error, driven by variance.
underfittingyetersiz öğrenme
Using a model too rigid for the signal: high training and test error, driven by bias.
shrinkagebüzülme
Pulling an estimate toward a fixed value to lower its variance at the cost of some bias.
hyperparameterhiperparametre
A setting chosen before fitting, such as the degree or a shrinkage factor, rather than learned by the fit.
model seçimi
Choosing among candidate models or hyperparameter values by an estimate of their test error.
validation setdoğrulama kümesi
The part of the data held out from fitting and used only to score candidate models.
cross-validationçapraz doğrulama
Estimating test error by fitting on part of the data and scoring on the held-out rest, so that every point is held out once.
leave-one-out cross-validation
Cross-validation with n fits, each leaving out a single point and predicting it.
k-fold cross-validationk katlı çapraz doğrulama
Cross-validation with the data split at random into k folds, each held out once while the others train the model.
foldkat
One of the k parts of the data in k-fold cross-validation.
leveragekaldıraç
For least squares, how strongly a point pulls the fit toward itself; for a line, 1/n plus the point's squared distance from the mean input divided by the sum of all such squared distances.
What comes next
§05 · Regularized regression: ridge and lasso
Next, the flexibility knob becomes a penalty on the size of the coefficients instead of the degree of a polynomial. The training error cannot say how strong that penalty should be; it is chosen the way this section chose degrees.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides and lecture notes, chapter 4: Measuring the performance Scope, order of topics and notation (training and test MSE, the expected label, the average model, D drawn from J, CV(n) and CV(k)) follow these materials; all explanations, data, figures and exercises here are original.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights, the course learning outcomes and the recommended books.
textbookG. James, D. Witten, T. Hastie, R. Tibshirani, An Introduction to Statistical Learning, Springer, 2013 Recommended in the syllabus; most of the lecture's figures for this chapter come from it.
standard resultLeave-one-out identity for linear least squares A standard result, used once as further reading and checked by two refits by hand. Every number in the figures was computed for this page from the simulation described in the captions.