0
$\begingroup$

enter image description here

I have learned that the hypothesis function for SVMs is predicting y=1 if transpose(w)xi + b>=0 and y=-1 otherwise. However, according to the loss function above, it implies that transpose(w)xi + b has to be greater or equal to 1 (>=1) if label y=1 and smaller than -1 (<=-1) if the label is -1 to have 0 penalties. So I am confused here...So does this mean that if transpose(w)xi + b =0.6>=0 (thus producing h(x)=1) and indeed label y=1, but according to the loss function there will still be penalty (because max(0, 1-0.6) = 0.4)??? Why? Didn't the model correctly classify?

Could someone please clarify for me? Thanks a lot!

$\endgroup$
1
$\begingroup$

SVMs are models to classify a dataset with a maximum-margin hyperplane. In fact, the optimization problem of a linear SVM is derived from the same assumption and is:

$\mathcal{P}: max_{w,b} \frac{1}{\Vert w \Vert}$ subject to $y^{(i)}(w^Tx^{(i)}+b)\geq 1\forall i$

$\equiv min_{w,b} \Vert w \Vert$ subject to $y^{(i)}(w^Tx^{(i)}+b)\geq 1\forall i$

$\equiv min_{w,b} \frac{1}{2}w^Tw$ subject to $y^{(i)}(w^Tx^{(i)}+b)\geq 1\forall i$

The above case is of the hard SVM (when the data is linearly separable). However, when the dataset is not exactly linearly separable, we go for a soft SVM and use the penalty method. The primal problem $\mathcal{P}$ is reformed to: \begin{aligned} & \mathcal{P}: & & min_{w,b} \frac{1}{2}w^Tw+C\sum_{i=1}^N \xi_i \\ & \text{subject to} & & y^{(i)}(w^Tx^{(i)}+b)\geq 1-\xi_i\forall i\\ &&& \xi_i\geq 0\forall i\\ \end{aligned} The above constrained optimization problem can be solved as a series of unconstrained problems as: $$min_{w,b} \Big[\frac{1}{2}w^Tw+C\sum_{i=1}^N \max\big(0,1-y^{(i)}(w^Tx^{(i)}+b)\big)\Big]$$ ,which brings to the answer of your question. In a soft SVM, we are looking for parameters $(w,b)$ which minimizes the above cost function overall. As the data is not exactly linearly separable, for every set of parameters $(w,b)$, there will be some non-zero penaltie for some $i$. But the goal is to minimize the whole cost function in order to get the maximum margin and minimum sum of penalties.

$\endgroup$
4
  • $\begingroup$ Thank you so much for the clarification. Just a side question, is kernel's trick also used in non-separable dataset SVMs? If we know that the dataset is not separable even if mapped into a higher dimension, do we still map it to higher dimension anyway (for some reason I don't know) and perform kernel's trick to calculate the dot product? Or since we allow some misclassifications now, we don't bother to map into higher dimension? $\endgroup$ – YCCCCC Aug 27 '19 at 20:52
  • $\begingroup$ @YCCCCC given a dataset is not linearly separable even if mapped into a higher dimension, it may be separable with the help of a non-linear kernel for some higher dimension. In such cases, the RBF kernel makes a good default kernel. Also, we can always go for soft margins, and if the sum of penalties turns out to be zero for the used kernel, it implies that we get a hard margin. It all depends on the choice of kernel, optimization technique and hyperparameters tuning. $\endgroup$ – babkr Aug 29 '19 at 5:10
  • $\begingroup$ Thank you so much for your reply. So kernels are basically used to map into higher dimensions, since using kernel's trick we don't even need to know what the mapping is, we just want the result, is this statement correct? So basically, in cases where the dataset does not seem to be linearly separable in any obvious way, we would use a kernel to solve the problem. Yes? $\endgroup$ – YCCCCC Aug 30 '19 at 0:14
  • $\begingroup$ This SVM exercise (scikit-learn.org/stable/auto_examples/exercises/…) shows the decision boundaries created on Iris dataset by first using linear kernel, then a polynomial kernel and finally an RBF kernel. This is the usual flow of improving our kernel and it's advised to get to know what they map to. $\endgroup$ – babkr Aug 30 '19 at 5:06
0
$\begingroup$

We are seeking a maximum-margin solution, not just a good separating hyperplane. So there is, indeed, a penalty for points "inside" the margin.

Otherwise, the optimal solution (given the best-separating hyperplane) would be to take $w$ very small (with a similarly scaled $b$ to keep the same hyperplane), making the margin very large and producing arbitrarily small loss. (https://stats.stackexchange.com/a/373075/232706)

$\endgroup$
1
  • $\begingroup$ Just a side question, is kernel's trick also used in non-separable dataset SVMs? If we know that the dataset is not separable even if mapped into a higher dimension, do we still map it to higher dimension anyway (for some reason I don't know) and perform kernel's trick to calculate the dot product? Or since we allow some misclassifications now, we don't bother to map into higher dimension? $\endgroup$ – YCCCCC Aug 27 '19 at 22:06

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.