sklearn SVM really slow

Question

I'm working with sklearn SVM and I have a problem.

When I run the method sklearn.SVM.SVC.fit() using a database with only a few features (< 10) it takes a very long time. This is weird because, when I run the same method with the same database using all of the features (> 100) it takes just a few seconds.

I'm using a polynomial kernel and this problem only appears when the degree is >= 3. And it is also weird that if I use only a few features, but I add 50 features with 0s in all the samples, it works fine!

I have tried the following experiments:

• fit() with all the features and any kernel degree. Works fine.

• fit() with a few features and kernel degree <= 2. Works fine.

• fit() with a few features and kernel degree >= 3. Very slow.

• fit() with kernel degree = 3, a few features but adding 50 features with 0s in all the samples. Works fine!!

My question is, how can I solve this? Does my trick of adding features with 0s affect the classification?

Answer 1

Support Vector Machines attempt to find a hyerplane that divides two classes with the largest margin. Therefore this is an optimization problem. Support vectors are the points that lie along the supporting hyerplane. One key factor that plays into the complexity of the runtime for a support vector is the slack parameter C. The slack parameter allows for a soft-margin and better generalization. The number of support vectors varies depending on how much slack we allow and how the data is distributed. The less slack we give the SVM the fewer support vectors we get and converserly the more slack we give it the more support vectors we receive.

There also exist a relationship between the complexity of the model. The more complex the models tend to require more support vectors.

In short, it doesn't really matter how many features you feed it, the SVM computational complexity is linear in the number of support vectors.