Classical Models

Decision trees, SVMs, k-NN, and linear/logistic regression — and when a simple model wins. Taught from zero: what shape of rule each model draws, worked by hand before any formula.

intermediate#trees#svm#knn#regression

Start here — every model is a way of drawing a line

You already know what a model does: examples go in, a rule comes out, and the rule makes predictions on things it has never seen. This page is about the rules themselves — the handful of shapes a rule can take.

Here's the framing that makes the whole zoo click. Picture your data as dots on a page: blue dots are one class, orange dots are the other. A classifier's entire job is to paint the page — to decide, for every possible spot, which colour goes there. The border between the painted regions is called the .

The models differ only in what shape of border they are allowed to draw

Logistic regression is only allowed to draw one straight line. A decision tree may only draw staircases — cuts parallel to the axes. k-nearest-neighbours draws a wobbly blob that hugs the data. An SVM draws a straight line but insists on the one with the widest empty gap around it. That is genuinely the main difference between them. Learn the four shapes and you have learned classical machine learning.

Think of it like different tools for cutting a shape out of paper:

A ruler-and-knife gives you one straight cut (logistic regression, SVM). Scissors that only cut horizontally or vertically give you a blocky staircase (decision trees). Tracing around the objects by eye gives you a wobbly hand-drawn outline (k-NN). None of these tools is best — the right one depends entirely on the shape you are trying to cut.

How to read this page

Everything starts in plain language with a fully worked-by-hand example; the formal notation lives behind the Depth switch at the top, and opens automatically once you have finished Machine Learning. Every code cell runs right here in your browser — change the numbers and rerun.

The one you already met — a straight line for numbers

Before classifying, recall the simplest model of all. predicts a number — a price, a temperature, a score — as a weighted sum of the inputs.

Five students, hours revised versus exam score:

Linear regression — the best straight line through five points— interactive, drag & zoom

Loading chart…

No line passes through all five dots — real data never lets you. The fitted line is the one whose total squared vertical miss is as small as possible: score = 45.3 + 5.9 x hours. The slope 5.9 is the model's whole claim about the world: one more hour of revision is worth about six marks.

The two numbers 45.3 and 5.9 are the trained model. That is the pattern you will see over and over: training compresses a table of data down to a few parameters, and prediction is then arithmetic.

Try to recall

The fitted line misses every single one of the five data points. Why is that not a bug?

Hint: Think about what the extra wobble in the dots represents.

Logistic regression — a straight line that outputs a probability

Now switch from predicting a number to predicting a category: is this email spam or not? You could try to fit a straight line to labels of 0 and 1, but a line runs off to $-\infty$ and $+\infty$ , and "this email is $-3.2$ spam" is nonsense.

Score first, then squash

Do the linear part exactly as before — add up the features with weights to get a single score. A big positive score means lots of spam evidence, a big negative score means lots of not-spam evidence. Then push that score through an S-shaped squashing function that maps any number into the range 0 to 1, so it can be read as a probability. That is the whole model: a straight line, followed by a squash.

The squashing function is the , and the model is called — a confusing name, since it classifies.

Think of it like a courtroom verdict:

Each piece of evidence gets a weight: the word FREE counts strongly for guilt, a known sender counts strongly against. The judge adds up the weighted evidence into one number — that is the straight-line part. The sigmoid is the judge then converting that total into a confidence: overwhelming evidence gives near-certainty, a tie gives 50/50, and everything in between slides smoothly.

The sigmoid — how any score becomes a probability— interactive, drag & zoom

Loading chart…

Score 0 maps to exactly 0.5 — total uncertainty. By score 3 the model is 95% sure, and by score 6 it is 99.8% sure but the curve has gone almost flat, so extra evidence barely moves it. That flattening is the model refusing to become infinitely confident, and it is why logistic regression gives usable probabilities rather than bare yes/no answers.

Classifying one email by hand

Suppose training has already found the weights: exclamation marks count +0.8 each, links count +1.1 each, and the bias is -2.0 (a built-in scepticism, since most mail is not spam).

An email arrives with 3 exclamation marks and 1 link.

Weighted sum of the features: $0.8 \times 3 = 2.4$ and $1.1 \times 1 = 1.1$ , so $2.4 + 1.1 = 3.5$ .
Add the bias: $3.5 - 2.0 = 1.5$ . That is the score.
Squash it: read $1.5$ off the curve above — a bit past $1$ , so about $0.82$ .

The model says 82% likely spam. Because $0.82 > 0.5$ , the predicted label is spam. Notice step 3 changed no decision — the sigmoid is monotonic, so the label is decided the moment the score crosses zero. The squash exists to give you a calibrated confidence, not to change the verdict.

Try to recall

An email scores exactly 0. What probability does the model report, and what does that mean in words?

Hint: Look at where the dashed line crosses the curve.

Here is the whole model — training loop included — in about fifteen lines of NumPy:

Python · runs in your browser

What this does: Trains a logistic regression from scratch on eight tiny emails using gradient descent, then prints the learned weights and the probability it assigns to each email. Watch how the four ordinary emails end up near 0 and the four spammy ones near 1. Try setting steps to 20 instead of 400 and rerun — with too little training the probabilities all hover around 0.5, because the weights have not moved far from zero yet.

Logistic regression is called a linear model even though the sigmoid is a curve. Why?

k-Nearest Neighbours — do not learn anything, just look it up

Every model so far compressed the data into a few weights. The next one refuses to do that. (k-NN) has no training step at all: it memorises the dataset and, when a new point arrives, asks its closest neighbours what they are.

Judge a point by the company it keeps

To classify something new, find the $k$ training examples nearest to it and let them vote. If four of the five nearest emails were spam, call it spam. There is nothing to fit and no weights to learn — the data itself is the model. All the work happens at prediction time.

Think of it like guessing a house price from the street:

You do not need a formula to estimate a house's value. Look at the five most similar houses on the same street and average what they sold for. That is k-NN, and it is what estate agents have always done.

Ten labelled emails and one new one to classify— interactive, drag & zoom

Loading chart…

The purple cross sits awkwardly in the gap between the two groups — exactly the interesting case. Its single nearest neighbour is an ordinary email, but three of its five nearest are spam. Which answer you get depends entirely on k, and that is the whole lesson of this section.

One prediction, worked out to the last decimal

The new email sits at $(3, 3)$ . Measure the straight-line distance to all ten stored emails — for the ordinary email at $(2.5, 2.2)$ that is $\sqrt{(3-2.5)^2 + (3-2.2)^2} = \sqrt{0.25 + 0.64} = \sqrt{0.89} = 0.943$ . Doing that for all ten and sorting smallest first:

rank	distance	label
1	0.943	ordinary
2	1.414	spam
3	1.581	spam
4	1.581	spam
5	1.803	ordinary

Now vote:

k = 1 — the single closest is ordinary. Predict ordinary.
k = 3 — ordinary, spam, spam. Predict spam.
k = 5 — ordinary, spam, spam, spam, ordinary. Three to two. Predict spam.

The prediction flipped between $k=1$ and $k=3$ on identical data. Nothing about the model changed except how many voices were allowed in the room.

Python · runs in your browser

What this does: Reproduces the worked example exactly — computes the distance from the new email to all ten stored emails, sorts them, and takes the vote for k = 1, 3 and 5. Watch the prediction flip from 0 (ordinary) to 1 (spam) as k grows. Try moving the query point q to [2.5, 2.5] and rerun to see the whole answer change.

Try to recall

k-NN is sometimes called a lazy learner. What is it being lazy about, and what does that laziness cost you later?

Hint: Ask when the work happens — at training time or at prediction time.

Decision trees — a game of twenty questions

Both models so far drew one straight boundary through the whole space. A does something different: it asks a sequence of yes/no questions, and each answer narrows down where you are.

Split the data, then split the splits

