Problem 554589 · hard · Level 05 Advanced Algorithms & Graphs

How Bendy Should the Curve Be?

model selection · overfitting · cross-validation · polynomial regression · ridge regression · hidden test set

A soil survey walks a 10 km path and takes moisture readings at a few random positions. Moisture changes smoothly along the path, but every path has its own profile (some gently rolling, some with several hills and hollows) and every probe its own amount of noise. The survey wants a model that predicts the moisture anywhere on the path.

Write predict(xs, ys, new_xs): xs[i] is a position in km (between 0 and 10) and ys[i] the reading there. Return a list with one predicted reading (a number) for every position in new_xs.

The tests call judge_transect(predict, n, seed). It trains your function on transect(n, seed), which returns (xs, ys) with n readings, and gives it the positions of 1000 hidden readings from the same path, keeping the readings to itself. transect(n, seed) is available in your code for experiments, and so are fit_poly(xs, ys, degree, lam=0.0) (least-squares polynomial weights, with an optional ridge penalty that leaves the intercept alone) and poly_value(w, x). Positions far from 0 raised to high powers make the fitting inaccurate, so rescale them before fitting polynomials of high degree.

How this problem is scored

A model passes a test when its mean squared error on the hidden readings is lower than that of the least-squares straight line through the training readings. Its quality (0 to 100) is 100 · log(base / mse) / log(base / best), where base is the line's error and best the error of the true profile that generated the readings (it still has an error: the noise). The errors are shown next to every test. Match the reference solution's quality (the par in the header) for the third star.

Examples

Input:  transect(3, 1)
Output: ([9.05, 9.56, 7.03], [-4.75, -3.95, 0.92])

Input:  judge_transect(predict, 20, 1)
Output: a summary such as {"mse": 1.7859, "total": 1000}
        this one passes: the straight line has an error of about 4.56

Constraints

  • 20 <= len(xs) <= 150, len(new_xs) = 1000
  • each test must finish in well under a second in your browser: a few hundred polynomial fits are fine
  • your predictions must not depend on the clock; if you use randomness, use a random.Random with a fixed seed

Goals

  • Choose the flexibility of a regression model separately for every data set
  • Use cross-validation on the training data, since the hidden data cannot be seen
  • Beat the straight line on hidden data and approach the true profile's error
Starting Python…