1
$\begingroup$

What is the typical number of kernel evaluations (between two training vectors) performed during a (kernelized) Support Vector Machine (SVM) training?

I am asking this question because I need to determine how much I need to optimize the kernel in order to have some hope to do the training in a reasonable amount of time. The current kernel calculation time is prohibitive (1+ hour), but there is room for improvement (by many orders of magnitude).

Note: There are about 60k vectors in one class and 10k vectors in the other one.

|cite|improve this question
$\endgroup$
3
$\begingroup$

That actually depends on the particular solver you are using, and the data you work with. It depends on the data, because the resulting number of support vectors you get depends on the problem at hand. As a consequence, adding/removing certain features might simplify your problem, thus taking less time to train and resulting in fewer support vectors.

In any case, this question is answered in detail in the paper Support Vector Machine Solvers, where a complexity of training a SVM is analyzed, and they also describe and compare different implementations.

Hope that helps.

ON REPLY TO YOUR FIRST REPLY: Do you use libsvm?. If so, you could try alpha seeding. LibSVM supports it. More details here and my reply to other question here for a quick intuitive description. Another approach migth be using stochastic gradient descent on SVM

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Useful reference, indeed. It reads "(…) the computational cost of solving the SVM problem has both a quadratic and a cubic component. It grows at least like $n^2$ when C is small and $n^3$ when C gets large." It also reads "In practice, computing kernel values often accounts for more than half the total computing time." The only missing information is the typical factors in front of these asymptotic complexities in practical implementations: do you have any information on this? $\endgroup$ – Eric O Lebigot Apr 8 '13 at 12:00
  • $\begingroup$ I'm sorry, I do not have any further information on the concrete factors. $\endgroup$ – jpmuc Apr 9 '13 at 7:49
  • 1
    $\begingroup$ @EOL don't be confused, kernel evaluations between two instances are performed no more than once; regardless of the complexity. The absolute number of evaluations depends entirely on how 'easy' a given training problem is. $\endgroup$ – Marc Claesen Jul 5 '13 at 19:07

Your Answer

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

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