Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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 )

share|improve this question

1 Answer

up vote 6 down vote

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)

share|improve this answer
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)? – Zack 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. – Suresh Venkat♦ Oct 26 '12 at 4:54
zack, maybe cite the paper... – vzn Oct 26 '12 at 5:10
@vzn: edited into question – Zack 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. – Suresh Venkat♦ Oct 26 '12 at 18:47
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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