EE 660 Homework Week 5

p. 1 of 2
EE 660 Homework Week 5
1. Consider the email spam classification problem of Murphy Problem 8.1. Suppose you
intend to use a linear perceptron classifier on that data. In the parts below, unless
stated otherwise, assume the dataset of samples is split into for
training and for testing. Also, for the tolerance in the VC
generalization bound, use 0.1 (for a certainty of 0.9). The parts below have short
answers.
Hint: You may use the relation that if is a linear perceptron classifier in D
dimensions (D features), . ( This will be proved in Problem 2.)
a) What is the VC dimension of the hypothesis set?
b) Expressing the upper bound on the out-of-sample error as
For measured on the training data, use from part (a) to get a value
for .
c) To get a lower , suppose you reduce the number of features to , and
also increase the training set size to 10,000. Now what is ?
d) Suppose that you had control over the number of training samples (by
collecting more email data). How many training samples would ensure a
generalization error of again with probability 0.9 (the same tolerance
), and using the reduced feature set (10 features)?
e) Instead suppose you use the test set to measure , so let’s call it .
What is the hypothesis set now? What is its cardinality?
f) Continuing from part (e), use the bound:
Use the original feature set and the original test set, so that . Give an
appropriate expression for and calculate it numerically.
2. AML Exercise 2.4 (page 52). In addition to the hints given in the book, you can solve
the problem by following the steps outlined below (on the next page).
N = 4601 NTr = 3000
NTest = 1601 δ
H
dVC (H ) = D +1
Eout h( g ) ≤ Ein h( g ) + ε vc
Ein h( g ) dvc
ε vc
ε vc D = 10
ε vc
NTr
ε vc = 0.1
δ = 0.1
Ein h( g ) Etest h( g )
Eout h( g ) ≤ Etest h( g ) + ε
NTest = 1601
ε
p. 2 of 2
For part (a):
i. Write a point as a dimensional vector;
ii. Construct the matrix suggested by the book;
iii. Write , the output of the perceptron, as function of and the weights
(note that is a dimensional vector with elements +1 and -1);
iv. Using the nonsingularity of , justify how any can be obtained.
For part (b):
i. Write a point as a linear combination of the other points;
ii. Write (output for the chosen point) and substitute the value of by the
expression just found on the previous item (Hint: use the function);
iii. What part of your expression in (ii) determines the class assignment of each point
, for ?
iv. You have just proven (part (a)) that with can be shattered.
When we add a line to can it still be shattered? In other words, can
you choose the value of ? Justify your answer. Hint: you can choose the
class label of the other points.
3. AML Problem 2.13 (a), (b).
Reading
AML Sections 4.0, 4.1 (pp. 119-126): Overfitting
Problem based on the reading
4. AML Exercise 4.3 (p. 125). part (a) - first question only; part (b) - first question
only. [Think about the second question of each part if you like; there isn’t necessarily
a single answer to each, though.]
xi d +1
(d +1) × (d +1)
h( X ) X w
h( X ) d +1
X h( X )
xk d +1
h xk ( ) xk
sgn{i}
xi i ≠ k
h( X ) X (d+1)×(d+1)
(d + 2)
th
X
h xk ( )
(d +1)