7
$\begingroup$

Imagine I am using an SVM to train a classifier for a given dataset, in one-vs-all configuration. For each class, I am performing cross validation for parameter selection (grid search to choose parameters for both SVM and kernel). I am also using the RBF kernel.

In many cases, what I am observing is that the number of support vectors for the positive class exactly matches (or is very close to) the total number of positive examples. The support vectors for the negative class vary, but is still quite high.

Thus, my questions are:

1) For a linear case, is it reasonable to expect that the number of support vectors from the positive set would be significantly less (given that the data is apparently not linearly seperable).

2) Does the number of support vectors selected reflect classification "capacity" in the sense that a high capacity classifier can separate highly overlapping classes with a complex decision boundary? Is it reasonable to assume that a higher number of support vectors is indicative of high capacity?

$\endgroup$
  • $\begingroup$ Usually a very high number of support vectors indicates you are overfitting. I am going to guess your kernel matrix looks like the unit matrix. This is caused by using a too low bandwidth for the RBF kernel (e.g. low $\sigma$ or high $\gamma$, depending on your parameterization). What is your cross-validation performance? $\endgroup$ – Marc Claesen Dec 5 '14 at 6:03
  • $\begingroup$ Probably also worth adding it is a reasonably small dataset (only ~400 examples in total, classes are also fairly uneven). I'm using leave-one-subject-out crossvaliation and getting around 93-97% on average. $\endgroup$ – NOP Dec 5 '14 at 6:13
  • $\begingroup$ And actually, no the kernel does not look like a unit matrix. $\endgroup$ – NOP Dec 5 '14 at 6:32
  • 1
    $\begingroup$ @MarcClaesen A large number of support vectors does not necessarily imply over-fitting. If you optimise the hyper-parameters using CV it is quite common to get a solution with a very bland kernel and a small value of C, in which case you end up with a lot of the data being support vectors, but a smooth model. I wouldn't worry about it, the sparsity of SVMs is a nice by-product, but little more than that - I use LS-SVMs for this kind of thing, which are fully dense, but just as good in terms of generalisation. $\endgroup$ – Dikran Marsupial Dec 5 '14 at 9:10
  • 1
    $\begingroup$ @DikranMarsupial Thanks for the reaction. I am aware that a large number of SVs does not guarantee an overfit, but it often is the problem when people start using the RBF kernel. I missed the fact the OP performed cross-validation, which entirely invalidated my suspicion. $\endgroup$ – Marc Claesen Dec 5 '14 at 9:55
2
$\begingroup$

The proportion of support vectors is an upper bound on the leave-one-out cross-validation error (as the decision boundary is unaffected if you leave out a non-support vector), and thus provides an indication of the generalisation performance of the classifier. However, the bound isn't necessarily very tight (or even usefully tight), so you can have a model with lots of support vectors, but a low leave-one-out error (which appears to be the case here). There are tighter (approximate) bounds, such as the Span bound, which are more useful.

This commonly happens if you tune the hyper-parameters to optimise the CV error, you get a bland kernel and a small value of C (so the margin violations are not penalised very much), in which case the margin becomes very wide and there are lots of support vectors. Essentially both the kernel and regularisation parameters control capacity, and you can get a diagonal trough in the CV error as a function of the hyper-parameters because their effects are correlated and different combinations of kernel parameter and regularisation provide similarly good models.

It is worth noting that as soon as you tune the hyper-parameters, e.g. via CV, the SVM no longer implements a structural risk minimisation approach as we are just tuning the hyper-parameters directly on the data with no capacity control on the hyper-parameters. Essentially the performance estimates or bounds are biased or invalidated by their direct optimisation.

My advice would be to no worry about it and just be guided by the CV error (but remember that if you use CV to tune the model, you need to use nested CV to evaluate its performance). The sparsity of the SVM is a bonus, but I have found it doesn't generate sufficient sparsity to be really worthwhile (L1 regularisation provides greater sparsity). For small problems (e.g. 400 patterns) I use the LS-SVM, which is fully dense and generally performs similarly well.

$\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.