6
$\begingroup$

I'm reading about SVM and I learned that we use a kernel function so the data become linearly separable in the high dimensional (vector?) space. But then I also learned that they use the soft-margin idea. But my question is why to use a soft-margin if the data is going to be linearly separable anyway in the high space? Or does that mean that even after mapping with the kernel it doesn't necessarily mean that it will become linearly separable?

$\endgroup$
7
+50
$\begingroup$

Does using a kernel function make the data linearly separable?

In some cases, but not others. For example, the linear kernel induces a feature space that's equivalent to the original input space (up to dot product preserving transformations like rotation and reflection). If the data aren't linearly separable in input space, they won't be in feature space either. Polynomial kernels with degree >1 map the data nonlinearly into a higher dimensional feature space. Data that aren't linearly separable in input space may be linearly separable in feature space (depending on the particular data and kernel), but may not be in other cases. RBF kernels map the data nonlinearly into an infinite-dimensional feature space. If the kernel bandwidth is chosen small enough, the data are always linearly separable in feature space.

When linear separability is possible, why use a soft-margin SVM?

The input features may not contain enough information about class labels to perfectly predict them. In these cases, perfectly separating the training data would be overfitting, and would hurt generalization performance. Consider the following example, where points from one class are drawn from an isotropic Gaussian distribution, and points from the other are drawn from a surrounding, ring-shaped distribution. The optimal decision boundary is a circle through the low density region between these distributions. The data aren't truly separable because the distributions overlap, and points from each class end up on the wrong side of the optimal decision boundary.

enter image description here

As mentioned above, an RBF kernel with small bandwidth allows linear separability of the training data in feature space. A hard-margin SVM using this kernel achieves perfect accuracy on the training set (background color indicates predicted class, point color indicates actual class):

enter image description here

The hard margin SVM maximizes the margin, subject to the constraint that no training point is misclassified. The RBF kernel ensures that it's possible to meet this constraint. However, the resulting decision boundary is completely overfit, and will not generalize well to future data.

Instead, we can use a soft margin SVM, which allows some margin violations and misclassifications in exchange for a bigger margin (the tradeoff is controlled by a hyperparameter). The hope is that a bigger margin will increase generalization performance. Here's the output for a soft margin SVM with the same RBF kernel:

enter image description here

Despite more errors on the training set, the decision boundary is closer to the true boundary, and the soft margin SVM will generalize better. Further improvements could be made by tweaking the kernel.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1. A very nice answer. Regarding linear separability with the RBF kernel: you write that it will happen "if the kernel bandwidth is chosen small enough". How small is enough here? And why would it not hold if the bandwidth is large? The dimensionality of the target space is $\infty$ independent of the bandwidth and my intuition is that if $n<p$ then any data are linearly separable. Clearly $n<\infty$ for any $n$. $\endgroup$ – amoeba Mar 11 '18 at 21:32
  • 1
    $\begingroup$ Yes, that's a good point, and something I'm trying to understand better too. It's true that feature space is infinite dimensional. And, the RBF kernel is positive definite, so the kernel matrix should be full rank, indicating that the data will occupy an $n$ dimensional subspace of feature space (and therefore be linearly separable). But, empirically, increasing the bandwidth $\sigma$ can reduce the variance along many directions in feature space, to the point that it's numerically indistinguishable from zero. (continue) $\endgroup$ – user20160 Mar 11 '18 at 22:18
  • 2
    $\begingroup$ (continued) So it seems the "effective dimensionality" we can take advantage of with a finite precision machine can be lower than $n$ for larger $\sigma$. I suspect what's happening here is that larger $\sigma$ gives smoother feature space mappings with less curvature, so the arrangement of points in feature space can get flattened out along many directions. I was thinking of writing a question about this. $\endgroup$ – user20160 Mar 11 '18 at 22:18
  • 1
    $\begingroup$ @amoebasaysReinstateMonica A very complex non-linear mapping will make a sample linearly separable (unless there are two exact points with different labels), however such guarantee doesn't propagate to the population. For example if we have data from two gaussians with different means, there is no transformation that will have 0 classification error on the population, but you will find one for the sample at hand. $\endgroup$ – Cagdas Ozgenc Jan 16 at 14:13
3
$\begingroup$

You are convoluting two different things. The classification algorithm used by SVM is always linear (e.g. a hyperplane) in some feature space induced by a kernel. Hard margin SVM, which is typically the first example you encounter when learning SVM, requires linearly separable data in feature space or there is no solution to the training problem. Typically, this first example works in input space but the same can be done in any feature space of your choosing.

But my question is why to use a soft-margin if the data is going to be linearly separable anyway in the high space?

Soft-margin SVM does not require data to be separable, not even in feature space. This is the key difference between hard and soft margin. Soft-margin SVM allows instances to fall within the margin and even on the wrong side of the separating hyperplane, but penalizes these instances using hinge loss.

Or does that mean that even after mapping with the kernel it doesn't necessarily mean that it will become linearly separable?

The use of a nonlinear kernel never gives any guarantees to make any data set linearly separable in the induced feature space. This is not necessary. The reason we use kernels is to map the data from input space onto a higher dimensional space, in which a (higher dimensional) hyperplane will be better at separating the data. That is all. If data is perfectly separable in feature space, your training accuracy is $1$ by definition. This is still rare even when using kernels.

