<p>The answer to your question is a bit tricky and <a href="http://www.stat.cmu.edu/~cshalizi/350/lectures/27/lecture-27.pdf">here</a> are good lecture notes to read to understand the various generalization error bounds. Let me try to summarize what's happening with SVMs and their generalization.  These PAC bounds are also found in "An Introduction to Support Vector Machines: And Other Kernel-Based Learning Methods" by 
Cristianini and John Shawe-Taylor.</p>

<p>Assuming a linear classifier correctly classifies all training examples (separable case), one bound (Vapnik '95 (<em>I think</em>)) on the generalization error of a linear classifier is (ignoring log factors):
$$
\epsilon = \tilde{O}\left(\frac{1}{n}\left( \frac{R^2}{\gamma^2} \right)\right),
$$
where $R$ is a bound on the size of the vectors, $n$ is the number of samples, and $\gamma$ is the <em>margin</em>, which is the distance to the support.  This bound says that the margin (the only quantity the learner has control over if the number of training examples are fixed), is an important quantity to maximize in SVM.</p>

<p>However, there is an intuition the margin is maximized in <em>sparse</em> solutions, and the sparseness of a solution is measured by the number of support vectors, so there is a relationship between the generalization bound and the quantity you're interested in.</p>

<p>Another relevant bound for any classifier (not just the linear case) is the following "compression bound" (Littlestone and Warmuth '86), which basically says that if a classifier gets $n$ examples right but can be obtained by training it on just $m$ examples then you can bound its generalization error by
$$
\epsilon \approx \frac{m \log n}{n-m}.
$$
Here, you can think of $m$ as the number of support vectors.  This directly relates the number of support vectors to the generalization error.</p>

<p>These two bounds help explain the interplay between the margins, the number of support vectors, and the generalization ability of an SVM (in the separable case).  In the non-separable case where you do not classify all training examples correctly, you get slack variables, slightly messier bounds, etc.</p>

CC BY-SA 3.0
2014-02-07T22:17:39.703Z
I do not really understand all these bounds. How do we know $R$ and $\gamma$ a-priori?! Seems to me that all these bounds are a-posteriori bounds, therefore one still cannot know how to choose $N$ to achieve a desired $\epsilon$ in the generalization error. Am I wrong?!
user693
CC BY-SA 3.0
2014-02-07T22:23:30.383Z
Unless you know something about the target distribution, you are right -- these are generally problem-dependent parameters that are not known in advance.  This is still a valid bound.  In practice, though, you have as much data as you have, and you use as much as you can.
Lev Reyzin
CC BY-SA 3.0
2014-02-07T22:26:16.867Z
I see your point and I understand that in practice it works. However, in theory, using more samples does not guarantee that the expected generalization error decreases. I mean that only upper bounds on the generalization error are known.
user693
CC BY-SA 2.5
2011-03-07T19:52:16.470Z
2011-03-07T20:06:34.923Z
2011-03-07T20:06:34.923Z
Lev Reyzin
<p>See Theorem 6.27 in "Structural risk minimization over data-dependent hierarchies" (Shawe-Taylor et al., <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=705570&amp;tag=1" rel="nofollow">http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=705570&amp;tag=1</a>) attributed to Littlestone and Warmuth, "Relating Data Compression and Learnability".</p>

CC BY-SA 2.5
2011-03-07T10:15:07.557Z
2011-03-07T10:15:07.557Z
Aryeh
<p>What is it the relationship between the number of support vectors in an <a href="http://en.wikipedia.org/wiki/Support_vector_machine" rel="nofollow">SVM</a> and its generalization ability?  When lots of support vectors are used to classify, is the error rate minimized, but only to certain threashold?</p>

CC BY-SA 2.5
2011-03-07T05:41:36.803Z
Some more detail would be helpful, and would prevent your question from being closed as not a real question.
Suresh Venkat
CC BY-SA 2.5
2011-03-07T06:15:29.257Z
1. for this audience define (or point to definitions of) support vectors and generalization. 2. Define the "error rate" (since there are different kinds of error)
Suresh Venkat
CC BY-SA 2.5
2011-03-08T03:25:03.403Z
Should I take a crack at restating the question to what I think it's asking?
Lev Reyzin
<lg.learning><ai.artificial-intel>
Support Vector Machines
edgarmtze
# Support Vector Machines

(Asked by: username_0 on 2011-03-07)

What is it the relationship between the number of support vectors in an [SVM](http://en.wikipedia.org/wiki/Support_vector_machine) and its generalization ability? When lots of support vectors are used to classify, is the error rate minimized, but only to certain threashold?

**Tags:** lg.learning, ai.artificial-intel
> **Comments:**
> **username_1**: Some more detail would be helpful, and would prevent your question from being closed as not a real question.  
> **username_1**: 1. for this audience define (or point to definitions of) support vectors and generalization. 2. Define the "error rate" (since there are different kinds of error)  
> **username_2**: Should I take a crack at restating the question to what I think it's asking?  

---

## 2 answers

### Answer by username_2 on 2011-03-07. Score: 8

The answer to your question is a bit tricky and [here](http://www.stat.cmu.edu/~cshalizi/350/lectures/27/lecture-27.pdf) are good lecture notes to read to understand the various generalization error bounds. Let me try to summarize what's happening with SVMs and their generalization. These PAC bounds are also found in "An Introduction to Support Vector Machines: And Other Kernel-Based Learning Methods" by
Cristianini and John Shawe-Taylor.

Assuming a linear classifier correctly classifies all training examples (separable case), one bound (Vapnik '95 (*I think*)) on the generalization error of a linear classifier is (ignoring log factors):
$$
\epsilon = \tilde{O}\left(\frac{1}{n}\left( \frac{R^2}{\gamma^2} \right)\right),
$$
where $R$ is a bound on the size of the vectors, $n$ is the number of samples, and $\gamma$ is the *margin*, which is the distance to the support. This bound says that the margin (the only quantity the learner has control over if the number of training examples are fixed), is an important quantity to maximize in SVM.

However, there is an intuition the margin is maximized in *sparse* solutions, and the sparseness of a solution is measured by the number of support vectors, so there is a relationship between the generalization bound and the quantity you're interested in.

Another relevant bound for any classifier (not just the linear case) is the following "compression bound" (Littlestone and Warmuth '86), which basically says that if a classifier gets $n$ examples right but can be obtained by training it on just $m$ examples then you can bound its generalization error by
$$
\epsilon \approx \frac{m \log n}{n-m}.
$$
Here, you can think of $m$ as the number of support vectors. This directly relates the number of support vectors to the generalization error.

These two bounds help explain the interplay between the margins, the number of support vectors, and the generalization ability of an SVM (in the separable case). In the non-separable case where you do not classify all training examples correctly, you get slack variables, slightly messier bounds, etc.

> **Comments:**
> **username_3**: I do not really understand all these bounds. How do we know $R$ and $\gamma$ a-priori?! Seems to me that all these bounds are a-posteriori bounds, therefore one still cannot know how to choose $N$ to achieve a desired $\epsilon$ in the generalization error. Am I wrong?!  
> **username_2**: Unless you know something about the target distribution, you are right -- these are generally problem-dependent parameters that are not known in advance.  This is still a valid bound.  In practice, though, you have as much data as you have, and you use as much as you can.  
> **username_3**: I see your point and I understand that in practice it works. However, in theory, using more samples does not guarantee that the expected generalization error decreases. I mean that only upper bounds on the generalization error are known.  

---

### Answer by username_4 on 2011-03-07. Score: 1

See Theorem 6.27 in "Structural risk minimization over data-dependent hierarchies" (Shawe-Taylor et al., <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=705570&tag=1>) attributed to Littlestone and Warmuth, "Relating Data Compression and Learnability".


---

