Problem 560060 · hard · Level 05 Advanced Algorithms & Graphs

A Thousand Imaginary Days

bias-variance trade-off · k-nearest neighbours regression · simulation · Monte Carlo · reusing work · prefix sums

A weather station records the temperature once at each of the times xs. The true temperature follows a known curve truth(x), but every reading has independent noise with standard deviation sigma. The station predicts the temperature at a time g as the average reading of the k recorded times nearest to g (by abs(x - g); among equal distances, the smaller index into xs first).

How good is that rule for each k? Imagine many different days. Write knn_bias_variance(xs, truth, sigma, ks, grid, runs, seed) that simulates them:

  • Make one rng = random.Random(seed). For each of the runs days, draw that day's readings ys = [truth(x) + rng.gauss(0, sigma) for x in xs] (one draw per time, in the order of xs). The same days are used for every k.
  • For each k and each point g of grid, collect the day's prediction at g.
  • At each g, the bias² is (mean prediction - truth(g))² and the variance is the mean of (prediction - mean prediction)² over the days (divide by runs).

Return a list with one tuple (k, bias2, variance) per value of ks, in that order, where bias2 and variance are averaged over the points of grid.

Examples

Input:  xs = [0, 1, 2], truth = lambda x: x, sigma = 0.0, ks = [1, 3], grid = [0, 1], runs = 5, seed = 0
Output: [(1, 0.0, 0.0), (3, 0.5, 0.0)]
Explanation: without noise every day is the same, so the variance is 0. With k = 3 the
prediction is 1 everywhere: wrong by 1 at g = 0 and right at g = 1.

Input:  xs = list(range(24)), truth = lambda h: 12 + 8 * math.sin(math.pi * (h - 9) / 12), sigma = 2.0,
        ks = [1, 3, 5, 9, 15], grid = [0.5, 2.5, ..., 22.5], runs = 300, seed = 1
Output: [(1, 0.4897, 3.8893), (3, 0.5284, 1.3378), (5, 1.3002, 0.7744),
         (9, 5.0176, 0.4245), (15, 16.6395, 0.2383)]        (rounded here)

Constraints

  • 1 <= len(xs) <= 200, 1 <= k <= len(xs) for every k in ks, 1 <= len(ks) <= 10
  • 1 <= len(grid) <= 40, 1 <= runs <= 1000
  • the largest tests have 200 times, 40 grid points, 7 values of k and 1000 days: re-sorting the times for every day and every k is far too slow
  • floats are compared with a tolerance of 1e-6

Goals

  • Measure bias² and variance of a learning procedure by retraining it on many simulated data sets
  • See the trade-off: few neighbours give low bias and high variance, many neighbours the reverse
  • Reuse the neighbour order and running sums so that all values of k cost little more than one
Starting Python…