Solved–Assignment #2 –SOlution

Description

Problem 1 (20 Points)

This problem investigates how changing the error measure can change the result of the learning process.

You have N data points y₁ y_N and wish to estimate a ‘representative’ value.

1. [10 pts] If your algorithm is to find the hypothesis h that minimizes the in-sample sum of squared deviations,

N

X

E_in(h) = (h y_n)²;

n=1

then show that your estimate will be the in sample mean,

N

1 X

^hmean ⁼ _{N n=1} ^yn^:

2. [10 pts] If your algorithm is to find the hypothesis h that minimizes the in-sample sum of absolute deviations,

N

X

E_in(h) = jh y_nj;

n=1

then show that your estimate will be the in-sample median h_med, which is any value for which half the data points are at most h_med and half the data points are at least h_med.

Problem 2 (20 Points)

Consider

e_n(w) = max(0; 1 y_nw^>x_n):

1. [5 pts] Show that e_n(w) is continuous and differentiable except when y_n = w>x_n.

2. [5 pts] Show that e_n(w) is an upper bound for the “0-1 loss” or [[sign(w^>x_n) 6= y_n]]. Thus, _{N n=1} e_n(w) is an upper bound for the in-sample classification error E_in(w).1P^N

Note: e_n (w) corresponds to the “hinge loss” used for maximum-margin classification, most notably for support vector machines (SVMs).

Problem 3 (20 Points)

There are a number of bounds on the generalization error , all holding with probability at least 1 .

Note that (c) and (d) are implicit bounds in . Fix d_VC = 50 and = 0:05. Plot these bounds as a function of N. Which is the best?

Problem 4 (20 Points)

The bias-variance decomposition of out-of-sample error is based on squared error measures. Recall that the out-of-sample error is given by

h i

E_out g^(D) = E_x (g^(D)(x) f(x))² (1)

where E_x denotes the expected value with respect to input x, and using g(D) is to make explicit the dependence of g on data D. From (1) we can remove the dependence on D by taking average:

E_D ^hE_out(g^(D))ⁱ = bias + var

where bias , E_x [bias(x)] and var , E_x [var(x)].

Problem 5 (20 Points)

In support vector machines, the hyperplane h separates the data if and only if it can be represented by weights (b; w) that satisfy

			min	yn(w>xn + b) = 1:				(3)
			n=1;:::;N
Consider the data below and a ‘hyperplane’ (b; w) that separates the data.
X =	22	23	y =	2 13	w =	3:2	b = 0:5
	0	0		1		1:2
	2	0		+1
	4	5		4 5

(a) [10 pts] Compute

= min y_n(w^>x_n + b):

1;:::;N

2. [5 pts] Compute the weights 1 (b; w) and show that they satisfy Eq (3).

2. [5 pts] Plot both hyperplanes to show that they are the same separator.

Note: This problem is to give a concrete example of re-normalizing the weights to show that the condition (3) and the following condition are equivalent, as covered at class:

yn(w>xn + b) > 0:

(4)