Order of Support Vectors, and how to reduce them

Question

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.

Answer 1

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}$).

Answer 2

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)

Answer 3

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.