Overfitting and regularization in Java

Problem

The perfect model that promises 5 minutes

The shop tells the customer when the order will arrive. The time is learned from past orders, as in the first lesson on machine learning: the feature is the distance to the customer, the label is the minutes to the door.

A colleague tries two models on 8 past orders. The line from linear regression is off by a few minutes. Their curve is never off:

double[] line = fit(train, 1, 0);
double[] curve = fit(train, 7, 0);
System.out.printf("line (degree 1): training MSE %.2f%n", mse(line, train));
System.out.printf("curve (degree 7): training MSE %.2f%n", mse(curve, train));
for (double km : new double[] {3.5, 21.5})
    System.out.printf("order %.1f km: line %.0f min, curve %.0f min%n",
            km, predict(line, km), predict(curve, km));

line (degree 1): training MSE 9.35
curve (degree 7): training MSE 0.00
order 3.5 km: line 24 min, curve 5 min
order 21.5 km: line 70 min, curve 79 min

The curve has MSE 0.00: perfect on the past. Then a new order comes, 3.5 km away. The curve promises 5 minutes, the line 24. The real time turns out to be 22 minutes. For an order 21.5 km away the curve says 79, the line 70, and the truth is 68.

The model that is never wrong about the past is the worst for the future. This is overfitting: the model has memorised the examples, noise included, instead of learning the relationship.

See it

The curve of degree d

The line is w₀ + w₁ · x. The curve adds powers of x: w₀ + w₁ · x + w₂ · x² + … + w₇ · x⁷. This is a polynomial of degree 7, with 8 weights. Degree 1 is the line.

The orders are an example, but they look like real ones: further is longer, with a few minutes of noise (traffic, the lift, waiting at the door). Besides the 8 for training there are 8 others for validation and 8 for the test. Why three groups is in the next card.

// training: km to the customer and minutes to the door
double[][] train = {{2, 19}, {5, 23}, {7, 38}, {10, 42}, {13, 52}, {16, 54}, {19, 63}, {22, 69}};
// validation: other orders, only for choosing
double[][] val = {{3, 24}, {6.5, 31}, {9, 36}, {12, 44}, {15, 52}, {18, 57}, {21, 70}, {4, 27}};
// test: run once, at the end
double[][] test = {{3.5, 22}, {8, 34}, {11, 38}, {14, 51}, {17, 59}, {20, 63}, {6, 30}, {21.5, 68}};

x is the distance, moved around 12 km and made ten times smaller. Otherwise 22⁷ is about 2.5 billion and the calculations lose precision.

// x is the distance around 12 km, ten times smaller
static double[] powers(double km, int degree) {
    double x = (km - 12) / 10;
    double[] p = new double[degree + 1];
    p[0] = 1;
    for (int j = 1; j <= degree; j++) p[j] = p[j - 1] * x;
    return p;
}

static double predict(double[] w, double km) {
    double[] p = powers(km, w.length - 1);
    double sum = 0;
    for (int j = 0; j < w.length; j++) sum += w[j] * p[j];
    return sum;
}

static double mse(double[] w, double[][] data) {
    double sum = 0;
    for (double[] row : data) {
        double e = predict(w, row[0]) - row[1];
        sum += e * e;
    }
    return sum / data.length;
}

You could find the weights with gradient descent, but at degree 7 it takes millions of steps. There is a shortcut: the best weights are the solution of a system of equations, with as many equations as there are weights. The system is solved with Gaussian elimination, as at school, only with 8 unknowns. The code is here so that everything is visible. You do not need to follow it line by line:

// the best weights directly: a system of equations
static double[] fit(double[][] data, int degree, double lambda) {
    int m = degree + 1;
    double[][] a = new double[m][m];
    double[] b = new double[m];
    for (double[] row : data) {
        double[] p = powers(row[0], degree);
        for (int i = 0; i < m; i++) {
            b[i] += p[i] * row[1];
            for (int j = 0; j < m; j++) a[i][j] += p[i] * p[j];
        }
    }
    // the penalty: λ on the diagonal, not the intercept
    for (int i = 1; i < m; i++) a[i][i] += lambda;
    return solve(a, b);
}

// Gaussian elimination: solves a · w = b
static double[] solve(double[][] a, double[] b) {
    int n = b.length;
    for (int c = 0; c < n; c++) {
        int p = c;
        for (int r = c + 1; r < n; r++)
            if (Math.abs(a[r][c]) > Math.abs(a[p][c])) p = r;
        double[] row = a[c];
        a[c] = a[p];
        a[p] = row;
        double t = b[c];
        b[c] = b[p];
        b[p] = t;
        for (int r = c + 1; r < n; r++) {
            double f = a[r][c] / a[c][c];
            for (int k = c; k < n; k++) a[r][k] -= f * a[c][k];
            b[r] -= f * b[c];
        }
    }
    double[] x = new double[n];
    for (int r = n - 1; r >= 0; r--) {
        double s = b[r];
        for (int k = r + 1; k < n; k++) s -= a[r][k] * x[k];
        x[r] = s / a[r][r];
    }
    return x;
}

