3
$\begingroup$

I am using scikit-learn's SVM for the MNIST digit classification dataset. In order to improve the performance I extended the dataset by adding rotated samples. I was aware that SVM takes O(N^3) time to train the data, where N is the number of training vectors.

However even prediction seems to take increase polynomially, the number of test vectors is the same. Is there any explanation for this or some equation that relates prediction time to the number of training samples?

I am using a 3rd degree polynomial as the kernel with C=100.0.

Note: I am doing a group project to compare the performance of various methods so I can't use any other method as my teammates would have used those. I referred to a paper by Decoste and Scholkoph which uses Virtual SVM. However I don't think I can run this on my current system if I can't run a simple extended training set.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The number of support vectors must be increasing. The prediction time is proportional to that; after all, the kernel classifier is $f(x) = \sum_i \alpha_i k(x, x_i)$, where the summation is over the support vectors. With sklearn you can find out how many you have by inspecting n_support_

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you! Yes, an increase in support vectors would give more prediction time. However is there a relation between number of support vectors and size of training dataset? $\endgroup$
    – Leela Prabhu
    Mar 8, 2016 at 14:03
  • $\begingroup$ That's a good question. The answer is yes, but for details I'll defer details to this paper: Sparseness of Support Vector Machines—Some Asymptotically Sharp Bounds. $\endgroup$
    – Emre
    Mar 8, 2016 at 16:27

Your Answer

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

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