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.