SVM parameter selection and cross validation

Question

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.

Answer 1

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.

Answer 2

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!