4 Supervised Learning
Supervised learning is the construction of a function that predicts an outcome from features, using a set of cases in which both are observed. This chapter states the problem formally: the data, the tasks, the loss that measures error, the risk that the learned function should minimize, and the reason why minimizing error on the training cases does not minimize error on new cases.
4.1 Data, features and outcome
The data consist of \(n\) cases. Case \(i\) has a vector of \(p\) features \(x_i = (x_{i1}, \dots, x_{ip})\), also called predictors, inputs, covariates or independent variables, and an outcome \(y_i\), also called the response, target, label or dependent variable. Arranged as a table, each row is a case and each column a feature, with the outcome as an additional column. The features form the \(n \times p\) matrix \(X\) (AMDS: A matrix as a table of data).
The cases are assumed to be independent draws from a joint distribution \(P(X, Y)\), the population. New cases, for which predictions will be made, are assumed to come from the same distribution. This assumption connects performance measured on the available data to performance in use, and it is the assumption that the population element of the question (Section 1.3) makes explicit.
4.2 Regression and classification
The type of the outcome defines the task.
- In regression, the outcome is numeric, such as a disease progression score. The learned function returns a number.
- In classification, the outcome is categorical, with \(K\) classes. With \(K = 2\) the task is binary classification, such as death or survival; with \(K > 2\) it is multiclass classification. A probabilistic classifier returns an estimate of the probability of each class, \(\hat p_k(x) \approx P(Y = k \mid X = x)\). A class prediction follows by choosing a class, for example the most probable one, or in the binary case the positive class whenever \(\hat p(x)\) exceeds a threshold.
In binary classification one class is designated the positive class, usually the event of interest, such as death. Metrics such as sensitivity are defined with respect to it (Chapter 8).
4.3 Loss
A loss function \(L(y, \hat y)\) assigns a non-negative cost to predicting \(\hat y\) when the outcome is \(y\). Common choices are:
| Task | Loss | \(L(y, \hat y)\) |
|---|---|---|
| Regression | Squared error | \((y - \hat y)^2\) |
| Regression | Absolute error | \(\lvert y - \hat y \rvert\) |
| Classification, class prediction | Zero–one | \(0\) if \(\hat y = y\), \(1\) otherwise |
| Classification, probability prediction | Log loss (cross-entropy) | \(-\log \hat p_y(x)\) |
| Classification, probability prediction | Brier (squared) | \(\sum_{k} \left(\mathbb{1}[y = k] - \hat p_k(x)\right)^2\) |
The log loss is the negative log-likelihood of a categorical model, so that minimizing it is maximum likelihood estimation (AMDS: Why cross-entropy is the classification loss). The loss used to fit a model and the metric used to evaluate it need not be the same: a logistic regression is fitted by minimizing log loss and may be evaluated by its AUC.
4.4 Risk and the optimal predictor
The quality of a function \(f\) is its risk, the expected loss on a new case drawn from the population:
\[ R(f) = \mathbb{E}_{(X, Y) \sim P}\left[ L\big(Y, f(X)\big) \right]. \tag{4.1}\]
For a given loss, the function with the smallest possible risk is determined by the population distribution. Under squared error it is the conditional mean,
\[ f^*(x) = \mathbb{E}[Y \mid X = x], \tag{4.2}\]
called the regression function (AMDS: Conditional expectation). Under zero–one loss it is the Bayes classifier, which predicts the class with the highest conditional probability, \(f^*(x) = \arg\max_k P(Y = k \mid X = x)\). Even \(f^*\) makes errors, because the features do not determine the outcome exactly: two patients with identical measurements can have different outcomes. The risk of \(f^*\) is the irreducible error, and no model can have lower risk.
4.5 Learning as empirical risk minimization
The population distribution is unknown, so neither \(R(f)\) nor \(f^*\) can be computed. A learning algorithm selects a function from a set of candidates \(\mathcal{F}\), the model class, using the training data. The most common principle is empirical risk minimization: choose the function that minimizes the average loss on the training cases,
\[ \hat f = \arg\min_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^{n} L\big(y_i, f(x_i)\big), \tag{4.3}\]
often with an added penalty on the complexity of \(f\) (Chapter 18). The model class defines the algorithm’s assumptions: linear models restrict \(\mathcal{F}\) to linear functions of the features; decision trees to piecewise-constant functions; neural networks to compositions of linear maps and nonlinear activations. Fitting is an optimization problem, solved in closed form for some classes and iteratively, for example by gradient descent, for others (AMDS: Gradient Descent).
Two kinds of quantity are involved. Parameters, such as regression coefficients or the split points of a tree, are estimated from the data by the fitting procedure. Hyperparameters, such as the strength of a penalty or the maximum depth of a tree, are set before fitting and control which functions the procedure can produce. Hyperparameters are chosen by comparing the performance of models fitted with different values (Chapter 20).
4.6 Overfitting
The training error (Equation 2.4) is the quantity that empirical risk minimization makes small, and it is therefore an optimistic estimate of the risk. The gap grows with the flexibility of the model class. A sufficiently flexible class contains functions that pass close to every training case, reproducing the noise in the outcomes along with the systematic relationship; such a function has low training error and high error on new cases. This is overfitting. A model class too restricted to represent the systematic relationship has high error on both training and new cases; this is underfitting.
Figure 4.1 illustrates both with simulated data. The outcome is a sine function of one feature plus normally distributed noise, and polynomials of degree 1, 3 and 12 are fitted by least squares to 20 training cases.
The straight line underfits: it cannot represent the curvature, and its errors are systematic. The cubic polynomial follows the true function closely. The degree-12 polynomial bends toward individual training points and oscillates between them. Its training error, 0.029, is the lowest of the three, against 0.071 for the cubic; its error on new cases, 0.158, is higher than the cubic’s 0.123.
Figure 4.2 shows the mean squared error of polynomials of every degree from 1 to 12, on the 20 training cases and on 5000 new cases from the same distribution and range of \(x\).
Training error decreases with every added degree, since each polynomial class contains the previous one. Test error falls sharply at degree 3, where the polynomial first captures the shape of the sine function, reaches its minimum at degree 5, and rises over the higher degrees, as added flexibility fits the noise in the 20 training cases. The minimum test error remains above the irreducible error of 0.09. This U-shaped relationship between flexibility and test error is the subject of Chapter 16.
4.7 Generalization requires held-out data
Since training error decreases with flexibility regardless of whether test error does, it cannot be used to choose between models or to report performance. Every estimate of predictive performance in this book is computed on cases that played no role in fitting the model, including the choice of its hyperparameters. The simplest design divides the data once into a training set and a test set; resampling (Chapter 10) repeats the division to use the data more efficiently and to measure the variability of the estimate.
4.8 No universally best algorithm
Averaged over all possible problems, no learning algorithm outperforms any other (Wolpert 1996). An algorithm performs well on a problem when its assumptions, encoded in its model class and fitting procedure, match the structure of that problem. In practice the structure is unknown, and algorithms are compared empirically by their estimated performance on new cases. The chapters on individual algorithms describe the assumptions each one makes.
4.9 Summary
- Supervised learning estimates a function from features to outcome, using cases in which both are observed and assumed to be drawn from the population of intended use.
- Regression predicts a numeric outcome; classification predicts a class or class probabilities.
- A loss function measures the cost of an error; the risk is the expected loss on a new case; the irreducible error is the risk of the best possible function.
- Learning algorithms minimize training loss within a model class, often with a complexity penalty. Parameters are estimated by fitting; hyperparameters control the fitting.
- Training error decreases with model flexibility; error on new cases first decreases and then increases. Performance is estimated on held-out data.
4.10 Further reading
- AMDS: Random Variables (conditional expectation), Information Theory (cross-entropy), Gradient Descent.
- Hastie et al. (2009), chapters 2 and 7; James et al. (2021), chapter 2.
- Vapnik (1998) on the theory of empirical risk minimization; Wolpert (1996) on the absence of a universally best algorithm.
- Wikipedia: Supervised learning, Loss function, Empirical risk minimization, Overfitting.