If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine? I care about both time and space complexity.

Does the answer change if the underlying metric space is unusual -- for instance, Damerau-Levenshtein edit distance (computing which is $O(n^2)$ time and space for strings of equal length) instead of Euclidean ($O(n)$ time and $O(1)$ space)?

(This is related to Computational complexity of learning (classification) algorithms - fitting the parameters but that's about the training process.)

(Edit: the paper that sparked this question is http://www.cs.stonybrook.edu/~xcai/fp.pdf )


If you're classifying using SVMs, then the underlying metric space is always a Hilbert space. If your classifier is linear, then the running time of the classification is linear in the dimensionality of the data (or the number of features).

If the classifier (in general) involves some kernel, then the classifier is expressed in terms of the number of support vectors, and the classification is linear in the number of such vectors. Processing each vector takes time proportional to the kernel computation time (which could be constant, or linear in the data dimension, or something else)

  • $\begingroup$ Hmm. I am looking at a paper that was not terribly concerned with theoretical precision. It talks about training a support vector machine using D-L edit distance "as the metric". Do I understand correctly that this has to have been implemented as an initial kernel transform, and subsequent classification operations would start by computing k D-L distances (k the number of support vectors), then run the normal SVM algorithm in a k-dimensional space, for overall time O(k·n^2)? $\endgroup$
    – zwol
    Oct 25 '12 at 20:10
  • $\begingroup$ I'm not sure what it means to define an SVM in a general metric space. SVMs are essentially "hyperplanes" and need a space that admits such a notion. $\endgroup$ Oct 26 '12 at 4:54
  • $\begingroup$ zack, maybe cite the paper... $\endgroup$
    – vzn
    Oct 26 '12 at 5:10
  • $\begingroup$ @vzn: edited into question $\endgroup$
    – zwol
    Oct 26 '12 at 11:10
  • $\begingroup$ (on the paper you link to) it's not clear how their construction yields a positive definite kernel. In any case, the running time is probably governed by the number of support points, because it's not clear that an explicit kernel representation can be extracted. $\endgroup$ Oct 26 '12 at 18:47

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.