Data, Models, and Learning

The previous seven chapters built a mathematical toolbox. Chapter 8 turns the key and opens the door to machine learning proper. Three ingredients recur in every ML pipeline: data (a set of observations $\mathcal{D} = \{(\mathbf{x}_n, y_n)\}_{n=1}^{N}$), a model (a parametric function family $f_\theta : \mathcal{X} \to \mathcal{Y}$), and a learning principle (a rule for picking $\theta$ from $\mathcal{D}$). Supervised learning, which we focus on next, asks: given labeled data, find $\theta$ so that $f_\theta(\mathbf{x}) \approx y$ on future inputs.

The dominant learning principle is empirical risk minimization (ERM). Define a loss $\ell(y, \hat{y})$ that measures disagreement (squared error for regression, cross-entropy for classification). The empirical risk averages the loss over training data: ERM picks $\hat\theta = \arg\min_\theta R_{\text{emp}}(\theta)$. This is the workhorse behind linear regression, logistic regression, SVMs, and deep networks — they differ only in the choice of $f_\theta$ and $\ell$.

The true quantity we care about is the expected risk $R(\theta) = \mathbb{E}_{(\mathbf{x}, y)}[\ell(y, f_\theta(\mathbf{x}))]$ under the unknown data distribution $p^*$. Empirical risk is a finite-sample estimate of expected risk — close when $N$ is large (law of large numbers), noisy when $N$ is small. The gap between the two is the generalization gap, and controlling it is the central theoretical concern of ML.

Two failure modes threaten ERM. Overfitting happens when a flexible model memorizes training quirks, driving $R_{\text{emp}}$ to zero while $R$ stays high. Underfitting happens when a rigid model cannot even fit the data, so both risks are high. The remedy is regularization — add a penalty $\lambda \Omega(\theta)$ that prefers simpler models — and model selection via held-out validation data or cross-validation.

The classical bias-variance decomposition frames this tension: where bias measures systematic error, variance measures sensitivity to the training sample, and $\sigma^2$ is irreducible noise. More capacity lowers bias but raises variance. Regularization and more data shift this trade-off. Understanding this decomposition is what separates a principled modeler from a hyperparameter tinkerer.

Worked example — train/test split: From 10 data points, use 8 for training and 2 for validation. If training MSE is 0.05 and validation MSE is 0.42, the generalization gap is $0.37$ — a clear overfitting signal. Reducing capacity or adding regularization $\lambda \|\mathbf{w}\|^2$ should shrink this gap on the next training run.