4
$\begingroup$

Have a quick question about parameter selection for an SVM. I'm using a rbf kernel, so trying to optimize C and gamma. I have an example set of around 4500, about 700 features, and using 700 examples from the set for testing. My dataset does consist of time series. I've been using a 5 fold cross validation with a grid search to find the optimal parameters for the test set and have continued to noticed fairly large differences between the accuracy of my training set vs. the accuracy of my test set. Note, however, when I say accuracy, I have imposed a cost matrix when evaluating the fit of the model such that certain classes have much higher costs when misclassified (note i also ran the svm with unequal class weights). Because my data is a time series, I'm wondering if I should use a different approach from cross validation e.g. a moving window evaluation or something similar. Is cross validation the best approach? Are there other ways to search for the optimal parameters? And also, are there ways to speed up the parameter search (I've heard of using minimum finding algorithms as an alternative to a grid search, which I'm considering implementing)?

Any thoughts would be most welcome. Thanks.

$\endgroup$
  • $\begingroup$ I would say that cross-validation is a good approach, since it is generally applicable and prevents overfitting---as long as you perform every parameter selection within the cross-validation loop. As for grid search: see my comment to @Sentry's answer below. More in general, you could try one of the many Meta-Heuristics algorithms, such as evolutionary strategies. These usually work quite well---especially if you have many different parameters to set---but they are not always trivial to implement yourself. $\endgroup$ – MLS Jul 30 '12 at 14:10
2
$\begingroup$

I have found the Nelder-Mead simplex method very handy for optimizing the hyper-parameters of kernel machines. It doesn't require gradient information and it is almost as fast as gradient descent. If you are using MATLAB it is the fminsearch function in the optimisation toolbox, or alternatively you can download my implementation here.

I would not advise using algorithms such as simulated annealing or genetic algorithms as it is very easy to over-fit the model selection criterion, even if you only have a couple of hyper-parameters to tune, and such methods that optimise the criterion very aggressively are likely to encounter this pitfall. This is actually a benefit of grid-search - it doesn't optimise the model selection criterion too closely and this helps avoid over-fitting.

Don't pay any attention to the difference between trainings set and test set performance, it generally doesn't mean much (in fact I would recommend not looking at training set performance at all unless you suspect something is going wrong).

Make sure you use a completely separate test set for evaluating the final performance of the model. If you tune the hyper-parameters using the test set, you will get a (possibly highly) optimistic performance estimate. Use a training-validation-test partitioning scheme and optimise the hyper-parameters using the validation set and measure performance on the test set. I use nested cross-validation.

As I understand it, cross-validation is O.K. for time-series data, provided the data in each partition are essentially statistically independent (e.g. the time period covered by each partition is much longer than the effects of autocorrelation in the time series etc.). However, I am no time-series expert, so caveat lector!

$\endgroup$
1
$\begingroup$

There is a recently proposed method to speed up grid search: "Fast Cross validation via sequential analysis"

http://www.scribd.com/doc/76134034/Fast-Cross-Validation-Via-Sequential-Analysis-Talk

Basically, they're doing a normal grid search, but try to eliminate bad parameters early in the process and not waste too much computation on them. It's fairly new and I don't know independent evaluations of their method, but I'm currently implementing it and want to give it a try.

$\endgroup$
  • 1
    $\begingroup$ I haven't read the paper you refer to, but note that in general you can view a grid search as a Bandit task and use the efficient algorithms for that framework. This does what you mention: reduce the computation on parameters that are unlikely to be the best choice. $\endgroup$ – MLS Jul 30 '12 at 14:06

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.