0.3 Introduction to complexity regularization

Competing goals: the bias-variance tradeoff

We ended the previous lecture with a brief discussion of overfitting. Recall that, given a set of $n$ data points, $D_n$ , and a space of functions (or models ) $\mathcal{F}$ , our goal in solving the learning from data problem is to choose a function ${\widehat{f}}_n\in \mathcal{F}$ which minimizes the expected risk $E\left[R,\left(,{\widehat{f}}_n,\right)\right]$ , where the expectation is being taken over the distribution $P_{XY}$ on the data points $D_n$ . One approach to avoiding overfitting is to restrict $\mathcal{F}$ to some subset of all measurable function. To gauge the performance of a given $f$ in this case, we examine the difference between the expected risk of $f$ and the Bayes' risk (called the excess risk ).

The approximation error term quantifies the performance hit incurred by imposing restrictions on $\mathcal{F}$ . The estimation error term is due to the randomness of the training data, and it expresses how well the chosen function ${\widehat{f}}_n$ will perform in relation to the best possible $f$ in the class $\mathcal{F}$ . This decomposition into stochastic and approximation errors is similar to the bias-variancetradeoff which arises in classical estimation theory. The approximation error is like a bias squared term, and the estimationerror is like a variance term. By allowing the space $\mathcal{F}$ to be large When we say $\mathcal{F}$ is large, we mean that $\left|\mathcal{F}\right|$ , the number of elements in $\mathcal{F}$ , is large. we can make the approximation error as small as we want at the cost of incurring a large estimationerror. On the other hand, if $\mathcal{F}$ is very small then the approximation error will be large, but the estimation error may be very small.This tradeoff is illustrated in [link] .

Why is this the case? We do not know the true distribution $P_{XY}$ on the data, so instead of minimizing the expected risk of we design a predictor by minimizing the empirical risk:

If $\mathcal{F}$ is very large then ${\widehat{R}}_n\left(f\right)$ can be made arbitrarily small and the resulting ${\widehat{f}}_n$ can “overfit” to the data since ${\widehat{R}}_n\left(f\right)$ is not a good estimator of the true risk $R\left({\widehat{f}}_n\right)$ .

The behavior of the true and empirical risks, as a function of the size (or complexity ) of the space $\mathcal{F}$ , is illustrated in [link] . Unfortunately, we can't easily determine whether we are over or underfitting just by looking at the empirical risk.

Strategies to avoid overfitting

Picking

is problematic if $\mathcal{F}$ is large. We will examine two general approaches to dealing with this problem:

1. Restrict the size or dimension of $\mathcal{F}$ (e.g., restrict $\mathcal{F}$ to the set of all lines, or polynomials with maximum degree $d$ ). This effectively places an upper bound on the estimation error, but ingeneral it also places a lower bound on the approximation error.
2. Modify the empirical risk criterion to include an extra cost associated with each model (e.g., higher cost for more complexmodels):
   $$\begin{array}{ccc}\hfill {\widehat{f}}_n& =& arg\underset{f\in \mathcal{F}}{min}\left\{{\widehat{R}}_n,\left(f\right),+,C,\left(f\right)\right\}.\hfill \end{array}$$
   The cost is designed to mimic the behavior of the estimation error so that the model selection procedure avoids models with a estimation error.Roughly this can be interpreted as trying to balance the tradeoff illustrated in [link] . Procedures of this type are often called complexity penalization methods.