Find the single question that best separates the classes — say does it contain the word FREE. Answering it divides the data into two purer groups. Then repeat the whole exercise inside each group, and inside those groups, until each final pocket is nearly all one class. That branching interrogation is the model, and reading a prediction means following the answers down to a leaf.

Think of it like a doctor triaging a patient:

No doctor multiplies your symptoms by weights. They ask one question, and the answer decides the next question. Fever? Yes. How long? Three days. Rash? No. Each answer prunes away possibilities until a diagnosis remains. A decision tree is that flowchart, learned from data instead of medical school.

To pick the best question, we need to score how mixed a group is. A group of 10 spam and 0 ordinary is perfectly pure; 5 and 5 is maximally mixed. The usual score is .

How impurity depends on the mix of a group— interactive, drag & zoom

Loading chart…

Both curves say the same thing: a group is worst at 50/50 and perfect at either extreme, with a smooth arc in between. Entropy peaks at 1 and Gini at 0.5, and entropy is slightly more sensitive near the middle — but in practice the trees they grow are almost indistinguishable, so Gini wins on being cheaper to compute.

Choosing the first question, by hand

Ten emails, five spam and five ordinary. Two candidate questions, and we must pick the better one.

Before any split. Half and half, so the impurity is $1 - 0.5^2 - 0.5^2 = 0.5$ — as mixed as it gets.

Candidate A — does it contain the word FREE?

Yes: 5 emails, 4 spam. Impurity $1 - 0.8^2 - 0.2^2 = 1 - 0.64 - 0.04 = 0.32$ .
No: 5 emails, 1 spam. Impurity $1 - 0.2^2 - 0.8^2 = 0.32$ .
Combine them weighted by group size: $\tfrac{5}{10}(0.32) + \tfrac{5}{10}(0.32) = 0.32$ .

Candidate B — was it sent on a weekday?

Yes: 6 emails, 4 spam. Impurity $1 - (4/6)^2 - (2/6)^2 = 0.444$ .
No: 4 emails, 1 spam. Impurity $1 - 0.25^2 - 0.75^2 = 0.375$ .
Weighted: $\tfrac{6}{10}(0.444) + \tfrac{4}{10}(0.375) = 0.417$ .

Compare the improvement. Candidate A cut impurity from $0.5$ to $0.32$ , a gain of $0.18$ . Candidate B managed only $0.5 - 0.417 = 0.083$ . The tree asks about FREE first — not because anyone told it that word matters, but because that question purified the groups most. Then it repeats the entire calculation inside each of the two new groups.

Python · runs in your browser

What this does: Reproduces the worked example — scores both candidate questions by the impurity they leave behind and reports which one a decision tree would choose as its first split. The word 'free' wins with a gain of 0.18 against 0.083 for the weekday question. Try flipping a couple of labels in y and rerun to see the winning question change.

Try to recall

A tree keeps splitting until every leaf holds a single training example. What has it learned, and what will happen on new data?

Hint: Think about what a leaf containing exactly one email is really storing.

Why does a decision tree need no feature scaling, while k-NN breaks without it?

Support vector machines — find the widest street

Back to straight lines, with one sharp new idea. If two classes can be separated by a line, there are infinitely many lines that separate them. Logistic regression picks one by minimising a loss over all points. A picks one by a different principle entirely.

Do not just separate them — separate them with as much room as possible

Of all the lines that split the two groups, choose the one with the widest empty corridor around it. Push the boundary as far from both classes as you can, so that new points would have to move a long way before they crossed it. Widest gap means most robust to noise.

Think of it like paving the widest possible road between two villages:

Both villages must stay entirely off the tarmac. Many roads fit — but you want the widest one, because a wide road tolerates a wandering driver. Notice which houses actually constrain you: only the few closest to the road on each side. Move a house deep inside a village and the road does not shift at all. Those constraining houses are the support vectors, and they are the only training points the finished model depends on.

Try it — drag the line and watch the margin change:

Maximal margin classifier — drag the line and watch the margin— GeoGebra, drag & exploreOpen on GeoGebra →

