Problem 576613 · medium · Level 05 Advanced Algorithms & Graphs

Four Folds Choose the Degree

k-fold cross-validation · hyperparameter · model selection · polynomial regression · seeded shuffle

The degree of a polynomial is not learned by the fitting; it has to be chosen. Choose it by cross-validation.

Write cv_degree(xs, ys, degrees, k, seed) that returns a tuple (scores, best, weights):

  1. Folds. Make the list idx = list(range(len(xs))) and shuffle it once with random.Random(seed).shuffle(idx). Fold i (for i from 0 to k - 1) is idx[i::k]. Use the same folds for every degree.
  2. Scores. For each degree d in degrees, for each fold in turn, fit a polynomial of degree d to the points outside the fold and compute its mean squared error on the points inside it. scores lists the average of the k fold errors for each degree, in the order of degrees.
  3. Choice. best is the degree with the smallest score; among equal scores, the smaller degree.
  4. Final model. weights is the polynomial of degree best fitted to all the points.

The setup provides fit_poly(xs, ys, degree), which returns the least-squares weights [w0, ..., w_degree], poly_mse(w, xs, ys), which returns the mean squared error of those weights on some points, and make_wave(n, seed), which returns n noisy observations of sin(3x). Use them.

Examples

Input:  xs, ys = the 24 points make_wave(12, 3) and make_wave(12, 5) joined together
        degrees = [0, 1, ..., 9], k = 4, seed = 0
Output: scores ≈ [0.5967, 0.1963, 0.1931, 0.0634, 0.0691, 0.0838, 0.0789, 0.0828, 0.2444, 0.3458]
        best = 3, weights = fit_poly(xs, ys, 3)

Input:  xs = [0, 1, 2, 3], ys = [0, 1, 2, 3], degrees = [0, 1], k = 2, seed = 0
Output: ([1.25, 0.0], 1, [0.0, 1.0])     (the weights up to rounding)
Explanation: the shuffle gives idx = [2, 0, 1, 3], so the folds are [2, 1] and [0, 3].

Constraints

  • 2 <= k <= len(xs) <= 300, each training part has more distinct x values than the largest degree
  • 1 <= len(degrees) <= 10, 0 <= degree <= 9, degrees are distinct and may come in any order
  • floats are compared with a tolerance of 1e-6

Goals

  • Cut shuffled data into folds by a stated rule and keep the same folds for every candidate
  • Score each polynomial degree by its average validation error over the folds
  • Choose the degree by that score and refit the chosen model on all the data
Starting Python…