The wine data (Aeberhard and Forina, 1992) record thirteen chemical measurements, among them alcohol content, flavanoids and proline, for 178 wines grown in one region of Italy, together with the cultivar of grape each wine came from: 59 from the first cultivar, 71 from the second and 48 from the third. Suppose a new bottle arrives with its chemistry measured but its cultivar unknown. The 178 wines whose cultivar is known are a set of worked examples, each pairing measurements with the right answer. A method that studies those examples and produces a rule for naming the cultivar of a new wine from its measurements is doing supervised learning. Ten-fold cross-validation, described in Cross-Validation, estimates that three quite different such rules, introduced below, name the cultivar correctly between 97.2% and 98.3% of the time.
Every method in the Regression topic of this collection is supervised learning, from simple linear regression to logistic regression, and so are decision trees and the ensembles built from them. This article sets out what all of them share: the setup, the two kinds of task, and the best prediction that any method could make, against which every real method can be measured. The rest of the topic covers three classifiers built on different ideas: k-nearest neighbors predicts from the most similar known cases, naive Bayes from a probability model of each class, and support vector machines from a boundary placed as far as possible from both classes.
The setup
Each example is an instance, one row of a dataset: one wine, one patient, one email. It has an output $y$, the quantity to be predicted, and a vector of $p$ inputs $x = (x_1, \dots, x_p)$ from which the prediction is made. The inputs are also called predictors or features, and the output the response, target or label (James, Witten, Hastie and Tibshirani, 2021, §2.1); Introduction to Regression discusses these names and why calling an input "independent" does not make it a cause. An instance whose output is known is labeled. The training set is a collection of $n$ labeled instances,
$$\mathcal{T} = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\},$$
where $x_i$ is the input vector of the $i$th instance and $y_i$ its output. A supervised method uses $\mathcal{T}$ to construct a prediction rule $\hat{f}$, and then predicts $\hat{y} = \hat{f}(x)$ for new instances whose inputs are known and whose output is not. The word "supervised" refers to the labels: during training, the known outputs show the method what it should have predicted, as a teacher marks answers right or wrong. In unsupervised learning there are no labels, and the task is to find structure among the inputs alone, such as groups of similar instances (see Introduction to Unsupervised Learning).
Which column is the output is a decision about the question, not a property of the data. A wine merchant who wants to verify a label treats the cultivar as the output and the chemistry as inputs. A winemaker who wants to know how a cultivar's alcohol content can be predicted from its other measurements might treat alcohol as the output and the cultivar as one of the inputs.
Regression and classification
The type of the output divides supervised problems in two (James et al., 2021, §2.1.5). When the output is a number, such as disease progression, price or temperature, the task is regression. When it is one of a fixed set of categories, such as a cultivar, malignant or benign, or spam or not, the task is classification, and a method that performs it is a classifier. The type of the inputs plays no part in the distinction: a classifier can use numerical inputs, and a regression can use categorical ones.
Some outputs can be framed either way, and the framing is a modeling choice. A rating from 1 to 10 can be predicted as a number, which allows a prediction such as 7.3 and treats the step from 3 to 4 as the same size as the step from 7 to 8, or as ten categories, which makes no such assumption but also ignores that 7 is closer to 8 than to 2. Logistic regression shows that the boundary is not sharp in method either: it predicts a category by first modeling a probability, which is a number.
Many methods handle both tasks with the same machinery. A decision tree predicts the mean output of a leaf for regression and its most common class for classification; k-nearest neighbors averages the outputs of the nearest training instances or takes a vote among them. The task is decided by the question, and the method chosen afterward.
The best possible prediction
Before asking how well any method does, it helps to ask how well any method could possibly do. Treat the input $X$ and output $Y$ of a new instance as random variables with some joint distribution, and suppose for the moment that the distribution is known. Which prediction rule is best depends on how errors are charged, the loss function.
For a number: the regression function
Under squared error loss, the cost of predicting $c$ when the outcome is $Y$ is $(Y - c)^2$. Fix an input value $x$, and let $\mu(x) = E(Y \mid X = x)$ be the mean of the outputs of all instances with that input. The expected loss of predicting the constant $c$ at $x$ splits into two parts. Add and subtract $\mu(x)$ inside the square:
$$E\bigl[(Y - c)^2 \mid X = x\bigr] = E\bigl[(Y - \mu(x))^2 \mid X = x\bigr] + 2\bigl(\mu(x) - c\bigr) E\bigl[Y - \mu(x) \mid X = x\bigr] + \bigl(\mu(x) - c\bigr)^2.$$
The middle expectation is zero, because $\mu(x)$ is the mean of $Y$ at $x$. What remains is
$$E\bigl[(Y - c)^2 \mid X = x\bigr] = \operatorname{Var}(Y \mid X = x) + \bigl(\mu(x) - c\bigr)^2.$$
The first term does not depend on $c$, and the second is smallest, zero, at $c = \mu(x)$. The best prediction at every $x$ is therefore the conditional mean,
$$f(x) = E(Y \mid X = x),$$
called the regression function (Hastie, Tibshirani and Friedman, 2009, §2.4, eq. 2.13). Even this ideal rule makes errors: its expected squared error at $x$ is $\operatorname{Var}(Y \mid X = x)$, the spread of outcomes among instances that share the same inputs. That is the irreducible error of James et al. (2021, §2.1.1), and the bias-variance decomposition separates it from the errors a fitted model adds.
The derivation works for any numeric output, including a 0/1 code for a yes-or-no outcome. Then $E(Y \mid X = x)$ is $\Pr(Y = 1 \mid X = x)$, so the best squared-error prediction of a 0/1 outcome is its probability. In the simulated problem described below, the probability that an instance at $x = (0.5, 0.5)$ belongs to class 1 is 0.8126. Predicting 0.8126 there has expected squared error $0.8126 \times 0.1874 = 0.1523$, while predicting 0.5 costs 0.2500 and predicting 1 costs 0.1874.
For a category: the Bayes classifier
For classification the natural loss is the 0-1 loss: a wrong class costs 1 and a right one costs 0, so the expected loss is the probability of error. If a rule predicts class $j$ for an instance with input $x$, it is wrong with probability $1 - \Pr(Y = j \mid X = x)$. That probability is smallest for the class whose conditional probability is largest. A rule that makes this choice at every $x$ has the smallest error probability at every $x$, and so also the smallest average over all inputs. So the best rule is
$$G(x) = \arg\max_j \Pr(Y = j \mid X = x),$$
which predicts the most probable class given the inputs. It is called the Bayes classifier (Hastie et al., 2009, §2.4, eqs. 2.21 to 2.23; James et al., 2021, §2.2.3, who state the result without proof). With two classes it predicts class 1 when $\Pr(Y = 1 \mid X = x) > 0.5$. The set of inputs where the two classes are equally probable is the Bayes decision boundary.
The Bayes classifier errs with probability $1 - \max_j \Pr(Y = j \mid X = x)$ at $x$. Averaged over the distribution of the inputs, this gives the Bayes error rate,
$$R^* = 1 - E\Bigl[\max_j \Pr(Y = j \mid X)\Bigr],$$
the lowest error rate any classifier can achieve on the problem (James et al., 2021, eq. 2.11). It is zero only when the classes never overlap, so that the inputs determine the class with certainty. Otherwise it plays the role for classification that the irreducible error plays for regression.
With two classes, Bayes' theorem gives the conditional probabilities in terms of the prior probabilities $\pi_0, \pi_1$ of the classes and the class densities $f_0, f_1$, the distributions of the inputs within each class:
$$\Pr(Y = k \mid X = x) = \frac{\pi_k f_k(x)}{\pi_0 f_0(x) + \pi_1 f_1(x)}.$$
The Bayes classifier picks the class with the larger $\pi_k f_k(x)$, and it errs with the smaller one's share, so the Bayes error rate is the overlap of the two weighted densities:
$$R^* = \int \min\bigl(\pi_0 f_0(x),\ \pi_1 f_1(x)\bigr)\, dx.$$
A problem where the answer is known
On real data the joint distribution is unknown, so the Bayes classifier cannot be computed. A simulated problem makes it visible. Two classes are equally likely. Each is a mixture of three round normal distributions in the plane, with standard deviation 0.6 in every direction: class 0 is centered on $(-1, 1)$, $(0, 2.5)$ and $(1.5, 0)$, and class 1 on $(1, -1)$, $(2.2, 1.2)$ and $(0.2, 0.6)$, each center chosen with probability one third. Because $f_0$ and $f_1$ are known, so is $\Pr(Y = 1 \mid X = x)$ at every point. Integrating the formula above numerically over a fine grid gives a Bayes error rate of 0.1816; classifying a million simulated instances with the Bayes classifier gives 0.1810. No classifier, however clever, can expect to make fewer than about 18 errors in 100 on this problem.
The figure shows a training set of 100 instances from each class (seed 742). Even the Bayes classifier misclassifies 18.5% of them, because some instances of each class fall where the other class is more likely. Two further features of the figure matter later. The class 0 cluster centered on $(1.5, 0)$ lies among the three clusters of class 1, so the Bayes boundary bends around it, and the region of class 0 sends a tongue down and to the right into the territory of class 1. And far from the data, where both densities are tiny, the boundary still exists and still decides: the Bayes classifier assigns every point to whichever class's tail is heavier there.
Learning approximates the ideal
A supervised method can be understood as an attempt to approximate the Bayes classifier, or the regression function, from a finite training set. There are two broad routes (James et al., 2021, §2.2.3 and §4.4).
Estimate the conditional probability directly. Logistic regression assumes that the log-odds of class 1 is a linear function of the inputs and fits its coefficients. k-nearest neighbors makes no such assumption: it estimates $\Pr(Y = j \mid X = x)$ by the fraction of class $j$ among the $k$ training instances closest to $x$ (James et al., 2021, eq. 2.12), replacing "the instances with input exactly $x$", of which there are usually none, by "the instances near $x$" (Hastie et al., 2009, §2.4).
Model each class, then apply Bayes' theorem. A generative method estimates the priors $\pi_k$, usually by the class proportions in the training set, and the class densities $f_k$, and computes the conditional probabilities from the formula above. Linear and quadratic discriminant analysis assume that each $f_k$ is a multivariate normal distribution. Naive Bayes assumes instead that within each class the inputs are independent, which reduces the estimation of a $p$-dimensional density to $p$ one-dimensional ones (James et al., 2021, §4.4.4).
Each of the three methods was fitted to the training set in the figure and tested on 20,000 new instances, and then the whole experiment was repeated with 100 independent training sets of the same size:
| Classifier | Training error | Test error | Mean test error, 100 training sets (SD) |
|---|---|---|---|
| Bayes classifier | 0.185 | 0.1832 | 0.1816 (exact) |
| 15-nearest neighbors | 0.190 | 0.2006 | 0.1997 (0.0090) |
| Gaussian naive Bayes | 0.290 | 0.2941 | 0.2820 (0.0093) |
| logistic regression | 0.290 | 0.2992 | 0.2928 (0.0094) |
Nearest neighbors comes within about two points of the Bayes error rate. Logistic regression is limited by its form: whatever its coefficients, its boundary is a straight line, and no straight line follows a boundary that bends around a cluster. Its error comes from bias, a mismatch between the shape the model can take and the shape of the truth, and more training data would not remove it. Naive Bayes models each class with one normal distribution per input. That allows curved boundaries, but a single bump per input cannot describe a class made of three separate clusters, so it fails here for the same underlying reason.
The comparison does not mean that flexible methods are better in general. On data whose Bayes boundary is close to a straight line, logistic regression would match the Bayes classifier closely and nearest neighbors would pay for its flexibility in variance, the change in its predictions from one training set to another. On the diabetes study, a least-squares plane predicts disease progression better than the best nearest-neighbor fit (The Bias-Variance Tradeoff). Which method approximates the ideal best depends on the shape of the truth and on how much data there is.
Gaussian naive Bayes, worked by hand
The course wiki's Naive Bayes article derives the method for text, where each input counts a word, and its companion covers the version that records only whether a word occurs. When the inputs are measurements, the usual choice is Gaussian naive Bayes: within class $k$, input $j$ is modeled as a normal distribution with its own mean $\mu_{jk}$ and standard deviation $\sigma_{jk}$, estimated from the training instances of that class (James et al., 2021, §4.4.4). Independence within the class means that the class density is the product of the input densities,
$$f_k(x) = \prod_{j=1}^{p} \frac{1}{\sqrt{2\pi}\,\sigma_{jk}} \exp\!\left(-\frac{(x_j - \mu_{jk})^2}{2\sigma_{jk}^2}\right),$$
and the classifier predicts the class with the largest $\pi_k f_k(x)$. Dividing each $\pi_k f_k(x)$ by their sum gives the estimated probabilities of the classes.
Take two of the wine measurements, alcohol (percent by volume) and flavanoids. The 178 wines were split at random, stratified by cultivar (seed 742), into 124 for training and 54 for testing. The training wines give these estimates (standard deviations computed by dividing by the class size, which is the maximum likelihood estimate and what scikit-learn uses):
| Cultivar | Training wines | Prior $\hat\pi_k$ | Alcohol mean | Alcohol SD | Flavanoids mean | Flavanoids SD |
|---|---|---|---|---|---|---|
| 1 | 41 | 0.3306 | 13.743 | 0.445 | 2.990 | 0.389 |
| 2 | 50 | 0.4032 | 12.166 | 0.491 | 2.089 | 0.733 |
| 3 | 33 | 0.2661 | 13.201 | 0.494 | 0.783 | 0.289 |
One test wine has alcohol 13.49 and flavanoids 1.84. For cultivar 1, its alcohol is $(13.49 - 13.743)/0.445 = -0.57$ standard deviations from the class mean, which gives a normal density of 0.7631, and its flavanoids are $(1.84 - 2.990)/0.389 = -2.96$ standard deviations away, a density of only 0.0128. Repeating the calculation for each class and each input:
| Cultivar | $\hat\pi_k$ | Density of alcohol | Density of flavanoids | Product $\hat\pi_k \hat f_k(x)$ | Estimated probability |
|---|---|---|---|---|---|
| 1 | 0.3306 | 0.7631 | 0.0128 | 0.00324 | 0.4045 |
| 2 | 0.4032 | 0.0215 | 0.5139 | 0.00446 | 0.5569 |
| 3 | 0.2661 | 0.6809 | 0.0017 | 0.00031 | 0.0386 |
The products sum to 0.00801, and each probability is a product divided by that sum. The two inputs pull in opposite directions. The alcohol content is typical of cultivars 1 and 3 and unusually high for cultivar 2; the flavanoids are typical of cultivar 2 and far outside the usual range of the other two. Multiplying the densities lets the stronger evidence win: the flavanoid density for cultivar 3 is so small that cultivar 3 is nearly ruled out, and cultivar 2 edges out cultivar 1, 0.557 to 0.405. The wine is in fact from cultivar 2. scikit-learn's GaussianNB returns the same probabilities to four decimals.
The independence assumption is not true here. Within cultivar 1, alcohol and flavanoids have a correlation of 0.489 in the training wines; within the other two cultivars, $-0.118$ and $-0.131$. Across all 13 inputs, the within-cultivar correlations have a median absolute value of 0.184 and reach 0.790. The classifier works anyway. On two inputs it classifies 50 of the 54 test wines correctly (0.926), and on all 13 inputs, 52 of 54 (0.963). Ten-fold cross-validation on all 178 wines gives accuracies of 0.972 for naive Bayes, 0.983 for logistic regression and 0.978 for 15-nearest neighbors on standardized inputs: three classifiers built on different ideas, all close to perfect on a problem where the cultivars differ clearly in their chemistry.
James et al. (2021, §4.4.4) explain why a false assumption can still give good classifications. Estimating how $p$ inputs vary jointly within each class takes a great deal of data; assuming independence removes that task, at the cost of some bias, and the reduction in variance often outweighs the bias, especially when $n$ is not large relative to $p$. A classifier also needs only the right class to come out on top, not accurate probabilities, which is why naive Bayes probabilities are often too extreme even when its decisions are good, a pattern measured on breast cancer data in Loss Functions for Classification. On the simulated mixture above, the assumption that hurt was not independence but the single normal distribution per input.
Parametric and nonparametric methods
Logistic regression and naive Bayes are parametric: each assumes a form for the function being estimated, fixed by a set number of parameters (coefficients, or class means and standard deviations), and fitting the model means estimating those parameters. k-nearest neighbors is nonparametric: it makes no assumption about the form, and its predictions can take any shape the data support (James et al., 2021, §2.1.2). Hastie et al. (2009, §2.4) put the contrast in terms of what each assumes about the regression function: least squares assumes it is well approximated by a globally linear function, nearest neighbors that it is well approximated by a locally constant one.
A parametric method that assumes the right form needs far less data than a nonparametric one, and a parametric method that assumes the wrong form cannot be rescued by more data. A nonparametric method avoids the second danger but needs enough data to fill the input space, and in many dimensions that is a great deal of data, the subject of the curse of dimensionality in K-Nearest Neighbors.
Prediction and explanation
Models are fitted for two different purposes (James et al., 2021, §2.1.1). Prediction is the goal when what matters is the output for new instances: whether a transaction is fraudulent, what a house will sell for, which digit an image shows. The model can be a black box if it is accurate. Explanation, which James et al. call inference, is the goal when what matters is how the output depends on the inputs: which habits are associated with depression, how much each feature adds to a house's price, which conditions precede a machine's failure. Then the model must be one a person can read.
The two goals pull toward different methods because flexibility and interpretability tend to trade against each other. James et al. (2021, Figure 2.7) place methods on the two scales: least squares and the lasso are inflexible and easy to interpret, trees sit in the middle, and bagging, boosting, support vector machines and deep learning are flexible and hard to interpret. The arrangement is a tendency, not a law. A tree with hundreds of leaves is no easier to read than many black boxes, and a linear model with dozens of interaction terms loses much of its clarity.
Interpretability also has more than one meaning. A linear model or a naive Bayes model has a global summary: one coefficient per input, or one table of class means. A nearest-neighbor classifier has no global summary, since there is no fitted rule to read, but each individual prediction is easy to explain by showing the training instances that produced it. Which kind of explanation is useful depends on the audience. A researcher who wants to know how inputs relate to the output needs the first kind; a doctor who wants to know why one patient was flagged may be well served by the second.
When accuracy and interpretability are both wanted, a sensible practice is to fit a simple, interpretable model first and keep a more flexible one only if it predicts clearly better on held-out data. Measuring "clearly better" is the subject of the Evaluating Model Performance topic, which begins with The Bias-Variance Tradeoff, and choosing among candidates is covered in Model Selection.
Training error is not the goal
A rule's error rate on its own training set is the training error; its error rate on new instances from the same source is the test error, the quantity that matters (James et al., 2021, eqs. 2.8 and 2.9). The table above shows the two agreeing for rigid methods and for the Bayes classifier. For flexible methods they can differ greatly: a 1-nearest-neighbor classifier assigns every training instance its own label and so has a training error of zero, or nearly so, whatever its test error. Every comparison in this topic is therefore made on data the method did not see during fitting, using a held-out test set (Training, Validation, and Test Sets) or Cross-Validation.
In Python
scikit-learn gives every supervised method the same interface: construct the model, call fit with the training inputs and outputs, and call predict (or predict_proba, for class probabilities) on new inputs.
from sklearn.datasets import load_wine
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import StratifiedKFold, cross_val_score, train_test_split
from sklearn.naive_bayes import GaussianNB
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
wine = load_wine()
X, y = wine.data, wine.target
X_tr, X_te, y_tr, y_te = train_test_split(X[:, [0, 6]], y, test_size=0.3,
stratify=y, random_state=742) # alcohol, flavanoids
nb = GaussianNB().fit(X_tr, y_tr)
print(nb.theta_, nb.var_ ** 0.5) # class means and standard deviations
print(nb.predict_proba([[13.49, 1.84]])) # [[0.4045 0.5569 0.0386]]
print(nb.score(X_te, y_te)) # 0.926
folds = StratifiedKFold(10, shuffle=True, random_state=0)
for model in (GaussianNB(),
make_pipeline(StandardScaler(), LogisticRegression(max_iter=5000)),
make_pipeline(StandardScaler(), KNeighborsClassifier(15))):
print(cross_val_score(model, X, y, cv=folds).mean()) # 0.972, 0.983, 0.978
GaussianNB stores the class means in theta_ and the variances in var_. It adds a tiny constant, by default $10^{-9}$ times the largest input variance, to every variance so that an input that is constant within a class cannot cause a division by zero; on the wine data the effect is invisible. The numbers in this article are computed by tools/experiments/data-science/introduction-to-supervised-learning.py in the site's repository, and the simulated problem is defined in tools/experiments/data-science/dsdata.py.
References
- Aeberhard, S., and Forina, M. (1992). Wine [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5PC7J record · 8 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
- James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages