Level 2 · Machine Learning Fundamentals: Learning from Examples

In Level 1 you turned things into vectors and measured how close they are. This level asks the question the whole path is named after: can a program learn a useful rule from examples, instead of being told the rule? You will give a program a table of examples with the right answers attached, let it build a predictor, and then test that predictor honestly on examples it has never seen.

Two very different learners appear here. The nearest-neighbour rule keeps every example and answers a new question by copying the answer of the most similar example. A threshold rule keeps almost nothing: it searches for a single cut-off, such as "sweetness above 5 means fruit", that makes the fewest mistakes. Comparing them teaches the most important idea in machine learning, generalisation: doing well on the examples you trained on is easy, and what matters is doing well on new ones.

You will also meet the first loss function, the squared error, which scores how wrong a numerical prediction is. The fact that the mean minimises the squared error links this level to Statistics level 1, and choosing the rule with the smallest loss is the seed of the idea that runs through Levels 4 to 6: learning is an optimisation problem over data.

Features and labels

A machine learning dataset for supervised learning has two parts. Each example has a feature vector, the inputs you can measure, and a label, the answer you want to predict. By convention the feature vectors are collected in a list called X (a list of rows, exactly the dataset of Level 1) and the labels in a list y, so y[i] is the answer for X[i].

Here is a tiny dataset of produce, each rated for sweetness and crunchiness on a scale from 0 to 10, and labelled as fruit or vegetable:

X = [[8, 3], [7, 5], [9, 2], [6, 4],     # sweetness, crunchiness
     [2, 8], [3, 6], [1, 9], [4, 7]]
y = ["fruit", "fruit", "fruit", "fruit",
     "veg", "veg", "veg", "veg"]
for features, label in zip(X, y):
    print(features, "->", label)

[8, 3] -> fruit
[7, 5] -> fruit
[9, 2] -> fruit
[6, 4] -> fruit
[2, 8] -> veg
[3, 6] -> veg
[1, 9] -> veg
[4, 7] -> veg

Two features means every example is a point on a plane, and a chart shows at once whether the classes sit apart. Press Run to see the fruit and the vegetables as two groups of dots:

X = [[8, 3], [7, 5], [9, 2], [6, 4], [2, 8], [3, 6], [1, 9], [4, 7]]
y = ["fruit"] * 4 + ["veg"] * 4
for label in ("fruit", "veg"):
    pts = [x for x, lab in zip(X, y) if lab == label]
    plot([p[0] for p in pts], [p[1] for p in pts], kind="scatter", label=label,
         xlabel="sweetness", ylabel="crunchiness")

A model is a function from a feature vector to a prediction. Learning means building that function from X and y. The simplest possible "model" ignores the features entirely and always predicts the same thing, and it is worth writing because every real model must beat it:

def always_fruit(features):
    return "fruit"

print([always_fruit(x) for x in X])

['fruit', 'fruit', 'fruit', 'fruit', 'fruit', 'fruit', 'fruit', 'fruit']

When the labels are categories, as here, the task is classification. When the label is a number (a price, a temperature, a delivery time), the task is regression. Both use the same X and y layout; only the kind of label and the way you score mistakes differ.

Common mistakes: letting X and y get out of step, for example by sorting or shuffling X without applying the same reordering to y; afterwards every label belongs to a different example and nothing will work. Putting the label inside the feature vector, so the model can "predict" the answer by reading it.

Practice: From Survey Records to X and y

Training and test data

A model that has seen an example can simply remember its answer, so testing a model on the examples it learned from says little about how it will do tomorrow. The standard remedy is to split the data once, before learning anything: a training set that the learner may use, and a test set that is locked away and used only at the end to measure the finished model.

Real datasets are too big to type, so from here on the examples use generated data: a function that invents plausible examples with a seeded random number generator. The seed makes the data identical on every run and every device, so you can check the numbers by eye. Fruit here are sweeter and a little less crunchy than vegetables, with enough spread that the two groups overlap:

import random

def make_produce(n, seed):
    rng = random.Random(seed)
    X, y = [], []
    for _ in range(n):
        if rng.random() < 0.5:
            X.append([round(rng.gauss(6.5, 1.5), 1), round(rng.gauss(4, 1.5), 1)])
            y.append("fruit")
        else:
            X.append([round(rng.gauss(3.5, 1.5), 1), round(rng.gauss(6, 1.5), 1)])
            y.append("veg")
    return X, y

X, y = make_produce(80, seed=4)
print(X[:3], y[:3])
print(y.count("fruit"), "fruit,", y.count("veg"), "veg")

[[7.7, 4.9], [7.9, 4.6], [4.3, 3.6]] ['fruit', 'fruit', 'veg']
41 fruit, 39 veg

To split, shuffle a list of indices (so X and y stay in step), then cut it:

def train_test_split(X, y, test_fraction, seed):
    idx = list(range(len(X)))
    random.Random(seed).shuffle(idx)
    n_test = int(len(X) * test_fraction)
    test, train = idx[:n_test], idx[n_test:]
    return ([X[i] for i in train], [y[i] for i in train],
            [X[i] for i in test], [y[i] for i in test])

X_train, y_train, X_test, y_test = train_test_split(X, y, 0.25, seed=4)
print(len(X_train), "training examples,", len(X_test), "test examples")

60 training examples, 20 test examples

Shuffling first matters because data often arrives in an order: all the fruit first, or the oldest records first. Cutting an ordered list would put all of one kind in the test set.

Common mistakes: looking at the test set while designing the model ("the test accuracy went down, let me change this") turns it into a second training set and makes the final number optimistic; Level 5 introduces a separate validation set for such decisions. Splitting without shuffling. Shuffling X and y separately, with two different random orders.

Practice: A Test Set That Stays Put, Train, Validation and Test, Keep the Rare Class in Both Sets

The nearest-neighbour prediction

Level 1 ended with a function that finds the row closest to a query. Attach labels to the rows and you have a classifier: to label a new example, find the most similar training example and copy its label. This is the nearest-neighbour rule (1-NN).

import math

def nearest_neighbour(query, X_train, y_train):
    i = min(range(len(X_train)), key=lambda i: math.dist(query, X_train[i]))
    return y_train[i]

print(nearest_neighbour([7.0, 4.0], X_train, y_train))
print(nearest_neighbour([2.5, 7.5], X_train, y_train))
print(nearest_neighbour([5.0, 5.0], X_train, y_train))   # a borderline item

fruit
veg
veg

"Training" a nearest-neighbour model means storing the training set; all the work happens at prediction time. That makes it a lazy learner, in contrast to the threshold rule below, which does its work up front and then predicts instantly. Nearest neighbour makes almost no assumptions about what the boundary between the classes looks like: wherever the training examples of one class are, the predictions follow them. That flexibility is its strength and, as the last section shows, its weakness.

To predict a whole test set, apply the function to each row:

predictions = [nearest_neighbour(q, X_train, y_train) for q in X_test]
print(predictions[:6])
print(y_test[:6])

['fruit', 'veg', 'veg', 'fruit', 'veg', 'veg']
['fruit', 'fruit', 'fruit', 'fruit', 'fruit', 'veg']

Common mistakes: searching the test set instead of the training set for neighbours (it would find the query itself and always be right). Using math.dist on features measured in very different units; with sweetness and crunchiness both on a 0-10 scale that is fine here, and Level 3 shows what to do when it is not.

Practice: Copy the Nearest Fish, Remember Only the Fish That Teach Something

Accuracy and error rate

To compare models you need a number. For classification the simplest is accuracy, the fraction of predictions that match the true labels, and its complement, the error rate. With n examples, true labels y_i and predictions \hat{y}_i,

\text{accuracy} = \frac{1}{n}\sum_{i=1}^{n} [\hat{y}_i = y_i]

where [\hat{y}_i = y_i] is 1 when the prediction is right and 0 when it is wrong. In Python a comparison is already True or False, which sum counts as 1 and 0, so the formula is one line:

def accuracy(predicted, actual):
    return sum(p == a for p, a in zip(predicted, actual)) / len(actual)

acc = accuracy(predictions, y_test)
print("1-NN test accuracy:", acc)
print("error rate:", round(1 - acc, 2))

1-NN test accuracy: 0.75
error rate: 0.25

A number means little without something to compare it with. The majority baseline predicts the most common training label for everything, the always_fruit idea from the first section, learned from data:

from collections import Counter

majority = Counter(y_train).most_common(1)[0][0]
baseline = [majority for _ in X_test]
print(majority, accuracy(baseline, y_test))

fruit 0.55

A model that cannot clearly beat the majority baseline has learned nothing useful. The baseline also exposes a trap. If 95 emails in 100 are genuine, "never spam" is 95% accurate and completely useless. Accuracy hides which mistakes a model makes; Level 3 splits them up with the confusion matrix, precision and recall.

Common mistakes: reporting accuracy on the training set as if it described new data. Comparing accuracies measured on different test sets. Forgetting that with 20 test examples each mistake moves accuracy by 5 percentage points, so a difference of one or two mistakes between models is mostly luck; Statistics level 5 has the tools to say how much.

Practice: The Bar Every Model Must Clear, Two Models, One Test Set

Threshold rules

Nearest neighbour keeps every example. At the other extreme is a rule that looks at a single feature and compares it with a single number: "if sweetness is above t, say fruit, otherwise vegetable". It is called a threshold rule (or a decision stump, because it is a decision tree with only one question; full trees arrive in Level 5).

Here is the rule with a hand-picked threshold, scored on the training data:

def threshold_rule(x, feature, t, above, below):
    return above if x[feature] > t else below

pred = [threshold_rule(x, 0, 5.0, "fruit", "veg") for x in X_train]
print(round(accuracy(pred, y_train), 3))

0.883

Picking t by hand is guessing. Learning the rule means searching for the threshold that makes the fewest training mistakes. Which thresholds are worth trying? Moving t between two neighbouring data values changes no prediction, so only one candidate per gap matters: the midpoint between consecutive sorted values. Sorting the values first (an Algorithms path staple) gives all the candidates:

def fit_threshold(X, y, feature, above, below):
    values = sorted(set(x[feature] for x in X))
    best_t, best_acc = None, -1
    for a, b in zip(values, values[1:]):
        t = round((a + b) / 2, 2)
        acc = accuracy([threshold_rule(x, feature, t, above, below) for x in X], y)
        if acc > best_acc:
            best_t, best_acc = t, acc
    return best_t, best_acc

print(fit_threshold(X_train, y_train, 0, "fruit", "veg"))   # sweetness
print(fit_threshold(X_train, y_train, 1, "veg", "fruit"))   # crunchiness: high means veg

(4.95, 0.9)
(5.3, 0.75)

The learned sweetness rule gets 90% of the training examples right; the best crunchiness rule only 75%. A full stump learner simply tries every feature and both directions and keeps the best combination:

def fit_stump(X, y, labels=("fruit", "veg")):
    best = None
    for feature in range(len(X[0])):
        for above, below in (labels, labels[::-1]):
            t, acc = fit_threshold(X, y, feature, above, below)
            if best is None or acc > best[0]:
                best = (acc, feature, t, above, below)
    return best

acc, feature, t, above, below = fit_stump(X_train, y_train)
print(f"feature {feature}, threshold {t}: above -> {above}, below -> {below} (train accuracy {acc})")

feature 0, threshold 4.95: above -> fruit, below -> veg (train accuracy 0.9)

Look at what just happened, because it is the pattern of all of machine learning. There was a family of possible rules (every feature, every threshold, every direction), a way to score a rule on the training data (accuracy), and a search for the best-scoring member of the family. Here the family is small enough to try exhaustively. In Level 4 the family becomes "every possible set of weights", far too many to try, and the search becomes gradient descent; the pattern stays the same.

