Statistical learning theory

Builds on Loss function Independent and identically distributed random variables Expected value Empirical risk minimization VC dimension

Definition

Statistical learning theory is the study of the following setting.

There are an input space $\mathcal X$ , an output space $\mathcal Y$ and an unknown probability distribution $P$ on $\mathcal X \times \mathcal Y$ .
A loss function $L \colon \mathcal Y \times \mathcal Y \to [0, \infty)$ measures the cost $L(f(x), y)$ of predicting $f(x)$ when the truth is $y$ .
The risk of a measurable function $f \colon \mathcal X \to \mathcal Y$ is $R(f) = E[L(f(X), Y)]$ , where $(X, Y)$ has law $P$ .
A learning algorithm maps a sample $(X_1, Y_1), \dots, (X_n, Y_n)$ of independent and identically distributed pairs with law $P$ to a function $\hat f_n$ . Usually $\hat f_n$ lies in a fixed class $\mathcal F$ .

Its questions are how fast $R(\hat f_n)$ approaches $\inf_{f \in \mathcal F} R(f)$ or the best possible risk, uniformly over the distributions $P$ in some class.

Remarks

A central tool is the uniform deviation $\sup_{f \in \mathcal F} \abs{R_n(f) - R(f)}$ , where $R_n(f) = \frac1n \sum_{i=1}^{n} L(f(X_i), Y_i)$ is the empirical risk; it controls empirical risk minimization. For binary classification with the $0$ - $1$ loss, this deviation tends to $0$ uniformly over all $P$ if and only if $\mathcal F$ has finite VC dimension.

Example: binary classification with $\mathcal Y = \set{0, 1}$ , the $0$ - $1$ loss $L(a, y) = \mathbf{1}\set{a \ne y}$ and $\mathcal F$ the half-planes in $\mathcal X = \R^2$ fits the setting; then $R(f)$ is the probability of a misclassification.

Non-example: clustering points with no labels does not fit clauses 2 and 3 as stated, since there is no output to predict. It belongs to unsupervised learning.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Empirical risk minimization concept
Expected value concept
Independent and identically distributed random variables concept
Loss function concept
VC dimension concept
Statistical learning theory definition

Tag	`M9SVV4FDZV`
URI	`m2://M9SVV4FDZV`
Kind	definition
Writing	W0 stub
MSC	68Q32, 62H30, 68T05
Defines	Statistical learning theory
Uses	Loss function, Independent and identically distributed random variables, Expected value, Empirical risk minimization, VC dimension

Statistical learning theory

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here