0.3 Introduction to complexity regularization  (Page 3/3)

The number of unique labellings of the training data that can be achieved with linear classifiers is, in fact, finite. A line can bedefined by picking any pair of training points, as illustrated in [link] . Two classifiers can be defined from each such line: one that outputs a label “1” for everything on or abovethe line, and another that outputs “0” for everything on or above. There exist $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ such pairs of training points, and these define all possible unique labellings of the training data.Therefore, there are at most $2\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ unique linear classifiers for any random set of $n$ 2-dimensional features (the factor of 2 is due to the fact that for each linear classifier thereare 2 possible assignments of the labelling).

Thus, instead of infinitely many linear classifiers, we realize that as far as a random sample of $n$ training data is concerned, there are at most

unique linear classifiers. That is, using linear classification rules, there are at most $n(n-1)\approx n^2$ unique label assignments for $n$ data points. If we like, we can encode each possibility with ${log}_{2}n(n-1)\approx 2{log}_{2}n$ bits. In $d$ dimensions there are $2\left(\genfrac{}{}{0pt}{}{n}{d}\right)$ hyperplane classification rules which can be encoded in roughly $d{log}_{2}n$ bits. Roughly speaking, the number of bits required for encoding each model is the VC dimension. Theremarkable aspect of the VC dimension is that it is often finite even when $\mathcal{F}$ is infinite (as in this example).

If $\mathcal{X}$ has $d$ dimensions in total, we might consider linear classifiers based on $1,2,\cdots ,d$ features at a time. Lower dimensional hyperplanes are less complex than higher dimensionalones. Suppose we set

These spaces have increasing VC dimensions, and we can try to balance the empirical risk and a cost function depending on the VC dimension.Such procedures are often referred to as Structural Risk Minimization . This gives you a glimpse of what the VC dimension is all about. In future lectures we will revisit this topic in greaterdetail.

Hold-out methods

The basic idea of “hold-out” methods is to split the $n$ samples $D\equiv {\{X_i,Y_i\}}_{i=1}^n$ into a training set, $D_T$ , and a test set, $D_V$ .

Now, suppose we have a collection of different model spaces $\left\{{\mathcal{F}}_{\lambda }\right\}$ indexed by $\lambda \in \Lambda$ (e.g., ${\mathcal{F}}_{\lambda }$ is the set of polynomials of degree $d$ , with $\lambda =d$ ), or suppose that we have a collection of complexity penalization criteria $L_{\lambda }\left(f\right)$ indexed by $\lambda$ ( e.g., let $L_{\lambda }\left(f\right)=\widehat{R}\left(f\right)+\lambda c\left(f\right)$ , with $\lambda \in {\mathbf{R}}^{+}$ ). We can obtain candidate solutions using the training set as follows. Define

and take

or

This provides us with a set of candidate solutions $\left\{{\widehat{f}}_{\lambda }\right\}$ . Then we can define the hold-out error estimate using the test set:

and select the “best” model to be $\widehat{f}={\widehat{f}}_{\widehat{\lambda }}$ where

This type of procedure has many nice theoretical guarantees, provided both the training and test set grow with $n$ .

Leaving-one-out cross-validation

A very popular hold-out method is the so call “leaving-one-out cross-validation” studied in depth by Grace Wahba (UW-Madison,Statistics). For each $\lambda$ we compute

or

Then we have cross-validation function

Summary

To summarize, this lecture gave a brief and incomplete survey of different methods for dealing with the issues of overfitting and modelselection. Given a set of training data, $D_n={\{X_i,Y_i\}}_{i=1}^n$ , our overall goal is to find

from some collection of functions, $\mathcal{F}$ . Because we do not know the true distribution $P_{XY}$ underlyingthe data points $D_n$ , it is difficult to get an exact handle on the risk, $R\left(f\right)$ . If we only focus on minimizing the empirical risk $\widehat{R}\left(f\right)$ we end up overfitting to the training data. Two general approaches were presented.

1. In the first approach we consider an indexed collection of spaces ${\left\{{\mathcal{F}}_{\lambda }\right\}}_{\lambda \in \Lambda }$ such that the complexity of ${\mathcal{F}}_{\lambda }$ increases as $\lambda$ increases, and
   $$\underset{\lambda \to \infty }{lim}{\mathcal{F}}_{\lambda }=\mathcal{F}.$$
   A solution is given by
   $$\begin{array}{c}\hfill {\widehat{f}}_{{\lambda }^{*}}=arg\underset{f\in {\mathcal{F}}_{{\lambda }^{*}}}{min}{\widehat{R}}_n\left(f\right)\end{array}$$
   where either ${\lambda }^{*}$ is a function which increases with $n$ ,
   $$\begin{array}{ccc}\hfill {\lambda }^{*}& =& \lambda \left(n\right),\hfill \end{array}$$
   or ${\lambda }^{*}$ is chosen by hold-out validation.
2. The alternative approach is to incorporate a penalty term into the risk minimization problem formulation. Here we consideran indexed collection of penalties ${\left\{C_{\lambda }\right\}}_{\lambda \in \Lambda }$ satisfying the following properties:
   1. $C_{\lambda }:\mathcal{F}\to {\mathbf{R}}^{+}$ ;
   2. For each $f\in \mathcal{F}$ and ${\lambda }_1<{\lambda }_2$ we have $C_{{\lambda }_1}\left(f\right)\le C_{{\lambda }_2}\left(f\right)$ ;
   3. There exists ${\lambda }_0\in \Lambda$ such that $C_{{\lambda }_0}\left(f\right)=0$ for all $f\in \mathcal{F}$ .
   In this formulation we find a solution
   $$\begin{array}{ccc}\hfill {\widehat{f}}_{{\lambda }^{*}}& =& arg\underset{f\in \mathcal{F}}{min}{\widehat{R}}_n\left(f\right)+C_{{\lambda }^{*}}\left(f\right),\hfill \end{array}$$
   where either ${\lambda }^{*}=\lambda \left(n\right)$ , a function growing the number of data samples $n$ , or ${\lambda }^{*}$ is selected by hold-out validation.

Consistency

If an estimator or classifier ${\widehat{f}}_{{\lambda }^{*}}$ satisfies

then we say that ${\widehat{f}}_{{\lambda }^{*}}$ is $\mathcal{F}$ -consistent with respect to the risk $R$ . When the context is clear, we will simply say that $\widehat{f}$ is consistent.