Problem 200011 · medium · Level 02 Linear Data Structures

The Lowest Error These Features Allow

irreducible error · lookup table · majority baseline · generalisation · grouping

A commuter logs every trip: the day, the weather and the hour she left (X[i] = [day, weather, leave]), and whether she arrived "late" or "on time" (y[i]). The same combination of features does not always give the same result: on some rainy Mondays at 8 the trains ran, on others they did not.

The most a model can do with these features is to predict one label per combination (every trip with the same [day, weather, leave] gets the same prediction). Write lookup_report(X_train, y_train, X_test, y_test) that returns a tuple (floor, lookup_test, majority_test, unseen):

  • floor: the smallest training error rate any rule that predicts from these features can achieve on the training data;
  • lookup_test: the test error rate of the lookup rule, which predicts for each combination seen in training its most common training label (on a tie, the label that occurs first among that combination's training trips), and for an unseen combination the overall majority label;
  • majority_test: the test error rate of always predicting the overall majority label of y_train (on a tie, the label that occurs first in y_train);
  • unseen: the number of test trips whose combination never occurs in the training data.

The tests use commute_log(n, seed), which returns (X, y); it is available in your code.

Examples

Input:  X_train = [["sun", 8], ["sun", 8], ["rain", 8], ["sun", 9], ["rain", 8], ["sun", 8]]
        y_train = ["ok", "late", "late", "ok", "late", "ok"]
        X_test  = [["sun", 8], ["rain", 9], ["rain", 8]], y_test = ["late", "ok", "late"]
Output: (0.16666666666666666, 0.3333333333333333, 0.6666666666666666, 1)
Explanation: ["sun", 8] was "ok" twice and "late" once, so every rule is wrong on at least one
of those three training trips; the other combinations are consistent: floor = 1 / 6.
The overall majority is a 3-3 tie, won by "ok", which occurs first. ["rain", 9] is unseen.

Constraints

  • 1 <= len(X_train), len(X_test) <= 10**4; all rows have the same length (1 to 5)
  • features are strings or whole numbers

Goals

  • Compute the smallest training error any rule of the given features can reach
  • Build a classifier that memorises the most common label of every feature combination
  • Compare it on test data with the majority baseline, and count test cases it has never seen
Starting Python…