3
$\begingroup$

Say we are training a radial SVM with parameters $C$ and $\gamma$. We would typically do this using grid search and CV. My prof. alluded that one does not have to exhaust all of $C$ values in the grid to obtain the optimal solution and I'm sure the popular packages don't search over all $C$ values either for the sake of speed. So my question is how is it done optimally, i.e. going over the least amount of $C$ values (for a given $\gamma$)?

I'm thinking that if one start from the lowest value of $C$, we may stop once the performance no longer improves. Is this optimal?

$\endgroup$
  • 1
    $\begingroup$ How are you defining "optimal"? $\endgroup$ – Sycorax Sep 28 '17 at 22:05
4
$\begingroup$

I'm sure the popular packages don't search over all C values either for the sake of speed

Hastie et al. made this point obsolete. Using the regularization paths for ordinary SVMs would allow one to explore many values for C faster (at the order of magnitude of the time of a single evaluation). See this paper: The Entire Regularization Path for the Support Vector Machine.

So you can investigate the whole path at once to pick the optimal cost without having to depend on heuristics.


While R wasn't mentioned, you can fiddle with the method in the R package svmpath, created by Hastie himself. [CRAN link and manual].

The SVM has a regularization or cost parameter C, which controls the amount by which points overlap their soft margins. Typically either a default large value for C is chosen (allowing minimal overlap), or else a few values are compared using a validation set. This algorithm computes the entire regularization path (i.e. for all possible values of C for which the solution changes), with a cost a small (~3) multiple of the cost of fitting a single model.

$\endgroup$
4
$\begingroup$

When C is very low, the model is biased, and usually produces poor results. When C is very large, the model produces poor results due to high variance. The optimal C is somewhere in between. You can usually start with C's in the range of $2^{-7}$ to $2^7$, using powers of 2 for steps. Usually the sweet spot is included. If needed, you can then increase resolution to search for the optimal C in a smaller range.

$\endgroup$
3
$\begingroup$

Note sure if your prof. meant it, but I'd like to mention another alternative to grid search for hyperparameter tuning: Bayesian optimization.

The idea is to treat $f: (C, \gamma) \rightarrow Result_{svm}$ as an unknown function, which we can evaluate only in certain points and would like to optimize as fast as possible.

Bayesian optimization method builds a model of the function $f$ using a Gaussian Process (GP) and at each step chooses the most "promising" point based on the current GP model. It starts with no information and acts like a random search, but gradually learns that some areas are "better" then others. These methods also try to deal with exploration-exploitation dilemma.

In my research, I use Bayesian optimization a lot, especially when I need to optimize not two, but a dozen of hyperparameters. See this question is you need further details.

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