A bank wants to flag fraudulent card transactions. One way to build the flag is to interview the fraud team and write their rules into code: a purchase abroad within an hour of a purchase at home, a run of small charges at petrol stations, a sudden jump in amount. Another is to collect a year of transactions that the team has already investigated, each marked fraudulent or legitimate, and let a program find the combination of features that separates the two. The second program is said to learn. If it is retrained every month on the newly investigated cases, its flags improve, or at least track the fraudsters as they change their methods, without anyone rewriting a rule.
Tom Mitchell's textbook makes that idea precise with three ingredients: a program learns from experience $E$ with respect to a class of tasks $T$ and a performance measure $P$ if its performance at tasks in $T$, as measured by $P$, improves with experience $E$ (Mitchell, 1997, Ch. 1; cited by attribution). For the bank, $T$ is classifying transactions, $P$ might be the share of fraud caught at a fixed rate of false alarms, and $E$ is the archive of investigated cases. The definition is deliberately broad. It covers a regression fitted to a spreadsheet, a spam filter, and a language model trained on a large share of the public web, and it says nothing about method. What it does insist on is the measure: a claim that a program has learned is a claim that $P$ went up, and checking it requires measuring $P$ on cases that played no part in the learning.
This article is an overview of the field as the rest of this collection develops it. It places artificial intelligence, machine learning and deep learning in relation to one another, describes the three standard settings, and spends most of its length on the two ideas that every method shares: fitting by minimizing a loss, and the gap between fitting and generalizing. Reinforcement learning, which the collection does not otherwise cover, gets a worked example.
Models, parameters and loss
Most of machine learning follows one pattern. Choose a family of functions, a model, indexed by adjustable numbers called parameters: the intercept and slopes of a regression line, the split points of a decision tree, the weights of a neural network. Choose a loss function that scores how badly a given setting of the parameters fits the training data: squared error for numbers (Loss Functions for Regression), cross-entropy for classes (Loss Functions for Classification). Then search for the parameters that make the loss small. The search is called training or fitting, and the procedure that carries it out, whether a closed formula, Newton's method or gradient descent, is the learning algorithm.
Least squares is the oldest instance. The simple linear regression article derives the slope and intercept that minimize the sum of squared residuals in closed form; logistic regression has no closed form and is fitted by Newton's method; a neural network has neither a closed form nor a guarantee of finding the best parameters, and is fitted by gradient descent from random starting weights. The algorithms differ greatly, but each answers the same question.
Settings that the learner does not fit, such as the number of neighbors in k-nearest neighbors, the depth of a tree or the learning rate of a network, are hyperparameters. They are chosen by comparing fitted models on held-out data, which is the subject of Training, Validation, and Test Sets and Cross-Validation.
Three settings
The kind of experience $E$ the program receives divides the field into three standard settings.
| Setting | What the learner is given | What it produces | Worked in this collection |
|---|---|---|---|
| Supervised | inputs paired with the correct output | a function from inputs to outputs | Introduction to Supervised Learning and its articles; regression, trees, ensembles, neural networks |
| Unsupervised | inputs only | a description of structure: groups, dense regions, a few underlying dimensions | Introduction to Unsupervised Learning and its articles |
| Reinforcement | the consequences of its own actions, as rewards | a policy: which action to take in each situation | the bandit example below |
Supervised learning has a teacher. Each training example comes with the answer, and the learner's job is to reproduce the answers on new inputs. James, Witten, Hastie and Tibshirani (2021, §2.1.4) describe the setting as one where for each observation of the predictors there is an associated response, and the aim is accurate prediction for future observations or understanding of how the response relates to the predictors. When the output is a number the task is regression; when it is a category, classification. Predicting the magnitude of an earthquake from seismometer readings is regression; deciding whether to approve a loan is classification. The supervised learning overview derives the best predictions possible in each case and computes, for a simulated problem, a Bayes error rate of 0.1816 that no classifier can beat, which is a useful reminder that some error is in the data rather than the method.
Unsupervised learning has no answers to imitate. The same textbook calls this "the somewhat more challenging situation" in which each observation has measurements but no associated response, so that the analysis is "in some sense working blind" (James et al., 2021, §2.1.4). Clustering finds groups of similar cases, such as segments of customers with similar purchases; dimension reduction finds a few combinations of the inputs that carry most of their variation, such as the principal components of a table of measurements; density estimation and outlier detection find where data are common and where they are rare. Because there is no correct answer to score against, judging the result is harder, and the unsupervised learning overview spends much of its length on how to check a clustering.
Reinforcement learning has neither answers nor a fixed dataset. Sutton and Barto (2018, §1.1) define it as learning "how to map situations to actions" so as to "maximize a numerical reward signal", where the learner "is not told which actions to take, but instead must discover which actions yield the most reward by trying them". They count it as a third paradigm alongside the other two, not a kind of unsupervised learning, because it tries "to maximize a reward signal instead of trying to find hidden structure" (§1.1). The rest of this article returns to it below.
The three are not exhaustive. Semi-supervised learning uses a few labeled examples together with many unlabeled ones (James et al., 2021, §2.1.4). Self-supervised learning manufactures its labels from the data itself, and it is how the language models of the language article are trained: the "label" for each position in a text is simply the next token, so a model trained to predict it is doing supervised learning on labels that cost nothing to collect. The library's Bigram Language Model shows that setup in its simplest form. And chat assistants are typically trained in stages that use all three settings, from next-token prediction to supervised examples to reinforcement learning from human or AI feedback, as the library's notes on RLHF and Constitutional AI describe.
Generalization
Fitting the training data is easy to do too well. A 1-nearest-neighbor classifier makes no errors on its own training set, because every training case is its own nearest neighbor, and a deep enough decision tree can do the same. What matters is the error on new cases from the same source, the generalization error or test error, and the training error is a biased estimate of it. The bias-variance tradeoff derives why: a flexible model fits the noise in its particular training set as well as the signal, and the noise does not recur.
The worked results elsewhere in this collection show how large and how varied the effect is.
- On a simulated problem with known answer, the Bayes classifier itself misclassifies 18.5% of a training sample of 200 cases (Introduction to Supervised Learning). Any classifier that does much better than that on its training data is fitting noise.
- A network with 73,985 parameters, trained on 341 tumors for 1,000 epochs, overfits in its predicted probabilities while its accuracy hardly changes: the median test log loss is 0.143 at the end of training against 0.084 with the weights from the epoch of lowest validation loss, while test accuracy moves from 0.974 to 0.965 (The Multilayer Perceptron). Which measure is watched decides whether overfitting is seen at all.
- When the inputs of a classifier are chosen using all the data before cross-validation, cross-validation reports an error of 1.3% for a classifier whose true error is 50%, because all 5,000 candidate inputs were pure noise; choosing them inside each fold reports 53.1% (Training, Validation, and Test Sets). This is leakage, information from the held-out cases reaching the model, and it is one of the most common ways a published result turns out to be wrong.
- Averaging hundreds of decorrelated trees reduces variance without increasing bias much (Random Forests), and combining several kinds of model by their out-of-fold predictions beat the best single member on Friedman's simulated regression problem in all 30 training sets, while on the nearly linear diabetes data no stack beat least squares alone (Stacking).
Generalization also has a second, harder meaning. A held-out test set drawn from the same source measures performance on more of the same. Deployed systems meet data that differ from their training data, in time, in place, in population or in the way it was collected, and a model can rely on a feature that predicted well in the training data for reasons that do not carry over. The computer vision article gives examples of such shortcuts in image classifiers, and the risks article discusses what they mean for people affected by a model's decisions.
Reinforcement learning worked: the 10-armed bandit
A slot machine with ten arms, each paying a random reward whose average the player does not know, is the simplest reinforcement learning problem. There is only one situation, the same machine every time, so the whole problem is which arm to pull. Sutton and Barto (2018, §2.3) use a test suite of such problems, the 10-armed testbed. For each problem the true value $q(a)$ of each arm $a$ is drawn from a normal distribution with mean 0 and variance 1, and each pull of arm $a$ returns a reward drawn from a normal distribution with mean $q(a)$ and variance 1.
An agent can estimate each arm's value by the average of the rewards it has received from that arm,
$$Q_t(a) = \frac{\text{sum of rewards from arm } a \text{ before step } t}{\text{number of times arm } a \text{ was pulled before step } t},$$
with $Q = 0$ for arms not yet tried. The greedy agent always pulls the arm with the largest current estimate. The ε-greedy agent does the same, except that with a small probability $\varepsilon$ it pulls an arm chosen uniformly at random. The greedy agent exploits what it knows; the ε-greedy agent also explores. Sutton and Barto (2018, §1.1) describe the dilemma: to obtain reward the agent must prefer actions it has found to be good, but to find them it must try actions it has not yet selected, and "neither exploration nor exploitation can be pursued exclusively without failing at the task".
The experiment below reruns their comparison at a smaller scale. Each of 30 seeded runs averages 100 independent bandit problems of 1,000 steps each, and the same problems are given to all three agents within a run. The table reports the median and interquartile range (IQR) over the 30 runs, for the last 100 steps of each problem.
| Agent | Average reward, steps 901–1,000 | Optimal arm chosen, steps 901–1,000 |
|---|---|---|
| greedy ($\varepsilon = 0$) | 1.007 (IQR 0.086) | 36.0% (IQR 7.0) |
| $\varepsilon = 0.01$ | 1.285 (IQR 0.052) | 58.6% (IQR 6.1) |
| $\varepsilon = 0.1$ | 1.355 (IQR 0.091) | 79.2% (IQR 2.9) |
The numbers agree with what Sutton and Barto report from 2,000 problems: the greedy method levels off at a reward of about 1 per step, finds the optimal action in about a third of the problems, and the ε-greedy methods do better in the long run (2018, §2.3). The best possible average, the mean value of the best of ten arms, is about 1.54; over the 3,000 problems used here it was 1.517. Even the agent with $\varepsilon = 0.1$ falls short of it, partly because it spends a tenth of its pulls on random arms forever. Reducing $\varepsilon$ over time removes that cost, and Sutton and Barto (2018, Ch. 2) describe several better ways to balance the two aims.
Three features of the example carry over to full reinforcement learning. The agent learns from rewards, not from labeled answers: no one tells it which arm is best. Its data depend on its own behavior, since it only learns about arms it pulls, which is why a learner that stops exploring can be wrong forever. And there is still an objective being optimized; it is the expected reward rather than a fit to labels.
General reinforcement learning adds situations, called states, that change in response to the agent's actions, so that an action can affect not only the immediate reward but every later one. Sutton and Barto (2018, §1.1) name these two features, "trial-and-error search and delayed reward", as the most important distinguishing features of reinforcement learning. A policy maps each state to an action, and the agent's goal is a policy that maximizes the total reward it expects to collect. Practical methods learn a value function that estimates future reward from each state, and many fit it, or a policy, by minimizing a loss: DeepMind's MuZero, for example, trains its networks on a loss that adds the errors in predicted rewards, predicted values and predicted move probabilities (Schrittwieser et al., 2020, eq. 1). MuZero plays chess, Go, shogi and Atari games by combining those learned predictions with Monte Carlo tree search, a lookahead search over possible future moves, and it does so "without any knowledge of the game rules", matching the earlier AlphaZero, which was given them (Schrittwieser et al., 2020, abstract).
Choosing a method
No method is best for every problem. The course wiki's No Free Lunch Theorems state that idea formally for search and optimization, and the experience of this collection agrees with it in practice. Logistic regression matches a neural network on the nearly linear breast cancer data and loses to it on two interleaved crescents (The Multilayer Perceptron); trees handle mixed numbers and categories with no scaling, but a single tree is unstable; nearest neighbors needs no training but a great deal of memory and careful scaling.
James et al. (2021, §10.6) give a sensible default. Simpler tools that perform as well as complex ones "are likely to be easier to fit and understand, and potentially less fragile", so it makes sense to try them as well and choose on the balance of performance and complexity; deep learning is "an attractive choice when the sample size of the training set is extremely large, and when interpretability of the model is not a high priority". Images, sound and text are the clearest cases, because specialized network architectures can exploit their structure, as the vision and language articles show. For a table of a few thousand rows and a dozen columns, a random forest or boosted trees are hard to beat, and a logistic regression is hard to beat for being understood.
The choice of method is usually less important than what surrounds it: whether the outcome being predicted is the one that matters, whether the training data represent the cases the model will meet, whether the evaluation is honest, and what happens when the model is wrong. Those are the subjects of the model selection and evaluation articles and of the risks article.
In Python
The ε-greedy agent of the bandit experiment takes a few lines of NumPy. This version plays one problem:
import numpy as np
rng = np.random.default_rng(0)
q = rng.normal(0, 1, 10) # true arm values, unknown to the agent
Q = np.zeros(10) # estimates
N = np.zeros(10) # pull counts
eps, total = 0.1, 0.0
for t in range(1000):
if rng.random() < eps:
a = rng.integers(10) # explore
else:
a = rng.choice(np.flatnonzero(Q == Q.max())) # exploit, ties at random
r = rng.normal(q[a], 1)
N[a] += 1
Q[a] += (r - Q[a]) / N[a] # running average of arm a's rewards
total += r
print(total / 1000, Q.argmax() == q.argmax())
The update Q[a] += (r - Q[a]) / N[a] is the sample average written incrementally: the new estimate moves toward the latest reward by a fraction $1/N$ of the error. Replacing $1/N$ with a constant step size gives an estimate that weights recent rewards more, which suits problems whose arms change over time (Sutton and Barto, 2018, §2.5). The experiment's numbers, for all 3,000 problems and the three agents, are computed by tools/experiments/data-science/machine-learning-overview.py in the site's repository.
References
- James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. §2.1.4 and §10.6. record · 30 pages
- Mitchell, T. M. (1997). Machine Learning. McGraw-Hill. Cited by attribution; not read for this article. record
- Schrittwieser, J., Antonoglou, I., Hubert, T., et al. (2020). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588, 604–609. Read in the arXiv version, arXiv:1911.08265v2. record
- Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Ch. 1 and 2. record