Theoretical Exercises

Problem 1:  Margin (6 points)

We say that a set of labeled vectors SN  (in Rp ) is linearly separable with a margin γ if there is a vector v ∈ Rp \ {0} such that for any (x,y) ∈ SN, where x ∈ Rp  and y ∈ {1, −1}:

y⟨v,x⟩

• Verify that this condition indeed corresponds to linear separability with distance γ from points to the hyperplane.  (3 points)

• Generalize this formula for the case where the separating hyperplane does not necessarily pass through the origin.  (3 points)

Problem 2:  Lasso interpretation (10 points)

Suppose we are minimizing

N

工(yi− β⊤ xi− β0 )2     subject to    ∥β∥1  ≤ s,β ∈ Rp .

i=1

Denote the corresponding minimizer by s  (we assume that it is unique for the sake of simplicity).

• How will the training RSS change as s increases from 0 to infinity?  (2 points)

• How will the test RSS change in the same setup?  (2 points)

 s(⊤)x change as s

• The same question for the variance of this estimator.  (3 points)

Problem 3:  Cross validation error of Perceptron and SVM (12 points)

Assume that we are given a set of N labeled, unit norm (∥x∥2  ≤ 1 for all x in this sample), linearly separable points in Rp  with margin γ .

• Upper bound the Leave-one-out cross-validation error of SVM in terms of the number of essential support vectors.  (4 points)

• Assume that the Perceptron algorithm is run through the sample multiple times until it makes the first pass through the data without a single mistake. Upper bound the leave-one-our error of the classifier that corresponds to the weights that made this mistakes-free pass in terms of the margin.  (5 points)

• Explain how your findings imply that both algorithms have small prediction risk when the sample size goes to infinite. Specify which statistical model (data-generating model) you are using.  (3 points)

Hint:  for simplicity we consider the Perceptron algorithm with zero intercepts and intialization w1 = 0.

Problem 4 (M): Ridge regression with non-zero intercept (8 + 8 = 16 points)

Exercise 3.5 in ESL book, page 95.

Computational Exercises

Problem 5:  Classification on MNIST (13 points)

MNIST, which stands for  “Modified National Institute of Standards and Technology,” is consid- ered the standard introductory dataset for computer vision. It was first introduced in 1999 and has since been used as a benchmark for testing classification algorithms based on handwritten images. Despite the emergence of new machine learning techniques, MNIST continues to be a trustworthy resource for both researchers and learners. In this exercise, we will tune different classifiers using 10-   fold cross-validation on MNIST. You are to tune the following classifiers: Logistic  Regression,  Linear  Discriminant  Analysis  (LDA),  Quadratic  Discriminant  Analysis  (QDA)  and  Naive Bayes. You are to download the training and the test data from the classes drive folder.