Generalisation
Held-out data, overfitting, and choosing a model by the error it makes on points it never saw.
Do this lesson in the simulatorA 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. The line answers sensibly. The polynomial, which had to bend hard to hit every noisy point, answers whatever the bends happen to say there, and ask it about a command past the end of your data and it goes off to infinity.
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.
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.
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))
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 leaves the fit very little room to be wrong. 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.
The size of the gap is the diagnostic. A little, as here, is the normal price of fitting. A lot means the model 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. Raw commands of 25 to 95 raised to the tenth power produce numbers that differ by ten orders of magnitude in one matrix, 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:
- Fit each candidate on the training set.
- Score each on the held-out set.
- 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:. Two of the test commands 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
- Print the degree 5 model's prediction at command 120. What has it done, and why is that the expected behaviour?
- Try degrees 1, 2 and 3 as well and plot training and test error against degree.
- Swap your train and test sets over and refit. How different is the fitted slope, and what does that difference tell you?