Support Vector Machines

Question

I had these questions in an exam today. State True or False and explain.

1. If k₁(.,.) and k₂(.,.) are two valid kernel functions, then if h = k₁ - k₂, is h(.,.) a valid kernel function?

2. A standard soft margin SVM is used to classify data set. We have a fixed C parameter. Two different algorithms A₁ and A₂ are used to obtain the support vector set {S: α _i > 0}. Call them S1 and S2. Is S1 = S2 in all cases? Assume both algorithm use the same kernel function.

EDITED:

I guessed as:

1. As kernel function need to be positive semi definite (PSD), the difference between two kernel functions need not be PSD. Hence FALSE.

2. α_i can be different among the two algorithms, the number of support vectors can differ as well. Hence FALSE again.

Answer 1

A) constant 0 is a kernel, constant 1 is a kernel, too. But 0-1=-1 is not PSD.

Thus false IMHO.

B) Assuming 2D data, where x=0 for Class 1, x=1 for Class 2, and y is uniformly random. Any vector from each class is as good a support vector as the others, yielding the same hyperplane. Visually:

x1 | y1
   |
x2 | y2

Which SVM is better, the one using x1 and y1 as support vectors, or the one using x2 and y2?