Hyperparameters optimization

April 13, 2018

Stefano Martina

---

The construction of machine learning models models demands big effort on hyperparameters tuning. Usually the hyperparameters are manually engineered and are the product of time-consuming experimentations. Hyperparameters choose is really important in model performance.

We can use two methods in order to overcome this manual intervention:

1. automatic hyperparameters optimization;
2. development of models with reduced hyperparameters number.

Hyperparameters optimization

Problem definition

Given a machine learning algorithm $A$ with hyperparameters $\lambda_1,\dots,\lambda_n$ in $\Lambda_1,\dots,\Lambda_n$, the hyperparameters space is defined as $\Lambda=\Lambda_1\times\cdots\times\Lambda_n$. For each hyperparameter setting $\vec{\lambda}\in\Lambda$, we use $A_\vec{\lambda}$ to indicate $A$ using this setting. We use $\loss(A_\vec{\lambda}, \data_{train}, \data_{valid})$ to denote the validation loss of $A_{\lambda}$ using $\data_{valid}$ validation set, when is trained using $\data_{train}$ training set.

Using $k$-fold cross validation we divide the dataset in $k$ splits $\data_{train}^{(1)},\dots,\data_{train}^{(k)}$ and $\data_{valid}^{(1)},\dots,\data_{valid}^{(k)}$. The hyperparameter optimization problem is:

$$\begin{equation} \argmin_{\vec{\lambda}\in\Lambda}\ f(\vec{\lambda}), \label{eq:problem} \end{equation}$$

where $f$ is the loss:

$$\begin{equation} f(\vec{\lambda}) = \frac{1}{k}\sum_{i=1}^k\loss(A_{\vec{\lambda}},\data_{train}^{(i)},\data_{valid}^{(i)}). \label{eq:loss} \end{equation}$$

Hyperparameters can be continuous, integer or categorical. An hyperparameter $\lambda_i$ is conditional on another hyperparameter $\lambda_j$ if $\lambda_i$ is active only when $\lambda_j$ takes values in a specific set $V_i(j)\subset\Lambda_j$.

Review

Historically the standard in hyperparameters optimization was grid search. This method consists in:

1. define a grid $V\subset\Lambda$ on hyperparameters space, respect to certain ranges;
2. evaluate \eqref{eq:loss} for all $\vec{\lambda}\in V$;
3. take the $\vec{\lambda}$ with the smaller value of loss.

A more advanced approach consists in starting with a coarse grid and refining the best result with a fine one around it.

other approaches include:

• gradient search when some differentiability and continuity conditions of the training criterion are satisfied [Bengio2000] ;
• evolutionary computation techniques [Guo2006] ;
• racing algorithms [Maron1994] .

It has been proven that a random search is more effective than grid search on models with low effective dimensionality [Bergstra2012] .

This improvement is visible in Fig 1 where an example bidimensional parameter space is shown. The green area identifies an important parameter, the yellow one an unimportant one. Thus the effective dimensionality of the example is closer to one respect to two. In both grid and random search settings we use a cardinality of nine for $V\subset\Lambda$, but in the grid layout we test the important parameter only on three values instead of nine.

Recently more sophisticated Sequential Model-based Bayesian Optimization (SMBO) [Hutter2011] methods have been developed. Those methods grant better results on \eqref{eq:problem} and are capable of optimize when $\Lambda$ has far more dimensions respect to other methods.

Sequential Model-based Bayesian Optimization (SMBO)

SMBO are generic framework for optimizing blackbox functions. It uses a probabilistic model $\model$ to model $f$ based on point evaluation and any prior. It uses $\model$ to evaluate promising inputs and update $\model$ itself.

In Fig 2 is visible the algorithm that resume the optimization. In order to determine the candidate $\vec{\lambda}$ in line 3, SMBO uses an acquisition function $a_\model:\Lambda\rightarrow\mR$. The purpose of this function is to quantify the usefulness of chosing a configuration $\vec{\lambda}\in\Lambda$. The objective is to maximise:

$$\begin{equation*} \argmax_{\vec{\lambda}\in\Lambda}\ a_\model(\vec{\lambda}). \end{equation*}$$

The function $a_\model$ must be selected according to the tradeof between the exploitation (concentrate in regions where the performances are good) and exploration (trying unexplored regions) of the hyperparameters space $\Lambda$. The most used function is the Expected Improvement (EI):

$$\begin{equation} EI(\vec{\lambda}) = \int_{-\infty}^{f_{min}}\max\{f_{min}-f, 0\}\cdot p_\model(f\mid\vec{\lambda})\ df \label{eq:ei} \end{equation}$$

that at each value $\vec{\lambda}$ integrates the improvements over $f_{min}$ accordingly to a posterior $p_\model(f\mid\vec{\lambda})$ over the model $\model$.

Using a gaussian posterior with mean $\mu_\vec{\lambda}$ and variance $\sigma_\vec{\lambda}^2$, \eqref{eq:ei} simplifies to:

$$\begin{equation*} EI(\vec{\lambda}) = \sigma_\vec{\lambda}\cdot(u\cdot\Phi(u)+\phi(u)), \end{equation*}$$

where $u=\frac{f_{min}-\mu_\vec{\lambda}}{\sigma_\vec{\lambda}}$ and $\phi$ and $\Phi$ are the PDF¹ and CDF² of the standard normal distribution.

The following bayesian optimization packages have been used in literature:

• Sequential Model-based Algorithm Configuration (SMAC) [Hutter2011] uses random forests to model $p_\model(f\mid\vec{\lambda})$ as a gaussian distribution whose mean and variance are the empirical mean and variance over predictions of the forest’s tree.
• Spearmint [Snoek2012] uses a Gaussian Process to model $p_\model(f\mid\vec{\lambda})$.

• Tree Parzen Estimator (TPE) [Bergstra2011] models $p(\vec{\lambda}\mid f)$ and $p(f)$ instead of $p(f\mid\vec{\lambda})$. That is:

  $$\begin{equation*} p(\vec{\lambda}\mid f) = \left\{ \begin{array}{ll} l(\vec{\lambda})&\mathrm{if}\ \ f<f^*\\ g(\vec{\lambda})&\mathrm{otherwise} \end{array} \right. \end{equation*}$$

  where $l(\vec{\lambda})$ is the PDF formed by using observations $\{\vec{\lambda}^{(i)}\}$ such that $f(\vec{\lambda}^{(i)})<f^*$ and $g(\vec{\lambda})$ using the remaining observations. $f^*$ is chosen to be a quantile $\gamma$ of the observed $f$ such that $p(f<f^*)=\gamma$.

Spearmint works for problems with few hyperparameters.

---

References

---

Footnotes