Why is scikit-learn SVM.SVC() extremely slow?

python scikit-learn svm
C. Gary picture C. Gary · Oct 17, 2016 · Viewed 27.9k times · Source

I tried to use SVM classifier to train a data with about 100k samples, but I found it to be extremely slow and even after two hours there was no response. When the dataset has around 1k samples, I can get the result immediately. I also tried SGDClassifier and naïve bayes which is quite fast and I got results within couple of minutes. Could you explain this phenomena?

Answer

sascha picture sascha · Oct 17, 2016

General remarks about SVM-learning

SVM-training with nonlinear-kernels, which is default in sklearn's SVC, is complexity-wise approximately: O(n_samples^2 * n_features) link to some question with this approximation given by one of sklearn's devs. This applies to the SMO-algorithm used within libsvm, which is the core-solver in sklearn for this type of problem.

This changes much when no kernels are used and one uses sklearn.svm.LinearSVC (based on liblinear) or sklearn.linear_model.SGDClassifier.

So we can do some math to approximate the time-difference between 1k and 100k samples:

1k = 1000^2 = 1.000.000 steps = Time X
100k = 100.000^2 = 10.000.000.000 steps = Time X * 10000 !!!

This is only an approximation and can be even worse or less worse (e.g. setting cache-size; trading-off memory for speed-gains)!

Scikit-learn specific remarks

The situation could also be much more complex because of all that nice stuff scikit-learn is doing for us behind the bars. The above is valid for the classic 2-class SVM. If you are by any chance trying to learn some multi-class data; scikit-learn will automatically use OneVsRest or OneVsAll approaches to do this (as the core SVM-algorithm does not support this). Read up scikit-learns docs to understand this part.

The same warning applies to generating probabilities: SVM's do not naturally produce probabilities for final-predictions. So to use these (activated by parameter) scikit-learn uses a heavy cross-validation procedure called Platt scaling which will take a lot of time too!

Scikit-learn documentation

Because sklearn has one of the best docs, there is often a good part within these docs to explain something like that (link):

enter image description here

Related questions

Scikit Learn SVC decision_function and predict

I'm trying to understand the relationship between decision_function and predict, which are instance methods of SVC (http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html). So far I've gathered that decision function returns pairwise scores between classes. I …

Read More
Making SVM run faster in python

Using the code below for svm in python: from sklearn import datasets from sklearn.multiclass import OneVsRestClassifier from sklearn.svm import SVC iris = datasets.load_iris() X, y = iris.data, iris.target clf = OneVsRestClassifier(SVC(kernel='linear', probability=True, class_…

Read More
Python : How to find Accuracy Result in SVM Text Classifier Algorithm for Multilabel Class

I have used following set of code: And I need to check accuracy of X_train and X_test The following code works for me in my classification problem over multi-labeled class import numpy as np from sklearn.pipeline import …

Read More