You can find kernels that make data linearly separable, but this usually requires very complex kernels which lead to results that generalize poorly. An example of this would be an RBF kernel with very high $\gamma$, which basically yields the unit matrix as kernel matrix (this is perfectly separable but will generalize badly on unseen data).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Good answer. More explicitly: If a kernel function would guarantee that it would always be able to linearly separate data, it would be useless. This is almost exactly the definition of a function with infinite VC-dimension, which means that you will never be able to learn/generalize the correct function regardless of the amount of data. See here: cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf $\endgroup$ – Bitwise Apr 18 '14 at 15:40
  • $\begingroup$ I am confused, Marc and @Bitwise. I thought that when using Gaussian kernel, the [implicit] dimension of the feature space is $\infty$ and I also thought that $n$ points are almost surely linearly separable whenever $n<p$ which of course holds when $p=\infty$. If true, then any dataset should be linearly separable when using any RBF kernel (and obviously RBF kernels are still not useless). What am I missing? This is the same point made in another comment below. $\endgroup$ – amoeba Mar 9 '18 at 9:05
  • $\begingroup$ To be honest, I think this answer is simply wrong so -1. Any RBF kernel yields linear separation on any data. Will be happy to revert the downvote if the answer is edited to clarify (and to explain why we still want to use soft-margin despite linear separability). $\endgroup$ – amoeba Mar 9 '18 at 9:14
1
$\begingroup$

Yes, it becomes linearly separable, especially if you always use the RBF kernel which maps to infinite dimensional space.

When people talk about soft margin, it is different from what you are thinking. The SVM by design expects that the functional margin [1] for the two classes be atleast 1. This requirement, however, need not be always satisfied, since this requirement is stricter than just being linearly separable. Thereby, you introduce slack variables to accommodate points that don't satisfy the functional margin requirement.

[1] https://stackoverflow.com/questions/14658452/how-to-understand-the-functional-margin-in-svm

Some more material to read:
1] Given a set of points in two dimensional space, how can one design decision function for SVM?
2] How to understand effect of RBF SVM

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ this is strange because I was watching Andrew NG video youtube.com/watch?v=bUv9bfMPMb4#t=2235 where he introduced the soft-margin idea based on the idea of some examples not being linearly separable! $\endgroup$ – Jack Twain Apr 16 '14 at 16:32
  • 1
    $\begingroup$ Sure, the data may not be linearly separable in the input space. That says nothing about their separability in the high dimensional space that kernels map them to?! $\endgroup$ – TenaliRaman Apr 16 '14 at 17:06
  • 2
    $\begingroup$ -1. Soft-margin SVM does not require nor guarantee linear separation in feature space. To see this: use soft margin SVM with a linear kernel on non-separable data and you will still get a result. Soft-margin SVM penalizes points that are within the margin and misclassified in feature space, typically using hinge loss. @AlexTwain your interpretation is correct. $\endgroup$ – Marc Claesen Apr 18 '14 at 13:37
  • 2
    $\begingroup$ Using a Gaussian kernel DOES make the data points linearly separable (as long as they are distinct from each other). This is because a Gaussian kernel corresponds to a feature map that maps n distinct points into n linearly independent points in an n-dimensional (sub-)space (check the comments after Theorem 2.6 in pdf). Now note that n linearly independent points in an n-dimensional space can always be separated by a half-plane no matter what the labels are. $\endgroup$ – sadkangaroo Mar 8 '18 at 22:34
  • $\begingroup$ +1. I thought that using soft-margin SVM introduces a hyper-parameter that acts as a regularization strength. Increasing the soft-margin increases regularization, which can be beneficial even if the data are linearly separable (as they always are with an RBF kernel). Is this correct? If so, it looks like the key to answering this question but you don't mention regularization at all. Is it somehow related to what you are saying about functional margin? I am not sure I understand your argument well. $\endgroup$ – amoeba Mar 9 '18 at 9:22
1
$\begingroup$

Although it is possible to select the Gaussian kernel and achieve separability in the feature space, this might not be the best strategy for minimizing the expected loss (i.e. the true risk as opposed to the empirical risk). Consider an example of labeled points in $\mathbb{R}^3$ where negative points lie in the ($\ell_2$) unit ball and positive points lie outside the ball of radius 2. However, suppose there also are a few outliers in the training sample: a few positive points lie in the "negative" region inside the unit ball.

Now, if we use a polynomial kernel that includes the $\ell_2$ norm of the data points as a new dimension, then we can almost linearly separate the data in the feature space. There are a few outliers of course, so we will still have some training error using this kernel. However, if the outliers correspond to fundamental noise in our problem, then it might be the case that the Bayes optimal decision rule in fact is the hypothesis that classifies points as positive if there norm is at least two and negative otherwise.

Indeed, if the outliers arise because for some points $x$ the label is not deterministic in the sense that $P(Y = 1 \mid X = x) \in (0, 1)$ rather than being $0$ or $1$, then the noise is fundamental to the problem and we should avoid fitting to it. We could instead go with a Gaussian kernel which makes the data linearly separable, but this would amount to overfitting and hurt the true risk of our hypothesis.

This example shows that there are cases when one does want to use a kernel, the data may still not be linearly separable in the new feature space, and so we still need the soft-margin SVM formulation.

| cite | improve this answer | |
$\endgroup$

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.