<p>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).</p>

<p>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)</p>

CC BY-SA 3.0
2012-10-25T20:10:42.517Z
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
CC BY-SA 3.0
2012-10-26T04:54:43.367Z
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
CC BY-SA 3.0
2012-10-26T05:10:53.003Z
zack, maybe cite the paper...
vzn
CC BY-SA 3.0
2012-10-26T11:10:17.280Z
@vzn: edited into question
zwol
CC BY-SA 3.0
2012-10-26T18:47:42.367Z
(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
CC BY-SA 3.0
2012-10-27T01:00:42.920Z
find this paper hard to follow wrt the SVM implementation. my understanding is that "kernels" can be seen as intermediate processing units. are they using a single kernel? the paper also seems overblown. it classifies 1/100 pages based on the D-L distance. but suspect the classifier is mainly operating on length of the (html) pages. which if there is a good variation (as is typical with html pages) then this is not a very hard classification problem. also 100 pages is such a small sample size that just doesnt make much sense at all.... it seems actually like a toy problem dressed up...
vzn
CC BY-SA 3.0
2012-10-25T19:46:19.117Z
2012-10-25T19:46:19.117Z
Suresh Venkat
<p>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.</p>

<p>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)?</p>

<p>(This is related to <a href="https://cstheory.stackexchange.com/questions/4278/computational-complexity-of-learning-classification-algorithms-fitting-the-p">Computational complexity of learning (classification) algorithms - fitting the parameters</a> but that's about the training process.)</p>

<p>(Edit: the paper that sparked this question is <a href="http://www.cs.stonybrook.edu/~xcai/fp.pdf" rel="nofollow noreferrer">http://www.cs.stonybrook.edu/~xcai/fp.pdf</a> )</p>

<cc.complexity-theory><time-complexity><machine-learning><space-complexity>
Computational complexity of classifying with an already-trained SVM
zwol
# Computational complexity of classifying with an already-trained SVM

(Asked by: username_0 on 2012-10-25)

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](https://cstheory.stackexchange.com/questions/4278/computational-complexity-of-learning-classification-algorithms-fitting-the-p) but that's about the training process.)

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

**Tags:** cc.complexity-theory, time-complexity, machine-learning, space-complexity


---

## 1 answers

### Answer by username_1 on 2012-10-25. Score: 6

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)

> **Comments:**
> **username_0**: 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)*?  
> **username_1**: 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.  
> **username_2**: zack, maybe cite the paper...  
> **username_0**: @username_2: edited into question  
> **username_1**: (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.  
> **username_2**: find this paper hard to follow wrt the SVM implementation. my understanding is that "kernels" can be seen as intermediate processing units. are they using a single kernel? the paper also seems overblown. it classifies 1/100 pages based on the D-L distance. but suspect the classifier is mainly operating on length of the (html) pages. which if there is a good variation (as is typical with html pages) then this is not a very hard classification problem. also 100 pages is such a small sample size that just doesnt make much sense at all.... it seems actually like a toy problem dressed up...  

---

