(c) Define a class variable yi 2 {?1, +1} which denotes the class of xi and let w=(w1,w2,w3)T . The max-margin SVM classifier solves the following problem
???0,0,?2?,b?1 and Using the method of Lagrange multipliers show that the solution is wthe margin is
For optimization problems with inequality constraints such as the above, we should apply KKT conditions which is a generalization of Lagrange multipliers. However this problem can be solved easier by noting that we have three vectors in the 3-dimensional space and all of them are support vectors. Hence the all 3 constraints hold with equality. Therefore we can apply the method of Lagrange multipliers to,
T1. ?2w
(e) Show that the solution remains the same if the constraints are changed to
for any
??1.
(f) (Extra Credit) Is your answer to (d) also true for any dataset and??1? Provide a counterexample
or give a short proof.
SVM
Suppose we only have four training examples in two dimensions (see figure above):
positive examples at x1 = [0, 0] , x2 = [2, 2] and negative examples at x3 = [h, 1] , x4 = [0, 3], where we treat 0 ≤ h ≤ 3 as a parameter
(1). How large can h ≥ 0 be so that the training points are still linearly separable? Up to (excluding) h=1
(2). Does the orientation of the maximum margin decision boundary change as a function of h when the points are separable (Y/N)? No, because x1, x2, x3 remain the support vectors.
(3). What is the margin achieved by the maximum margin boundary as a function of h?
[Hint : It turns out that the margin as a function of h is a linear function.]
(4). Assume that we can only observe the second component of the input vectors. Without the other component, the labeled training points reduce to (0,y = 1), (2,y = 1), (1,y = -1), and (3,y =-1). What is the lowest order p of polynomial kernel that would allow us to correctly classify these points?
The classes of the points on the x2-projected line observe the order 1,-1,1,-1. Therefore, we need a cubic polynomial.