What machine learning is

A bank decides whom to lend to, a shop how much stock to order, a search engine which ten pages to show first. None of these decisions follows from a formula derived from first principles, but each comes with a history: loans that were or were not repaid, past sales, past clicks. Machine learning turns such a history into a rule that predicts the outcome for a new case. Outside text and images, most of this work is done on tables (prices, credit, churn, demand, search ranking), and the workhorses are linear models, decision trees and gradient boosting; neural networks are built from the same parts, linear maps, losses, gradient descent and regularization. On medium-sized tabular datasets, tree ensembles still beat deep networks (Grinsztajn, Oyallon and Varoquaux, 2022). Fitting a rule to the history is the easy part. The hard part is generalization: a rule that is perfect on the examples can be useless on the next case, and a careless check can make a useless rule look perfect. This note sets up the problem in the language of the probability course, shows why the error on the training examples is optimistic, and lays out the course.

Notation. An object (a customer, a flat, a query–document pair) is described by a feature vector $x \in \mathcal X$, usually $\mathbb R^d$; its target is $y \in \mathcal Y$. The pairs come from an unknown distribution $P$ on $\mathcal X \times \mathcal Y$, and the training set $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$ holds $n$ independent draws from it. A model is a function $f$ from $\mathcal X$ to predictions, chosen from a family $\mathcal F$; the trained model is $\hat f$. A loss $L(y, \hat y) \ge 0$ is the cost of predicting $\hat y$ when the truth is $y$.

From examples to a rule#

The training set is a table: one row per object, one column per feature, plus the target column. To predict the price of a flat, the features might be the area, the district, the floor and the year of construction, and the target the price. A supervised learning method takes the table and returns a function $\hat f$ that, given the features of a flat that was not in the table, returns a price.

“Good” needs a number. The loss says how bad one prediction is, for example the squared error $L(y, \hat y) = (y - \hat y)^2$, and the empirical risk of a model is its average loss on the training set:

$$\hat R_n(f) = \frac1n \sum_{i=1}^n L\big(y_i, f(x_i)\big) .$$

Most training procedures, from least squares to gradient boosting, minimize it over a family of models: $\hat f = \arg\min_{f \in \mathcal F} \hat R_n(f)$, empirical risk minimization. What we care about, though, is the loss on the next object, the risk

$$R(f) = E_{(X, Y) \sim P}\, L\big(Y, f(X)\big) ,$$

the expectation of the loss under the distribution that produces the data. The empirical risk is a sample average of losses, and for a model fixed before the data are seen it is an unbiased estimate of the risk. If the loss has a finite mean under $P$, the estimate converges to the risk by the law of large numbers. If the loss also has a finite variance $\sigma_L^2$, the standard error is $\sigma_L/\sqrt n$, of order $1/\sqrt n$, and the central limit theorem turns it into an error bar; a bounded loss satisfies both conditions, and Hoeffding’s inequality then gives a bound for every $n$.

The trained model is not fixed before the data are seen: it was chosen because it fits them. Worked example. The simplest model ignores the features and predicts one number $c$. Four flats cost 3, 5, 4 and 8 (millions). The squared loss is minimized by the mean, $c = \bar y = 5$, and its empirical risk is $\frac14(4 + 0 + 1 + 9) = 3.5$. Is 3.5 the risk of predicting 5? Suppose the prices have mean $\mu$ and variance $\sigma^2$. On a new flat, the risk of the constant $\bar y$ is $E(Y - \bar y)^2 = \sigma^2 + (\bar y - \mu)^2$, whose average over training sets is $\sigma^2 + \sigma^2/n$. The empirical risk is $\frac1n \sum_i (y_i - \bar y)^2$, whose average is $\frac{n-1}{n}\sigma^2$, the biased variance estimate of the estimators note. With $n = 4$:

$$E\,\hat R_n(\bar y) = 0.75\,\sigma^2, \qquad E\,R(\bar y) = 1.25\,\sigma^2 .$$

A model with a single parameter already looks better on its training data than it is, because the parameter was chosen to fit those data: the gap is $2\sigma^2/n$. Models with thousands of parameters can make the gap as large as the risk itself.

The best possible prediction#

Which function would we choose if we knew $P$? For the squared loss, the answer is the conditional mean $m(x) = E[Y \mid X = x]$, the best predictor: for any $f$, $R(f) = R(m) + E\,(m(X) - f(X))^2$. Its own risk, $R(m) = E\operatorname{Var}(Y \mid X)$, is the noise that the features do not explain, the irreducible error. Other losses pick out other summaries of the conditional distribution (other losses, other targets):

