Linear SVM very slow - python scikits.learn

Not an answer, but fwiw a couple of runtimes for scikits.learn libsvm / liblinear, just to give an idea of how they vary with kernel. ("The most important parameter is the one you haven't thought of.")

    # added 10 Aug, sgd waaay faster  --
 12 sec  sgd        mnist28 (10000, 784)  tol 0.1  C 1  penalty l2  correct 89.6 %
321 sec  LinearSVC  mnist28 (10000, 784)  tol 0.1  C 1  penalty l2  correct 86.6 %

  94 sec LinearSVC   mnist28 (5000, 784)  tol 0.01  C 1  correct 90.6 %
 341 sec SVC linear  mnist28 (5000, 784)  tol 0.01  C 1  correct 93.9 %
1353 sec SVC rbf     mnist28 (5000, 784)  tol 0.01  C 1  correct 84.3 %
     # added --
 174 sec LinearSVC   mnist28 (5000, 784)  tol 0.001  C 1  correct 90.6 %
 319 sec SVC linear  mnist28 (5000, 784)  tol 0.001  C 1  correct 93.9 %
4059 sec SVC rbf     mnist28 (5000, 784)  tol 0.001  C 1  correct 84.3 %

The data is Mnist from http://deeplearning.net/data/mnist/mnist.pkl.gz, train the first 5k, test the last 5k of the 70k vecs. My versions: python 2.6.4 numpy 1.6.0 scikits.learn 0.8.1, mac ppc.

http://peekaboo-vision.blogspot.com/2010/09/mnist-for-ever.html gets to 98 % -- rbf kernel, default tol .001 (LinearSVC .0001), runtimes unknown.

To see how runtimes vary with number of features, one could just use np.repeat( X, repeat, axis=1 ).

Again fwiw, here's the code snippet. (It took me a while to realize that, while LinearSVC has multi_class=, SVC is automatically multiclass if y has > 2 values; but it's not clear which multiclass algorithm it then uses.)

if algo == "sgd":
    clf = linear_model.SGDClassifier( seed=seed )
elif algo == "LinearSVC":
    clf = svm.LinearSVC( multi_class=True, tol=tol, C=C )
        # penalty = "l1", dual = (penalty == "l2")
else:
    clf = svm.SVC( kernel=algo, tol=tol, C=C, gamma=gamma, shrinking=True )  # linear, rbf
fit = clf.fit( X, y )
ypred = fit.predict( Xtest )
correct = (ypred == ytest) .mean() * 100

t = "%.0f sec %s  %s %s  tol %.2g  C %.2g  correct %.1f %%" % (
    time() - t0, algo, source, X.shape, tol, C, correct)
print t
print >>tty, t
svmutil.pconfus( ytest, ypred, nclass )

I totally agree with Lucas that the data set is pretty large. I strongly recommend to drastically reduce the number of features.

Liblinear is one of the best SVM solvers out there. Compared to SGD it is really user-friendly: it does not require careful hyper-parameter tuning but you need to keep some things in mind (see LIBSVM guide). Most importantly: center your data since SVMs are not scale invariant. (If you haven't done it, this should be the first thing you should try!)

Furthermore, did you use the default parameters for SVC or did you use kernel="linear"? The default kernel of SVC is non-linear (it's a poly kernel). If your data is non-linear it is plausible that SVC converges faster because LinearSVC has a hard time finding a reasonable linear fit (in this case use a smaller C parameter for LinearSVC).

Good luck!

best, Peter

I'm not sure whether this switch is exposed in scikits but liblinear is able to switch between optimising the primal and the dual. You should try try that. Other than this, I don't think there is much that you can do. And I highly doubt that you can write a SVM that is faster than LibLinear. You might try stochastic gradient descent methods for linear classification. I haven't done much with them myself but I think they should be faster. Cheers, Andy

Have you considered using their logistic regression implementation instead? The method is not too different, but it's optimized with SGD.

Before switching to another library you should try to increase the tolerance of the convergence criterion of your model. For instance, most of the time in scikit-learn this is a parameter called tol (see the documentation of LinearSVC for instance).

As Peter said: don't forget to scale your data. Have look at the chapter on data preprocessing.

You can also try to reduce the dimensionality by transforming you data with:

from scikits.learn.pca import RandomizedPCA
pca = RandomizedPCA(n_components=500).fit(X_train)
X_train_pca = pca.transform(X_train)

# keep the pca instance around to be able transform
# the test set the same way later
X_test_pca = pca.transform(X_test)

Then you can train your SVC, LinearSVC, SGDClassifier or LogisticRegression model on X_train_pca instead. If you want to use SVC with a rbf kernel (the default) it might be worth trying to whiten the data as well:

pca = RandomizedPCA(n_components=500, whiten=True).fit(X_train)
X_train_pca = pca.transform(X_train)

I don't have much experience with using dense data like that, but I'm not surprised that it takes a long time to run on a 100,000,000 entry dense matrix! You might try some feature selection to reduce the dimensionality of the input. In my experience, the feature selection in scikits.learn can run out of memory on inputs that large, though you can easily alter the code used here to run in an online fashion to improve its memory efficiency.