How do we use cross-validation to get hyper parameters for soft-margin Gaussian kernel SVM?

Question

I was reading this How to select kernel for SVM?

but as I am relatively new to the applied techniques in ML (only familiar with some theory) I may need some explaining on the answers. Specifically, my task is to solve for $C$ (the slack variable in soft-margin SVM) and $\sigma$ (the standard deviation of the Gaussian RBF kernel I am applying). Many of the comments just say (use cross-validation) but I would like a specific algorithm to do so. From my understanding, (I'm trying to do $k$-fold cross validation) we split the training set into $k$ roughly equal pieces (by shuffling or some other randomization) and then figuring out the best (in this case, HYPER, not just regular $\alpha$ and $\beta$ parameters we get from vanilla SVM) parameters. But HOW we get our best parameters (in this case $C$ and $\sigma$) is confounding my research.

Currently, I believe what I am doing, after reading the comments in that question thread, is "grid-search", where I am listing orders of magnitude for $C$ and linearly spacing my variance parameter $\sigma$. But I don't like this method and am wondering if there is some way to train for our values with cross-validation that is not this brute force method. This takes up a lot of time ($O(|C\times\sigma|)$, where the cardinality operator represents how many values of each we test in our grid search) and goes through bad values, while skipping over good or optimal values.

So is there any specific way to solve for an approximate optimal slack and variance parameter? Detailed descriptions of any training algorithms during this cross validation phase would be appreciated. Thanks

Answer 1

There are two popular ways to find the hyper-parameters.

1. You already mentioned this, is brute force approach of doing a grid search or random search. This involves picking multiple hyper-parameters (either from a grid or at random) and finding the one that works best in a K-fold cross-validation / validation set. Random search works typically better than grid search. Ref: http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf

2. Bayesian optimization, where you start at some initial best guess, and gradually move towards a solution based on a "cost function", each time running with a new set of hyper-parameters that probably improve the result over the previous set. This had some good references: https://arimo.com/data-science/2016/bayesian-optimization-hyperparameter-tuning/

Note, neither guarantee any theoretical guarantees to get to a good set of hyper-parameters, and require multiple runs (proportional to the number of hyper-parameters to tune).