Final Exam Solution

Description

All questions have multiple-choice answers ([a], [b], [c], …). You can collaborate with others, but do not discuss the selected or excluded choices in the answers. You can consult books and notes, but not other people’s solutions. Your solutions should be based on your own work. De nitions and notation follow the lectures.

Note about the nal

There are twice as many problems in this nal as there are in a homework set, and some problems require packages that will need time to get to work properly.

Problems cover di erent parts of the course. To facilitate your search for rel-evant lecture parts, an indexed version of the lecture video segments can be found at the Machine Learning Video Library:

http://work.caltech.edu/library

To discuss the nal, you are encouraged to take part in the forum http://book.caltech.edu/bookforum

where there is a dedicated subforum for this nal.

Please follow the forum guidelines for posting answers (see the \BEFORE post-ing answers” announcement at the top there).

c 2012-2015 Yaser Abu-Mostafa. All rights reserved. No redistribution in any format. No translation or derivative products without written permission.

Nonlinear transforms

• 1. The polynomial transform of order Q = 10 applied to X of dimension d = 2 re-sults in a Z space of what dimensionality (not counting the constant coordinate x₀ = 1 or z₀ = 1)?

• 1. 1. 12

• 1. 2. 20

• 1. 3. 35

• 1. 4. 100

• 1. 5. None of the above

Bias and Variance

• 2. Recall that the average hypothesis g was based on training the same model H on di erent data sets D to get g^(D) 2 H, and taking the expected value of g^(D) w.r.t. D to get g. Which of the following models H could result in g 62 H?

• 1. 1. A singleton H (H has one hypothesis)

• 1. 2. H is the set of all constant, real-valued hypotheses

• 1. 3. H is the linear regression model

• 1. 4. H is the logistic regression model

• 1. 5. None of the above

Over tting

• 3. Which of the following statements is false?

• 1. 1. If there is over tting, there must be two or more hypotheses that have di erent values of E_in.

• 1. 2. If there is over tting, there must be two or more hypotheses that have di erent values of E_out.

• 1. 3. If there is over tting, there must be two or more hypotheses that have

di erent values of (E_out E_in).

4. We can always determine if there is over tting by comparing the values of

^(Eout ^Ein^).

4. We cannot determine over tting based on one hypothesis only.

• 4. Which of the following statements is true?

• 4. 1. Deterministic noise cannot occur with stochastic noise.

• 4. 2. Deterministic noise does not depend on the hypothesis set.

• 4. 3. Deterministic noise does not depend on the target function.

• 4. 4. Stochastic noise does not depend on the hypothesis set.

• 4. 5. Stochastic noise does not depend on the target distribution.

Regularization

• 4. The regularized weight w_reg is a solution to:

1		N
		X
minimize		(wTxn yn)2 subject to wT T w C;
	N
		n=1

where is a matrix. If w^T_lin ^T w_lin C, where w_lin is the linear regression solution, then what is w_reg?

• 1. 1. w_reg = w_lin

• 1. 2. w_reg = w_lin

• 1. 3. w_reg = ^T w_lin

• 1. 4. w_reg = C w_lin

• 1. 5. w_reg = Cw_lin

• 6. Soft-order constraints that regularize polynomial models can be

• 6. 1. written as hard-order constraints

• 6. 2. translated into augmented error

• 6. 3. determined from the value of the VC dimension

• 6. 4. used to decrease both E_in and E_out

• 6. 5. None of the above is true

Regularized Linear Regression

We are going to experiment with linear regression for classi cation on the processed US Postal Service Zip Code data set from Homework 8. Download the data (extracted features of intensity and symmetry) for training and testing:

http://www.amlbook.com/data/zip/features.train

http://www.amlbook.com/data/zip/features.test

(the format of each row is: digit intensity symmetry). We will train two types of binary classi ers; one-versus-one (one digit is class +1 and another digit is class 1, with the rest of the digits disregarded), and one-versus-all (one digit is class +1 and the rest of the digits are class 1). When evaluating E_in and E_out, use binary classi cation error. Implement the regularized least-squares linear regression

for classi cation that minimizes

1	N	wTzn	yn		2	+wTw
	X
N	n=1					N

where w includes w₀.

7. Set = 1 and do not apply a feature transform (i.e., use z = x = (1; x₁; x₂)). Which among the following classi ers has the lowest E_in?

7. 1. 5 versus all

7. 2. 6 versus all

7. 3. 7 versus all

7. 4. 8 versus all

7. 5. 9 versus all

7. Now, apply a feature transform z = (1; x₁; x₂; x₁x₂; x²₁; x²₂), and set = 1. Which among the following classi ers has the lowest E_out?

7. 1. 0 versus all

7. 2. 1 versus all

7. 3. 2 versus all

7. 4. 3 versus all

7. 5. 4 versus all

7. If we compare using the transform versus not using it, and apply that to ‘0 versus all’ through ‘9 versus all’, which of the following statements is correct for = 1?

7. 1. Over tting always occurs when we use the transform.

7. 2. The transform always improves the out-of-sample performance by at least 5% (E_out with transform 0:95E_out without transform).

7. 3. The transform does not make any di erence in the out-of-sample perfor-mance.

• 1. 4. The transform always worsens the out-of-sample performance by at least 5%.

• 1. 4. The transform improves the out-of-sample performance of ‘5 versus all,’ but by less than 5%.

• 10. Train the ‘1 versus 5’ classi er with z = (1; x₁; x₂; x₁x₂; x²₁; x²₂) with = 0:01 and = 1. Which of the following statements is correct?

• 10. 1. Over tting occurs (from = 1 to = 0:01).

• 10. 2. The two classi ers have the same E_in.

• 10. 3. The two classi ers have the same E_out.

• 10. 4. When goes up, both E_in and E_out go up.

• 10. 5. When goes up, both E_in and E_out go down.

Support Vector Machines

• 10. Consider the following training set generated from a target function f : X ! f 1; +1g where X = R²

x1 = (1; 0); y1 = 1	x2 = (0; 1); y2 = 1		x3 = (0; 1); y3 = 1
x4 = ( 1; 0); y4 = +1 x5 = (0; 2); y5 = +1			x6 = (0; 2); y6 = +1
	x7 = ( 2; 0); y7 = +1
Transform this training set into another two-dimensional space Z
z1 = x22	2x1 1	z2 = x12	2x2 + 1

Using geometry (not quadratic programming), what values of w (without w₀) and b specify the separating plane w^Tz + b = 0 that maximizes the margin in the Z space? The values of w₁; w₂; b are:

1. 1; 1; 0:5

2. 1; 1; 0:5

3. 1; 0; 0:5

4. 0; 1; 0:5

5. None of the above would work.

12. Consider the same training set of the previous problem, but instead of explicitly transforming the input space X , apply the hard-margin SVM algorithm with the kernel

K(x; x⁰) = (1 + x^Tx⁰)²

(which corresponds to a second-order polynomial transformation). Set up the expression for L( ₁::: ₇) and solve for the optimal ₁; :::; ₇ (numerically, using a quadratic programming package). The number of support vectors you get is in what range?

• 1. 0-1

• 2. 2-3

• 3. 4-5

• 4. 6-7

• 5. >7

Radial Basis Functions

We experiment with the RBF model, both in regular form (Lloyd + pseudo-inverse)

with K centers:

sign	K	wk exp	jjx kjj2	+ b!
	Xk
	=1

(notice that there is a bias term), and in kernel form (using the RBF kernel in hard-margin SVM):

!

X

sign _ny_n exp jjx x_njj² + b :

_n>0

The input space is X = [ 1; 1] [ 1; 1] with uniform probability distribution, and the target is

f(x) = sign(x₂ x₁ + 0:25 sin( x₁))

which is slightly nonlinear in the X space. In each run, generate 100 training points at random using this target, and apply both forms of RBF to these training points. Here are some guidelines:

• Repeat the experiment for as many runs as needed to get the answer to be stable (statistically away from ipping to the closest competing answer).

• In case a data set is not separable in the ‘Z space’ by the RBF kernel using hard-margin SVM, discard the run but keep track of how often this happens, if ever.

• When you use Lloyd’s algorithm, initialize the centers to random points in X and iterate until there is no change from iteration to iteration. If a cluster becomes empty, discard the run and repeat.

• 13. For = 1:5, how often do you get a data set that is not separable by the RBF

kernel (using hard-margin SVM)? Hint: Run the hard-margin SVM, then check that the solution has E_in = 0.

• 13. 1. 5% of the time

• 13. 2. > 5% but 10% of the time

• 13. 3. > 10% but 20% of the time

• 13. 4. > 20% but 40% of the time

• 13. 5. > 40% of the time

• 13. If we use K = 9 for regular RBF and take = 1:5, how often does the kernel form beat the regular form (excluding runs mentioned in Problem 13 and runs with empty clusters, if any) in terms of E_out?

• 13. 1. 15% of the time

• 13. 2. > 15% but 30% of the time

• 13. 3. > 30% but 50% of the time

• 13. 4. > 50% but 75% of the time

• 13. 5. > 75% of the time

• 13. If we use K = 12 for regular RBF and take = 1:5, how often does the kernel form beat the regular form (excluding runs mentioned in Problem 13 and runs with empty clusters, if any) in terms of E_out?

• 13. 1. 10% of the time

• 13. 2. > 10% but 30% of the time

• 13. 3. > 30% but 60% of the time

• 13. 4. > 60% but 90% of the time

• 13. 5. > 90% of the time

• 13. Now we focus on regular RBF only, with = 1:5. If we go from K = 9 clusters to K = 12 clusters (only 9 and 12), which of the following 5 cases happens most often in your runs (excluding runs with empty clusters, if any)? Up or down means strictly so.

• 13. 1. E_in goes down, but E_out goes up.

• 1. 2. E_in goes up, but E_out goes down.

• 1. 2. Both E_in and E_out go up.

• 1. 2. Both E_in and E_out go down.

• 1. 2. E_in and E_out remain the same.

• 17. For regular RBF with K = 9, if we go from = 1:5 to = 2 (only 1.5 and 2), which of the following 5 cases happens most often in your runs (excluding runs with empty clusters, if any)? Up or down means strictly so.

• 17. 1. E_in goes down, but E_out goes up.

• 17. 2. E_in goes up, but E_out goes down.

• 17. 3. Both E_in and E_out go up.

• 17. 4. Both E_in and E_out go down.

• 17. 5. E_in and E_out remain the same.

• 17. What is the percentage of time that regular RBF achieves E_in = 0 with K = 9 and = 1:5 (excluding runs with empty clusters, if any)?

• 17. 1. 10% of the time

• 17. 2. > 10% but 20% of the time

• 17. 3. > 20% but 30% of the time

• 17. 4. > 30% but 50% of the time

• 17. 5. > 50% of the time

Bayesian Priors

• 17. Let f 2 [0; 1] be the unknown probability of getting a heart attack for people in a certain population. Notice that f is just a constant, not a function, for simplicity. We want to model f using a hypothesis h 2 [0; 1]. Before we see any data, we assume that P (h = f) is uniform over h 2 [0; 1] (the prior). We pick one person from the population, and it turns out that he or she had a heart attack. Which of the following is true about the posterior probability that h = f given this sample point?

• 17. 1. The posterior is uniform over [0; 1].

• 17. 2. The posterior increases linearly over [0; 1].

• 17. 3. The posterior increases nonlinearly over [0; 1].

• 17. 4. The posterior is a delta function at 1 (implying f has to be 1).

• 17. 5. The posterior cannot be evaluated based on the given information.

Aggregation

• 20. Given two learned hypotheses g₁ and g₂, we construct the aggregate hypothesis g given by g(x) = ¹₂ (g₁(x) + g₂(x)) for all x 2 X . If we use mean-squared error, which of the following statements is true?

• 20. 1. E_out(g) cannot be worse than E_out(g₁).

• 20. 2. E_out(g) cannot be worse than the smaller of E_out(g₁) and E_out(g₂).

• 20. 3. E_out(g) cannot be worse than the average of E_out(g₁) and E_out(g₂).

• 20. 4. E_out(g) has to be between E_out(g₁) and E_out(g₂) (including the end values of that interval).

• 20. 5. None of the above

9