Page 196 - Understanding Machine Learning

Support Vector Machines
178

15.8 EXERCISES
15.1 Show that the hard-SVM rule, namely,
argmax min | w,x i + b| s.t. ∀i, y i ( w,x i + b) > 0,
(w,b): w =1 i∈[m]
is equivalent to the following formulation:

argmax min y i ( w,x i + b). (15.13)
(w,b): w =1 i∈[m]
Hint: Define G ={(w,b): ∀i, y i ( w,x i + b) > 0}.
1. Show that
argmax min y i ( w,x i + b) ∈ G
(w,b): w =1 i∈[m]
2. Show that ∀(w,b) ∈ G,

min y i ( w,x i + b) = min | w,x i + b|
i∈[m] i∈[m]
15.2 Margin and the Perceptron Consider a training set that is linearly separable 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
2
will make when running on this training set is (ρ/γ ) .
15.3 Hard versus soft SVM: Prove or refute the following claim:
There exists λ> 0 such that for every sample S of m > 1 examples, which is separa-
ble by the class of homogenous halfspaces, the hard-SVM and the soft-SVM (with
parameter λ) learning rules return exactly the same weight vector.
15.4 Weak duality: Prove that for any function f of two vector variables x ∈ X,y ∈ Y,it
holds that
minmax f (x,y) ≥ maxmin f (x,y).
x∈X y∈Y y∈Y x∈X