2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ It seems that the slow regimes correspond to those in which there are too many support vectors. Try increasing the regularization coefficient C, which penalizes slack, and monitoring the number of support vectors through clf.n_support_ $\endgroup$
    – Emre
    Oct 17 '17 at 3:15
  • $\begingroup$ stackoverflow.com/questions/40077432/… $\endgroup$
    – G__
    Jun 9 at 17:44
2
$\begingroup$

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.

$\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.