Kernel SVM on sparse data

Question

I have a sparse dataset where a lot of the columns (features) contain mostly zero values. Class labels are multiple discrete categories (10 classes to be precise). I'm wondering if this should trouble classifying the dataset by learning an SVM with kernel (say RBF, polynomial, or linear)? And which kernel should cause trouble, which should not?

Empirically, I fit an SVM with RBF kernel using R (package e1071) and it throws a lot of warnings and the prediction accuracy is very poor. I'm not sure if this is the problem with SVM and RBF kernel or something else.

Answer 1

The point of using kernels is to map data that is non-separable in input space onto a higher dimensional feature space, where it becomes easier to separate. Usually when you have a lot of features there is no need to use a nonlinear kernel. You can find more information about that in A Practical Guide to Support Vector Classification (appendix C).

If you want to use kernels you will need to find good values for the associated hyperparameter(s). For the RBF kernel you need to tune $\gamma$. If it is too large, your model will overfit, if it is too low it will underfit. You can optimize both hyperparameters of SVMs ($\gamma$ and $C$) automatically using packages like Optunity (available in R).

Answer 2

One of the benefits of the SVM algorithm with the kernel trick is that the dimension of the problem has little impact on runtime. LIBSVM explicitly supports sparse datasets.

(package e1071) and it throws a lot of warnings

It looks like that package is built onto of LIBSVM. In this case it might be a rare issue where 32 bit precision isn't quite enough - it depends on the warnings you are getting. Switching to a double precision version of LIBSVM as a test and seeing if the results change significantly would be a good sanity check.

the prediction accuracy is very poor

This is hard to tell without your data. It could just be that your data is hard to classify / can't be done well with an SVM, or it could be a symptom of the "warnings" you are getting.

In general, the RBF kernel doesn't provide much benefit in high dimensional spaces. Some results from the LIBSVM group have shown that degree 2 polynomial kernels can often provide some accuracy on sparse datasets. Ultimately, the linear kernel is often good enough for high dimensional problems. For this reason LIBLINEAR also exists, which is explicitly linear SVMs (and logistic regression) only . You probably want to try a linear model on your data as a sanity check as well, you may find logistic regre