Homework 10: Support Vector Machine
Part I: Written Exercises
1. This problem is for the hard-margin SVM. Consider the following training data,
x1 x2 y 0 0 -1
(a) Plot the training data, and the hyperplane given by: wT = [3, −3] and w0 = −3
(b) Are the points linearly separable?
(c) For w and w0 given above:
i. compute the functional margin for each training example and show the functional margin with respect to the set of training examples
ii. compute the geometric margin for each training example, and show the geometric margin with respect to set of training examples
iii. compute the canonical weights with respect to the training examples
(d) Identify which of the training examples are support vectors
(e) If we add the point x = (1,3)T and y = −1 to the training data, does the margin change? Does the separating hyperplane change? Do the support vectors change?
(f) If we remove the point (1,1.5)T does the margin change? Does the separating hyperplane change?
(g) If we remove the point (0,0)T does the margin change? Does the separating hyperplane change?
(h) Specify a constrained objective function to find a hyperplane that separates the training examples above where the separating hyperplane has the largest possible margin.1 Use the numbers given in the problem.
2. Would the following constrained optimizations create the same decision boundary? Justify your answer.
max γ
Subject to:
−1(5.1w1 + 3.5w2 + 1.4w3 + 0.2w4 + w0) ≥ γ −1(4.9w1 + 3.0w2 + 1.4w3 + 0.2w4 + w0) ≥ γ −1(4.7w1 + 3.2w2 + 1.3w3 + 0.2w4 + w0) ≥ γ −1(4.6w1 + 3.1w2 + 1.5w3 + 0.2w4 + w0) ≥ γ 1(7.0w1 + 3.2w2 + 4.7w3 + 1.4w4 + w0) ≥ γ 1(16.4w1 + 3.2w2 + 4.5w3 + 1.5w4 + w0) ≥ γ 1(6.9w1 + 3.1w2 + 4.9w3 + 1.5w4 + w0) ≥ γ 1(.5w1 + 2.3w2 + 4.0w3 + 1.3w4 + w0) ≥ γ ||w||2 = 1
min ||w||2
Subject to:
−1(5.1w1 + 3.5w2 + 1.4w3 + 0.2w4 + w0) ≥ 1 −1(4.9w1 + 3.0w2 + 1.4w3 + 0.2w4 + w0) ≥ 1 −1(4.7w1 + 3.2w2 + 1.3w3 + 0.2w4 + w0) ≥ 1 −1(4.6w1 + 3.1w2 + 1.5w3 + 0.2w4 + w0) ≥ 1 1(7.0w1 + 3.2w2 + 4.7w3 + 1.4w4 + w0) ≥ 1 1(16.4w1 + 3.2w2 + 4.5w3 + 1.5w4 + w0) ≥ 1 1(6.9w1 + 3.1w2 + 4.9w3 + 1.5w4 + w0) ≥ 1 1(.5w1 + 2.3w2 + 4.0w3 + 1.3w4 + w0) ≥ 1
3. In class, we discussed the soft-margin SVM:
1 Xn
ξ(i)
subject to y(i)(wT x(i) + w0) ≥ 1 − ξ(i), and ξ(i) ≥ 0
min 2wT w + C
(a) For a point x(i) if ξ(i) = 0, what do we know about where x(i) is wrt the margin.
Is x(i) correctly classified by the hyperplane? 1You do not need to solve your constrained optimization problem.
i=1
(b) Forapointx(i) if0<ξ(i) <1,whatdoweknowaboutwherex(i) iswrtthe margin. Is x(i) correctly classified by the hyperplane?
(c) For a point x(i) if ξ(i) > 1, what do we know about where x(i) is wrt the margin. Is x(i) correctly classified by the hyperplane?
4. Given the following points, plot the decision boundary when C = 0.1 and C = 10. You can use the code from
x(i) x(i) y(i) 12
5. For the following non-linearly separable points, find a transformation to make them linearly separable. Using matplotlib to plot the points before and after your trans- formation.
x(i) x(i) y(i) 12
6. For the points in question 5, if you remove (−0.80, −0.06), does the margin stay the same? Describe which points will not change the margin and which points might change the margin.
7. This problem is in the hard-margin case. Consider the following training examples ((1, 2.5)T , 1), ((0, 0.75)T , −1), ((1, 1)T , −1), ((2, 2)T , 1), ((3, 1)T , 1), ((2, 3)T , 1).
• Suppose you determined that α == [0.889, 0, 1.389, 0, 0.5, 0]. What is w? • Whatis w0?
• Predict the label of (1, 0)T and (3, 3)T . Show your work.
8. (Donotturnin)ShowthatifΦ(x)=Φ([xi1,xi2])=(1,√2xi1,√2xi2,x21,x2,√2xi1xi2) then Φ(x)T Φ(x′) = (1 + xT x′)2
9. (Do not turn in) The following points are not linearly separable.
i x(i) x(i) y(i)
Which of the following kernel functions could be used to perfectly classify the data using a hard margin SVM?
• linear
• quadratic
• cubic
• radial basis
(This question is modified from an outside source.)
Part II: Programming Exercise
10. Complete the notebook HW10 SVM Pegasos.ipynb
In this assignment, you will perform handwritten digit classification using the MNIST
dataset of handwritten digits. Each example represents an image of a digit (size 4
28 × 28) that has been been flattened into a feature vector of length 784. Each feature specifies a grayscale pixel value.
You will apply SVMs to automatically classify the digits. Note: we will be using a simplified multiclass one-vs-rest approach. (While you will not transform the data in this assignment, please note that SVMs can classify digits with a 1.1% error rate if we applied a degree 4 polynomial transformation to the data.)
This assignment has 3 components:
Step 1: Implement the Pegasos algorithm to perform binary classification. You will be asked to distinguish a handwritten 0 from any other handwritten digit.
Step 2: Perform multiclass classification using the Pegasos binary classification algorithm you wrote in step 1. You will use a simplified one-vs-rest approach to automatically classify digits.
Step 3: Try different hyperparameters to see if you can improve the accuracy of automatically classifying digits. Please include a short writeup describing the techniques you used and the effectiveness of each of them.
Additional instructions regarding the programming assignment’s submission require- ments will be provided on Monday.
