Support Vector Machine: identifying support vectors and kernel linear separability

Question

I went through the MIT Artificial Intelligence lecture on Support Vector Machines by Professor Patrick Winston: https://www.youtube.com/watch?v=_PwhiWxHK8o

I've got a couple of questions. Would be helpful if someone has gone through this lecture or is familiar with the SVM derivation in general but I think anyone who is familiar with Linear Algebra or SVMs can answer these questions without going through the lecture fully.

1) Around (27:00 and after). We are solving the system as a constrained optimisation problem using Lagrange Multipliers. In the Lagrangian the constraints take the form:

$$ \sum_{i} \alpha_i[y_i(\bar w.\bar x_i+b)-1] $$

This constraint comes from all the $ \bar x_i $ vectors that lie on the "gutters" of the hyperplane(I'm assuming these are the support vectors?). So does this mean we have to manually provide these specific boundary vectors? I haven't used SVMs but this seems like a hassle especially for higher dimensional input spaces.

Prof Winston also mentions that $\alpha_i$ will be zero for "non-gutter" vectors. Do we provide these vectors to the Lagrangian as constraints too? In other words do we sum for i = {all training examples} or i = {"gutter" training examples}.

2) Around (42:00 and after). Prof Winston explains how using the Kernel Trick we can transform the input to a higher dimensional space where it's linearly separable. I'm wondering if kernels always guarantee linear separation? I'm guessing this is highly dependent on the Kernel used and the input data right?

Any help appreciated. Thanks in advance.

Answer 1

Question 1: No, the optimization figures that out itself. You provide the constraint for every training example, and the support vectors are the ones that lie on the "gutters" (usually called lying on or within the margin); these are the ones that will have $\alpha_i > 0$. For the non-support vectors, $\alpha_i = 0$ at the optimal solution, but the optimization algorithm determines which ones are zero and which aren't.

Question 2: You're right that this is dependent on the choice of kernel and what the data looks like:

• For a linear kernel, the original problem, this is obviously not true.
• For something like a polynomial kernel, it will allow for linear separability for some kinds of data distributions, but not others; thinking through some examples of where it does and where it doesn't is a good exercise for yourself.
• For something like the kernel $k(x, y) = \exp(- \lVert x - y\rVert^2 / (2 \sigma^2))$ – which goes by many names including Gaussian, RBF (somewhat "improperly"), squared exponential, or exponentiated quadratic – it turns out that any dataset will always be linearly separable, as long as there are no two identical points with different labels.

But even if a dataset is perfectly linearly separable, that doesn't mean that a soft-margin SVM will actually prefer that solution. There's a tradeoff between maximizing the margin and the regularization that you do in an SVM; you might be able to get a bigger margin by allowing a few points to violate it a bit, compared to having an exact but very small margin. Playing around with this a bit is also a good exercise for yourself.