3
$\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$
5
  • 1
    $\begingroup$ Would be better to raise this question on Cross validated site. $\endgroup$ Sep 5, 2019 at 18:28
  • 1
    $\begingroup$ Will post it there too. But to be honest, I am more interested in the Mathematics behind the derivation. $\endgroup$
    – Nitin
    Sep 5, 2019 at 18:34
  • 2
    $\begingroup$ Understand but you’re using terms (SVM, kernel trick...) that are not familiar to mathematics. $\endgroup$ Sep 5, 2019 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, 2019 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, 2019 at 20:20

1 Answer 1

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

$\endgroup$
1
  • $\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$ Sep 5, 2019 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .