Homework 4 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 homework

The goal of the homework is to facilitate a deeper understanding of the course material. The questions are not designed to be puzzles with catchy answers. They are meant to make you roll up your sleeves, face uncertainties, and ap-proach the problem from di erent angles.

The problems range from easy to di cult, and from practical to theoretical. Some problems require running a full experiment to arrive at the answer.

The answer may not be obvious or numerically close to one of the choices, but one (and only one) choice will be correct if you follow the instructions precisely in each problem. You are encouraged to explore the problem further by experimenting with variations on these instructions, for the learning bene t.

You are also encouraged to take part in the forum http://book.caltech.edu/bookforum

where there are many threads about each homework set. We hope that you will contribute to the discussion as well. Please follow the forum guidelines for posting answers (see the \BEFORE posting 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.

Generalization Error

In Problems 1-3, we look at generalization bounds numerically. For N > d_vc, use the simple approximate bound N^dvc for the growth function m_H(N).

1. For an H with d_vc = 10, if you want 95% con dence that your generalization error is at most 0.05, what is the closest numerical approximation of the sample size that the VC generalization bound predicts?

1. 1. 400,000

1. 2. 420,000

1. 3. 440,000

1. 4. 460,000

1. 5. 480,000

2. There are a number of bounds on the generalization error , all holding with probability at least 1 . Fix d_vc = 50 and = 0:05 and plot these bounds as a function of N. Which bound is the smallest for very large N, say N = 10; 000? Note that [c] and [d] are implicit bounds in .

8

4m

(2N)

[a]

Original VC bound:q

ln

H

N

[b]

Rademacher Penalty Bound:q

2 ln(2Nm

H

(N))

+ q

2

ln

1

+

1

N

N

N

q

N

2

[c]

Parrondo and Van den Broek:

1

(2 + ln

6mH(2N)

)

1

4m

(N )

[d]

Devroye:q

(4 (1 + ) + ln

H

)

2N

1. 5. They are all equal.

3. For the same values of d_vc and of Problem 2, but for small N, say N = 5, which bound is the smallest?

8

4m

(2N)

[a]

Original VC bound:q

ln

H

N

[b]

Rademacher Penalty Bound:q

2 ln(2Nm

H

(N))

+ q

2

ln

1

+

1

N

N

N

q

N

2

[c]

Parrondo and Van den Broek:

1

(2 + ln

6mH(2N)

)

1

4m

(N )

[d]

Devroye:q

(4 (1 + ) + ln

H

)

2N

5. They are all equal.

Bias and Variance

Consider the case where the target function f : [ 1; 1] ! R is given by f(x) = sin( x) and the input probability distribution is uniform on [ 1; 1]. Assume that the training set has only two examples (picked independently), and that the learning algorithm produces the hypothesis that minimizes the mean squared error on the examples.

4. Assume the learning model consists of all hypotheses of the form h(x) = ax. What is the expected value, g(x), of the hypothesis produced by the learning algorithm (expected value with respect to the data set)? Express your g(x) as ax^, and round a^ to two decimal digits only, then match exactly to one of the following answers.

4. 1. g(x) = 0

4. 2. g(x) = 0:79x

4. 3. g(x) = 1:07x

4. 4. g(x) = 1:58x

4. 5. None of the above

4. What is the closest value to the bias in this case?

4. 1. 0.1

4. 2. 0.3

4. 3. 0.5

4. 4. 0.7

4. 5. 1.0

4. What is the closest value to the variance in this case?

4. 1. 0.2

4. 2. 0.4

4. 3. 0.6

4. 4. 0.8

4. 5. 1.0

4. Now, let’s change H. Which of the following learning models has the least expected value of out-of-sample error?

4. 1. Hypotheses of the form h(x) = b

4. 2. Hypotheses of the form h(x) = ax

• 1. 3. Hypotheses of the form h(x) = ax + b

• 1. 3. Hypotheses of the form h(x) = ax²

• 1. 3. Hypotheses of the form h(x) = ax² + b

VC Dimension

• 8. Assume q 1 is an integer and let m_H(1) = 2. What is the VC dimension of a

hypothesis set whose growth function satis es: m_H(N + 1) = 2m_H(N) ^N_q ? Recall that ^M_m = 0 when m > M.

[a] q 2

[b] q 1

[c] q

[d] q + 1

[e] None of the above

9. For hypothesis sets H₁; H₂; :::; H_K with nite, positive VC dimensions d_vc(H_k), some of the following bounds are correct and some are not. Which among the correct ones is the tightest bound (the smallest range of values) on the VC dimension of the intersection of the sets: d_vc(^TK_k=1H_k)? (The VC dimension of an empty set or a singleton set is taken as zero)

[a] 0 d_vc(^TK H_k) ^PK d_vc(H_k)

k=1 k=1

[b] 0 d_vc(^TK_k=1H_k) minfd_vc(H_k)g^K_k=1

[c] 0 d_vc(^TK_k=1H_k) maxfd_vc(H_k)g^K_k=1

[d] minfd_vc(H_k)g^K_k=1 d_vc(^TK_k=1H_k) maxfd_vc(H_k)g^K_k=1

[e] minfd_vc(H_k)g^K_k=1 d_vc(^TK_k=1H_k) ^PK_k=1 d_vc(H_k)

10. For hypothesis sets H₁; H₂; :::; H_K with nite, positive VC dimensions d_vc(H_k), some of the following bounds are correct and some are not. Which among the correct ones is the tightest bound (the smallest range of values) on the VC dimension of the union of the sets: d_vc(^SK_k=1H_k)?

[a] 0		dvc(	S	K	H	k)	P	K dvc(	k)
				K				k=1	HK
				k=1
[b] 0	dvc(Sk=1Hk)						K	1 + Pk=1 dvc(Hk)

[c] minfdvc(Hk)gkK=1 dvc(SkK=1Hk)							PkK=1 dvc(Hk)
f H	gK			S	K	H	K		HK
			dvc(		K		Pk=1	dvc(
[d] max dvc( k)	kK=1				k=1	k)			k)
[e] maxfdvc(Hk)gk=1		dvc(		Sk=1Hk)			K 1 + Pk=1 dvc(Hk)

5