Problem 528094 · easy · Level 05 Advanced Algorithms & Graphs

Twelve Points, Ten Curves

overfitting · underfitting · polynomial regression · mean squared error · training error · generalisation

A student fitted polynomials of rising degree to twelve noisy measurements and wants to know which one to trust. A polynomial is given by its weights w = [w0, w1, ..., wd] and predicts w0 + w1·x + w2·x² + ... + wd·x^d; its degree is len(w) - 1 (trailing zero weights still count).

Write error_table(curves, x_train, y_train, x_new, y_new) that returns a tuple (rows, best):

  • rows has one tuple (degree, train_mse, new_mse) per curve, in the order of curves, where train_mse is the mean squared error of the curve on the points (x_train[i], y_train[i]) and new_mse the same on (x_new[i], y_new[i]);
  • best is the degree of the curve with the smallest new_mse; among curves with equal new_mse, the smaller degree.

The setup provides make_wave(n, seed), which returns (xs, ys): n noisy observations of sin(3x) for x between -1 and 1, and fit_poly(xs, ys, degree), which returns the least-squares weights of a polynomial of that degree. The tests build their curves with them, for example [fit_poly(*make_wave(12, 3), d) for d in range(10)].

Examples

Input:  curves = [[2.5], [1.0, 2.0], [1.0, 0.0, 1.0]]
        x_train = [0, 1, 2], y_train = [1, 2, 5], x_new = [3, -1], y_new = [10, 2]
Output: ([(0, 2.9166666666666665, 28.25), (1, 0.3333333333333333, 9.0), (2, 0.0, 0.0)], 2)
Explanation: the parabola 1 + x² passes through all five points. The line 1 + 2x misses
(2, 5) by 1 on training (mean 1/3) and misses the new points by 3 each (mean 9).

Constraints

  • 1 <= len(curves) <= 12, 1 <= len(x_train), len(x_new) <= 1000
  • floats are compared with a tolerance of 1e-6

Goals

  • Evaluate polynomial models on the data they were fitted to and on new data
  • See that training error keeps falling with the degree while error on new data does not
  • Choose a model by its error on new data, with a clear tie rule
Starting Python…