Generalisation

Held-out data, overfitting, and choosing a model by the error it makes on points it never saw.

U12.3Learning, and the capstoneUniversity35 min

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Sim to real: why a policy that works in simulation fails on the robot

A model that fits the data you gave it is not the goal. The goal is a model that is right about data you have not collected yet, which is a different and much harder claim.

The claim a fit makes

Any fit reports a training error: how far the model is from the points it was fitted to. It is the easiest number to compute and the easiest to fool. Add parameters and it falls. Add enough parameters and it reaches zero, because the model can pass exactly through every point you have.

At that moment the model has learned nothing except your particular noise.

Overfitting, concretely

Take six measurements of speed against command. Fit a straight line: two parameters, and the line misses each point slightly, because each measurement has flow noise on it. Now fit a degree 5 polynomial: six parameters, six points, and there is exactly one such polynomial through all six. Training error zero.

Ask the two of them about a command between the ones you measured and, with noise this small, they give much the same answer: the bends the polynomial needed to hit every noisy point are small there. Ask about a command past the end of your data and nothing holds the bends down. In a run of the task below, trained on commands 30 to 80, the polynomial misses command 95 by 18 cm/s and says command 120 drives backwards at 272 cm/s, where the line says 22.6 forwards.

Six training points with a straight line and a degree 5 polynomial through them, and the test points they are judged on203040506070809010005101520commandspeed, cm/straining range, 30 to 80misses 95 by 18line: 2 parametersdegree 5: 6 parameters,through all six pointsat 120 it says -272filled: trained onhollow: test
Inside the training range the two curves nearly agree. Past command 80 nothing holds the polynomial's bends down: it misses command 95 by 18 cm/s and at command 120 says -272, where the line says 22.6.

This is the bias and variance trade-off in its original setting. Too few parameters and the model cannot represent the truth, so it is wrong the same way every time (bias). Too many and it chases the noise, so it is wrong a different way every time you refit it on fresh data (variance). The error on new data is the sum of the two, and it has a minimum in the middle.

Five refits on fresh data for a degree 0, degree 1 and degree 5 model30558001020degree 0: a constantwrong the same way: bias305580degree 1: a linerefits agree, and fit305580degree 5a new mistake each time: variancecommand, 25 to 95; shaded: the training range
The same robot sampled the six training commands five times, and each model was refitted each time. The constant misses every time in the same way; the degree 5 curves agree inside the shaded range and scatter everywhere outside it.

The only honest test

Split the data. Fit on one part, and report the error on the other.

train:  the points the fit was allowed to see
test:   the points it was not

The rule is absolute: the test points may not touch the fit, in any way, not even to choose which model to use. If you look at the test error, choose a model, and then report that same test error as your result, you have quietly fitted to the test set too. The professional arrangement is three sets: train to fit, validation to choose, test to report, and the test set opened once.

With very little data, hold-out is wasteful and k-fold cross validation does better: split into k parts, fit k times leaving each part out in turn, average the k held-out errors. Every point is used for both jobs, and nothing is contaminated.

Three-fold cross validation: each row fits on four commands and scores the two it left out304050607080commandfit 1testfitfittestfitfit0.36fit 2fittestfitfittestfit0.28fit 3fitfittestfitfittest0.49held-outmean 0.38every command is tested once and helps fit twice
Three-fold cross validation of the straight line on the six speeds the cell below measures. Each command is left out once, and the three held-out errors, in cm/s, are averaged into one honest score.
from bugbot import *
connect()

DT = 0.1

def hold(cmd, ticks, collect=False):
    vs = []
    for i in range(ticks):
        err = (imu()[0] + 180) % 360 - 180
        turn = 0 if abs(err) < 2.0 else (-20.0 if err > 0 else 20.0)
        drive(cmd, 0, turn)
        if collect:
            vs.append(flow()[1])
        wait(DT)
    return vs

def sample(cmd):
    hold(cmd, 12)
    out = sum(hold(cmd, 3, True)) / 3.0
    hold(-cmd, 12)
    back = sum(hold(-cmd, 3, True)) / 3.0
    return (out - back) / 2.0

train = [(c, sample(c)) for c in (30, 50, 70)]
test = [(c, sample(c)) for c in (40, 60, 80)]
stop()

n = len(train)
sx = sum(c for c, v in train)
sv = sum(v for c, v in train)
sxx = sum(c * c for c, v in train)
sxv = sum(c * v for c, v in train)
a = (n * sxv - sx * sv) / (n * sxx - sx * sx)
b = (sv - a * sx) / n

def rms(points):
    return (sum((a * c + b - v) ** 2 for c, v in points) / len(points)) ** 0.5

print("train error", round(rms(train), 3))
print("test error ", round(rms(test), 3))

Run this in the simulator

The line misses its three training points by 0.039 cm/s and the three test points by 0.43, eleven times as much, and most of that is command 80, which lies past the top of the training range and comes out 0.71 cm/s below the line. Even for a straight line on a genuinely straight relationship, the training error comes out the smaller of the two, and the reason is worth understanding: three points and two parameters leave the fit only one spare degree of freedom, so the line tilts and shifts to soak up most of their noise. Training error is an optimistic estimate of the error on new data, always, and the fewer points there are per parameter, the more optimistic it is.

Measured speed minus the fitted line, for the three training commands and the three test commands304050607080-0.8-0.400.4commandmeasured minus line, cm/straining range-0.71filled: traininghollow: test
The line bends to its own three points, so they sit almost on it. The test points were never seen, and command 80, past the end of the training range, is 0.71 cm/s off.

So the test error is the number to believe. Here 0.43 cm/s is 3 to 6 percent of the speeds involved, a model worth using. What should worry you is a test error that is large against the thing being predicted, or one that gets worse as you add parameters: that is a model that has learned things that will not repeat.

Fitting a polynomial in plain Python

For a model that is linear in its parameters, including a polynomial, the normal equations generalise directly. Build the matrix of sums, build the right hand side, solve with Gaussian elimination:

def fit(points, degree):
    m = degree + 1
    a = []
    for i in range(m):
        row = [sum(u(c) ** (i + j) for c, v in points) for j in range(m)]
        row.append(sum(v * u(c) ** i for c, v in points))
        a.append(row)
    # ... eliminate, back substitute, return the coefficients

Scale the inputs first, u(c) = (c - 55) / 25 or similar. A degree 5 fit needs sums of the commands up to the tenth power, so with raw commands of 30 to 80 one matrix holds entries from 6 up to about 10^19, and the solution comes back as noise. Scaling is not a nicety here, it is the difference between an answer and rubbish.

Model selection

With held-out error in hand, choosing between models stops being a matter of taste:

  1. Fit each candidate on the training set.
  2. Score each on the held-out set.
  3. Take the winner, and prefer the simpler model when the scores are close.

That last clause is Occam's razor with a practical justification: the simpler model has less variance, so its held-out score is itself more trustworthy.

Task: choose the model by held-out error

Sample fourteen commands, six for training and eight for testing, fit a degree 1 and a degree 5 model to the training six, print all four errors, and print train 5: and best degree:. Three of the test commands, 25, 85 and 95, lie outside the training range, which is where an overfitted model is at its worst.

from bugbot import *
connect()

DT = 0.1
TRAIN = [30, 40, 50, 60, 70, 80]
TEST = [25, 35, 45, 55, 65, 75, 85, 95]

Challenges

  1. Print the degree 5 model's prediction at command 120. What has it done, and why is that the expected behaviour?
  2. Try degrees 1, 2 and 3 as well and plot training and test error against degree.
  3. Swap your train and test sets over and refit. How different is the fitted slope, and what does that difference tell you?