9
$\begingroup$

Are there better alternative methods to choose C and Gamma which yield better training performance?

$\endgroup$
5
$\begingroup$

Grid search is slow as it spends a lot of time investigating hyper-parameter settings that are no where near optimal. A better solution is the Nelder-Mead simplex algorithm, which doesn't require calculation of gradient information and is straightforward to implement (there should be enough information on the Wikipedia page). There may also be some java code in the Weka toolbox, however I work in MATLAB and haven't looked at Weka in any great detail.

SMO is an algorithm for finding the model parameters, rather than the hyper-parameters.

$\endgroup$
  • $\begingroup$ Could you provide your matlab implementation? $\endgroup$ – Zach Nov 28 '11 at 21:00
  • 1
    $\begingroup$ There is one here theoval.cmp.uea.ac.uk/matlab/#optim but if you already have the optimisation toolbox then fminsearch is also an implementation of the Nelder-Mead method IIRC. $\endgroup$ – Dikran Marsupial Nov 29 '11 at 10:41
5
$\begingroup$

The Nelder-Mead simplex method can involve as many function evaluations as a simple grid search. Usually the error surface is smooth enough close to the optimal parameter values that a coarse grid search followed by a finer one in a smaller region should suffice.

If you're interested in gradient based optimization of C and gamma, there are methods like optimizing the radius-margin bounds or optimizing the error rate on a validation set. The computation of the gradient of the objective function involves something like one SVM train but a simple gradient descent may involve only a few dozen iterations. (Look at http://olivier.chapelle.cc/ams/ for an article and a Matlab implementation.)

$\endgroup$
  • $\begingroup$ In my experience, nelder-mead is usually faster than grid search and gradient descent is only slightly faster becuase while it takes fewer iterations, the cost of computing the gradient is high. So if you have an implementation that provides gradient descent then use it, but Nelder-Mead probably won't be far behind. Of course as soon as you have more than two hyper-parameters to tune grid search immediately becomes much the slowest method. It would be interesting to see an study of the comparative efficiencies of each method. $\endgroup$ – Dikran Marsupial Dec 5 '11 at 11:17
  • $\begingroup$ You're right that if the number of parameters is more than a couple, grid search is not viable. But the same is true of Nelder-Mead, because the size of the simplex is determined by the dimensionality. $\endgroup$ – Innuo Dec 7 '11 at 14:26
  • $\begingroup$ only to the same extent as for gradient descent, adding an extra dimension to the problem only adds one extra point to the simplex, so like gradient descent it scales roughly linearly in the number of hyper-parameters. I've used it with problems with 40+ hyper-parameters and it is only slightly slower than gradient descent (you tend to get over-fitting in model selection either way though with that many hyper-parameters). $\endgroup$ – Dikran Marsupial Dec 7 '11 at 14:35
0
$\begingroup$

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.

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