Loss	$L(y, \hat y)$	Best prediction at $x$	Likelihood reading (optional)
Squared	$(y - \hat y)^2$	mean of $Y \mid X = x$	Gaussian
Absolute	$\lvert y - \hat y \rvert$	median of $Y \mid X = x$	Laplace
0–1	$[y \ne \hat y]$	most probable class
Cross-entropy	$-\log q(y \mid x)$	$q(\cdot \mid x) = P(Y = \cdot \mid X = x)$	categorical

The third column needs no assumption about the noise. The conditional mean minimizes the expected squared loss for every distribution with $E\,Y^2 < \infty$, Gaussian or not, and the conditional median minimizes the expected absolute loss whenever $E\lvert Y \rvert < \infty$. The loss decides which summary of $Y \mid X = x$ we estimate. The last column is an optional reading from the maximum likelihood note: up to constants, the squared, absolute and cross-entropy losses are negative log-likelihoods of these noise models, so minimizing them is maximum likelihood when the model holds. With exponential noise, for example, least squares still estimates the conditional mean, but it is no longer the maximum-likelihood fit. Not every useful loss has such a reading: the 0–1 loss has none, and the hinge loss of the support vector machine is not a normalized conditional likelihood. For classification with the 0–1 loss, the best rule predicts the most probable class, the Bayes classifier, and its risk $R^* = E\big[1 - \max_k P(Y = k \mid X)\big]$ is the Bayes error.

A trained model falls short of the best in two ways. Writing $R^*$ more generally for the smallest possible risk under the chosen loss ($R(m)$ for the squared loss, the Bayes error for the 0–1 loss) and $f^*_{\mathcal F}$ for the best member of the family,

$$R(\hat f) - R^* = \underbrace{R(\hat f) - R(f^*_{\mathcal F})}_{\text{estimation error}} + \underbrace{R(f^*_{\mathcal F}) - R^*}_{\text{approximation error}} .$$

A family that is too simple cannot approximate $m$; a family that is too rich for $n$ examples cannot be estimated well from them. Every method in this course chooses a point on this trade-off, and the bias–variance note makes it exact for the squared loss.

Kinds of tasks#

Task	Target	Examples	Typical loss or metric
Regression	a number	price, demand, delivery time	squared or absolute error
Binary classification	one of two classes	default, churn, fraud	cross-entropy; precision, recall, ROC-AUC
Multiclass, multilabel	one of $K$ classes, or a set of labels	topic of an article, tags	softmax cross-entropy
Ranking	an order of items for a query	search results, recommendations	pairwise and listwise losses, NDCG
Clustering	none	customer segments	within-cluster distance

The first four are supervised: the training set contains the targets. Ranking differs in that the loss depends on several objects at once: a list is good if the relevant documents come first, whatever the scores are. Unsupervised tasks have no target at all; besides clustering they include density estimation, anomaly detection and dimensionality reduction, the subjects of the section on learning without labels.

Fitting is easy, generalizing is hard#

The most flexible family contains all functions, and in it a perfect training fit always exists: the memorizer returns $y_i$ when asked about $x_i$ and some default elsewhere. Its empirical risk is zero. With continuous features, a new object almost never coincides with a training object, so the memorizer answers every new question with its default: it has learned nothing. A rich family overfits in a less extreme way, and the figure shows how. Polynomials of increasing degree are fitted by least squares to 12 points of a sine with noise of variance $0.09$ (the same setup as the bias–variance example); both curves are exact expected values over the noise:

Figure

Training error falls, error on new data does not

The training error falls with every added coefficient: 0.541 for a constant, 0.067 at degree 3, 0.015 at degree 9, and exactly 0 at degree 11, where the polynomial passes through all 12 points. The error on new data falls only while the model is too simple for the sine: it is smallest at degree 3 (0.121), and then grows to 0.208 at degree 9, 0.421 at degree 10 and 3.16 at degree 11. From degree 5 on, the polynomial can follow the sine almost exactly, and the expected training error is $\sigma^2 (n - p)/n$ for $p = \text{degree} + 1$ coefficients: each coefficient absorbs one direction of the noise, $0.09/12 = 0.0075$ of training error per coefficient. That absorbed noise is what the model gets wrong on new data.

Probability says how much data the check needs. For one model fixed in advance, Hoeffding’s inequality bounds the deviation of its validation loss from its risk; for the best of $K$ candidates chosen on the same validation set, the bound pays $\ln K$ for the selection (a first generalization bound). The validation note turns this into practice: training, validation and test sets, cross-validation, and error bars on the result.

