Problem 294147 · medium · Level 02 Linear Data Structures

Memorise or Generalise?

generalisation · training error · test error · nearest neighbour · threshold rule · learning curve

A greengrocer sorts produce by a single sweetness score: label 1 for fruit, 0 for vegetable. Two learners compete:

  • nearest: predict the label of the training item with the closest score (the smallest abs(x - q); on a tie, the smallest training index). A training item is predicted like any other score, so its own entry takes part;
  • cutoff: the threshold rule "above t predicts above, otherwise 1 - above" with the fewest training mistakes, where t ranges over the midpoints of neighbouring distinct training scores; ties go to the smallest t, then to above = 1. A training set whose scores are all equal offers no threshold; the tests never use one.

Write learning_curve(xs, ys, test_xs, test_ys, sizes). For each s in sizes, train both learners on the first s training items and measure their error rates (the fraction of wrong predictions) on those s items and on the whole test set. Return a list with one tuple (s, nearest_train, nearest_test, cutoff_train, cutoff_test) per size.

The tests use sweetness_sample(n, seed), which returns (xs, ys); it is available in your code.

Examples

Input:  xs = [1, 2, 3, 4, 5, 6, 7, 8], ys = [0, 0, 0, 1, 0, 1, 1, 1]
        test_xs = [4.2, 4.8, 5.3, 3.9, 2.5, 6.5], test_ys = [0, 1, 1, 0, 0, 1], sizes = [4, 8]
Output: [(4, 0.0, 0.3333333333333333, 0.0, 0.3333333333333333),
         (8, 0.0, 0.6666666666666666, 0.125, 0.3333333333333333)]
Explanation: with all 8 items, nearest copies the unusual items at 4 and 5 and gets the
four test items near them wrong. The best cutoff, "above 3.5 predicts 1", makes one
training mistake (the item at 5) and two test mistakes.

Input:  xs = [3.0, 3.0, 6.0], ys = [0, 1, 1], test_xs = [2.0, 7.0], test_ys = [0, 1], sizes = [3]
Output: [(3, 0.3333333333333333, 0.0, 0.3333333333333333, 0.0)]
Explanation: the second item's nearest training item is the first one (same score, smaller index).

Constraints

  • 2 <= s <= len(xs) <= 400 for every s in sizes; 1 <= len(test_xs) <= 600; at most 6 sizes
  • scores have at most two decimals; labels are 0 or 1

Goals

  • Measure training and test error of two learners as the training set grows
  • See that the nearest-neighbour rule has (almost) no training error but a larger test error
  • See that a simple threshold rule's training error is an honest guide to its test error
Starting Python…