What is learning? ERM, generalization and the ML workflow

A definition you can compute with

Tom Mitchell's definition is still the sharpest: a program learns from experience $E$ with respect to a task $T$ and performance measure $P$ if its performance on $T$, measured by $P$, improves with $E$. Every learning problem you will meet can be written as a triple. Spam filtering: $T$ = label emails, $E$ = labelled emails, $P$ = fraction correctly labelled. A language model: $T$ = predict the next token, $E$ = trillions of tokens of text, $P$ = cross-entropy on held-out text (7.6 Decoder-only: GPT and autoregressive generation). An agent: $T$ = complete tasks with tools, $E$ = trajectories with rewards, $P$ = success rate (10.9 Evaluating agents). Writing the triple down before coding is the fastest way to notice that the performance measure you can compute is not the one you care about — the central tension of evaluation (3.5 Evaluating models: metrics, validation and the bias–variance trade-off, 8.7 Evaluating LLMs).

Four kinds of learning

The boundaries blur in practice — a language model is trained with self-supervision, then fine-tuned with supervision, then shaped with reinforcement learning (8.1 The LLM lifecycle and model landscape) — but the vocabulary stays.

Hypothesis space, loss and empirical risk

Fix a hypothesis space $\mathcal{H}$: the set of functions the model can represent (all lines; all depth-5 trees; all transformers with a given architecture and weights $\theta \in \mathbb{R}^p$). Fix a loss $\ell(\hat y, y)$ that scores one prediction: squared error $(\hat y - y)^2$, 0–1 loss $\mathbf{1}[\hat y \ne y]$, cross-entropy $-\log \hat p_y$ (1.9 Information theory: entropy, cross-entropy and KL divergence, 4.3 Loss functions catalog). Assume the data are drawn independently and identically distributed (i.i.d.) from an unknown distribution $P$ over $(\mathbf{x}, y)$. What we want to minimize is the true risk (expected loss on new data):

We cannot compute it because we do not know $P$. What we can compute on a training set $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ is the empirical risk, the average training loss:

Empirical risk minimization (ERM) chooses $\hat h = \arg\min_{h\in\mathcal{H}} \hat{R}_n(h)$. Fitting a line by least squares, training a network with gradient descent, growing a tree greedily — all are ERM or approximations of it. The whole question of machine learning is: when is $R(\hat h)$ close to $\hat{R}_n(\hat h)$?

Why training error lies, and by how much

For one fixed function $h$, the law of large numbers (1.8 Statistics essentials) says $\hat{R}_n(h)\to R(h)$ as $n$ grows: the training loss is an unbiased, concentrating estimate of the true loss. But $\hat h$ is not fixed — it was chosen to make $\hat{R}_n$ small, so it is optimistically biased on the very data that selected it. The generalization gap $R(\hat h) - \hat{R}_n(\hat h)$ is the price of that selection. Statistical learning theory bounds it: with high probability, for every $h\in\mathcal{H}$ at once,

where "complexity" is a measure of how many distinct behaviours $\mathcal{H}$ can exhibit on $n$ points (the VC dimension or Rademacher complexity — roughly, how many parameters, or how wiggly). The shape of the bound is what matters: the gap grows with the richness of the hypothesis space and shrinks like $1/\sqrt{n}$ with data. Memorizing this shape explains most of the trade-offs that follow.

Intuition. A test set works because it is data the selection never saw: on it, $\hat h$ is a fixed function, so the law of large numbers applies and the test error is an honest estimate with standard error $\approx\sqrt{p(1-p)/n_{\text{test}}}$ (3.5 Evaluating models: metrics, validation and the bias–variance trade-off). Use it to choose a model and it stops being honest.

Approximation versus estimation

Let $R^* = \min_h R(h)$ over all functions (the Bayes error — irreducible noise) and $h^*_{\mathcal{H}} = \arg\min_{h\in\mathcal{H}} R(h)$ the best function in your family. The excess risk of what you actually get splits into two pieces:

Approximation error is the fault of the hypothesis space being too small — a line cannot fit a parabola — and shows up as underfitting: high training and test error. Estimation error is the fault of finite data letting you pick a bad member of a large family — overfitting: low training error, high test error. Making $\mathcal{H}$ bigger lowers the first and raises the second; this is the bias–variance trade-off, derived precisely in 3.5 Evaluating models: metrics, validation and the bias–variance trade-off and managed in 3.6 Regularization and generalization. Fit degree-1 and degree-15 polynomials to ten noisy points from a sine curve and you see both failure modes in one picture: the line misses the curve everywhere, the degree-15 polynomial passes through every point and swings wildly between them.

Splits: train, validation, test

Because the training error is optimistic and the test set must stay untouched, model development uses three disjoint sets. Train fits parameters. Validation (or k-fold cross-validation, 3.5 Evaluating models: metrics, validation and the bias–variance trade-off) compares models and hyperparameters — degree of the polynomial, $k$ in kNN, learning rate. Test is evaluated once, at the end, to report a number. Choosing among 200 hyperparameter settings on the validation set is itself a form of fitting, so the validation score of the winner is slightly optimistic too; the test set is what protects you. Information must never flow backwards: no scaling statistics computed on all data, no duplicates across splits, no features that encode the answer, no future data in a time-series training set (2.3 pandas, data wrangling and plotting, 3.13 Feature engineering, data quality and data-centric ML).

No free lunch and inductive bias

Averaged over all possible data-generating functions, every learning algorithm has the same expected test error — the no-free-lunch theorem. Learning only works because the real world is not an arbitrary function: it has regularities, and a model learns precisely to the extent that its assumptions, its inductive bias, match them. kNN assumes nearby inputs have similar outputs (smoothness, 3.4 k-Nearest Neighbors). Linear models assume additive effects. Trees assume axis-aligned, piecewise-constant structure (3.8 Decision trees). CNNs assume translation equivariance and locality (5.1 Convolution: the operation and its math). Transformers assume little and compensate with data (7.1 Attention Is All You Need: the big picture). There is no universally best model; there is a best model for data with a given structure, found by trying candidates under honest validation.

The workflow

1. Frame. Write the $(T, E, P)$ triple; decide what a useful result looks like and what a model would replace.
2. Data. Collect, split first, then explore the training split (2.3 pandas, data wrangling and plotting).
3. Baseline. Predict the mean or majority class; then the simplest sensible model. Everything later must beat this honestly.
4. Iterate. Feature engineering, model families, hyperparameters — one change at a time, tracked (2.5 Tooling: Git, GPUs, experiments and the Hugging Face Hub).
5. Evaluate. Validation metrics with error bars; error analysis on the worst mistakes; a single test-set evaluation.
6. Ship and monitor. Data drifts; the i.i.d. assumption dies the moment the world changes. Monitoring is part of the model.

Where this shows up later

• Every loss in 4.3 Loss functions catalog is an $\ell$ here; every architecture in Phases 4–7 is a choice of $\mathcal{H}$; every optimizer in 4.5 Optimizers and learning-rate schedules is a way to do ERM.
• The generalization gap is measured by validation protocols in 3.5 Evaluating models: metrics, validation and the bias–variance trade-off and shrunk by regularization in 3.6 Regularization and generalization and 4.7 Regularization in deep nets.
• Self-supervised ERM on text is the pretraining objective of LLMs — 7.6 Decoder-only: GPT and autoregressive generation, 8.1 The LLM lifecycle and model landscape; the i.i.d. assumption breaking is distribution shift — 5.9 Interpretability, robustness and adversarial examples, 8.12 Safety, risks and responsible AI.
• Choosing the performance measure you can compute versus the one you care about is the entire topic of LLM and agent evaluation — 8.7 Evaluating LLMs, 10.9 Evaluating agents.