Level 3 · Machine Learning Fundamentals: Classic Models

Level 2 built two learners from scratch, the nearest-neighbour rule and the threshold rule, and showed that the real test of a model is new data. This level builds the classic models that people reached for long before deep learning, and still do: k-nearest neighbours for classification and regression, the least-squares line, and Naive Bayes. Each is short enough to write in a few lines of plain Python, and each teaches an idea that later models inherit.

Alongside the models come two practical skills. Feature scaling fixes the silent failure of every distance-based method when features are measured in different units, and it uses the mean and standard deviation from the Statistics path. The confusion matrix, precision and recall replace accuracy when the two kinds of mistake (a missed spam email, a genuine email thrown away) have different costs.

The connections to the other paths are close here. The least-squares line is the same line as in Statistics level 3, found with the same covariance-over-variance formula; here the emphasis is on using it to predict. Naive Bayes is Bayes' rule from the same Statistics level, applied to word counts. Finding the k nearest neighbours is a partial sort, the job heapq.nsmallest does in the Algorithms path.

k-nearest neighbours

The nearest-neighbour rule of Level 2 copies the label of a single example, so one mislabelled or unusual training example changes the prediction for everything around it. k-nearest neighbours (kNN) asks the k closest training examples and takes a majority vote. Write N_k(\mathbf{x}) for the set of the k training examples closest to the query \mathbf{x}. The prediction is the class c with the most votes among them:

The sum counts the neighbours with label c, which is what Counter does, and \operatorname{argmax}_c ("the c that makes this largest") is most_common(1). Here is the Level 2 produce generator again, with a training set of 60:

import math, random, heapq
from collections import Counter

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

def k_nearest(query, X, k):
    return heapq.nsmallest(k, range(len(X)), key=lambda i: math.dist(query, X[i]))

def knn_classify(query, X, y, k):
    votes = Counter(y[i] for i in k_nearest(query, X, k))
    return votes.most_common(1)[0][0]

X_train, y_train = make_produce(60, seed=2)
query = [7.0, 5.5]
near = k_nearest(query, X_train, 5)
print([(X_train[i], y_train[i]) for i in near])
print(knn_classify(query, X_train, y_train, 1), knn_classify(query, X_train, y_train, 5))

[([7.0, 5.6], 'veg'), ([6.6, 5.0], 'fruit'), ([7.7, 5.4], 'fruit'), ([7.4, 6.1], 'fruit'), ([6.8, 6.2], 'fruit')]
veg fruit

The query is sweet, so it is probably a fruit, but its single nearest neighbour happens to be an unusually sweet vegetable. With k = 5 the four fruit around it outvote that one example.

How should you choose k? It is a dial between two extremes, and the way to set it is to measure. Here each value of k is scored on 1,000 fresh examples from the same generator:

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

X_new, y_new = make_produce(1000, seed=99)
for k in (1, 3, 9, 15, 31, 59):
    pred = [knn_classify(x, X_train, y_train, k) for x in X_new]
    print(k, accuracy(pred, y_new))

1 0.84
3 0.86
9 0.869
15 0.873
31 0.862
59 0.536

With k = 1 every quirk of the training data shows up in the predictions. As k grows the votes average the quirks away and accuracy rises. But with k = 59 nearly the whole training set votes on every query, so every prediction is simply the majority class, and the model is no better than the Level 2 baseline. Small k is flexible and noisy; large k is smooth and eventually blind. Somewhere in between is best, and Level 5 shows how to find it without a supply of fresh data, using cross-validation.

With two classes, an odd k avoids tied votes; with more classes, break ties deliberately, for example in favour of the nearest neighbour's label.

Common mistakes: choosing k by looking at test-set accuracy, which leaks the test set into the design. Setting k larger than the training set. Forgetting that kNN predictions cost a pass over the whole training set each, which is slow for large data; it is the price of a model that does no work at training time.

Practice: Which Bird Is Singing?, How Many Neighbours Should Vote?

k-nearest neighbours for regression

The same idea predicts numbers. Instead of a vote, average the labels of the k nearest training examples, \hat{y} = \frac{1}{k}\sum_{i \in N_k(\mathbf{x})} y_i. Here is a generator for delivery times: the time grows by about 3 minutes per kilometre on top of 5 minutes of handling, plus random traffic delays. With a single feature the "vector" has one entry and the distance is just the absolute difference:

def make_deliveries(n, seed):
    rng = random.Random(seed)
    km = [round(rng.uniform(0.5, 8), 1) for _ in range(n)]
    minutes = [round(5 + 3 * d + rng.gauss(0, 2), 1) for d in km]
    return km, minutes

def knn_regress(query, xs, ys, k):
    near = heapq.nsmallest(k, range(len(xs)), key=lambda i: abs(query - xs[i]))
    return sum(ys[i] for i in near) / k

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

km_train, min_train = make_deliveries(30, seed=1)
km_new, min_new = make_deliveries(500, seed=2)
print(list(zip(km_train, min_train))[:4])
for k in (1, 3, 7, 15, 30):
    pred = [knn_regress(d, km_train, min_train, k) for d in km_new]
    print(k, round(mse(pred, min_new), 2))

[(1.5, 9.7), (6.9, 27.1), (6.2, 24.0), (2.4, 14.4)]
1 7.55
3 4.58
7 4.65
15 8.68
30 46.86

The pattern matches classification. One neighbour copies each training example's traffic luck; a few neighbours average it out; all 30 neighbours predict the overall mean for every delivery, the best constant of Level 2, and ignore the distance entirely. The noise in this data has standard deviation 2, so even a perfect model would have an MSE of about 2² = 4 on new data: that part of the error is irreducible.

kNN regression predicts a staircase: between training points the prediction stays flat, then jumps. It also cannot extrapolate. Ask it about a 20 km delivery and it averages the longest deliveries it has seen, around 8 km, because those are the nearest. For data that follows a trend, a model that captures the trend itself does better, and that is the least-squares line two sections down.

Common mistakes: dividing by len(ys) instead of k. Using kNN far outside the range of the training data and trusting the answer.

Practice: How Many Cones This Hour?, A Hundred Thousand Sensors on One Pipe

Feature scaling

Suppose the produce data gains a third feature, the weight in grams. Fruit and vegetables in this data weigh about the same, around 150 g give or take 40, so the new feature carries no information. It should be harmless. It is not:

def add_weight(X, seed):
    rng = random.Random(seed)
    return [x + [round(rng.gauss(150, 40))] for x in X]

X3_train, X3_new = add_weight(X_train, 5), add_weight(X_new, 6)
print(X3_train[:3])
pred = [knn_classify(x, X3_train, y_train, 9) for x in X3_new]
print("9-NN with weight in grams:", accuracy(pred, y_new))

[[4.0, 5.8, 103], [7.8, 1.9, 104], [2.8, 7.9, 177]]
9-NN with weight in grams: 0.596

Accuracy collapses from 0.87 (for 9-NN without the weight) to 0.6, not far above a coin toss. The reason is arithmetic. Sweetness and crunchiness differ between two items by a few units; weight differs by tens of grams. Squared and added inside the Euclidean distance, the weight difference swamps everything else, so the "nearest" neighbours are simply the items of similar weight, and weight says nothing about the label. The model is no longer looking at the features that matter.

Feature scaling puts every feature on a comparable scale before measuring distance. The usual method is standardisation: subtract each feature's mean \mu_j and divide by its standard deviation \sigma_j, z = (v - \mu_j) / \sigma_j, the z-score of Statistics level 2. Afterwards every feature has mean 0 and standard deviation 1, so a difference of 1 means "one typical spread" whatever the units.

def fit_standardiser(X):
    cols = list(zip(*X))                      # one tuple per feature
    means = [sum(c) / len(c) for c in cols]
    sds = [math.sqrt(sum((v - m) ** 2 for v in c) / len(c)) for c, m in zip(cols, means)]
    return means, sds

