4
$\begingroup$

I would like to do a random search for hyperparameter optimization. The procedure can be found in link. One possibility is to define a fine grid and take random combinations. A better approach would be to define a distribution for each parameter.

I'm thinking about optimizing SVM with parameters C and gamma (RBF kernel) and also k-nearest neighbours. Of course C and gamma are continuous while k is discrete.

What distributions can be choosen for C, gamma and k?

Second, let's assume a random search optimization over parameters which have to sum to one. How could one incorporate this constraint into the search?

$\endgroup$
2
$\begingroup$

What distributions can be choosen for C, gamma and k?

To reproduce results from other methods, define a box and sample uniformly in the box. This will parallel the procedure of grid search, or any other tuning method, since each point is equally likely a priori.

But if you want some distributions more informative than these, then you'll have to work that out for the problem at hand because that is inherently a context-dependent question: some problems have larger/smaller $\gamma$ and $C$ than others, which is why we tune hyper-parameters in the first place.

If you decide to make this a fully Bayesian problem with informative probabilities over hyper-parameters, embedding the problem as a logistic regression can create a direct path to probability models.

Second, let's assume a random search optimization over parameters which have to sum to one. How could one incorporate this constraint into the search?

Use a stick-breaking process. You start with a unit interval, and pick a point in the interval according to a probabiltiy distribution over the unit interval. Then you iterate $k-1$ times the process for the interval "to the right" (or left) of the chosen point. At the end, you'll have $k$ value which sum to 1.

You could also review the stan documentation pertaining to sampling of simplex random variables for an alternative presentation of the concept.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Let's say I have a box [1,10]. How can I sample uniformly from it (e.g. using Matlab)? Should I just generate a random number between [1,10]? $\endgroup$ – BlackHawk May 3 '16 at 22:51
  • $\begingroup$ Regarding the stick-breaking process: Let's assume I have an initial interval of [0,1] and I pick the value 0.7 at random for the first value. So we now that only 0.3 remains for the other values, so I sample from [0,0.3] for the second value. Let's say the second value gets a value of 0.2, so the third value will be sampled from [0,0.1]. Is my understanding correct? $\endgroup$ – BlackHawk May 3 '16 at 22:54
  • $\begingroup$ Your understanding is correct. Don't know how to do it in Matlab. $\endgroup$ – Sycorax May 3 '16 at 23:27
  • $\begingroup$ @BlackHawk but note the relationship between the Dirichlet distribution and simplex-valued random variables. $\endgroup$ – Sycorax May 3 '16 at 23:35
  • $\begingroup$ What role does this relationship play here? $\endgroup$ – BlackHawk May 3 '16 at 23:48
3
$\begingroup$

There are full bayesian formulations for SVMs. Why not using those?. In the case of SVM you may consider Relevance Vector Machines.

kNN is not bayesian, and independent of the underlying probability distribution. How to define a prior then?.

Bayesian models are generative models, that is, they model a complete pdf from which the data is supposed to be sampled from. Therefore, I find it would be more natural to consider GMM or some other more modern non-parametric technique. The question becomes then on how to determine the optimal number of components. The standard way is to sample from a Dirichlet prior, and then sample from the particular mixture obtained from it.

$\endgroup$
-2
$\begingroup$

You are basically describing a Bayesian Optimization (updating the distributions of parameters as you observe fitness values). The GPyOpt devel branch has a tutorial on how to fit SVM with it. Constraints should be relatively straightforward to add.

However, all this might be an overkill. If you are simply interested in how search might improve fitting you might just as well start simple with something like a genetic algorithm.

$\endgroup$
  • $\begingroup$ Where does OP suggest updating his parameter distributions after observing fitness? $\endgroup$ – Sycorax May 2 '16 at 15:18
  • $\begingroup$ you are doing a search. As you get results from your search (in terms of statistical loss for example) you want to update the distribution from where you sample hyper-parameters so that it's more likely the next hyper-parameters are good. Bayesian optimization simply involves updating the original distribution from where you were sampling hyper-parameters to guide search onto promising areas. I suppose you don't HAVE to, but there is no real reason not to run efficient search. $\endgroup$ – CarrKnight May 2 '16 at 15:44
  • $\begingroup$ I understand what Bayesian Optimization is, but my point is that OP is not necessarily asking about BO. In fact, OP is explicitly asking about random search methods, as he explicitly names this method. We can directly contrast random search to BO because BO incorporates information about the objective function while random search does not, so BO is not an answer to OP's question (even if it may be superior to random search). $\endgroup$ – Sycorax May 2 '16 at 15:47
  • $\begingroup$ Sure, fair enough. It seems to me however that if the question pertains the choice of distributions to sample from it is just natural to suggest using a methodology that discover such distribution on its own. Moreover since the final aim of the question is fitting SVMs then providing, as I did, a link to a tutorial showing the passages will do wonder. Perhaps this might still be an overkill but surely it can't really hurt or deserve the opprobrium it generated. $\endgroup$ – CarrKnight May 2 '16 at 21:18
  • $\begingroup$ Thanks for the tutorial. Unfortunately, I'm not familiar with python. Do you know a similar tutorial for Matlab or Java? $\endgroup$ – BlackHawk May 3 '16 at 22:43

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.