3
$\begingroup$

What is it the relationship between the number of support vectors in an SVM and its generalization ability? When lots of support vectors are used to classify, is the error rate minimized, but only to certain threashold?

$\endgroup$
  • 4
    $\begingroup$ Some more detail would be helpful, and would prevent your question from being closed as not a real question. $\endgroup$ – Suresh Venkat Mar 7 '11 at 5:41
  • 4
    $\begingroup$ 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) $\endgroup$ – Suresh Venkat Mar 7 '11 at 6:15
  • 2
    $\begingroup$ Should I take a crack at restating the question to what I think it's asking? $\endgroup$ – Lev Reyzin Mar 8 '11 at 3:25
8
$\begingroup$

The answer to your question is a bit tricky and here 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.

$\endgroup$
  • $\begingroup$ 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?! $\endgroup$ – user693 Feb 7 '14 at 22:17
  • $\begingroup$ 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. $\endgroup$ – Lev Reyzin Feb 7 '14 at 22:23
  • $\begingroup$ 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. $\endgroup$ – user693 Feb 7 '14 at 22:26
1
$\begingroup$

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".

$\endgroup$

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.