With n training examples this search tries about n thresholds per feature and scores each with a pass over the data, so it costs about n² steps per feature. Sorting the examples once and updating the count of mistakes as t slides past each value brings that down to n log n, the same trick as the sweep lines of the Algorithms path.

Common mistakes: trying only thresholds that equal a data value, then being unsure which side the value itself falls on; midpoints avoid the question. Only trying one direction ("above means fruit") when the feature might work the other way round. Forgetting the tie rule: acc > best_acc keeps the first best threshold, >= keeps the last, and they can give different models.

Practice: The Temperature Where the Dough Rises, The One Sensor That Predicts Failure

Squared error as a loss

For regression, "right or wrong" is too crude: predicting 21 minutes for a delivery that took 20 is nearly right, predicting 40 is badly wrong. A loss function puts a number on how wrong a prediction is, and the loss of a model on a dataset is the average over all examples. The standard choice is the squared error, and its average is the mean squared error (MSE). Next to it is the mean absolute error (MAE):

\text{MSE} = \frac{1}{n}\sum_{i=1}^{n} (\hat{y}_i - y_i)^2, \qquad \text{MAE} = \frac{1}{n}\sum_{i=1}^{n} |\hat{y}_i - y_i|

Each sum becomes a sum(... for p, a in zip(predicted, actual)), with p playing \hat{y}_i and a playing y_i:

def mse(predicted, actual):
    return sum((p - a) ** 2 for p, a in zip(predicted, actual)) / len(actual)

def mae(predicted, actual):
    return sum(abs(p - a) for p, a in zip(predicted, actual)) / len(actual)

km      = [1, 2, 3, 4, 5, 6]
minutes = [9, 11, 15, 16, 21, 24]
rule = [6 + 3 * d for d in km]              # a guessed rule: 6 minutes plus 3 per km
print(rule)
print(round(mse(rule, minutes), 3), round(mae(rule, minutes), 3))

[9, 12, 15, 18, 21, 24]
0.833 0.5

The guessed rule is off by 1 on one delivery and by 2 on another, so its MSE is (1 + 4) / 6. The mean absolute error (MAE), the average size of the errors, is easier to read (it is in minutes), but the squared error has two properties that make it the default. It punishes large errors much more than small ones: one error of 10 costs as much as a hundred errors of 1. And it is a smooth function of the prediction, which is what gradient descent needs in Level 4.

Loss functions let you choose between predictors by calculation instead of by eye. Take the simplest family, a constant prediction c for every delivery. Which c is best? Try a range:

for c in range(13, 20):
    print(c, round(mse([c] * len(minutes), minutes), 2))
print("mean:", sum(minutes) / len(minutes))

The best constant is 16, which is exactly the mean of the minutes. That is not a coincidence: the mean is the constant that minimises the squared error, for any list of numbers. (Expand \sum_{i}(c - y_i)^2 and it is a parabola in c whose lowest point is at the mean.) The median plays the same role for absolute error. This is the Statistics path's mean and median seen from a new side: each is the answer to an optimisation problem, "which single number is least wrong?", with a different definition of wrong.

The parabola is easy to see on a chart. Press Run to draw the MSE of every constant from 10 to 22 minutes:

minutes = [9, 11, 15, 16, 21, 24]
cs = [c / 2 for c in range(20, 45)]
plot(cs, [sum((c - y) ** 2 for y in minutes) / len(minutes) for c in cs],
     xlabel="constant prediction c", ylabel="MSE", title="Loss of a constant prediction")

The best constant has an MSE of about 27 minutes², while the guessed rule, which uses the distance, scores under 1. Using the features is worth it. In Level 3 you will find the best line a + b·km by formula (least squares), and in Level 4 by gradient descent, both by minimising exactly this MSE.

