SVM Hyperparameters Tuning

Question

I am using SVM classifier to classify data, My dataset consist of about 1 milion samples,

Currently im in the stage of tunning the machine , Try to find the best parameters including a suitable kernel (and kernel parameters), also the regularization parameter (C) and tolerance (epsilon).

My corrent approach is using a blackbox global optimization algorithm to find the best parameter set, i use k-fold cross validation as a minimazation function, The optimization algorithms i have in stock: Cma-ES, Simplex, HillClimbing, Down hill, GA and Simulated Annealing.

The problem is that the crossvalidation is a very slow process which makes all of the algorithms run for hours or even days.. and from what i know crossvalidation is the only option i have..

I want to know if it's possible to run the optimization on only a small part of the dataset to improve the runtime? , or are the parameters i will find will not work well on the full, larger dataset.

Also are the kernel parameters have any correlation with the C parameter? is it possible to firstly tune the C parameter and only after one was found continue and optimize the kernel parameters?

I know hyperparameter tuning is a very common issue so how is that im feeling there is no "clean" solution for this problem.. It must be a way that makes it possible for large datasets,

Ill appreciate any kind of help and advices

Answer 1

My experience with SVM does not include 1M datasets. I work usually up to 50K datasets. So caveat emptor.

1) there is no way to decouple gamma from C. I answered your other question on that Are the kernel parameters and the regularization parameter correlated in SVM?

2) There is no epsilon for classification. This is a hyperparameter for regression only

3) on datasets up to 50K I found that PSO work better than simplex, and SA. I hav not tried CMA or GA. There is no downhill or hill climbing unless you use some approximations to the leave one out error there is no closed expression for the gradient.

4) You don't need to use a low variance CV - I found that 2-fold is good enough. If you cannot afford the computational time of the 2-fold, than you could use a subsample, but in my experience that yields worse results.

5) IN MY EXPERIENCE, the error surface for the hyperparametrs is somewhat smooth - not convex, but smooth - there are no deep and narrow regions of low error that are worth spending a lot of computational time searching for them. Provided you are not selecting hyperparameters in a bad region of the error surface, there is no point in probing the surface too much. On that note, I would suggest a 5x5 grid search followed by another 5x5 grid around the minimum of the first grid - this should be enough. You end up probing the error surface 50 times, and you probably get a result as good as any black box optimization with the same limit on the number of probing. And it is much easily to parallelize.

Answer 2

Your questions

• "I want to know if it's possible to run the optimization on only a small part of the dataset to improve the runtime?"

As usual: "depends on the data". If you do this, try to make the smaller sample so that it has a similar distribution of labels ("stratified sampling"). This is a valid approach and can work well if your subset is sampled well.

• "Also are the kernel parameters have any correlation with the C parameter? is it possible to firstly tune the C parameter and only after one was found continue and optimize the kernel parameters?"

I cannot give you a perfectly qualified answer here, but i know from personal experience:

The C-parameter can have a big impact on the runtime (assuming a fixed epsilon here). So if you did a full run once, you could at least remember some rough bounds for the C-value per kernel. Maybe you could avoid some "obviously unnecessary" combinations this way.

Bayesian Optimization

You could try Bayesian optimization [*]. The speedup will be greater, the more hyperparameter combinations (Kernal / C / epsilon) you have. The more combinations, the more crossvalidations have to be performed.

Bayesian optimization attempts to minimizes the number of evaluations and incorporate all knowledge (= all previous evaluations) into this task. Minimizing the number of evaluations also means fewer crossvalidations. So this is probably what you want.

There is even an implementation available (**) with Jasper Snoek, first author of the mentioned paper, involved (i do knot if the other authors are involved as well).

*: https://arxiv.org/abs/1206.2944
**: https://github.com/JasperSnoek/spearmint

Disclaimer: I have studied this for the last few weeks and am really enthusiastic about this ;) I also have experience with SVMs, unfortunately i have not tried both BO and SVM in combination.

Answer 3

Have you considered Random Search for the Hyper-Parameters, I know they have it in Scikit-learn. I also found the paper that explains it by James Bergstra ,Yoshua Bengio. From my understanding the method works best when you have a low affective dimention compared to the number of hyper parameters.

Answer 4

My understanding is that for non-linear SVM kernels training time scales as a square of the number of training examples, i.e. if you double the training examples training time will quadruple. Add in cross validation and your 1M training examples and it is not surprisingly that training is prohibitively computationally expensive.

If your training samples are unbalanced (i.e. for a classification problem a large majority of outcomes belong to one class), sub-sampling the majority class to reduce both class imbalance and therefore the total training set size might be optimal. In this case you're discarding data that may not be needed, but still producing a representative training set.

If your training samples are balanced, then cross validation on a reduced-size training set really defeats the purpose of cross validation - namely validating that the train/test split for each fold is representative of the distribution of the entire 1M record training set. Rather than reduce the size of the training set, I'd reduce the number of folds - or simply not do cross validation, but instead use a proportionally large (and therefore hopefully representative) test set, e.g. 20-40% of your 1M samples.

In general a Bayesian Optimisation method is much more efficient than either grid or random hyperparam optimisation as it is a guided search in hyperparam space. There are a variety of Bayesian and a few non-Bayesian hyper-parameter optimisation libraries to choose from. Have a look at:

http://fastml.com/optimizing-hyperparams-with-hyperopt/

I've used hyperopt with a lot of success. SMAC looks very interesting as it incorporates cross validation and will not necessarily validate every fold if it determines that a particular candidate set of hyperparams will not score better as compared to previous folds.

If you do want to use SVM with cross validation on 1M training examples then GPUs might be able to do the heavy computational lifting you require. Check out:

http://mklab.iti.gr/project/GPU-LIBSVM