The course as a bridge#

Optional depth: how each method rests on the probability course and where the NLP and Generative Models courses use it. The rest of the note does not depend on it.

This course sits between the probability course and two courses that build on it, NLP and Generative Models. Each method is introduced with the probability it rests on, and each note says where the later courses use it. The main threads:

Probability tool	What it becomes here	Where NLP and Generative Models use it
Expectation	risk as an expected loss; a minibatch gradient as an estimate of an expected gradient (gradient descent)	every training objective is an empirical risk
Concentration, the LLN, the CLT, the bootstrap	generalization, validation and its error bars, selection bias, metrics	evaluation and leakage in NLP
Conditional expectation	the target of least squares and of nearest neighbours; the bias–variance split
Maximum likelihood	squared error read as a Gaussian likelihood; cross-entropy in logistic regression and the softmax; the EM algorithm	text classifiers, language models, cross-entropy and KL
Bayesian inference	ridge and lasso as priors (regularization); smoothed target encoding	weight decay in fine-tuning
The multivariate Gaussian	PCA, Gaussian mixtures, the geometry of nearest neighbours in high dimension	autoencoders and VAEs, semantic search

Two threads start in this course itself: backpropagation, which trains the recurrent networks and Transformers of the NLP course and every network of the Generative Models course, and learning to rank, which scores the passages of semantic search and retrieval-augmented generation.

Figure

The course as a bridge: from probability to NLP and generative models

The course map#

Each step either answers a limitation of the one before it or, in the last rows, changes the task:

Failure	Answer
Memorizing the training set does not generalize	risk and validation: this note, data, features and leakage, validation
Similar inputs should get similar outputs, but similarity in many dimensions is nearly meaningless	nearest neighbours and the curse of dimensionality
A neighbour vote has no global structure	least squares
The closed form is too expensive or does not exist	gradient descent, stochastic and adaptive optimizers
With many features the fit chases noise	regularization
Least squares on class labels lets easy points move the boundary	linear classifiers and surrogate losses
We need probabilities, not only a side of a line	logistic regression
Accuracy hides the errors that matter	classification metrics
The best separating line is not unique, and lines are too simple	support vector machines, kernels
More than two classes, or several labels at once	multiclass and multilabel classification
A line cannot express interactions	decision trees
Why do flexible models overfit?	the bias–variance decomposition
One tree is unstable	bagging and random forests
Averaging does not fix bias	gradient boosting
Features must be designed by hand	neural networks, backpropagation, training deep networks
There are no labels at all	clustering, mixtures and EM, dimensionality reduction, anomaly detection
The output is an order, not a label	learning to rank, recommender systems

The notes are grouped into seven sections: the learning problem (this note and the next three), linear regression, linear classification, trees and ensembles, neural networks, learning without labels, and problems beyond classification. After the course, a reader should be able to turn a business question into a supervised problem with a target, features and a metric; build a validation scheme that matches deployment and catches leakage; fit and debug linear models, trees and boosting and derive their gradients; choose between boosting and a neural network for a given dataset; and read scikit-learn or PyTorch training code knowing what each line does.

What changed#

	A program written by hand	A model learned from examples
The rule	written by a person who understands the process	chosen from a family $\mathcal F$ by minimizing $\hat R_n$
What it needs	knowledge of the mechanism	examples from the distribution of future cases
What “correct” means	passes the specified cases	small risk $R(f)$ on new cases
How it is checked	tests of the specification	loss on held-out data, with an error bar
Typical failure	a bug	overfitting, leakage, a change of the distribution

Limitations#

• New data must look like old data. Every guarantee is about pairs drawn from the same $P$. A new market, a crisis, or a policy that reacts to the model’s own predictions changes $P$, and the validated risk no longer applies.
• The loss is a choice. A model minimizes the loss it is given; on a problem with 1% fraud, never predicting fraud already scores 99% accuracy, so accuracy can rank a useless model above a useful one.
• Prediction is not causation. A model of $P(Y \mid X)$ says what $Y$ tends to be when $X$ is observed, not what $Y$ becomes when $X$ is changed: a churn model ranks the customers likely to leave, but does not say which offer would keep them.
• Labels cost. Supervised learning needs a target for every training example, and collecting targets is often the most expensive part of a project.

What you should remember#

• A supervised problem is a table of features $x$ and targets $y$, a family of models and a loss; training minimizes the empirical risk $\hat R_n(f) = \frac1n\sum_i L(y_i, f(x_i))$.
• What matters is the risk $R(f) = E\,L(Y, f(X))$ on new data; for a model fixed in advance and a loss with finite variance, $\hat R_n$ estimates it with error of order $1/\sqrt n$.
• A trained model’s training error is optimistic: already for a fitted constant, $E\hat R_n = \frac{n-1}{n}\sigma^2$ against a risk of $\frac{n+1}{n}\sigma^2$.
• The best possible predictor is $E[Y \mid X]$ for squared loss and the most probable class for 0–1 loss; their risk is the irreducible error and the Bayes error.
• A loss decides the best prediction whatever the noise: the mean for squared error, the median for absolute error, the most probable class for 0–1. Some common losses also read as negative log-likelihoods (squared error of Gaussian noise, cross-entropy of a categorical model); not every useful loss does.
• Richer families lower the training error steadily; the error on new data falls and then rises. Only held-out data measure it.

Code#

The fitted constant’s optimism by simulation, and the polynomial errors of the figure exactly and by simulation:

import numpy as np
from numpy.polynomial import legendre as L

rng = np.random.default_rng(0)

# a constant prediction fitted to n = 4 values: its training error against its risk on new data (sigma^2 = 1)
n, sims = 4, 200_000
y = rng.normal(size=(sims, n))
c = y.mean(axis=1)                                          # the fitted constant, y-bar
train = ((y - c[:, None]) ** 2).mean(axis=1)                # empirical risk of y-bar on its own sample
risk = 1 + c ** 2                                           # E(Y - c)^2 for a new Y ~ N(0, 1)
print(round(float(train.mean()), 3), round(float(risk.mean()), 3))   # 0.751 1.25: (n-1)/n and (n+1)/n
print(np.mean([3, 5, 4, 8]), np.mean((np.array([3, 5, 4, 8]) - 5) ** 2))  # 5.0 3.5: the toy example

# polynomials fitted to 12 equally spaced points of sin(2 pi x) + N(0, 0.3^2): exact expected errors
m, s2, n = (lambda x: np.sin(2 * np.pi * x)), 0.09, 12
x = np.linspace(0, 1, n)
gx, gw = L.leggauss(200); gx, gw = (gx + 1) / 2, gw / 2      # quadrature on [0, 1] for a new X ~ U(0, 1)
def expected_errors(deg):
    Phi = L.legvander(2 * x - 1, deg)
    A = np.linalg.pinv(Phi)                                 # y -> coefficients
    G = L.legvander(2 * gx - 1, deg) @ A                    # y -> predictions on the quadrature grid
    train = (((m(x) - Phi @ A @ m(x)) ** 2).sum() + s2 * (n - deg - 1)) / n
    test = s2 + gw @ (G @ m(x) - m(gx)) ** 2 + s2 * gw @ (G ** 2).sum(axis=1)
    return train, test
for deg in (0, 1, 3, 5, 9, 10, 11):
    print(deg, *np.round(expected_errors(deg), 3))
# 0 0.541 0.598 | 1 0.329 0.318 | 3 0.067 0.121 | 5 0.045 0.128 | 9 0.015 0.208 | 10 0.008 0.421 | 11 0.0 3.158

# the same numbers by simulation for degree 3: 20,000 training sets, each scored on 1,000 fresh points
P = L.legvander(2 * x - 1, 3)
Y = m(x) + 0.3 * rng.normal(size=(20_000, n))
coef = np.linalg.lstsq(P, Y.T, rcond=None)[0]
xt = rng.random(1000)
Yt = m(xt) + 0.3 * rng.normal(size=(20_000, 1000))
print(round(float(((Y - (P @ coef).T) ** 2).mean()), 3), round(float(((Yt - (L.legvander(2 * xt - 1, 3) @ coef).T) ** 2).mean()), 3))
# 0.067 0.122

Next#

The setup assumed that every object arrives as a vector of numbers and that the training rows are independent draws from the distribution the model will meet. Real data arrive as tables with categories, missing values, dates and free text, and the easiest way to break the second assumption is to let information about the target slip into the features. The next note turns raw columns into features and shows how leakage makes a useless model look excellent.

References#

• E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture 1: introduction.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Chapter 2 (statistical decision theory, Section 2.4), Section 7.2 (model complexity and test error), Section 7.4 (optimism of the training error).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Chapter 2 (empirical risk minimization and overfitting), Chapter 5 (the bias–complexity trade-off).
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Section 1.1 (polynomial curve fitting).
• L. Grinsztajn, E. Oyallon, G. Varoquaux. Why do tree-based models still outperform deep learning on tabular data? NeurIPS Datasets and Benchmarks Track, 2022.