def standardise(X, means, sds):
    return [[(v - m) / s for v, m, s in zip(x, means, sds)] for x in X]

means, sds = fit_standardiser(X3_train)
print([round(m, 1) for m in means], [round(s, 1) for s in sds])
S_train = standardise(X3_train, means, sds)
S_new = standardise(X3_new, means, sds)          # the TRAINING means and sds
pred = [knn_classify(x, S_train, y_train, 9) for x in S_new]
print("9-NN standardised:", accuracy(pred, y_new))

[5.6, 4.9, 151.4] [2.2, 1.7, 41.4]
9-NN standardised: 0.865

After standardisation the useless weight feature counts no more than the others, and accuracy recovers almost all the way (0.865 against 0.869 without the weight). The small loss that remains is there because weight now adds random noise to every distance: scaling makes features comparable, it does not make useless features disappear. Choosing which features to use is a separate job.

Two details matter. First, the means and standard deviations are computed on the training set only and then applied unchanged to test and new data. Computing them on the test set leaks information about it into the model, and in real use each new example must be scaled on its own anyway. Second, zip(*X) turns a list of rows into a list of columns, the idiom for per-feature statistics. (Dividing by n - 1 instead of n, as Statistics level 2 discusses, changes every feature by the same factor and makes no difference to nearest neighbours.)

The other common method is min-max scaling, (v - min) / (max - min), which maps each training feature onto 0 to 1; a single extreme value squeezes all the others together, so standardisation is usually safer. Scaling matters for every method that uses distances (kNN, k-means in Level 5) and, as Level 4 shows, for gradient descent.

Common mistakes: scaling training and test data separately, each with its own statistics. Dividing by a standard deviation of 0 when a feature is constant (drop the feature instead). Scaling the labels by accident along with the features.

Practice: Seconds Should Not Outvote Acidity, A Scaler That Remembers Its Training Data, Name the Pressed Leaf

Fitting a line

The delivery data follows a trend: more kilometres, more minutes. A linear regression model captures the trend with two numbers, an intercept a and a slope b, and predicts \hat{y} = a + bx, with x the distance in km. Of all the lines you could draw, which is best? Level 2 gave the criterion: the one with the smallest mean squared error on the training data. That line is called the least-squares line, and unlike most models it has a formula. The slope is the covariance of x and y divided by the variance of x, and the line passes through the point of means (\bar{x}, \bar{y}):

Each sum is one generator expression over zip(xs, ys); the factor \frac{1}{n} of the covariance and the variance cancels, so the code leaves it out:

def fit_line(xs, ys):
    mx, my = sum(xs) / len(xs), sum(ys) / len(ys)
    sxy = sum((x - mx) * (y - my) for x, y in zip(xs, ys))
    sxx = sum((x - mx) ** 2 for x in xs)
    b = sxy / sxx
    a = my - b * mx
    return a, b

a, b = fit_line(km_train, min_train)
print(f"minutes ≈ {a:.2f} + {b:.2f} × km")
pred = [a + b * d for d in km_new]
print("MSE on new data:", round(mse(pred, min_new), 2))

minutes ≈ 4.39 + 3.19 × km
MSE on new data: 4.15

From 30 noisy deliveries the line recovers close to the true rule (5 minutes plus 3 per km), and its error on new data is lower than the best kNN result (4.58), close to the irreducible 4. That is what a correct assumption buys you: the line "knows" the data is straight, so it needs far fewer examples than kNN, which assumes nothing. It also extrapolates sensibly:

print("line, 20 km:", round(a + b * 20, 1))
print("7-NN, 20 km:", round(knn_regress(20, km_train, min_train, 7), 1))

line, 20 km: 68.2
7-NN, 20 km: 26.9

A chart shows the line among its data. Here is the line fitted to the six deliveries of Level 2; press Run to see the points and the line through them:

km, minutes = [1, 2, 3, 4, 5, 6], [9, 11, 15, 16, 21, 24]
mx, my = sum(km) / 6, sum(minutes) / 6
slope = sum((x - mx) * (y - my) for x, y in zip(km, minutes)) / sum((x - mx) ** 2 for x in km)
plot(km, minutes, kind="scatter", label="deliveries", xlabel="km", ylabel="minutes")
plot([0, 7], [my - slope * mx, my + slope * (7 - mx)], label="least-squares line")

The flip side is that a wrong assumption costs just as much. If delivery times levelled off for long distances, the line would keep climbing and be confidently wrong, while kNN would follow the data. Choosing a model is choosing an assumption.

The residuals are the differences between the actual and predicted values on the training data. For the least-squares line they always add up to zero (the line passes through the means), and looking at them is the quickest check that the line is a reasonable model: residuals scattered without pattern are good news, residuals that curve (negative, then positive, then negative) mean the data is not straight.

residuals = [y - (a + b * x) for x, y in zip(km_train, min_train)]
print([round(r, 1) for r in residuals[:6]])
print("sum:", round(sum(residuals), 10))

[0.5, 0.7, -0.2, 2.4, -0.3, 0.3]
sum: 0.0

This is the regression line of Statistics level 3, where the question was what the slope says about a relationship; here it is how well the line predicts. With several features the same idea gives multiple regression (the normal equations of Statistics level 6 and Level 5 here), and in Level 4 you will find this line again by gradient descent, which is how models without a formula are trained.

Common mistakes: swapping x and y (regressing km on minutes gives a different line). Dividing by zero when every x is the same. Judging the line only by its training error: the numbers that matter are on new data.

Practice: Minutes per Kilometre, Is the Line Better Than a Guess?, Predict Each Delivery Before It Happens

The confusion matrix

Accuracy counts mistakes without saying which kind they are. For a spam filter, letting one spam email through is a small annoyance; sending a job offer to the spam folder is a disaster. The confusion matrix counts every combination of actual and predicted label. Here are twelve emails and a filter's decisions:

actual    = ["spam", "ham", "ham", "spam", "ham", "ham", "spam", "ham", "ham", "ham", "spam", "ham"]
predicted = ["spam", "ham", "spam", "ham", "ham", "ham", "spam", "ham", "ham", "ham", "ham", "ham"]

def confusion_matrix(actual, predicted, labels):
    counts = Counter(zip(actual, predicted))
    return [[counts[(a, p)] for p in labels] for a in labels]

labels = ["spam", "ham"]
m = confusion_matrix(actual, predicted, labels)
print("actual \\ predicted", labels)
for label, row in zip(labels, m):
    print(f"{label:>18}", row)
print("accuracy:", accuracy(predicted, actual))

actual \ predicted ['spam', 'ham']
              spam [2, 2]
               ham [1, 7]
accuracy: 0.75

Each row is an actual class and each column a predicted class, so the diagonal holds the correct predictions and everything off the diagonal is a mistake of a particular kind. In a two-class problem one class is called positive (the thing you are looking for, here spam) and the four cells get names:

• true positives (TP): spam caught, 2;
• false negatives (FN): spam missed, 2;
• false positives (FP): genuine email wrongly flagged, 1;
• true negatives (TN): genuine email let through, 7.

The same layout works for any number of classes and shows which pairs of classes the model confuses. False positives and false negatives are the type I and type II errors of Statistics level 5.

Common mistakes: reading the matrix the wrong way round; always label which axis is actual and which is predicted. Leaving a label out of labels, so its counts silently disappear.

Practice: Which Diseases Get Mixed Up?

Precision and recall

Two ratios summarise the positive class:

• precision = \frac{TP}{TP + FP}: of the emails flagged as spam, how many really were? Low precision means genuine mail in the spam folder.
• recall = \frac{TP}{TP + FN}: of the real spam, how much was caught? Low recall means spam in the inbox.

def precision_recall(actual, predicted, positive):
    tp = sum(a == positive and p == positive for a, p in zip(actual, predicted))
    fp = sum(a != positive and p == positive for a, p in zip(actual, predicted))
    fn = sum(a == positive and p != positive for a, p in zip(actual, predicted))
    precision = tp / (tp + fp) if tp + fp else 0.0
    recall = tp / (tp + fn) if tp + fn else 0.0
    return precision, recall

p, r = precision_recall(actual, predicted, "spam")
print(round(p, 3), r)
print("F1:", round(2 * p * r / (p + r), 3))

0.667 0.5
F1: 0.571

The filter is 75% accurate, but it catches only half the spam. The F1 score combines the two ratios into one number, their harmonic mean F_1 = \frac{2PR}{P + R} for precision P and recall R, which is low if either is low; use it when you need a single score, and report precision and recall separately when you can.

Most classifiers produce a score, such as "probability of spam", and a threshold turns it into a decision. Moving the threshold trades precision against recall: a strict filter flags only the most obvious spam (high precision, low recall), a lenient one flags anything suspicious (high recall, low precision).

scores = [0.95, 0.9, 0.8, 0.7, 0.65, 0.55, 0.4, 0.3, 0.2, 0.1]
truth  = ["spam", "spam", "ham", "spam", "spam", "ham", "spam", "ham", "ham", "ham"]
for threshold in (0.85, 0.6, 0.35):
    decided = ["spam" if s >= threshold else "ham" for s in scores]
    p, r = precision_recall(truth, decided, "spam")
    print(threshold, round(p, 2), round(r, 2))

0.85 1.0 0.4
0.6 0.8 0.8
0.35 0.71 1.0

Which point is right depends on the costs, and that is a decision about the problem, not about the model. A spam filter wants high precision; a screening test for a serious illness wants high recall, and accepts that some healthy people are sent for a second test.

Common mistakes: quoting precision without recall (flagging only the single most obvious email gives precision 1.0). Dividing by zero when nothing is predicted positive. Computing the ratios for the wrong class as positive; with imbalanced data, always make the rare class the positive one.

Practice: Did the Camera Really See a Hedgehog?, A Report Card for Every Disease, Catch Nineteen in Twenty

Naive Bayes

The last classic model reasons with probabilities instead of distances. It is the standard first model for text, so here is a tiny training set of messages:

train = [
    ("win cash now", "spam"), ("free prize win", "spam"),
    ("claim your cash prize now", "spam"), ("free cash offer", "spam"),
    ("lunch at noon", "ham"), ("meeting moved to noon", "ham"),
    ("can you send the notes", "ham"), ("notes from the meeting", "ham"),
    ("free for lunch", "ham"),
]
print(Counter(label for _, label in train))

Counter({'ham': 5, 'spam': 4})

For a new message you want P(\text{spam} \mid \text{words}), the probability that it is spam given the words in it. Bayes' rule from Statistics level 3 turns this around:

where \propto means "proportional to": the two sides differ by a factor that is the same for every class, so it does not change which class wins.

The first factor, the prior, is the share of spam in the training data. The second is the hard part: the probability of this exact combination of words, which you could never count directly. The naive assumption is that, within a class, words appear independently of each other, so P(\text{words} \mid \text{spam}) is simply the product \prod_j P(w_j \mid \text{spam}) over the words w_j of the message. That is obviously false ("cash" and "prize" go together), but the model often classifies well anyway, because it only needs to get the comparison between classes right.

Each P(w \mid c) is a count: how often the word w appears in the messages of class c, divided by the total number of words in them. One fix is essential. A word that never appeared in spam would get probability 0 and veto the whole product, so every count gets 1 added (Laplace smoothing), and the denominator grows by the size of the vocabulary V to keep the probabilities summing to 1:

where N_c is the number of words in the class's messages. Taking logarithms turns the product into a sum, \log P(c) + \sum_j \log P(w_j \mid c), and that sum is the inner for loop of log_scores:

