17
$\begingroup$

I am using SVM models to do short term forecasting of air pollutants. To train a new model I need to find appropriate metaparameters for an SVM model (I mean C, gamma and so on).

Libsvm documentation (and many other books I have read) suggests using grid search to find these parameters - so I basically train model for each combination of these parameters from a certain set and choose the best model.

Is there any better way to find optimal (or near optimal) metaparameters? For me it is mainly a matter of computation time - one grid search of this problem takes about two hours (after I did some optimisations).

Pros of grid search:

  • It can be easily parallelized - if you have 20 CPUs it will run 20 times faster, parallelizing other methods is harder
  • You check big parts of metaparameter space, so if there is a good solution you will find it.
$\endgroup$
10
$\begingroup$

The downside being of grid search being that the runtime grows as fast as the product of the number of options for each parameter.

Here is an entry in Alex Smola's blog related to your question

Here is a quote:

[...] pick, say 1000 pairs (x,x’) at random from your dataset, compute the distance of all such pairs and take the median, the 0.1 and the 0.9 quantile. Now pick λ to be the inverse any of these three numbers. With a little bit of crossvalidation you will figure out which one of the three is best. In most cases you won’t need to search any further.

I haven't tried this myself, but it does seem kind of promising.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How is this related to the question? The question is about finding the best parameters to an SVM model (in a quick way). $\endgroup$ – Roronoa Zoro Feb 7 '12 at 23:40
  • 2
    $\begingroup$ @Roronoa Zoro: and so is the answer. It is explaining how to find the parameters for radial basis functions based SVMs (C and \lambda in Smola's blog post) in 3|Cs| time as opposed to |\gammas||Cs| like it is done in the case of grid search. $\endgroup$ – carlosdc Feb 7 '12 at 23:49
  • $\begingroup$ Just to clarify to make sure I'm understanding the heuristic, basically you just randomly draw 1000 data points from the dataset for training the SVM, then take the inverse of the .1, .9 quantiles and median and those are likely to be good candidates for a suitable gamma? $\endgroup$ – tomas Feb 24 '12 at 21:06
6
$\begingroup$

If you make the assumption that there is a relatively smooth function underlying the grid of parameters, then there are certain things that you can do. For example, one simple heuristic is to start with a very coarse grid of parameters, and then use a finer grid around the best of the parameter settings from the coarse grid.

This tends to work quite well in practice, with caveats of course. First is that the space is not necessarily smooth, and there could be local optima. The coarse grid may completely miss these and you could end up with a sub-optimal solution. Also note that if you have relatively few samples in your hold-out set, then you may have a lot of parameter settings that give the same score (error or whatever metric you're using). This can be particularly problematic if you are doing multi-class learning (e.g. using the one-versus-all method), and you have only a few examples from each class in your hold-out set. However, without resorting to nasty nonlinear optimisation techniques, this probably serves as a good starting point.

There's a nice set of references here. In the past I've taken the approach that you can reasonably estimate a good range of kernel hyperparameters by inspection of the kernel (e.g. in the case of the RBF kernel, ensuring that the histogram of the kernel values gives a good spread of values, rather than being skewed towards 0 or 1 - and you can do this automatically too without too much work), meaning that you can narrow down the range before starting. You can then focus your search on any other parameters such as the regularisation/capacity parameter. However of course this only works with precomputed kernels, although you could estimate this on a random subset of points if you didn't want to use precomputed kernels, and I think that approach would be fine too.

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

I use simulated annealing for searching parameters.

The behavior is governed by a few parameters:

  • k is Boltzmann's constant.
  • T_max is your starting temperature.
  • T_min is your ending threshold.
  • mu_T (μ) is how much you lower the temperature (T->T/μ)
  • i is the number of iterations at each temperature
  • z is a step size - you determine what exactly that means. I randomly move within old*(1±z).
  1. Take a starting point (set of parameter values).
  2. Get an energy for it (how well it fits to your data; I use chi-squared values).
  3. Look in a random direction ("take a step").
    • If the energy is lower than your current point, move there.
    • If it's higher, move there with a probability p = e^{-(E_{i+1} - E_i)/(kT)}.
  4. Repeat, occasionally lowering T->T/μ every i iterations until you hit T_min.

Play around with the parameters a bit and you should be able to find a set that works well and fast.

And the GNU Scientific Library includes simulated annealing.

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

If anyone is interested here are some of my thoughts on the subject:

  • As @tdc suggested I'm doing coarse/fine grid search. This introduces two problems:
    • In most cases I will get set of good metaparameter sets that have wildly different parametes --- i'm interpreting it in this way that these parameters are optimal solutions, but to be sure I should check all fine grids near all these good parameters (that would be take a lot of time), so for now I check only neighbourhood of bets metaparameter set.
    • In most cases fine search doesn't increase SVM performance (that may be due to fact that I'm checking only neightbourhood of best point from coarse grid.
  • I observed behaviour that most computing time is spent on metaparemeters sets that will not yield good results, for example: most metaparameter sets will compute in under 15 seconds (and best of them have error rate of 15%), and some take 15 minutes (and most of these have error rates bigger that 100%). So when doing grid search I kill points that take more than 30seconds to compute and assume they had infinite error.
  • I use multiprocessing (which is simple enough)
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If the kernel is radial, you can use this heuristic to get a proper $\sigma$ -- C optimisation is way easier then.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The link is dead. What was the heuristic you were referencing? $\endgroup$ – Aalawlx Oct 16 '17 at 17:19

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.