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

Primal versus Dual Problem

• 1. Recall that N is the size of the data set and d is the dimensionality of the input space. The original formulation of the hard-margin SVM problem (min-imize ¹₂ w^Tw subject to the inequality constraints), without going through the Lagrangian dual problem, is

• 1. 1. a quadratic programming problem with N variables

• 1. 2. a quadratic programming problem with N + 1 variables

• 1. 3. a quadratic programming problem with d variables

• 1. 4. a quadratic programming problem with d + 1 variables

• 1. 5. not a quadratic programming problem

Notice: The following problems deal with a real-life data set. In addition, the computa-tional packages you use may employ di erent heuristics and require di erent tweaks. This is a typical situation that a Machine Learning practitioner faces. There are uncertainties, and the answers may or may not match our expectations. Although this situation is not as ‘sanitized’ as other homework problems, it is important to go through it as part of the learning experience.

SVM with Soft Margins

In the rest of the problems of this homework set, we apply soft-margin SVM to handwritten digits from the processed US Postal Service Zip Code data set. 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).

The data set has thousands of points, and some quadratic programming packages cannot handle this size. We recommend that you use the packages in libsvm:

http://www.csie.ntu.edu.tw/_~cjlin/libsvm/

Implement SVM with soft margin on the above zip-code data set by solving

• 1. 4. 7 versus all

• 1. 4. 9 versus all

• 4. Comparing the two selected classi ers from Problems 2 and 3, which of the following values is the closest to the di erence between the number of support vectors of these two classi ers?

• 4. 1. 600

• 4. 2. 1200

• 4. 3. 1800

• 4. 4. 2400

• 4. 5. 3000

• 4. Consider the 1 versus 5 classi er with Q = 2 and C 2 f0:001; 0:01; 0:1; 1g. Which of the following statements is correct? Going up or down means strictly so.

• 4. 1. The number of support vectors goes down when C goes up.

• 4. 2. The number of support vectors goes up when C goes up.

• 4. 3. E_out goes down when C goes up.

• 4. 4. Maximum C achieves the lowest E_in.

• 4. 5. None of the above

• 4. In the 1 versus 5 classi er, comparing Q = 2 with Q = 5, which of the following statements is correct?

• 4. 1. When C = 0:0001, E_in is higher at Q = 5.

• 4. 2. When C = 0:001, the number of support vectors is lower at Q = 5.

• 4. 3. When C = 0:01, E_in is higher at Q = 5.

• 4. 4. When C = 1, E_out is lower at Q = 5.

• 4. 5. None of the above

Cross Validation

In the next two problems, we will experiment with 10-fold cross validation for the polynomial kernel. Because E_cv is a random variable that depends on the random partition of the data, we will try 100 runs with di erent partitions and base our answer on how many runs lead to a particular choice.

• 7. Consider the 1 versus 5 classi er with Q = 2. We use E_cv to select C 2 f0:0001; 0:001; 0:01; 0:1; 1g. If there is a tie in E_cv, select the smaller C. Within the 100 random runs, which of the following statements is correct?

• 7. 1. C = 0:0001 is selected most often.

• 7. 2. C = 0:001 is selected most often.

• 7. 3. C = 0:01 is selected most often.

• 7. 4. C = 0:1 is selected most often.

• 7. 5. C = 1 is selected most often.

• 7. Again, consider the 1 versus 5 classi er with Q = 2. For the winning selection in the previous problem, the average value of E_cv over the 100 runs is closest to

• 1. 1. 0:001

• 1. 2. 0:003

• 1. 3. 0:005

• 1. 4. 0:007

• 1. 5. 0:009

RBF Kernel

Consider the radial basis function (RBF) kernel K(x_n; x_m) = exp ( x_n x_mjj²) in the soft-margin SVM approach. Focus on the 1 versus 5 classi er.

9. Which of the following values of C results in the lowest E_in?

9. 1. C = 0:01

9. 2. C = 1

9. 3. C=100

9. 4. C=10⁴

9. 5. C=10⁶

9. Which of the following values of C results in the lowest E_out?

9. 1. C = 0:01

9. 2. C = 1

9. 3. C=100

9. 4. C=10⁴

9. 5. C=10⁶

5