The penalty line gets 0 for now. We will get to it.

The idea

Training, validation and test

In the evaluation lesson the data had two groups: training and test. Now a third one is needed. Here is why: we want to pick the degree. If we pick it by the training error, 7 always wins, because its error is 0. If we pick it by the test, the test has taken part in a decision and is no longer honest at the end.

So the data is in three groups:

training set: the weights are learned from it;
validation set: the models are compared on it and the degree is picked;
test set: run once, at the end, for the chosen model.

System.out.println("MSE: training / validation");
int best = 1;
double bestVal = Double.MAX_VALUE;
for (int degree = 1; degree <= 7; degree++) {
    double[] w = fit(train, degree, 0);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("degree %d: %.2f / %.2f%n",
            degree, trainErr, valErr);
    if (valErr < bestVal) {
        bestVal = valErr;
        best = degree;
    }
}
double testErr = mse(fit(train, best, 0), test);
System.out.printf("chosen degree: %d, test: %.2f%n",
        best, testErr);

MSE: training / validation
degree 1: 9.35 / 3.64
degree 2: 6.74 / 9.35
degree 3: 6.61 / 9.09
degree 4: 5.64 / 11.95
degree 5: 3.75 / 18.81
degree 6: 3.30 / 29.06
degree 7: 0.00 / 121.20
chosen degree: 1, test: 5.57

The training error falls with every degree: 9.35, 6.74, …, 0.00. The validation error grows: 3.64, 9.35, …, 121.20. The more weights the curve has, the better it remembers the 8 points and the worse it guesses new ones. Validation picks degree 1, the line, and its test error is 5.57 (the square root of 5.57 is about 2.4 minutes of average error).

One thing looks odd: the line has a smaller error on validation (3.64) than on training (9.35). With 8 orders chance is big: the validation set just happened to get orders closer to the line. That is why, with little data, do not trust the second digit.

See it

The curve twists

System.out.println("MSE: training / validation");
int best = 1;
double bestVal = Double.MAX_VALUE;
for (int degree = 1; degree <= 7; degree++) {
    double[] w = fit(train, degree, 0);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("degree %d: %.2f / %.2f%n",
            degree, trainErr, valErr);
    if (valErr < bestVal) {
        bestVal = valErr;
        best = degree;
    }
}
double testErr = mse(fit(train, best, 0), test);
System.out.printf("chosen degree: %d, test: %.2f%n",
        best, testErr);

System.out.println("training / validation, max |w|");
double[] lambdas = {0, 0.001, 0.01, 0.1, 1, 10};
double bestLambda = 0;
double bestVal = Double.MAX_VALUE;
for (double lambda : lambdas) {
    double[] w = fit(train, 7, lambda);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("λ %.3f: %.2f / %.2f, %.2f%n",
            lambda, trainErr, valErr, biggest(w));
    if (valErr < bestVal) {
        bestVal = valErr;
        bestLambda = lambda;
    }
}
double testErr = mse(fit(train, 7, bestLambda), test);
System.out.printf("chosen λ: %.3f, test: %.2f%n",
        bestLambda, testErr);

Step by step, in words

8 training orders: the distance in km and the minutes to the door. The further, the longer, with some noise.
Degree 1 is a line. It misses most points by a few minutes: training MSE 9.35.
Each degree adds one weight. The curve bends more and gets closer to every training point.
Degree 7 has 8 weights for 8 points and passes through every one: training MSE 0.00. It looks perfect.
Now 8 other orders, for validation. Between the training points the curve swings away: validation MSE 121.20.
For each degree: training error falls, validation error rises. Validation picks degree 1, the line.
Another fix: keep degree 7 but penalise big weights. With λ = 0.1 the curve calms down: validation MSE 9.55.
The curve that learned the training points by heart is the worst on new orders. Test error: 5.57 for the line, 9.96 for the curve with λ = 0.1.

The degree 7 curve hits every blue point and misses the orange ones by tens of minutes. The bars below say the same for every degree: blue (training) falls, orange (validation) grows.

Try it

Find the bug

A colleague picks the degree like this. Their program always picks 7. On which line is the bug?

Pick the line with the bug.

The idea

Three cures

1. A simpler model. Validation has already picked it: the line. When the relationship is almost straight, the line is enough, and every extra weight is room for noise.

