1. [10 points] SVM Basics
Consider the following dataset D in the two-dimensional space; x(i) ∈ R2 and y(i) ∈ {1, −1}
i
x(i)
x(i)
y(i)
1
2
3
4
5
6
-1
-2.5
2
4.7
4
-4.3
3
-3
-3
5
3
-4
1
-1
-1
1
1
-1
1 2
Recall a hard SVM is as follows:
min
w,b
2
1
2 kwk
s.t. y(i) (w| x(i) + b ≥ 1) , ∀(x(i), y(i)) ∈ D (1)
(a) What is the optimal w and b? Show all your work and reasoning. (Hint: Draw it out.) Your answer:
(b) Which of the examples are support vectors?
Your answer:
(c) A standard quadratic program is as follows,
1
minimize
z
z| P z + q| z
2
subject to Gz ≤ h
Rewrite Equation (1) into the above form. (i.e . define z, P, q, G, h using w, b and values in D). Write the constraints in the same order as provided in D and typeset it using bmatrix.
Your answer:
(d) Recall that for a soft-SVM we solve the following optimization problem.
min
w,b
2 kwk
+ C · X ξ(i) s.t. y(i)(w| x(i) + b ≥ 1 − ξ(i)), ξ(i) ≥ 0 , ∀(x(i), y(i)) ∈ D
i=1
Describe what happens to the margin when C = ∞ and C = 0. Your answer:
2. [4 points] Kernels
(2)
(a) If K1(x, z) and K2 (x, z) are both valid kernel functions, and α and β are positive, prove that
is also a valid kernel function. Your answer:
αK1(x, z) + βK2(x, z)
(b) Show that K (x, z) = (x| z)2 is a valid kernel, for x, z ∈ R2. (i.e . write out the Φ(·), such that K (x, z) = Φ(x)| Φ(z)
Your answer:
