Support Vector Machine

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

For your question 2 u can transform the input to a higher dimensional space whatever it is linear separable or not but u need soft margin for non linear separable case after u apply kernel on your data actually it is linear separable in high dimension for example if your data in 2 dimenion it will transform into 3 dimensional space and separate with a hyperplane when it project to a higer dimensional space it must be linear separable accroding to a theory finally they will project back to 2 dimension and become a nonlinear boundary

For your question 1 not sure what are u asking but I guess your question is about how to find support vector? actually u have 2 method to find it out first one SMO and second one QP with phase 1 simplex method accroding to the formula: $\alpha_i(y_i(w^{T}x_i+b)-1)$

when the data on the boundary:
for class = -1
$\alpha_i(1(1)-1)=\alpha_i(y_i(w^{T}x_i+b)-1)$
$\alpha_i \neq 0$
$y_i(w^{T}x_i+b)-1=0$

for class = +1
$\alpha_i(-1(-1)-1)=\alpha_i(y_i(w^{T}x_i+b)-1)$
$\alpha_i \neq 0$
$y_i(w^{T}x_i+b)-1=0$
why its ture? because it is KKT condition
That's all I know about SVM I hope it can help u