Overview of the Learning Problem

The fundamental problem in learning from data is proper Model Selection. As we have seen in the previous lectures, a model that is too complex could overfit the training data (causing an estimation error) and a model that is too simple could be a bad approximation of the function that we are trying to estimate (causing an approximation error). The estimation error arises because of the fact that we do not know the true joint distribution of data in the input and output space, and therefore we minimize the empirical risk (which, for each candidate model, is a random number depending on the data) and estimate the average risk again from the limited number of training samples we have. The approximation error measures how well the functions in the chosen model space can approximate the underlying relationship between the output space on the input space, and in general improves as the “size” of our model space increases.

Lecture Outline

In the preceding lectures, we looked at some solutions to deal with the overfitting problem. The basic approach followed was the Method of Sieves, in which the complexity of the model space was chosen as a function of the number of training samples. In particular, both the denoising and classification problems we looked at consider estimators based on histogram partitions. The size of the partition was an increasing function of the number of training samples. In this lecture, we will refine our learning methods further introduce model selection procedures that automatically adapt to the distribution of the training data, rather than basing the model class solely on the number of samples. This sort of adaptivity will play a major role in the design of more effective classifiers and denoising methods. The key to designing data-adaptive model selection procedures is obtaining useful upper bounds on the estimation error. To this end, we will introduce the idea of “Probably Approximately Correct” learning methods.

Structural Risk Minimization (SRM)

The basic idea is to select FnFn based on the training data themselves. Let F1F1, F2F2, ...be a sequence of model spaces of increasing sizes/complexities with

Let

be a function from FkFk that minimizes the empirical risk. This gives us a sequence of selected models f^n,1,f^n,2,⋯f^n,1,f^n,2,⋯ Also associate with each set FkFk a value Cn,k>0Cn,k>0 that measures the complexity or “size” of the set FkFk. Typically, Cn,kCn,k is monotonically increasing with kk (since the sets are of increasing complexity) and decreasing with nn (since we become more confident with more training data). More precisely, suppose that the Cn,kCn,k chosen so that

for some small δ>0δ>0. Then we may conclude that with very high probability (at least 1-δ1-δ) the empirical risk R^nR^n is within Cn,kCn,k of RR uniformly on the class FkFk. This type of bound suffices to bound the estimation error (variance) of the model selection process of the form R(f)≤R^n(f)+Cn,kR(f)≤R^n(f)+Cn,k, and SRM selects the final model by minimizing this bound over all functions in ⋃k≥1Fk⋃k≥1Fk. The selected model is given by f^n,k^f^n,k^, where

A typical example could be the use of VC dimension to characterize the complexity of the collection of model spaces i.e.,Cn,kCn,k is derived from a bound on the estimation error.

Complexity Regularization

Consider a very large class of candidate models FF. To each f∈Ff∈F assign a complexity value Cn(f)Cn(f). Assume that the complexity value is chosen so that

This probability bound also implies an upper bound on the estimation error and complexity regularization is based on the criterion

Complexity Regularization and SRM are very similar and equivalent in certain instances. A distinguishing feature of SRM and complexity reqularization techniques is that the complexity and structure of the model is not fixed prior to examining the data; the data aid in the selection of the best complexity. In fact, the key difference compared to the Method of Sieves is that these techniques can allow the data to play an integral role in deciding where and how to average the data.

Approximation and Estimation Errors

In order to develop complexity regularization schemes we will need to revisit the estimation error / approximation error trade-off. Let f^n=argminf∈FR^n(f)f^n=argminf∈FR^n(f) for some space of models FF.

The approximation error depends on how close f*f* is close to FF, and without making assumptions, this is unknown. The estimation error is quantifiable, and depends on the complexity or size of FF. The error decomposition is illustrated in Figure 1. The estimation error quantifies how much we can “trust” the empirical risk minimization process to select a model close to the best in a given class.

Figure 1: Relationship between the errors

Probability bounds of the forms in Equation 4 and Equation 6 guarantee that the empirical risk is uniformly close to the true risk, and using Equation 4 and Equation 6 it is possible to show that with high probability the selected model f^nf^n satisfies

or

The PAC Learning Model

The estimation error will be small if R(f^n)R(f^n) is close to inff∈FR(f)inff∈FR(f). PAC learning expresses this as follows. We want f^nf^n to be a “probably approximately correct” (PAC) model from FF. Formally, we say that f^nf^n is εε accurate with confidence 1-δ1-δ, or (ε,δ)-(ε,δ)-PAC for short, if

This says that the difference between R(f^n)R(f^n) and inff∈FR(f)inff∈FR(f) is greater than εε with probability less than δδ. Sometimes, especially in the machine learning community, PAC bounds are stated as, “with probability of at least 1-δ1-δ, |R(f^n)-inff∈FR(f)|≤ε|R(f^n)-inff∈FR(f)|≤ε”

To introduce PAC bounds, let us consider a simple case. Let FFconsist of a finite number of models, and let |F||F| denote that number. Furthermore, assume that minf∈FR(f)=0minf∈FR(f)=0.