2. More data. The degree 7 curve has 8 weights. With 8 points it can pass exactly through each one. With 16 points it cannot, so it has to pass between them, and that smooths the noise:

double[][] both = Arrays.copyOf(train, train.length + val.length);
System.arraycopy(val, 0, both, train.length, val.length);
for (double[][] data : new double[][][] {train, both})
    System.out.printf("degree 7, %d orders: test %.2f%n",
            data.length, mse(fit(data, 7, 0), test));

degree 7, 8 orders: test 84.44
degree 7, 16 orders: test 9.41

Arrays.copyOf(train, 16) makes an array with 16 places and the first 8 rows of train, and System.arraycopy copies val into the other 8.

The test error falls from 84.44 to 9.41. Here validation is used for training too, so there is nothing left to pick the degree with. In a real project cross-validation is used for that (see “More”).

3. A penalty for big weights. The twisting curve has huge weights: the biggest is 571.59. The curve hits every point because huge weights with different signs almost cancel out, and what is left of them twists the curve. Regularization adds a penalty to the error: λ times the sum of the squared weights. Now training looks for weights that both hit the points and are small. In the code this is the only penalty line in fit. λ is picked with validation, like the degree:

// the biggest weight, without the intercept
static double biggest(double[] w) {
    double max = 0;
    for (int j = 1; j < w.length; j++) max = Math.max(max, Math.abs(w[j]));
    return max;
}

System.out.println("training / validation, max |w|");
double[] lambdas = {0, 0.001, 0.01, 0.1, 1, 10};
double bestLambda = 0;
double bestVal = Double.MAX_VALUE;
for (double lambda : lambdas) {
    double[] w = fit(train, 7, lambda);
    double trainErr = mse(w, train);
    double valErr = mse(w, val);
    System.out.printf("λ %.3f: %.2f / %.2f, %.2f%n",
            lambda, trainErr, valErr, biggest(w));
    if (valErr < bestVal) {
        bestVal = valErr;
        bestLambda = lambda;
    }
}
double testErr = mse(fit(train, 7, bestLambda), test);
System.out.printf("chosen λ: %.3f, test: %.2f%n",
        bestLambda, testErr);

training / validation, max |w|
λ 0.000: 0.00 / 121.20, 571.59
λ 0.001: 2.80 / 26.49, 36.79
λ 0.010: 3.59 / 17.08, 19.16
λ 0.100: 5.72 / 9.55, 20.21
λ 1.000: 19.95 / 16.71, 13.35
λ 10.000: 100.67 / 93.35, 4.92
chosen λ: 0.100, test: 9.96

The last number of each line (max |w|) is the biggest weight in absolute value, without the intercept. With λ = 0.1 the biggest weight falls from 571.59 to 20.21, and validation from 121.20 to 9.55. A penalty that is too strong (λ = 10) squashes the curve almost to a flat line: the error becomes big on the training data too (100.67). This is the opposite of overfitting, underfitting: the model is too restricted to catch the relationship.

The test error for the chosen λ is 9.96: much better than 84.44, but the line (5.57) is still the best. Regularization does not turn a curve into a line, it only keeps it from going wild.

Try it

Fill in the blank

The penalty goes on the diagonal of the system, without the intercept (i starts at 1). What is added?

// the penalty: λ on the diagonal, not the intercept
for (int i = 1; i < m; i++) a[i][i] += ;

Try it

Predict the output

An error with a penalty: MSE is 2, the weights are 3 and −4, λ is 0.1. What will it print?

double mse = 2.0;
double[] w = {3, -4};
double lambda = 0.1;
double penalty = 0;
for (double x : w) penalty += x * x;
System.out.printf("%.2f%n", mse + lambda * penalty);

Answer

4.50

2.70

2.00

The idea

The nearest neighbour memorises

The nearest neighbours from the first lesson have the same illness. With k = 1 the model returns the time of the nearest past order. For an order from the training set the nearest one is the order itself, so the training error is 0:

// the average time of the k nearest orders
static double knn(double[][] data, double km, int k) {
    boolean[] used = new boolean[data.length];
    double sum = 0;
    for (int t = 0; t < k; t++) {
        int best = -1;
        for (int i = 0; i < data.length; i++) {
            if (used[i]) continue;
            if (best < 0 || Math.abs(data[i][0] - km) < Math.abs(data[best][0] - km)) best = i;
        }
        used[best] = true;
        sum += data[best][1];
    }
    return sum / k;
}

static double knnMse(double[][] train, double[][] data, int k) {
    double sum = 0;
    for (double[] row : data) {
        double e = knn(train, row[0], k) - row[1];
        sum += e * e;
    }
    return sum / data.length;
}

