1
$\begingroup$

I am using SVMs to learn models. Every time want to use them on a "real life" data set, I see that they take forever to run.

I found that the computational complexity is O(n_samples^2 * n_features).

I made an experiment and it seems to be correct:

  • Sample size = 8780 It takes 17 secondes to train a model.
  • Sample size = 87804 It takes 1758 secondes to train a model.

However, I have a dataset with 870 000 samples. Using this formula, training with 870000 samples and 39 features will take me 50 hours...

What is the recommended approach for using SVMs with so much data?

Is working on a subset of data correct? If so how to select it?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

You probably want to use a linear SVM, or similar linear model, with kernel approximation. The Nyström method is reasonably good and works for any kernel function as long as its approximately low-rank on your dataset (most are); random Fourier features can also be quite effective for certain kernels.

This blog post gives a reasonable overview, and that author's basic implementations are available in scikit-learn.

You should also be sure to use either LIBLINEAR or other scalable linear SVM solvers, or standard code for stochastic gradient descent. Don't use software like LIBSVM, which is at least quadratic in the number of input points.

Improve this answer
$\endgroup$
0
$\begingroup$

On one hand, I agree with @Dougel, that you should use stochastic gradient solvers. I would suggest http://leon.bottou.org/projects/sgd.

Some improvement may be first applying dimensional reduction on the dataset. A popular go-to is just throw PCA to it and see if it goes well before thinking too hard about it. Assuming static structure of dataset, the eigen-dimensions you get should be valid for incoming data too. Well, maybe you need to recompute every month or so...

On the other hand, I think 870000 samples and 39 features are some rather manageable numbers given today's technologies. And if you have access to a workstation, leaving the code to run for 50 hours ~= 2 days isn't that bad for an offline evaluation of a model.

Improve this answer
$\endgroup$
1
  • $\begingroup$ vw may be preferable to Leon Bottou's SGD code; it's faster and more actively developed by a large community. Or, if you're already using a framework like scikit-learn/Shogun/..., they probably have something that's similar to SVMSGD above built in. $\endgroup$
    – Danica
    Commented Mar 8, 2016 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.