0.2 Introduction to classification and regression

Pattern classification

Recall that the goal of classification is to learn a mapping from the feature space, $\mathcal{X}$ , to a label space, $\mathcal{Y}$ . This mapping, $f$ , is called a classifier . For example, we might have

We can measure the loss of our classifier using $0-1$ loss; i.e.,

Recalling that risk is defined to be the expected value of the loss function, we have

The performance of a given classifier can be evaluated in terms of how close its risk is to the Bayes' risk.

(Bayes' Risk)

The Bayes' risk is the infimum of the risk for all classifiers:

$$R^{*}=\underset{f}{inf}R\left(f\right).$$

We can prove that the Bayes risk is achieved by the Bayes classifier.

Bayes Classifier

The Bayes classifier is the following mapping:

$$f^{*}\left(x\right)=\left\{\begin{array}{cc}1,\hfill & \eta \left(x\right)\ge 1/2\hfill \\ 0,\hfill & otherwise\hfill \end{array}\right)$$

where

$$\eta \left(x\right)\equiv P_{Y|X}(Y=1|X=x).$$

Note that for any $x$ , $f^{*}\left(x\right)$ is the value of $y\in \{0,1\}$ that maximizes $P_{XY}(Y=y|X=x)$ .

Risk of the bayes classifier

Let $g\left(x\right)$ be any classifier. We will show that

For any $g$ ,

Next consider the difference

where the second equality follows by noting that ${\mathbf{1}}_{\left\{g\right(x)=0\}}=1-{\mathbf{1}}_{\left\{g\right(x)=1\}}$ . Next recall

For $x$ such that $\eta \left(x\right)\ge 1/2$ , we have

and for $x$ such that $\eta \left(x\right)<1/2$ , we have

which implies

or

Note that while the Bayes classifier achieves the Bayes risk, in practice this classifier is not realizable because we do not know the distribution $P_{XY}$ and so cannot construct $\eta \left(x\right)$ .

Regression

The goal of regression is to learn a mapping from the input space, $\mathcal{X}$ , to the output space, $\mathcal{Y}$ . This mapping, $f$ , is called a estimator . For example, we might have

We can measure the loss of our estimator using squared error loss; i.e.,

Recalling that risk is defined to be the expected value of the loss function, we have

The performance of a given estimator can be evaluated in terms of how close the risk is to the infimum of the risk for all estimator under consideration:

Minimum risk under squared error loss (mse)

Let $f^{*}\left(x\right)=E_{Y|X}\left[Y\right|X=x]$

Empirical risk minimization

Empirical Risk

Let ${\{X_i,Y_i\}}_{i=1}^n\stackrel{iid}{\sim }{P}_{XY}$ be a collection of training data. Then the empirical risk is defined as

$${\widehat{R}}_n\left(f\right)=\frac{1}{n}\sum _{i=1}^n\ell (f\left(X_i\right),Y_i).$$

Empirical risk minimization is the process of choosing a learning rule which minimizes the empirical risk; i.e.,

$${\widehat{f}}_n=arg\underset{f\in \mathcal{F}}{min}{\widehat{R}}_n\left(f\right).$$

Pattern classification

Let the set of possible classifiers be

$$\mathcal{F}=\left\{x,\mapsto ,\text{sign},\left(w^{\text{'}}x\right),:,w,\in ,{\mathbf{R}}^d\right\}$$

and let the feature space, $\mathcal{X}$ , be ${[0,1]}^d$ or ${\mathbf{R}}^d$ . If we use the notation $f_w\left(x\right)\equiv \text{sign}\left(w^{\text{'}}x\right)$ , then the set of classifiers can be alternatively represented as

$$\mathcal{F}=\left\{f_w,:,w,\in ,{\mathbf{R}}^d\right\}.$$

In this case, the classifier which minimizes the empirical risk is

$$\begin{array}{ccc}\hfill {\widehat{f}}_n& =& arg\underset{f\in \mathcal{F}}{min}{\widehat{R}}_n\left(f\right)\hfill \\ & =& arg\underset{w\in {\mathbf{R}}^d}{min}\frac{1}{n}\sum _{i=1}^n{\mathbf{1}}_{\{\text{sign}\left(w^{\text{'}}{X}_i\right)\ne Y_i\}}.\hfill \end{array}$$

Regression

Let the feature space be

$$\mathcal{X}=[0,1]$$

and let the set of possible estimators be

$$\mathcal{F}=\left\{\text{degree},,d,,\text{polynomials},,\text{on},,[0,1]\right\}.$$

In this case, the classifier which minimizes the empirical risk is

$$\begin{array}{ccc}\hfill {\widehat{f}}_n& =& arg\underset{f\in \mathcal{F}}{min}{\widehat{R}}_n\left(f\right)\hfill \\ & =& arg\underset{f\in \mathcal{F}}{min}\frac{1}{n}\sum _{i=1}^n{(f\left(X_i\right)-Y_i)}^2.\hfill \end{array}$$

Alternatively, this can be expressed as

$$\begin{array}{ccc}\hfill \widehat{w}& =& arg\underset{w\in {\mathbf{R}}^{d+1}}{min}\frac{1}{n}\sum _{i=1}^n{(w_0+w_1{X}_i+...+w_d{X}_i^d-Y_i)}^2\hfill \\ & =& arg\underset{w\in {\mathbf{R}}^{d+1}}{min}{\parallel Vw-Y\parallel }^2\hfill \end{array}$$

where $V$ is the Vandermonde matrix

$$V=\left[\begin{array}{cccc}1& X_1& ...& X_1^d\\ 1& X_2& ...& X_2^d\\ ⋮& ⋮& \ddots & ⋮\\ 1& X_n& ...& X_n^d\end{array}\right].$$

The pseudoinverse can be used to solve for $\widehat{w}:$

$$\widehat{w}={\left(V^{\text{'}}V\right)}^{-1}{V}^{\text{'}}Y.$$

A polynomial estimate is displayed in [link] .

Overfitting

Suppose $\mathcal{F}$ , our collection of candidate functions, is very large. We can always make

smaller by increasing the cardinality of $\mathcal{F}$ , thereby providing more possibilities to fit to the data.

Consider this extreme example: Let $\mathcal{F}$ be all measurable functions. Then every function $f$ for which

has zero empirical risk ( ${\widehat{R}}_n\left(f\right)=0$ ). However, clearly this could be a very poor predictor of $Y$ for a new input $X$ .

Classification overfitting

Consider the classifier in [link] ; this demonstrates overfitting in classification. If the data were in fact generated from two Gaussian distributions centered in the upper left and lower right quadrants of the feature space domain, then the optimal estimator would be the linear estimator in [link] ; the overfitting would result in a higher probability of error for predicting classes of future observations.

Regression overfitting

Below is an m-file that simulates the polynomial fitting. Feel free to play around with it to get an idea of the overfitting problem.

% poly fitting % rob nowak  1/24/04clear close all  % generate and plot "true" functiont = (0:.001:1)'; f = exp(-5*(t-.3).^2)+.5*exp(-100*(t-.5).^2)+.5*exp(-100*(t-.75).^2);figure(1) plot(t,f)  % generate n training data & plot n = 10;sig = 0.1; % std of noise x = .97*rand(n,1)+.01;y = exp(-5*(x-.3).^2)+.5*exp(-100*(x-.5).^2)+.5*exp(-100*(x-.75).^2)+sig*randn(size(x)); figure(1)clf plot(t,f)hold on plot(x,y,'.')  % fit with polynomial of order k  (poly degree up to k-1)k=3; for i=1:k    V(:,i) = x.^(i-1); endp = inv(V'*V)*V'*y;  for i=1:k     Vt(:,i) = t.^(i-1);end yh = Vt*p;figure(1) clfplot(t,f) hold onplot(x,y,'.') plot(t,yh,'m')