Welcome to the Machine Learning track. We now move from programming behaviour by hand to learning it from data. Before meeting any algorithm, we must formalise what "learning" means, because the formal statement tells us what can go wrong — and almost everything that goes wrong in practice is a failure to generalise.
Mitchell's definition#
Tom Mitchell's 1997 definition remains the clearest:
A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.
For a spam filter: T = classify emails; P = fraction classified correctly; E = a corpus of labelled emails. Always identify T, P and E before building anything. Many failed projects never clearly defined P.
Traditional programming versus machine learning#
In traditional programming, humans write rules; the computer applies them to data to produce answers. In machine learning, humans provide data and answers; the computer produces the rules (a model), which are then applied to new data. ML is the right tool when rules are too complex to write (recognising faces), change over time (fraud patterns), or must be personalised (recommendations).
The formal supervised learning problem#
We assume:
- An unknown data distribution $\mathcal{P}$ over input–output pairs $(\mathbf{x}, y)$.
- A training set $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ drawn i.i.d. (independently and identically distributed) from $\mathcal{P}$.
- A hypothesis space $\mathcal{H}$ of candidate functions $h: \mathcal{X} \to \mathcal{Y}$ (e.g. all linear functions, all trees of depth 5, all networks of a given architecture).
- A loss function $\ell(h(\mathbf{x}), y)$ measuring the cost of a prediction.
Our true goal is to minimise the expected risk (generalisation error):
But we cannot compute it — $\mathcal{P}$ is unknown. We can only compute the empirical risk on the training set:
Empirical Risk Minimisation (ERM) picks $\hat{h} = \arg\min_{h \in \mathcal{H}}\hat{R}_n(h)$.
The central problem: generalisation#
A model that memorises the training set achieves zero empirical risk, yet may perform terribly on new data. The difference
is the generalisation gap. Machine learning is, at its core, the science of keeping this gap small while also keeping the training error small.
Decomposing the error#
The excess risk of our learned model over the best possible predictor (the Bayes optimal predictor $h^*$) splits into two parts:
- A small hypothesis space has large approximation error (it cannot represent the truth) but small estimation error.
- A large hypothesis space has small approximation error but large estimation error (many functions fit the data by chance).
This trade-off — the bias–variance trade-off in another form — governs model selection throughout the course. Even the Bayes optimal predictor has non-zero error $R(h^*)$ if labels are noisy: the irreducible error.
The i.i.d. assumption and its failure#
ERM's guarantees assume training and test data come from the same distribution. In the real world this often fails: a model trained on hospital A's scanners is deployed at hospital B; a spam filter meets new spam tactics; a model trained before a crisis is used during one. This distribution shift is one of the main reasons deployed models degrade, and we will study it in the MLOps track.
A first learning example#
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
for k in [1, 5, 15]:
model = KNeighborsClassifier(n_neighbors=k).fit(X_tr, y_tr)
print(f"k={k:>2}: train acc={model.score(X_tr, y_tr):.3f} test acc={model.score(X_te, y_te):.3f}")With $k = 1$ the training accuracy is perfect — the model memorises — but the test accuracy is what matters. The held-out test set is our estimate of $R(\hat{h})$.