# Computational complexity of classifying with an already-trained SVM

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)

• 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)?
– zwol
Oct 25 '12 at 20:10
• 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. Oct 26 '12 at 4:54
• zack, maybe cite the paper...
– vzn
Oct 26 '12 at 5:10
• @vzn: edited into question
– zwol
Oct 26 '12 at 11:10
• (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. Oct 26 '12 at 18:47