Problem 549386 · medium · Level 05 Advanced Algorithms & Graphs

Open the Test Set Once

validation set · test set · hyperparameter · ridge regression · regularisation strength · model selection

A lab calibrates a sensor with a flexible polynomial and a ridge penalty of strength λ that keeps its weights small. The penalty strength has to be chosen, and the lab's rule is strict: the test measurements are used exactly once, at the end.

Each data set is a tuple (xs, ys). Write choose_lambda(train, val, test, degree, lams) that returns a tuple (best, val_errors, test_error):

  • for each λ in lams, fit the polynomial of the given degree with penalty λ to train and compute its mean squared error on val; val_errors lists these errors in the order of lams;
  • best is the λ with the smallest validation error; among equal errors, the larger λ (the simpler model);
  • test_error is the mean squared error on test of the polynomial with penalty best fitted to the training and validation points together (training points first).

The setup provides fit_poly(xs, ys, degree, lam) (the ridge fit; the intercept is not penalised), poly_mse(w, xs, ys) and make_wave(n, seed), which returns n noisy observations of sin(3x).

Examples

Input:  train = ([0, 1, 2, 3], [0, 1, 2, 3]), val = ([4], [4]), test = ([5], [6]),
        degree = 1, lams = [0, 1]
Output: (0, [0.0, 0.17361111111111172], 1.0)
Explanation: without a penalty the line y = x predicts the validation point exactly; with λ = 1
the slope shrinks to 0.83 and the prediction at 4 misses by 0.42. The line refitted on all five
points is again y = x, which misses the test value 6 by 1.

Input:  train = make_wave(12, 3), val = make_wave(12, 5), test = make_wave(12, 6),
        degree = 9, lams = [0, 0.0001, 0.001, 0.01, 0.1, 1, 10]
Output: best = 0.001, val_errors ≈ [168.88, 0.1137, 0.1081, 0.1174, 0.1509, 0.2869, 0.6304],
        test_error ≈ 0.0849

Constraints

  • 0 <= degree <= 9, 1 <= len(lams) <= 10, λ >= 0, the values of lams are distinct
  • 1 <= len(val), len(test); the training points have more distinct x values than degree whenever λ = 0 is tried
  • floats are compared with a tolerance of 1e-6

Goals

  • Compare settings of the regularisation strength on a validation set only
  • Retrain the chosen setting on training and validation data together
  • Report the test error once, for the chosen model
Starting Python…