Generally speaking, the supervised learning problem can be described as follows.

Let be a *population* of objects, where each object is represented by a set of *features*, i.e., .

Each feature is actually a *property* derivable from the particular object instance.

In addition, we assume each object is paired with a value , so that , and we call any a *labeled example* (or *observation*), namely any object instance with its associated value.

Now, suppose we have as a set of labeled examples, namely a *sample* drawn from the population of objects above together with their associated values, and let us call it the *training set*.

Using **matrix notation**, the training set can be represented as follows.

First, we write each as a (column) vector of features:

Then, we represent all the object instances by a matrix , so that:

where stands for the *transpose* operator, i.e., .

In addition, the set of values associated with the objects can be written as an column vector , as follows:

Finally, the training set can be overall represented by

Intuitively, supervised learning is the machine learning task of inferring an *unknown* function, called the *target function*, from labeled training data so that this function can be in turn used for predicting which value should be assigned to *unseen* instances of population , i.e., instances which lay outside the training set and whose actual value is unknown.

Note that if (i.e., if each takes on *continuous* values) then supervised learning problem turns into a **regression problem**. On the other hand, if and (i.e., if each takes on *discrete* values) the supervised learning problem turns into a -ary **classification problem**.

To put it more formally, assuming the existence of an unknown target function , which maps each object to its correct value, the goal of a supervised learning algorithm is to exploit the training set to *learn* another function called *hypothesis* and **selected from a fixed family of functions, namely a fixed space of possible hypotheses** , which best approximates .

We assume there exists a **joint probability distribution** over all possible values and , which we will denote by for short. In addition, the training set consists of instances drawn independently identically distributed (i.i.d.) from . This allows us to model *uncertainty in predictions* (e.g., due to noise in data) so that is not a deterministic function of yet it is a random variable with a conditional probability distribution for a fixed value of . Similarly to the joint probability distribution, we denote by the conditional probability distribution over all the possible values and .

It turns out that the hypothesis we would like to find may either lead to learning the whole joint probability distribution or to learning directly the conditional probability distribution . The former leads to so-called **generative models** (e.g., Naïve Bayes), whereas the latter refers to so-called **discriminative models** (e.g., Logistic Regression).

Anyway, since the hypothesis space which the function can be selected from is usually very large (in fact, may be also infinite!), how do we choose ?

There are two fundamental approaches for choosing : **empirical risk minimization** and **structural risk minimization**. The former picks the hypothesis function that best fits the training data. The latter includes also a penalty function in order to control the bias/variance tradeoff.

No matter what approach is used to select the hypothesis, we are given a non-negative, real-valued *loss function* .

Generally speaking, measures how different the prediction made by a certain hypothesis when applied to is from the actual value . A typical choice for the function is the *0-1 loss function*, which is defined as:

, where is the *indicator function*. In this particular case, the indicator function is defined on the set of all the possible pairs , and indicates membership of an element in a specific subset of the original domain, namely . The indicator function returns for all the elements of and for all the other elements.

Finally, we define the risk associated with the hypothesis as the *expectation* of the loss function:

.

The ultimate goal of the learning task is thus to find such a hypothesis for which the risk is minimal:

.

**Empirical Risk Minimization**

In general, the risk cannot be computed because the whole joint probability distribution is unknown to the learning algorithm. In fact, we can only operate on a *sample* drawn from such distribution, namely the training set . Thus, an approximation, called *empirical risk* (or *in-sample error*), can be computed by averaging the loss function on the training set :

.

Empirical risk minimization states that the learning algorithm should provide a hypothesis which minimizes the empirical risk above:

.

Note that we removed the factor from the empirical risk minimization since it doesn’t affect the optimization (i.e., the value for which a sum gets minimized also minimizes ).

Therefore, the supervised learning algorithm consists in solving the above optimization problem.

However, as we stated before, a truly effective learning algorithm should be able to devise a hypothesis which in turn can be used to predict *unseen* examples (i.e., those outside the training set).

