Does using a kernel function make the data linearly separable? If so, why using soft-margin SVM?

Question

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?

Answer 1

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.

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):

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:

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.

Answer 2

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).

Answer 3

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

Answer 4

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.