def train_naive_bayes(examples):
    word_counts = {}                    # class -> Counter of words
    class_counts = Counter(label for _, label in examples)
    for text, label in examples:
        word_counts.setdefault(label, Counter()).update(text.split())
    vocab = {w for counts in word_counts.values() for w in counts}
    return class_counts, word_counts, vocab

def log_scores(text, model):
    class_counts, word_counts, vocab = model
    total = sum(class_counts.values())
    scores = {}
    for label in class_counts:
        counts = word_counts[label]
        n_words = sum(counts.values())
        score = math.log(class_counts[label] / total)                # log prior
        for w in text.split():
            if w in vocab:                                           # skip words never seen
                score += math.log((counts[w] + 1) / (n_words + len(vocab)))
        scores[label] = score
    return scores

model = train_naive_bayes(train)
print(len(model[2]), "words in the vocabulary")
for msg in ("free cash now", "free for the meeting", "send your prize notes"):
    s = log_scores(msg, model)
    print(msg, "->", max(s, key=s.get), {k: round(v, 2) for k, v in s.items()})

21 words in the vocabulary
free cash now -> spam {'spam': -7.89, 'ham': -10.96}
free for the meeting -> ham {'spam': -13.93, 'ham': -11.76}
send your prize notes -> spam {'spam': -13.24, 'ham': -13.55}

The scores are added logarithms rather than multiplied probabilities. A long message multiplies many small numbers, and the product quickly becomes too small for a float to hold (it underflows to 0.0, and then every class ties). Logs turn the product into a sum, and since the logarithm is increasing, the class with the largest log score is the class with the largest probability.

If you want probabilities rather than just the winner, undo the logs and divide by the total, subtracting the largest score m first so that exp never underflows. For scores s_c this is the softmax function, which reappears whenever a model turns scores into probabilities:

def probabilities(scores):
    top = max(scores.values())
    weights = {k: math.exp(v - top) for k, v in scores.items()}
    total = sum(weights.values())
    return {k: round(w / total, 3) for k, w in weights.items()}

print(probabilities(log_scores("free cash now", model)))
print(probabilities(log_scores("free for lunch", model)))

{'spam': 0.956, 'ham': 0.044}
{'spam': 0.23, 'ham': 0.77}

"free" appears in both classes, so on its own it is weak evidence; "cash" and "now" tip the first message firmly to spam, and "lunch" pulls the second to ham. Naive Bayes trains in a single counting pass, handles thousands of features cheaply and needs little data, which is why it remains a strong baseline for text. Its probabilities, however, are usually too confident, because the independence assumption counts correlated words as separate pieces of evidence.

Common mistakes: forgetting smoothing, so one unseen word makes a probability exactly zero. Multiplying raw probabilities for long messages and getting 0.0 for every class. Counting the vocabulary per class instead of over all classes. Letting capital letters or punctuation split one word into several ("Free", "free!"); normalise the text first.

Practice: How Likely Is 'Refund' in a Billing Ticket?, The Words That Give a Ticket Away, Sort the Tickets by Topic

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.

• Is the Line Better Than a Guess?
• How Likely Is 'Refund' in a Billing Ticket?
• Sort the Tickets by Topic
• Which Bird Is Singing?
• How Many Cones This Hour?
• Seconds Should Not Outvote Acidity

Checklist

• Implement k-nearest neighbours for classification (majority vote) and regression (average), using heapq.nsmallest for the k closest.
• Explain how k trades flexibility against smoothness, and what happens at k = 1 and at k equal to the training-set size.
• Show why unscaled features break distance-based models, and standardise features using statistics from the training set only.
• Fit the least-squares line with the covariance-over-variance formula, compute its residuals, and explain what it gains and risks compared with kNN.
• Build a confusion matrix and name its four cells for a two-class problem.
• Compute precision, recall and F1, and describe how moving a decision threshold trades one against the other.
• Train a Naive Bayes text classifier with Laplace smoothing and log probabilities, and turn its scores into probabilities safely.