Homework 3 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.

2 ²N

 

Generalization Error

• 1. The modi ed Hoe ding Inequality provides a way to characterize the general-ization error with a probabilistic bound

P [jE_in(g) E_out(g)j > ] 2M e ^{2 2N}

for any > 0. If we set = 0:05 and want the probability bound 2M e

to be at most 0:03, what is the least number of examples N (among the given choices) needed for the case M = 1?

• 1. 1. 500

• 1. 2. 1000

• 1. 3. 1500

• 1. 4. 2000

• 1. 5. More examples are needed.

• 2. Repeat for the case M = 10.

• 2. 1. 500

• 2. 2. 1000

• 2. 3. 1500

• 2. 4. 2000

• 2. 5. More examples are needed.

• 2. Repeat for the case M = 100.

• 2. 1. 500

• 2. 2. 1000

• 2. 3. 1500

• 2. 4. 2000

• 2. 5. More examples are needed.

Break Point

• 2. As shown in class, the (smallest) break point for the Perceptron Model in the two-dimensional case (R²) is 4 points. What is the smallest break point for the Perceptron Model in R³? (i.e., instead of the hypothesis set consisting of separating lines, it consists of separating planes.)

• 1. 1. 4

• 1. 2. 5

• 1. 3. 6

• 1. 4. 7

• 1. 5. 8

Growth Function

• 5. Which of the following are possible formulas for a growth function m_H(N):

i)	1	+ N					iv) 2bN=2c
ii)	1	+ N +				N2	v) 2N
		p	N		N		M
iii)	P			c	i
		ib=1					m = 0 when m > M.
where buc is the biggest integer u, and

• 1. 1. i, v

• 1. 2. i, ii, v

• 1. 3. i, iv, v

• 1. 4. i, ii, iii, v

• 1. 5. i, ii, iii, iv, v

Fun with Intervals

• 6. Consider the \2-intervals” learning model, where h: R ! f 1; +1g and h(x) =

+1 if the point is within either of two arbitrarily chosen intervals and 1 oth-erwise. What is the (smallest) break point for this hypothesis set?

1. 1. 3

1. 2. 4

1. 3. 5

1. 4. 6

1. 5. 7

7. Which of the following is the growth function m_H (N) for the \2-intervals” hypothesis set?

[a]

N+1

+ 1

[b]

N

2

4

+1

[c]

4

+

N

2

+ 1

N+1

+1

[d]

N+1

+

N+1

+

N+1

+

N+1

+ 1

4

3

2

1

• 1. 5. None of the above

• 8. Now, consider the general case: the \M-intervals” learning model. Again h : R ! f 1; +1g, where h(x) = +1 if the point falls inside any of M arbitrarily chosen intervals, otherwise h(x) = 1. What is the (smallest) break point of this hypothesis set?

• 8. 1. M

• 8. 2. M + 1

• 8. 3. M²

• 8. 4. 2M +1

• 8. 5. 2M 1

Convex Sets: The Triangle

• 8. Consider the \triangle” learning model, where h : R² ! f 1; +1g and h(x) =

+1 if x lies within an arbitrarily chosen triangle in the plane and 1 otherwise. Which is the largest number of points in R² (among the given choices) that can be shattered by this hypothesis set?

• 1. 1. 1

• 1. 2. 3

• 1. 3. 5

• 1. 4. 7

• 1. 5. 9

Non-Convex Sets: Concentric Circles

• 10. Compute the growth function m_H(N) for the learning model made up of two concentric circles in R². Speci cally, H contains the functions which are +1 for

a² x²₁ + x²₂ b²

and 1 otherwise. The growth function is

[a]	N + 1
[b]	N+1		+ 1
[c]	N+1		+ 1
	2
	3

4. 2N²+1

4. None of the above

5