Common mistakes: averaging the raw errors p - a, where positive and negative errors cancel and a terrible model can score 0. Comparing MSE values across problems measured in different units (squared minutes against squared pounds). Reporting MSE when readers need a size they can picture; its square root, the root mean squared error, is back in the original units.

Practice: How Wrong Were the Arrival Times?, Which Fare Rule Fits Best?, One Number for Every Day

Generalisation

You now have two trained classifiers for the produce data: 1-NN, which stores all 60 training examples, and the stump "sweetness above 4.95 means fruit", which stores one feature index and one number. Score both on the data they learned from and on the test set:

def stump_predict(x):
    return threshold_rule(x, feature, t, above, below)

for name, model in (("1-NN", lambda x: nearest_neighbour(x, X_train, y_train)), ("stump", stump_predict)):
    train_acc = accuracy([model(x) for x in X_train], y_train)
    test_acc = accuracy([model(x) for x in X_test], y_test)
    print(f"{name:6} train {train_acc:.2f}  test {test_acc:.2f}")

1-NN   train 1.00  test 0.75
stump  train 0.90  test 0.90

Twenty test examples are few, so draw a large fresh batch from the same generator, standing in for the produce the model will meet in the future:

X_new, y_new = make_produce(2000, seed=99)
for name, model in (("1-NN", lambda x: nearest_neighbour(x, X_train, y_train)), ("stump", stump_predict)):
    print(f"{name:6} new data {accuracy([model(x) for x in X_new], y_new):.3f}")

1-NN   new data 0.830
stump  new data 0.834

Three lessons are hidden in these few numbers.

First, training accuracy is not a measure of learning. 1-NN scores a perfect 1.00 on its training set because every training example's nearest neighbour is itself. It has memorised the data, including the unusual examples: the sweet vegetable and the sour fruit that are just random variation. On new data it drops to 0.83. The stump cannot memorise anything with one number, so its training score of 0.90 is much closer to what it achieves on new data. The gap between training and new-data performance is the first thing to look at in any model.

Second, small test sets are noisy. On the 20 test examples the stump looked far better (0.90 against 0.75); on 2,000 new examples the two models are practically tied. Three lucky or unlucky test examples made the whole difference. Before believing that one model beats another, ask how many test examples the difference rests on. Level 5 shows how to make better use of limited data with cross-validation.

Third, some error cannot be removed. The two groups in make_produce overlap: some vegetables really are sweeter than some fruit. No rule based on sweetness and crunchiness can get those right, so even the best possible classifier stays below 100% here. Chasing the last few training mistakes, as 1-NN does, only fits the noise.

A model generalises when what it learned from the training data carries over to new data from the same source. That is the real goal of machine learning, and it creates a tension that runs through the rest of the path. A model that is too simple (always "fruit") misses real patterns; a model that is too flexible (1-NN) learns the noise as well. Level 3 adds a dial between the two, k in k-nearest neighbours, and Level 5 studies the tension directly as overfitting, underfitting, bias and variance.

Common mistakes: celebrating a high training score. Declaring a winner from a handful of test examples. Assuming more flexibility always helps; it helps until the model starts fitting noise, and after that it hurts.

Practice: Memorise or Generalise?, Hide One Fish at a Time, The Lowest Error These Features Allow

Practice

These problems are required on this path at this level; the path adds one problem from each of the level's topics, picked for you and kept.

Checklist

Arrange a supervised dataset as a feature list X and a label list y, and tell classification from regression.
Generate a reproducible dataset with random.Random(seed), and split it into training and test sets by shuffling indices.
Implement the nearest-neighbour classifier and predict a whole test set.
Compute accuracy and error rate, and compare a model with the majority baseline.
Learn a threshold rule by trying the midpoints between sorted feature values, over every feature and both directions.
Describe learning as a search over a family of rules for the one with the best training score.
Compute mean squared error and mean absolute error, and explain why the mean is the best constant under squared error.
Explain why 1-NN has perfect training accuracy, why that says nothing about new data, and why a 20-example test set can mislead.