# SVM prediction time increase with number of test cases

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.

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_

• 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? Mar 8, 2016 at 14:03
• 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.
– Emre
Mar 8, 2016 at 16:27