2
$\begingroup$

I am working in an extremely memory constrained environment, and the number of support vectors my Matlab design is generating is just not something that scales. That led me to move to finding a way to lower the number of support vectors. And I came across this paper from MIT: http://dspace.mit.edu/handle/1721.1/54725

The paper is available for free download.

Now on Page 4203 (look at the bottom, journal page indexing prolly), the last paragraph states: The application of Reduced Set Methods [8], a model order reduction technique, allowsthe nonlinear descriminant function tobe expressed using N M << support-vectors.

Now the 8th Reference for this paper is only a link to a toolbox, here: Statistical PatternRecognition Toolbox ForMatlab (STPRTool): http://cmp.felk.cvut.cz/cmp/software/stprtool/index.html

My question is: does anyone have any idea how to reduce support vectors? Some simple algorithm and its implementation? I will be grateful for a response.

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

A simple (quick&dirty) way. I assume this is a classification problem. If you look at the Wolffe dual representation of the svm problem, you actually want a larger proportion of the $\alpha_i$'s to be 0. In other words you want to multiply the second term of the objective function (in the dual representation) by a number $0<\gamma<1$ or equivalently multiply the $y_i$'s by $\gamma^{-1/2}$ (e.g. map them from $\text{sign}(y_i)$ to $\text{sign}(y_i)\gamma^{-1/2}$).

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Well, for the alphas I do understand that they are sparse, but support vectors are supposed to be equal to smaller than the training matrix. Question is how to take a subset of them that accurately represents or fairly represents the decision boundary. $\endgroup$ – user1343318 Apr 30 '13 at 21:01
  • $\begingroup$ I don't understand your question. The complexity of your decision boundary is the $\#$ of non-0 alpha's. $\endgroup$ – user603 May 1 '13 at 6:37
  • $\begingroup$ What I am trying to say is that final prediction is made by a combination of alphas, the bias, and a Kernel which operates on support vectors and test example. The problem here is the number of support vectors. That is the problem. I will be grateful for a response. $\endgroup$ – user1343318 May 1 '13 at 12:58
  • 1
    $\begingroup$ but the support vectors are those observations for which the corresponding alpha_i's>0 (strict). This is why by reducing the # of non-0 alpha's you also reduce the # of support vectors. Is it clear? $\endgroup$ – user603 May 1 '13 at 14:03
1
$\begingroup$

The easiest solution would be to use a linear SVM, in which case the 'support vectors' can be combined together in a single weight vector.

For kernel SVMs, you might want to look at budget SVMs, which focus on strategies to reduce the number of support vectors kept during the optimization. Here is one interesting reference with source code :

Z. Wang, K. Crammer, and S. Vucetic, “Breaking the Curse of Kernelization : Budgeted Stochastic Gradient Descent for Large-Scale SVM Training,” Journal of Machine Learning Research, vol. 13, pp. 3103–3131, 2012. (pdf)(source code)

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

There are a number of different clever algorithms to try to reduce the number of support vectors, but if your problem is ill-conditioned or you are using wrong parameter values, there is not much you can do.

Is your problem well balanced?. I often come across with the problem, that data is highly imbalanced (there are very small number of samples of a given class). If that is the case, you will end up with a higher number of SVs.

Also, using the proper kernel for the problem makes a difference.

You may want to go through this short guide. It gives you good advice on how to use SVMs and deal with some common problems.

| cite | improve this answer | | | | |
$\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.