Loading interactive visualization…

Drag the two large circles to move and tilt the separating line. The red segments show each point's distance to it, and the dotted lines mark the margin — the distance to the closest point. Hunt for the widest possible corridor, then notice that only two or three points ever touch the dotted lines. Those are the support vectors: every other point could be deleted without moving the boundary.

The widest street between two points

Strip it to the bone. One ordinary email at $(1, 1)$ , one spam email at $(3, 3)$ , and nothing else.

Where should the boundary go? Anywhere between them separates the two, but the widest gap comes from the perpendicular bisector — dead in the middle, at right angles to the line joining them. That is $x_1 + x_2 = 4$ .
How wide is the corridor? The distance from $(1,1)$ to that line is $\frac{|1 + 1 - 4|}{\sqrt{1^2 + 1^2}} = \frac{2}{\sqrt{2}} = 1.414$ . By symmetry $(3,3)$ is the same distance away, so the full corridor is $2\sqrt{2} \approx 2.83$ wide.
Who decided this? Both points — they are the support vectors. Add fifty more ordinary emails clustered near the origin and the answer does not budge, because none of them are closer to the boundary than $(1,1)$ is.

That last point is the character of an SVM: the model is determined by its hardest examples, and utterly indifferent to the easy ones. Logistic regression, by contrast, lets every single point tug on the boundary a little.

Try to recall

You delete a training point that sat far from an SVM's boundary and retrain. What changes?

Hint: Which points were touching the dotted margin lines?

What distinguishes an SVM's objective from logistic regression's?

See all three shapes at once

Same dataset, three models, three completely different borders. This is the picture worth remembering from the entire page:

Python · runs in your browser

What this does: Trains logistic regression, k-NN and a one-question decision stump on the identical dataset and paints the region each one assigns to each class. Look at the borders: logistic regression gives a clean diagonal, k-NN gives a wobbly outline that follows the data, and the stump gives a single straight cut perpendicular to one axis. Try changing k from 5 to 1 and rerun to watch the k-NN border grow islands around individual points.

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(1)
n = 40
X = np.vstack([rng.normal([2, 2], 0.9, (n, 2)), rng.normal([4.2, 4.2], 0.9, (n, 2))])
y = np.array([0] * n + [1] * n)

gx, gy = np.meshgrid(np.linspace(0, 7, 80), np.linspace(0, 7, 80))
grid = np.c_[gx.ravel(), gy.ravel()]        # every spot on the page

# 1) logistic regression — one straight boundary, trained by gradient descent
w, b = np.zeros(2), 0.0
for _ in range(600):
    p = 1 / (1 + np.exp(-np.clip(X @ w + b, -30, 30)))
    w -= 0.3 * (X.T @ (p - y)) / len(y)
    b -= 0.3 * (p - y).mean()
logreg = (grid @ w + b > 0).astype(int)

# 2) k-nearest neighbours, k = 5 — a wobbly boundary that hugs the data
k = 5
d = np.sqrt(((grid[:, None, :] - X[None, :, :]) ** 2).sum(-1))
knn = (y[np.argsort(d, axis=1)[:, :k]].mean(axis=1) > 0.5).astype(int)

# 3) a decision stump — the single best yes/no question, found by Gini
best = (1e9, 0, 0.0)
for col in (0, 1):
    for t in np.linspace(0, 7, 71):
        imp = sum(len(s) * (1 - s.mean() ** 2 - (1 - s.mean()) ** 2)
                  for s in (y[X[:, col] <= t], y[X[:, col] > t]) if len(s))
        if imp / len(y) < best[0]:
            best = (imp / len(y), col, t)
_, col, t = best
hi = int(y[X[:, col] > t].mean() > 0.5)
stump = np.where(grid[:, col] > t, hi, 1 - hi)

