Pattern Classification

Recall that the goal of classification is to learn a mapping from the feature space, XX, to a label space, YY. This mapping, ff, is called a classifier. For example, we might have

We can measure the loss of our classifier using 0-10-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.

Definition 1: (Bayes' Risk)

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

R * = inf f R ( f ) . R * = inf f R ( f ) . (4)

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

Definition 2: Bayes Classifier

The Bayes classifier is the following mapping:

f * ( x ) = 1 , η ( x ) ≥ 1 / 2 0 , o t h e r w i s e f * ( x ) = 1 , η ( x ) ≥ 1 / 2 0 , o t h e r w i s e (5)

where

η ( x ) ≡ P Y | X ( Y = 1 | X = x ) . η ( x ) ≡ P Y | X ( Y = 1 | X = x ) . (6)

Note that for any xx, f*(x)f*(x) is the value of y∈{0,1}y∈{0,1} that maximizes PXY(Y=y|X=x)PXY(Y=y|X=x).

Note that while the Bayes classifier achieves the Bayes risk, in practice this classifier is not realizable because we do not know the distribution PXYPXY and so cannot construct η(x)η(x).

Regression

The goal of regression is to learn a mapping from the input space, XX, to the output space, YY. This mapping, ff, 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:

Empirical Risk Minimization

Definition 3: Empirical Risk

Let {Xi,Yi}i=1n∼iidPXY{Xi,Yi}i=1n∼iidPXY be a collection of training data. Then the empirical risk is defined as

R ^ n ( f ) = 1 n ∑ i = 1 n ℓ ( f ( X i ) , Y i ) . R ^ n ( f ) = 1 n ∑ i = 1 n ℓ ( f ( X i ) , Y i ) . (22)

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

f ^ n = arg min f ∈ F R ^ n ( f ) . f ^ n = arg min f ∈ F R ^ n ( f ) . (23)

Example 1: Pattern Classification

Let the set of possible classifiers be

F = x ↦ sign ( w ' x ) : w ∈ R d F = x ↦ sign ( w ' x ) : w ∈ R d (24)

and let the feature space, XX, be [0,1]d[0,1]d or RdRd. If we use the notation fw(x)≡sign(w'x)fw(x)≡sign(w'x), then the set of classifiers can be alternatively represented as

F = f w : w ∈ R d . F = f w : w ∈ R d . (25)

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

f ^ n = arg min f ∈ F R ^ n ( f ) = arg min w ∈ R d 1 n ∑ i = 1 n 1 { sign ( w ' X i ) ≠ Y i } . f ^ n = arg min f ∈ F R ^ n ( f ) = arg min w ∈ R d 1 n ∑ i = 1 n 1 { sign ( w ' X i ) ≠ Y i } . (26)

Figure 1: Example linear classifier for two-class problem.

Example 2: Regression

Let the feature space be

X = [ 0 , 1 ] X = [ 0 , 1 ] (27)

and let the set of possible estimators be

F = degree d polynomials on [ 0 , 1 ] . F = degree d polynomials on [ 0 , 1 ] . (28)

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

f ^ n = arg min f ∈ F R ^ n ( f ) = arg min f ∈ F 1 n ∑ i = 1 n ( f ( X i ) - Y i ) 2 . f ^ n = arg min f ∈ F R ^ n ( f ) = arg min f ∈ F 1 n ∑ i = 1 n ( f ( X i ) - Y i ) 2 . (29)

Alternatively, this can be expressed as

w ^ = arg min w ∈ R d + 1 1 n ∑ i = 1 n ( w 0 + w 1 X i + ... + w d X i d - Y i ) 2 = arg min w ∈ R d + 1 ∥ V w - Y ∥ 2 w ^ = arg min w ∈ R d + 1 1 n ∑ i = 1 n ( w 0 + w 1 X i + ... + w d X i d - Y i ) 2 = arg min w ∈ R d + 1 ∥ V w - Y ∥ 2 (30)

where VV is the Vandermonde matrix

V = 1 X 1 ... X 1 d 1 X 2 ... X 2 d ⋮ ⋮ ⋱ ⋮ 1 X n ... X n d . V = 1 X 1 ... X 1 d 1 X 2 ... X 2 d ⋮ ⋮ ⋱ ⋮ 1 X n ... X n d . (31)

The pseudoinverse can be used to solve for w^:w^:

w ^ = ( V ' V ) - 1 V ' Y . w ^ = ( V ' V ) - 1 V ' Y . (32)

A polynomial estimate is displayed in Figure 2.

Figure 2: Example polynomial estimator. Blue curve denotes f*f*, magenta curve is the polynomial fit to the data (denoted by dots).

Overfitting

Suppose FF, our collection of candidate functions, is very large. We can always make

smaller by increasing the cardinality of FF, thereby providing more possibilities to fit to the data.

Consider this extreme example: Let FF be all measurable functions. Then every function ff for which

has zero empirical risk (R^n(f)=0R^n(f)=0). However, clearly this could be a very poor predictor of YY for a new input XX .

Example 3: Classification Overfitting

Consider the classifier in Figure 3; 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 Figure 1; the overfitting would result in a higher probability of error for predicting classes of future observations.

Figure 3: Example of overfitting classifier. The classifier's decision boundary wiggles around in order to correctly label the training data, but the optimal Bayes classifier is a straight line.

Example 4: 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/04
clear
close all
 
% generate and plot "true" function
t = (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);
end
p = inv(V'*V)*V'*y;
 
for i=1:k
    Vt(:,i) = t.^(i-1);
end
yh = Vt*p;
figure(1)
clf
plot(t,f)
hold on
plot(x,y,'.')
plot(t,yh,'m')
 

Figure 4: Example polynomial fitting problem. Blue curve is f*f*, magenta curve is the polynomial fit to the data (dots). (a) Fitting a polynomial of degree d=0d=0: This is an example of underfitting (b)d=2d=2 (c) d=4d=4 (d) d=6d=6: This is an example of overfitting. The empirical loss is zero, but clearly the estimator would not do a good job of predicting yy when xx is close to one.

(a) (b) (c) (d)