Unfortunately, with emprirical risk minimization we are guaranteed of very few errors on the training set (i.e., a low in-sample error) but we cannot ensure the learned hypothesis is able to *generalize* on unseen example as well (i.e., a low *out-of-sample* error). For instance, a hypothesis function , which is a lookup table that simply memorizes all the training examples, has the minimum in-sample error () but no ability to generalize on unseen examples. This problem is called **overfitting** and it is mostly caused by the huge size of the hypothesis space which is picked from. Intuitively, not every hypothesis space has the same size. By increasing the size of the set of functions that the learning algorithm can choose from we implicitly increase the *complexity*, and therefore the *flexibility*, of the hypothesis we are going to select. That means that our hypothesis will almost perfectly fit our training examples (i.e., low bias) but will not be able to predict unseen examples correctly (i.e., high variance).

As a side note, let us consider how the size of the hypothesis space may vary.

Generally speaking, can be expressed as follows:

.

Given two sets and the possible number of functions that can be derived using as the **domain** and as the **range** are .

Therefore,

Let us first consider as our hypothesis space, which is made of all the purely conjunctive concepts over the same boolean attributes. Each attribute is required to be *true*, *false*, or *ignored*.

It turns out that is the set of boolean attributes (i.e., ), whereas is the set of possible outcomes for each attribute (i.e., ). Thus, .

Now, assume instead to consider another hypothesis space as the set of all the boolean functions whose domain consists of all the possible boolean -uples. That is, and :

.

Then, what can we say about ?

It is straightforward to see that the set of hypotheses coincides with all the possible truth tables which can be derived from all the possible -uple boolean inputs. The number of possible inputs to any of this hypothesis is thus , namely all the possible binary assignments of a tuple of length . For each of those possible inputs, any function can either output or , i.e., . Overall, we have a total number of possible hypotheses, namely the number of possible hypotheses is exactly the number of possible boolean assignments for a tuple of length .

As it turns out, with just there are possible hypotheses we can choose from!

It results that the latter hypothesis space is far greater than the former, i.e., . Intuitively, this means that is a **more expressive and complex** hypothesis space. From a side, this increases the chance the target function can be expressed (i.e., it is more likely to pick the “right” hypothesis from a larger family of functions). On the other hand, this also increases the number of hypotheses that are consistent with our training set, so it may get worse predictions on unseen examples.

Things get even worst and need to be properly fixed within a specific theory when the size of the hypothesis space becomes infinite. For instance, how many distinct *linear separators* exist in -dimensional Euclidean space ()? Infinitely many! In fact, if we consider the easy case of we are focussing on finding how many lines the space can be partitioned to. More generally, for the hypothesis space coincides with all the possible hyperplanes that divides .

As I said before, there is a measure of the size even for such infinite hypothesis spaces that requires setting up a more advanced theory framework. Please, refer to **Vapnik-Chervonenkis** (**VC**) dimension and **Probabilistic Approximately Correct** (**PAC**) learning.

**Structural Risk Minimization**

Structural risk minimization seeks to prevent overfitting by incorporating a **regularization** penalty into the optimization of the risk function. The regularization penalty can be viewed as implementing a form of **Occam’s razor**, according to which simpler hypotheses should be preferred over more complex ones.

A wide variety of penalties have been employed that correspond to different definitions of complexity.

For instance, consider a typical **linear regression** problem where is the generic input and its predicted value, which is computed from a linear function parametrized by :

.

In such a case, a popular regularization penalty is given by which is the **squared** Euclidean norm of the weights, also known as the norm. Other well-known penalties include the so-called norm, which is computed as , and the norm, which is simply the count of non-zero s, i.e., .

Whether you go for , , or you may indicate such penalty as .

Also, in this scenario a typical empirical risk function is the average of the squared losses, i.e.,

Without considering regularization penalty, the above risk function can be minimized according to the empirical risk minimization we seen before, as follows:

.

In fact, if we consider also the regularization the supervised learning problem aims to find a hypothesis which minimizes this **revisited** risk function:

.

Note that the above optimization differs from the empirical risk minimization due to the penalty factor .

For instance, if , the structural risk minimization is computed as follows:

.

The parameter controls the bias-variance tradeoff. More specifically, when , the structural risk minimization turns into empirical risk minimization, thus providing a hypothesis with low bias and high variance. On the other hand, as increases, the learned hypothesis will have high bias and low variance. The value of can be chosen empirically via **cross validation**.