fig, axes = plt.subplots(1, 3, figsize=(10, 3.4))
for ax, z, name in zip(axes, [logreg, knn, stump],
                       ["logistic regression", f"k-NN (k={k})", "decision stump"]):
    ax.contourf(gx, gy, z.reshape(gx.shape), levels=[-0.5, 0.5, 1.5],
                colors=["#cfe0f5", "#f7d9cc"])
    ax.scatter(X[:n, 0], X[:n, 1], s=14, c="#2b6cb0")
    ax.scatter(X[n:, 0], X[n:, 1], s=14, c="#d97757", marker="^")
    ax.set_title(name, fontsize=10)
    ax.set_xticks([]); ax.set_yticks([])
plt.tight_layout()

print(f"the stump's one question: is feature {col} greater than {t:.2f}?")

When a simple model wins

The honest answer to "which model should I use" is not "the newest one". Three situations where a classical model beats a neural network outright:

Tabular data. On the spreadsheet-shaped data that runs most of the world — rows of mixed numeric and categorical columns — tree ensembles remain state of the art. A careful 2022 benchmark across 45 datasets found tree-based models still outperforming deep-learning architectures on medium-sized tabular data (around 10,000 rows), even before accounting for their far shorter training time. The reasons the authors identify are structural: neural networks struggle to stay robust to uninformative features, to preserve the orientation of the data, and to learn the irregular, jagged functions tabular targets often require.

Small data. A neural network with millions of parameters and 500 training rows will memorise them. Logistic regression with five weights cannot — it has nowhere to store the noise. When data is scarce, a model's inability to be clever is protection, not a limitation.

When you must explain the decision. A tree of depth three can be printed on a card and read aloud in a meeting; logistic regression weights say plainly which features pushed the answer which way. For credit, medical, and hiring decisions this is frequently a legal requirement rather than a nicety, and a 2% accuracy gain does not buy an unexplainable model.

The practical rule

Always fit a simple model first. Logistic regression or a small tree takes two minutes and gives you a baseline that is honest about how hard the problem really is. Perhaps a third of the time it is already good enough. When it is not, you now know exactly how much a complex model has to earn — and you would be astonished how often a deep model shipped with no baseline was quietly worse than logistic regression all along.

Where classical models genuinely lose

On raw perceptual data — pixels, audio, text — they are not competitive, and no amount of tuning fixes it. The reason is that these models need features handed to them, and nobody can hand-write the features that distinguish a cat from a dog in raw pixel values. Learning the features and the classifier together is precisely what CNNs and Transformers do, and it is why they took over vision and language completely.

The cheat sheet

Model	Boundary shape	Training cost	Prediction cost	Needs scaling?	Interpretable?	Best when
Linear regression	straight (numeric output)	very low	very low	helps	yes	a genuine linear trend, few features
Logistic regression	one straight line	low	very low	yes	yes	linearly separable, calibrated probabilities wanted
k-NN	wobbly, hugs the data	none	high	essential	somewhat	few features, plenty of data, irregular boundary
Decision tree	axis-aligned staircase	low	very low	no	very	mixed feature types, rules must be readable
SVM (linear)	one straight line, widest gap	medium	low	yes	somewhat	high dimensions, clear separation, modest data
SVM (RBF kernel)	smooth and curved	high	medium	yes	no	curved boundary, under ~100k rows

Try to recall

You have 800 rows of hospital data with 12 mixed numeric and categorical columns, and the model's reasoning must be explainable to a clinician. Which family should you reach for, and which should you avoid?

Hint: Check the size of the data and the explainability requirement against the table.

Once you have a working single tree, the highest-value next step is almost always to average many of them: that is Ensembles & Boosting, and it is what actually wins on tabular problems.

Here is what all of this looks like in real scikit-learn — the same five models, one loop:

Python · needs a GPU — run on Colab

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression
from sklearn.neighbors import KNeighborsClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.svm import SVC

X, y = load_breast_cancer(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0, stratify=y)

models = {
    # scaling matters for the distance- and margin-based models, not for the tree
    "logistic regression": make_pipeline(StandardScaler(), LogisticRegression(max_iter=2000)),
    "k-NN (k=5)":          make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)),
    "decision tree":       DecisionTreeClassifier(max_depth=3, random_state=0),
    "linear SVM":          make_pipeline(StandardScaler(), SVC(kernel="linear", C=1.0)),
    "RBF SVM":             make_pipeline(StandardScaler(), SVC(kernel="rbf", C=1.0, gamma="scale")),
}

for name, model in models.items():
    cv = cross_val_score(model, X_tr, y_tr, cv=5).mean()   # honest model selection
    test = model.fit(X_tr, y_tr).score(X_te, y_te)         # touched once, at the end
    print(f"{name:22s} cv {cv:.3f}   test {test:.3f}")

Explain it yourself

Draw two clouds of dots on paper and, without any formulas, sketch the boundary each of logistic regression, k-NN and a decision tree would draw between them. Then explain aloud why an SVM would place its line differently from logistic regression. If you cannot say what makes the SVM's line special, reread the widest-street section.

Recap — the key ideas

A classifier's job is to paint the space; the models differ mainly in what shape of boundary they are allowed to draw.
Logistic regression = a weighted sum squashed by the sigmoid into a probability. Straight boundary, calibrated confidence, trained by minimising cross-entropy.
k-NN memorises everything and takes a majority vote among the $k$ nearest points. No training, expensive prediction, must have scaled features, and collapses in high dimensions.
Decision trees ask a sequence of yes/no questions, greedily choosing whichever split most reduces impurity (Gini or entropy). Axis-aligned staircases, no scaling needed, highly readable — and prone to overfitting unless depth is limited.
SVMs pick the boundary with the widest empty margin, determined only by the few support vectors. The hinge loss ignores comfortably-correct points; the kernel trick buys curved boundaries cheaply.
Simple models still win on tabular data, on small datasets, and whenever the decision must be explained. Always fit one first as a baseline.

Practice — and how to make it stick

Learn it the way that actually works

• Retrieval practice: before scrolling back, try to name all five models and the boundary shape each one draws — pulling it from memory is what builds the trace, not rereading.
• Spaced repetition: mark this topic complete to add it to your Review queue, so it resurfaces just before you would have forgotten it.
• Interleaving: mix these exercises with Machine Learning and Evaluation & Metrics problems rather than doing them in a block — the messier practice is the sturdier memory.

Start here — edit and run it, and if you get stuck or hit an error, ask Ada on the right: she can see your code and terminal output.

Practice labPython · runs in your browser · Ada can see your terminal

Your task: Find the k that generalises best. The starter runs k-NN with k = 1 and k = 15 on two overlapping blobs and prints train and test accuracy for each. First, explain to yourself why k=1 scores exactly 1.00 on training data — what is every training point's own nearest neighbour? Then do the TODO: add 3, 5 and 31 to the list of k values and find which k gives the best TEST accuracy. Finally, raise the noise from 1.1 to 2.0 and rerun — does the best k get larger or smaller, and why?

editor

terminal

Press Run (⌘/Ctrl+Enter) to execute.

Ask Ada — she can read your terminal

Then work through these:

By hand, no code: take the ten emails from the tree worked example and compute the Gini gain of a third question of your own invention. Does it beat 0.18?
From scratch: implement the decision stump loop yourself for a continuous feature — sort the values, try every midpoint between consecutive values as a threshold, and keep the best gain. That is genuinely how CART handles numeric features.
Break k-NN deliberately: take any two-feature dataset and multiply one feature by 1000. Re-run k-NN and watch accuracy collapse, then fix it with standardisation. Doing this once makes the scaling rule unforgettable.
Baseline discipline: on any tabular dataset you like, fit logistic regression and a depth-3 tree before anything else, and write both numbers down. Every later model has to beat them to justify its existence.
Feel the margin: in the GeoGebra applet above, find the maximal-margin line by hand, then drag one non-support point around and confirm the answer does not move.

Next: turn one tree into a forest with Ensembles & Boosting, then learn to measure any of these honestly in Evaluation & Metrics.