Linear kernel in SVM performing much worse than RBF or Poly

Question

When trying to train a SVM on some Kaggle data, I have encountered a situation where the linear kernel fails to give any results.

This doesn't make sense to me because the RBF kernel works just fine, and my understanding is that a linear kernel is a strictly simpler version that doesn't map the data into higher dimensions. In fact, all my research suggests that not only is a linear kernel possible, but that in most cases, it should be faster to converge (with the trade-off that the results might not be as accurate).

However, this has not proved to be the case. While the RBF kernel was able to produce a result during cross-validation after ~6 minutes, the linear kernel just sat there with no output after ~6 hours. After this point, I just force quit the training and moved onto testing other SVM parameters.

A breakdown of some facts:

• Roughly 60,000 examples, around 120 features (Sometimes cutting down to 30 features helps, and linear kernel will produce a result after many hours)
• I'm using SKLearn GridSearchCV to perform my training
• I have tested this used SVC(kernel='linear') as well as LinearSVC(), both with the same outcome
• This issue has come up with multiple data sets across different competitions

My current hypothesis is that the training stops possibly because the data is not linearly separable. I might be missing something else obvious though. Any guidance is appreciated, thanks!

Answer 1

This depends very much on your dataset: There is data, which can not be separated using a linear kernel. It is impossible, and you won't get any reasonable result. Take for example the simple XOR function. The plot of the XOR looks like this:

No matter how hard you try, you will never be able to separate this using a linear SVM, or any linear method.

Here's some short MATLAB code which illustrates the problem:

x = [0 0; 0 1; 1 0; 1 1];    % training points
y = [0; 1; 1; 0];            % target: XOR
linearSvm = fitcsvm(x,y);    % train with linear kernel
linearSvm.predict(x)

>> ans = 
        0
        0
        0
        0

The SVM has no chance of finding a solution. Now if we use a kernel, we create a mapping to a higher-dimensional space. The kernel trick allows us to implicitly do this mapping, by calculating a kernel function, which returns the result of a scalar product in this high-dimensional space, without needing to map the input values to this space. The RBF kernel is special, as it corresponds to an infinite-dimensional space. Now if we specify a RBF kernel and run the same example again, then:

gaussSvm = fitcsvm(x,y,'KernelFunction','rbf');  % RBF kernel
gaussSvm.predict(x)

>> ans = 
        0
        1
        1
        0

the SVM easily finds the correct result. The same result (in this XOR case) is also found when using a polynomial kernel. There are many more examples, where data simply can't be separated linearly, for example:

Of course, if your data is almost linearly separable, then you can (and probably will) get good results with a linear kernel. Using soft-margin SVMs, which allow for a few misclassifications, often leads to good results, as they can ignore outliers.

If the linear kernel gives no result, you will have to accept that your data is not (well) linearly separable. You'll either have to switch to a kernel, or allow for more misclassifications in the soft-margin SVM.

Answer 2

You can still use a linear SVM classifier in a non-separable case. However, you should then tolerate misclassifications. You should then tune the hyperparameter $C$.

There are cases where a linear SVM in a non-separable case gives better results than a RBF kernel. For instance, the optimal decision boundary for two classes with equal covariance matrices is linear.

Answer 3

One quick note: gridsearch gets very slow as your hyperparameter space grows. Randomized search often leads to just-as-good hyperparameters, and is much faster:

http://scikit-learn.org/stable/auto_examples/model_selection/randomized_search.html