2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Would be better to raise this question on Cross validated site. $\endgroup$ – mathcounterexamples.net Sep 5 '19 at 18:28
  • $\begingroup$ Will post it there too. But to be honest, I am more interested in the Mathematics behind the derivation. $\endgroup$ – Nitin Sep 5 '19 at 18:34
  • 2
    $\begingroup$ Understand but you’re using terms (SVM, kernel trick...) that are not familiar to mathematics. $\endgroup$ – mathcounterexamples.net Sep 5 '19 at 18:42
  • $\begingroup$ To be completely fair, the Kernel trick comes from Mathematics: en.wikipedia.org/wiki/Positive-definite_kernel. And you really don't need to know about SVMs to answer the second question. I'm asking about kernels in general. Also, I've tagged the post under machine-learning. $\endgroup$ – Nitin Sep 5 '19 at 19:13
  • $\begingroup$ 1. I think the point of singling out the support vectors is that you only need to sum over a relatively small subset of the vectors (so i = {"gutter" training examples}) 2. yeah it's highly dependent on the kernel. $\endgroup$ – user113102 Sep 5 '19 at 20:20
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If u want to know how the kernel works u can search on youtube Andrew Ng machine learning course about SVM with kernel or a chinese channel 李政軒 support vector machine (this channel explain very details don't worry if u don't understand chinese because the powerpoint is in english) $\endgroup$ – Linear Algebra fans Sep 5 '19 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.