System.out.println("MSE: training / validation");
for (int k = 1; k <= 4; k++)
    System.out.printf("k = %d: %.1f / %.1f%n", k, knnMse(train, train, k), knnMse(train, val, k));

MSE: training / validation
k = 1: 0.0 / 28.9
k = 2: 22.0 / 11.2
k = 3: 19.0 / 19.7
k = 4: 48.7 / 23.2

k = 1 is memorising in its purest form: 0.0 on training, 28.9 on validation. With k = 2 the average of two neighbours smooths the noise and validation falls to 11.2. A bigger k makes it worse again: the average of far orders blurs the relationship. Here k is like the degree of the curve: it is picked with validation.

The idea

When it hurts

Validation with little data. 8 validation orders give noisy numbers. The choice can be random: between degree 2 and 3 the difference (9.35 and 9.09) is noise. The less data you have, the simpler the model you should pick.
Validation touched many times. You try 100 degrees, λ values and features and pick the best on validation. One of them is the best by chance. That is why the test stays aside, untouched.
Regularization without scale. The penalty is the same for all weights. If one feature is in kilometres and another in metres, the weight of the metres is a thousand times smaller and is barely penalised. Features are scaled first, as x is made smaller here.
A penalty that is too strong. λ = 10 gives underfitting: the model does not catch even the training data. Look at both errors: if both are high, the model is too simple.
More data is not free. Every order in the training set is a real order that has to be collected and checked. Sometimes the simpler model is the cheaper cure.

More precisely, if you are curious

The formula. The program looks for the weights for which the sum of squared errors plus λ · (w₁² + w₂² + … + w₇²) is the smallest. MSE is the same sum divided by the number of orders, so in front of MSE it is as if λ were 8 times smaller. This is L2 regularization (ridge). If the penalty is the sum of the absolute values, |w₁| + |w₂| + …, it is L1 (lasso): it makes some weights exactly 0, so it also picks features.

Why on the diagonal. The best weights are where the slope of the error is 0 for every weight. Each weight gives one equation. The slope of λ · w² is 2 · λ · w, and all the other terms of the slope also have a 2 in front. After dividing by 2 the penalty is λ · w in the equation of the same weight, that is, on the diagonal of the system.

Cross-validation. With little data: you split the training data into 5 parts, learn on 4 and measure on the fifth, five times, and take the average. Every order is validation once, and the choice does not depend on one random group.

Other cures. With gradient descent: stopping when the validation error starts to grow (early stopping). With neural networks: dropout, which switches off random neurons at every step. The idea is the same: the model must not be able to rely on memorised details.

In real code. In scikit-learn these are PolynomialFeatures, Ridge (λ is called alpha), Lasso, KNeighborsRegressor, cross_val_score and GridSearchCV, which tries the values and picks with cross-validation. In ML.NET regularization is a parameter of the trainers (L2Regularization). Gaussian elimination is replaced there by more stable methods, because at a high degree the system is sensitive to rounding.

double[][] is an array of arrays: train[i][0] is the kilometres of order i, and train[i][1] the minutes.

Exercise

Pick k

Solve this in your editor.

Finish the k-NN program: pick k with validation (the smallest validation error), then run the test only for the chosen k.

MSE: training / validation
k = 1: 0.0 / 28.9
k = 2: 22.0 / 11.2
k = 3: 19.0 / 19.7
k = 4: 48.7 / 23.2
chosen k: 2, test: 16.9

Validation picks k = 2, and the test error is 16.9. Compare with the line: 5.57. For this almost straight relationship the line beats the neighbours too.

More tasks

The degrees with more data. Learn degrees 1 to 7 on 16 orders (training and validation) and print the training and the test error. From which degree on does the test error start to grow?
A grid of λ. Try λ from 0.02 to 0.5 in steps of 0.02 for degree 7. Which λ does validation pick, and what is its test error?

Test

Check yourself

1. A model has error 0 on the training data and a big error on new data. What is this called?Overfitting: the model has memorised the training dataUnderfitting: the model is too simpleData leakage

2. Why is the degree picked with validation and not with the test?The choice learns from the data it chooses by. The test has to stay untouched to be honest at the endValidation is bigger than the testThere is no difference, the two are the same

3. What does regularization do?It changes the degree of the curve to 1It removes half of the training pointsIt adds a penalty for big weights to the error, so the curve cannot twist to hit every point

4. k-NN with k = 1 has error 0 on the training data. Why is that not good news?Because an error of 0 is impossibleBecause k = 1 is too slowEvery training point is its own nearest neighbour, so the model just returns the remembered time

5. Which one does NOT cure overfitting?A stronger penalty λMore dataA higher degree of the curve

Overfitting: the model that memorises

Cookies