# Support Vector Machine: identifying support vectors and kernel linear separability

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.

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.
• 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.