Understanding Machine Learning: From Theory to Algorithms

214 Support Vector Machines

15.8 Exercises

1. Show that the hard-SVM rule, namely,
   argmax
   (w,b):‖w‖=1

min

i∈[m]

|〈w,xi〉+b| s.t. ∀i, yi(〈w,xi〉+b)> 0 ,

is equivalent to the following formulation:

argmax

(w,b):‖w‖=1

min

i∈[m]

yi(〈w,xi〉+b). (15.13)

Hint:DefineG={(w,b) :∀i,yi(〈w,xi〉+b)> 0 }.

1. Show that
   argmax
   (w,b):‖w‖=1

min

i∈[m]

yi(〈w,xi〉+b)∈G

2. Show that∀(w,b)∈G,
   min
   i∈[m]

yi(〈w,xi〉+b) = min

i∈[m]

|〈w,xi〉+b|

2.Margin and the PerceptronConsider a training set that is linearly sep-

arable with a marginγand such that all the instances are within a ball of

radiusρ. Prove that the maximal number of updates the Batch Perceptron

algorithm given in Section 9.1.2 will make when running on this training set

is (ρ/γ)^2.

3.Hard versus soft SVM:Prove or refute the following claim:

There existsλ > 0 such that for every sampleSofm > 1 examples, which

is separable by the class of homogenous halfspaces, the hard-SVM and the

soft-SVM (with parameterλ) learning rules return exactly the same weight

vector.

4.Weak duality:Prove that for any functionf of two vector variablesx∈

X,y∈Y, it holds that

minx∈Xmaxy∈Yf(x,y)≥maxy∈Yminx∈Xf(x,y).