Algorithms for converting experience (training data) into expertise/knowledge (prediction function or program). Can be categorized along different axes:

• Supervised learning (privileged information present in training data that's the object of prediction in test data) vs Unsupervised learning (no functional difference between training and test data).
• Active learning vs Passive learning

Formal Model - Statistical Learning Framework

Formally, given a distribution $\mathcal{D}$ over data space $\mathcal{X}$, ground truth target function $f:\mathcal{X}\to \mathcal{Y}$, training data $S=((x_1{y}_1),\dots (x_m,y_m))$, a learning algorithm outputs a prediction function $h_S:\mathcal{X}\to \mathcal{Y}$.

The generalization error of $h$ (for a classification problem) is the probability of randomly choosing an example $x$ for which $h(x)\ne f(x)$, i.e.,

The goal of the algorithm is to find the predictor (which depends on the training set $S$) that minimizes the error with respect to the unknown $\mathcal{D}$ and $f$. The training error or empirical risk/error $L_S(h)$ is the error that the classifier incurs over the training samples.

Empirical risk minimization (ERM) is the simple learning paradigm that aims to minimize the training error, but one needs to watch out for overfitting, wherein the model performs excellently on the training data but poorly on the true distribution. A common remedy is to restrict the hypothesis class $\mathcal{H}$ of the predictor functions $h$ choosing in advance the set of predictors we will optimize over based on some prior knowledge we have about the learning problem. This biases the algorithm to a particular set of predictors (inductive bias). Formally,

$L_{\mathcal{D},f}(h_S)$ depends on the training set $S$ which arises from a random process (usually i.i.d sampling). This means there is randomness in the choice of the predictor $h_S$ and, consequently, in the risk $L_{\mathcal{D},f}(h_S)$. The sample could be unrepresentative with some probability, and even if not, there could be errors due to the finiteness of the sample. This can be formalized by the notion of PAC Learnability, which characterizes learning problems (specifically hypothesis sets for arbitrary data-label distributions) that can be solved to arbitrarily low error rates $ϵ$ with arbitrarily low probability of failure $\delta$ given a sufficient number of samples (sample complexity).

The limits of learnability

Although some guarantees on learning problems can be derived, it can also be proved that there is no panacea. This is called the No-Free-Lunch theorem, a formal statement that no learning algorithm is perfect for every possible dataset out there. This arises because the PAC learning framework makes absolutely no assumptions about the data distribution, so one can always construct an adversarial distribution for the outputs of any given learning algorithm, including an ERM learner.

We can decompose the error of an ${\text{ERM}}_{\mathcal{H}}$ predictor into two components. If $h_S$ is an ERM hypothesis:

where ${ϵ}_{\text{app}}=\underset{h\in \mathcal{H}}{\text{min}}{L}_{\mathcal{D}}(h)$ and ${ϵ}_{\text{est}}=L_{\mathcal{D}}(h_S)-{ϵ}_{\text{app}}$. ${ϵ}_{\text{app}}$ approximation error is the bias of the learning algorithm, i.e., the minimum possible risk achievable in the hypothesis class. ${ϵ}_{\text{est}}$ is the estimation error arising from not being guaranteed to find the true risk minimizer given a finite training sample.