From rules to examples
An agronomist in Malawi wants to predict maize yield from rainfall and fertiliser. She could try to write the rule by hand — so much yield per millimetre of rain, so much per kilogram of nitrogen — but the true relationship is unknown, noisy, and different on every farm. What she does have is records: hundreds of fields, each with its rainfall, its fertiliser and the harvest that resulted.
Machine learning turns that around. Instead of writing the rule, we choose a family of possible rules and let the data pick the member that fits best. The same idea recognises handwriting, filters spam, translates languages and — scaled up enormously — powers the language models in the final level of this course. This lesson builds the foundations from scratch in numpy: what a model is, how its mistakes are measured, and how gradient descent improves it. The next lessons, Neural networks and Training in practice, build directly on it.
You will need vectors and matrices (Linear algebra) and partial derivatives (Multivariable calculus); a little probability helps with the losses.
Supervised learning
Definition— Supervised learning
We are given a training set of examples . Each is a vector of features describing the example; is its label, the answer we want to predict. We assume the examples are drawn independently from some unknown distribution. The goal is a function such that for new examples from the same distribution.
When the label is a number (yield, price, temperature) the task is regression; when it is a category (spam or not, which digit, germinated or not) it is classification. Features are whatever we can measure and encode as numbers: rainfall in millimetres, the presence of a word, the pixels of an image. Choosing and encoding features well used to be most of the work; deep learning automates much of it, as the next lesson shows.
A model is a family of functions indexed by parameters . A linear model with features has parameters, a weight per feature plus an intercept:
Appending a constant feature to every example lets us write this as , and for all examples at once as , where the design matrix has one row per example. Settings we choose before learning — the learning rate, the degree of a polynomial — are hyperparameters, to distinguish them from the parameters learned from data.
Finally, a loss function measures how bad a prediction is when the truth is . Learning means choosing to minimise the average loss on the training set, the empirical risk:
But the training set is a means, not the end. What we care about is the expected loss on new data, the generalisation error. A model can drive its training loss to zero and still predict new examples badly; most of the craft of machine learning is about that gap.
Measuring mistakes: squared error and cross-entropy
For regression, the standard choice is squared error, , whose average is the mean squared error (MSE). Squaring makes all errors positive, punishes large errors much more than small ones, and gives a smooth function whose gradient is easy to compute. There is a deeper reason too: if the labels are the true function plus Gaussian noise, minimising squared error is exactly maximum-likelihood estimation. Its weakness is the same as its strength — one wild outlier can dominate — and the absolute error is the robust alternative.
For classification with two classes, labelled , the model outputs a probability that , and the standard loss is binary cross-entropy (log loss):
If the true label is 1 the loss is : near zero when the model is confident and right, and growing without bound as , when the model is confident and wrong. It is the negative log-likelihood of the label under the model's predicted probability, which is why it is also called the log loss, and it connects to information theory: it measures, in nats, how surprised the model is by the truth.
Example— Cross-entropy by hand
A spam filter says that an email is spam. If it is spam (), the loss is . If it is not (), the loss is — about 22 times larger. A filter that said would lose either way. Cross-entropy rewards being right and confident, and punishes being wrong and confident severely.
Why not train directly on accuracy, the fraction of correct predictions? Because it is a step function of the parameters: nudging slightly almost never changes any prediction, so its gradient is zero almost everywhere and gives no direction to improve. Cross-entropy is a smooth stand-in that still rewards putting probability on the right answer. We train with a smooth loss and report accuracy (and other metrics, as Training in practice discusses).
Linear regression by gradient descent
With the linear model and squared error, the loss is
Its partial derivative with respect to one parameter follows from the chain rule: each term contributes . Collecting all into a vector:
Read it as: the residuals (how wrong each prediction is), weighted by each example's features, averaged. The gradient points in the direction of steepest increase of the loss, so gradient descent steps the other way:
where the learning rate sets the step size. The MSE of a linear model is a convex quadratic — a bowl — so with a small enough gradient descent slides to the unique bottom (if is invertible). Here it is on synthetic yield data whose true rule we know, so we can check the answer:
import numpy as np
rng = np.random.default_rng(0)
# Synthetic data: maize yield (tonnes per hectare) from seasonal rainfall (hundreds of mm)
# and nitrogen fertiliser (tens of kg per hectare). The "true" rule is known only to us.
n = 200
rain = rng.uniform(2, 9, n)
nitrogen = rng.uniform(0, 12, n)
noise = rng.normal(0, 0.4, n)
yield_t = 0.45 * rain + 0.20 * nitrogen + 0.8 + noise
X = np.column_stack([np.ones(n), rain, nitrogen]) # a column of ones gives the intercept
y = yield_t
def mse(theta):
r = X @ theta - y
return r @ r / n
def gradient(theta):
return 2 / n * X.T @ (X @ theta - y)
theta = np.zeros(3)
lr = 0.01
for step in range(20001):
if step in (0, 10, 100, 1000, 5000, 20000):
print(f"step {step:5d}: loss {mse(theta):7.4f} theta = {np.round(theta, 3)}")
theta -= lr * gradient(theta)
print("true parameters: [0.8 0.45 0.2 ]")
print(f"prediction for 600 mm of rain and 80 kg/ha of nitrogen: {np.array([1, 6, 8]) @ theta:.2f} t/ha")The loss falls fast at first and then crawls, and the intercept is the last parameter to settle. Why it crawls, and how to fix it, appears in the next section. The final loss is not zero: about 0.157, close to the noise variance we added. No model can predict noise, so this is about as good as it gets.
The normal equations
For this particular model we need not descend at all. At the minimum of a smooth convex function the gradient is zero, so
These are the normal equations. When is invertible — when no feature is a linear combination of the others — they have the unique solution . Geometrically, is the orthogonal projection of onto the column space of : the residual is perpendicular (normal) to every column, which is where the name comes from.
In practice, never form the inverse. Solve the linear system, or better, call a least-squares routine (np.linalg.lstsq), which uses an orthogonal factorisation and stays accurate when is nearly singular. The cost is about : superb for thousands of features, impossible for millions.
import numpy as np
rng = np.random.default_rng(0)
n = 200
rain = rng.uniform(2, 9, n)
nitrogen = rng.uniform(0, 12, n)
y = 0.45 * rain + 0.20 * nitrogen + 0.8 + rng.normal(0, 0.4, n)
X = np.column_stack([np.ones(n), rain, nitrogen])
# 1. The normal equations, and the numerically safer least-squares solver.
theta_ne = np.linalg.solve(X.T @ X, X.T @ y)
theta_ls, *_ = np.linalg.lstsq(X, y, rcond=None)
print("normal equations:", np.round(theta_ne, 4))
print("np.linalg.lstsq: ", np.round(theta_ls, 4))
best = np.mean((X @ theta_ls - y) ** 2)
# 2. How large may the learning rate be? For this loss, gradient descent converges
# exactly when lr < 2 / (largest eigenvalue of the Hessian 2/n X^T X).
def steps_to_converge(X, lr, limit=100000):
theta = np.zeros(X.shape[1])
for step in range(limit):
loss = np.mean((X @ theta - y) ** 2)
if not np.isfinite(loss) or loss > 1e6:
return "diverged"
if loss < best + 1e-4:
return f"converged in {step} steps"
theta -= lr * 2 / n * X.T @ (X @ theta - y)
return f"not converged after {limit} steps"
def show(values):
return ", ".join(f"{v:.2f}" for v in values)
H = 2 / n * X.T @ X
eig = np.linalg.eigvalsh(H)
print(f"\nHessian eigenvalues: {show(eig)} -> learning rate must be below {2 / eig.max():.4f}")
for lr in (0.001, 0.01, 0.02, 0.03):
print(f"raw features, lr = {lr:<6}: {steps_to_converge(X, lr)}")
# 3. Standardise each feature (mean 0, standard deviation 1): the bowl becomes round.
Z = X.copy()
Z[:, 1:] = (X[:, 1:] - X[:, 1:].mean(axis=0)) / X[:, 1:].std(axis=0)
eig_z = np.linalg.eigvalsh(2 / n * Z.T @ Z)
print(f"\nstandardised: eigenvalues {show(eig_z)}, condition number {eig_z.max() / eig_z.min():.1f}"
f" (raw: {eig.max() / eig.min():.0f})")
for lr in (0.1, 0.5, 0.9):
print(f"standardised features, lr = {lr:<4}: {steps_to_converge(Z, lr)}")The block shows three things. The two direct methods agree with each other and with gradient descent. Gradient descent on the raw features has a hard speed limit: for this loss it converges only if is below , the largest eigenvalue of the Hessian , while its progress along the flattest direction is governed by the smallest eigenvalue. Their ratio, the condition number, is about a thousand here: the bowl is a long, narrow valley, and gradient descent zig-zags down it. Standardising the features (subtracting each one's mean and dividing by its standard deviation) makes the bowl nearly round, and the same method converges in a few dozen steps. Feature scaling is one of the cheapest speed-ups in machine learning.
So why ever use gradient descent? Because most models are not linear regression. Neural networks, logistic regression and almost everything else have no closed-form solution, and gradient descent — in the stochastic, mini-batch form of Training in practice — scales to billions of parameters and examples where matrix factorisation cannot.
Logistic regression
For classification we need outputs between 0 and 1. Logistic regression passes the linear score through the sigmoid (logistic) function:
The sigmoid squashes any real score into ; a score of 0 means , so the decision boundary — where we switch from predicting 0 to predicting 1 — is the hyperplane . Logistic regression is a linear classifier with calibrated-looking probabilities on top.
We train it by minimising the average cross-entropy. Using , the chain rule collapses beautifully:
It has the same shape as linear regression's gradient: prediction minus truth, weighted by features. There is no closed form this time, but the loss is convex, so gradient descent finds the global minimum.
import numpy as np
rng = np.random.default_rng(1)
# Two measurements of each seed in a sample (standardised length and width) and whether
# it germinated (1) or not (0). The true rule is known only to the simulation.
n = 300
X_raw = rng.normal(0, 1, (n, 2))
true_w, true_b = np.array([2.0, -1.0]), 0.5
p_true = 1 / (1 + np.exp(-(X_raw @ true_w + true_b)))
y = (rng.random(n) < p_true).astype(float)
X = np.column_stack([np.ones(n), X_raw])
train, test = np.arange(0, 200), np.arange(200, 300) # the rows are already in random order
def sigmoid(z):
return 1 / (1 + np.exp(-z))
def loss_and_grad(theta, X, y):
p = sigmoid(X @ theta)
eps = 1e-12 # guards against log(0)
loss = -np.mean(y * np.log(p + eps) + (1 - y) * np.log(1 - p + eps))
grad = X.T @ (p - y) / len(y) # the same form as linear regression's
return loss, grad
theta = np.zeros(3)
for step in range(3001):
loss, grad = loss_and_grad(theta, X[train], y[train])
if step in (0, 100, 1000, 3000):
print(f"step {step:4d}: cross-entropy {loss:.4f}")
theta -= 0.5 * grad
def accuracy(theta, idx):
predictions = sigmoid(X[idx] @ theta) >= 0.5
return np.mean(predictions == y[idx])
print("learned [b, w1, w2]:", np.round(theta, 2), " true:", np.array([true_b, *true_w]))
print(f"accuracy: train {accuracy(theta, train):.1%}, test {accuracy(theta, test):.1%}")
print(f"always guessing the commoner class would score {max(y[test].mean(), 1 - y[test].mean()):.1%} on test")The learned weights point in the same direction as the true ones but are smaller: with 200 examples whose labels are themselves random draws, the estimate is close but not exact, and it would sharpen with more data. Test accuracy should be read against a baseline — always guessing the commoner class — and against the best possible: since labels here are random given the features, no classifier could be perfect. (Test accuracy slightly above training accuracy is just sampling luck on 100 examples.)
With more than two classes, softmax regression (multinomial logistic regression) gives each class a score, turns the scores into probabilities with , and uses the cross-entropy . It is the last layer of almost every classification network.
Training, validation and test sets
How do we estimate generalisation error, and choose hyperparameters, without fooling ourselves? By keeping data the model has not learned from.
- The training set is used to fit the parameters.
- The validation set (or development set) is used to compare models and choose hyperparameters: the polynomial degree, the learning rate, the amount of regularisation.
- The test set is used once, at the end, to report how the chosen model performs on new data.
Why both validation and test? Because choosing among many models using the validation score is itself a kind of fitting: with enough tries, some model scores well on the validation set by luck. The test set, untouched by every decision, gives an honest estimate. Typical splits are something like 80/10/10, but with huge datasets a few thousand validation and test examples suffice. When data are scarce, -fold cross-validation rotates: split the data into folds, train on and validate on the remaining one, times, and average.
The easiest way to ruin all this is data leakage: information from the evaluation data creeping into training. Classic forms include standardising features using statistics computed on all the data, including the test set; duplicates or near-duplicates appearing in both training and test sets (the same patient's scans, the same web page crawled twice); and, with time series, training on the future to predict the past — split by time, not at random. A model that looks remarkable in evaluation and disappoints in use has very often leaked.
Remember also the assumption hiding in the definition: new data come from the same distribution as the training data. Train a crop model on one region's soils and deploy it in another, and that assumption — not the algorithm — may be what fails.
Overfitting and generalisation
A model that is too simple cannot capture the pattern: it underfits, with high error on training and new data alike. A model that is too flexible can bend to fit the noise in its particular training set: it overfits, with low training error and high error on new data. Polynomial regression on fifteen noisy points from a sine curve shows both; a polynomial of degree is just linear regression on the features .
import numpy as np
rng = np.random.default_rng(5)
def sample(m):
x = rng.uniform(0, 1, m)
return x, np.sin(2 * np.pi * x) + rng.normal(0, 0.25, m) # a smooth truth plus noise
x_train, y_train = sample(15)
x_val, y_val = sample(200)
def features(x, degree):
return np.vander(x, degree + 1, increasing=True) # columns 1, x, x^2, ..., x^degree
def fit(x, y, degree):
theta, *_ = np.linalg.lstsq(features(x, degree), y, rcond=None)
return theta
def mse(theta, x, y, degree):
return np.mean((features(x, degree) @ theta - y) ** 2)
print("degree train MSE validation MSE")
for degree in (0, 1, 3, 5, 9, 14):
theta = fit(x_train, y_train, degree)
print(f"{degree:6d} {mse(theta, x_train, y_train, degree):11.4g} {mse(theta, x_val, y_val, degree):16.4g}")
print("noise variance (the best any model can do on new data): 0.0625")Read the table from top to bottom. A constant (degree 0) and a straight line underfit. Degree 3 comes close to the noise floor of 0.0625 on validation data. As the degree rises further, training error keeps falling — more flexibility can only help on the data you fit — but validation error turns round and climbs; degree 14 passes exactly through all fifteen points and is useless between them. Plotted against model complexity, validation error traces the classic U-shape, and the validation set is how we find its bottom.
Three remedies recur throughout machine learning: more data (the noise averages out and wild fits become impossible), a simpler model, and regularisation — penalising large parameters so the model prefers smooth explanations — which Training in practice covers along with early stopping and data augmentation.
Bias and variance, at the level of ideas
Imagine training the same kind of model many times on different random training sets of the same size, and looking at its prediction at one fixed input . For squared error, the expected error on a new label decomposes exactly into three parts:
Bias is how far the average model is from the truth: a straight line fitted to a sine curve is wrong on average however much data it sees. Variance is how much the model changes from one training set to another: the degree-14 polynomial is wildly different on every sample. Noise is the irreducible part no model can remove. Simple models tend to have high bias and low variance; flexible models, low bias and high variance; and the best classical choice balances the two.
Analogy, not a formal construction
Think of archers shooting at a target. One archer's arrows cluster tightly but off-centre: low variance, high bias. Another's are centred on average but scattered everywhere: low bias, high variance. You want arrows that are both centred and tight — and wind gusts (the noise) will scatter even the best archer a little.
A modern caveat, honestly stated: very large neural networks often have far more parameters than training examples, fit their training data perfectly, and still generalise well — sometimes better as they grow. Researchers call one form of this double descent: past the point where the model can just interpolate the data, test error can fall again. The classical U-shape remains the right picture for small models like the polynomials above, but it is not the whole story, and understanding why huge models generalise is an active research area.
Common misconceptions
Misconception
"Lower training error means a better model." Training error measures memory as much as understanding. Compare models on validation data; report the test set once.
Misconception
"The normal equations are always better than gradient descent, because they are exact." They are exact for linear least squares only, cost in the number of features, and do not exist for most other models. Gradient descent is the general tool.
Misconception
"More features always help." Each feature adds flexibility, and with it variance; irrelevant features let the model fit noise. With few examples, fewer, better features often win.
Misconception
"I can tune on the test set as long as I only look at it a few times." Every decision made by looking at the test set leaks it into the model. Once it has influenced a choice, it is a validation set, and you need a fresh test set for an honest number.
Exercises
1. Learning from data
Warm-upHumanA model predicts for four examples whose true labels are . What is the mean squared error?
2. Learning from data
Warm-upHumanA classifier outputs , its probability that a photo shows a cat. The photo does show a cat (). Which output gives the largest cross-entropy loss?
3. Learning from data
CoreComputationalWrite mse_gradient(X, y, theta) returning the gradient of as a numpy array of the same shape as theta. Use matrix operations, not a Python loop over examples.
The tests compare your gradient with a numerical one computed by finite differences — the standard way to check any hand-derived gradient.
4. Learning from data
CoreComputationalWrite fit_linear(X, y, lr, steps) that starts from and runs steps iterations of gradient descent with learning rate lr on the mean squared error, returning . X already contains a column of ones.
The tests check your result against np.linalg.lstsq on standardised data.
5. Learning from data
CoreComputationalWrite logistic_loss_grad(X, y, theta) returning (loss, grad) for logistic regression: the mean binary cross-entropy of against labels y (0s and 1s), and its gradient .
Make it numerically safe: very large scores like must not produce nan or inf. (Hint: , which np.logaddexp(0, -z) computes stably.)
6. Learning from data
CoreHumanA team predicts next month's electricity demand for each city from weather and past demand. They shuffle five years of monthly records at random, split 80/20 into training and test sets, standardise features using the mean and standard deviation of all the data, and report a test error far better than any deployed model has achieved. What is the most serious problem?
7. Learning from data
CoreHumanA linear model predicting house prices has a training MSE of 410 and a validation MSE of 425 (in squared thousands of a currency unit). Experts estimate the irreducible noise at around 50. What is the most likely situation, and the most promising next step?
8. Learning from data
StretchComputationalWrite k_fold(n, k, seed) for -fold cross-validation. Shuffle the indices with np.random.default_rng(seed).permutation(n), split the shuffled order into k folds whose sizes differ by at most one (np.array_split does this), and return a list of k pairs (train_idx, val_idx): fold i is the validation set of pair i, and the other folds, concatenated, are its training set.
Further reading and resources
- Stanford CS229: Machine LearningLecture notes covering linear and logistic regression, generalisation and much more, with full derivations.
- The Elements of Statistical Learning · Trevor Hastie, Robert Tibshirani and Jerome FriedmanFree online. The statistician's view of the same ideas, including the bias–variance decomposition.
- Mathematics for Machine Learning · Marc Peter Deisenroth, A. Aldo Faisal and Cheng Soon OngFree online. The linear algebra, calculus and probability this lesson leans on.
- Dive into Deep LearningFree, runnable textbook; its early chapters cover the same ground with code.
- NumPy documentation
- scikit-learnThe standard Python library for classical machine learning, once you have built the ideas yourself.
- Reconciling modern machine learning practice and the bias-variance trade-off · Mikhail Belkin, Daniel Hsu, Siyuan Ma and Soumik Mandal · 2019The "double descent" paper, on why very large models can generalise despite fitting their training data.