6
$\begingroup$

I'm trying to run the libsvm-provided wrapper script easy.py on a training set of 100K rows, each row has ~300 features. The feature data is relatively sparse, say only 1/10th are non-zero values.

The script is excruciatingly slow, I'm talking days (or more). I ran the same script on 1% of the data, and it finished in about 20 minutes, with some reasonable looking results, so it looks like the input data / format is correct and there are no obvious issues with it.

I found the documentation for libsvm to be somewhat lacking and not very helpful on practical issues like performance. Their FAQ is silent on these matters: http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html

Has anyone experienced similar issues with SVM training speed? Do you know of more suitable libraries or specific strategies to try out in such cases?

$\endgroup$
  • 3
    $\begingroup$ If the complexity is indeed $O(n^3)$, then you should expect the full dataset to take $10^6 \times 20 \, min \approx$ 40 years. So it looks like your method is doing not so badly after all. $\endgroup$ – Hans Engler Aug 27 '11 at 21:58
  • $\begingroup$ I removed the part about n^3 because I'm not sure about that, and you're right, the 20 mins would translate to years in that case. I can't be the first person trying to train SVMs on 100K rows though, right? $\endgroup$ – user6020 Aug 28 '11 at 0:23
  • $\begingroup$ n^3 is wrong. For a general kernel the complexity is in pn^2. For linear kernels it can be sup linear. $\endgroup$ – user603 Aug 29 '11 at 7:15
  • $\begingroup$ If you are not going to use kernel then switch to liblinear. It is amazingly much faster than libsvm. $\endgroup$ – user49428 Jul 3 '14 at 9:05
8
$\begingroup$

I've seen liblinear runtimes very sensitive to tol; try tol=.1, and if possible linear not rbf. How many classes do you have ? How much memory do you have ? Monitor real / virtual with "top" or the like.

Stochastic gradient descent, SGDClassifier in scikits.learn is fast. For example, on Mnist handwritten digit data, 10k rows x 768 features, 80 % of the raw data 0, -= mean and /= std:

 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 %

This is with no tuning nor cross-validation; your mileage will vary.

Added: see also Sofia-ml -- comments anyone ?

And please post what worked / what didn't.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy