Gridsearch for SVM parameter estimation

Question

I'm currently experimenting with gridsearch to train a support vector machine. I understand that, if I have parameter gamma and C, the R function tune.svm performs a 10-fold cross validation for all combinations of these 2 parameters.

Since I did not know how to start, I tried to get some information about it, for example wikipedia2 suggests values that are not linear, e.g. C in the range {10, 100, 1000}.

So far I use the examples from my second wikipedia link, which is:

gammas = 2^(-15:3)
costs = 2^(-5:15)

Which results into 399 combinations.

This takes very, very long (~2000 samples). For example for the kernel "radial" my best result is gamma = 0.5 and cost = 2.

Couldn't I get the same result if I just used values like (1, 2, 3, 4, ... 10) for costs and (0, 0.5, 1, 1.5, 2) for gammas? I know this example is constructed because I already know the result.

My question:

But why this exponential scale?

There are so many values between 0 and 1 that I think this is a waste of computation time and only so few very big numbers that it couldn't find a very exact result anyway. It would only make sense for me if this was used to find a smaller range, let's say we then know the best cost is 2^3 and then we search around that. But it's nowhere mentioned that is performed that way.

Answer 1

The reason for the exponential grid is that both C and gamma are scale parameters that act multiplicatively, so doubling gamma is as likely to have roughly as big an effect (but in the other direction) as halving it. This means that if we use a grid of approximately exponentially increasing values, there is roughly the same amount of "information" about the hyper-parameters obtained by the evaluation of the model selection criterion at each grid point.

I usually search on a grid based on integer powers of 2, which seems to work out quite well (I am working on a paper on optimising grid search - if you use too fine a grid you can end up over-fitting the model selection criterion, so a fairly coarse grid turns out to be good for generalisation as well as computational expense.).

As to the wide range, unfortunately the optimal hyper-parameter values depends on the nature of the problem, and on the size of the dataset and cannot be determine a-priori. The reason for the large, apparently wasteful grid, is to make sure good values can be found automatically, with high probability.

If computational expense is an issue, then rather than use grid search, you can use the Nelder-Mead simplex algorithm to optimise the cross-validation error. This is an optimisation algorithm that does not require gradient information, so it is pretty straightforward to use for any problem where grid-search is currently used. I'm not an R user, but Nelder-Mead is implemented in R via optim.

Answer 2

This is called the "parameter tuning" issue for SVMs. One of the easiest approaches is to take the median of each for the greatest levels of class prediction accuracy obtained as you go through the CV folds.

Also, as a rule of thumb, use a simpler classifier to determine if your data are linearly separable. If k-nearest neighbor (kNN) or linear regression works better, then you shouldn't use a more expensive (computationally) approach like SVM. SVM can be easily overused, so make sure you evaluate linear regression, kNN, linear discriminant analysis, random forests, etc.