Bayesian Optimization Summary: Effective Methodology of Exploring Hyperparameters in Deep Learning Models

Introduction

Hyperparameter Optimization refers to the problem of exploring the optimal value of a hyperparameter, a value that must be set in advance to perform learning. In this context, the optimal value of a hyperparameter refers to the value of the hyperparameter that results in the best generalized performance of the trained learning model.

For example, when training a deep learning model, the learning rate, minibatch size, L2 regularization coefficient, etc. are typical hyperparameters. Of course, those hyperparameters are strictly related to the learning algorithm or regularization, and in some cases, factors that determine the structure of a deep learning model (e.g., number of layers, convolution filter size, etc.) can also be considered hyperparameters and added as objects of exploration.

Manual Search

If you’ve trained a deep learning model at least once, you’ve undoubtedly experienced a lot of trial and error in determining the values of these key hyperparameters. For example, when we complete an implementation of the AlexNet model, we usually start by taking the hyperparameters introduced in the original AlexNet paper and applying them to learning. However, in most situations, the dataset used in the original AlexNet paper and the dataset you want to use are different, so the hyperparameter values introduced in the original paper are rarely the perfect solution to the problem you’re trying to solve.

When faced with this situation, you’ll typically rely on your intuition or popular know-how to select candidate hyperparameter values to try next, perform learning with them, and record the performance results measured against the validation set. After this process is repeated a few times, you’ll probably have chosen the hyperparameter values that performed best against the validation set among all the attempts up to that point to train the deep learning model for the final submission. This method of exploring for optimal hyperparameter values is known as manual search.

While manual search is the most intuitive method of Hyperparameter Optimization, it has some issues. The first is that the process of finding the “optimal” hyperparameter is somewhat based on luck. As an example, let’s describe the process of performing a manual search to find the optimal learning rate for a deep learning model. It’s highly likely that there’s a time limit on this process, and you’ll probably get very impatient, thinking:

I need to get this deep learning model to perform quickly, and my professor or boss keeps pushing me, and I don’t have time... I’m in trouble :’(

Let’s say you have a limited amount of time to train a deep learning model and measure its performance by applying 9 different learning rate values in sequence: 0.01, 0.05, 0.03, 0.02, 0.025, 0.0225, 0.0275, 0.015, 0.04, and the result is the top result in the figure above, so you choose 0.0025
as the final learning rate value. This exploration process was probably a careful application of your own intuition with each learning session, and it’s very hard for anyone to deny that the results of such a painstaking process are the best possible results.

However, what if “the (unknown) generalization performance function as a function over learning rate” actually looked something like the second image above? While 0.0025 was not actually the optimal learning rate value (values between 0.003 and 0.0035 are optimal), we can speculate that your impatience and bias in the existing manual exploration process led to disappointing results. We may have unintentionally pointed out a mistake you may have made in the past, but it’s not fully your fault. The disadvantage of doing a manual search based on subjectivity and intuition is that it’s relatively difficult to guarantee that the optimal hyperparameter values you find are “actually” optimal, as shown in the example above.

The second problem with manual search is that it becomes more complicated when you want to explore multiple types of hyperparameters at once. The best example of this is the relationship between the learning rate and L2 regularization coefficient.

$L(W)=\frac{1}{N}\sum _{i=1}^N{L}_i(f(x_i,W),y_i)+\lambda \cdot R(W)$L(W)=1N∑_i=1NL_i(f(xi,W),y_i)+λ⋅R(W)

The second term in the loss function above is the L2 regularization term, where when changing the value of λ, the L2 regularization coefficient, (in the entire parameter W space of the deep learning model) the shape of the loss functions L(W) will also change. Because of this, we can assume that the value of the optimal learning rate for optimal performance will also change naturally.

Because some of these hyperparameters have mutual influence on each other, it becomes very difficult to apply existing intuition to each hyperparameter when exploring more than one at a time.

Grid Search vs. Random Search

Compared to manual search, grid search and random search are relatively systematic ways to perform Hyperparameter Optimization.

Grid search selects candidate hyperparameter values at regular intervals within a specific range to explore, records the performance measured for each of them, and then selects the hyperparameter value that showed the best performance. While this method still requires a human touch to decide how many intervals to search, what length to set the intervals, and so on, it has the advantage of a more uniform and vast exploration compared to the manual search. However, the tradeoff is that with this method, the overall exploration time increases exponentially as the number of exploration target hyperparameters increases.

On the other hand, random search is broadly similar to grid search, but differs in that it uses random sampling to select candidate hyperparameter values within the interval being explored. Random search is known to find optimal hyperparameter values faster than grid search, as it significantly reduces the number of unnecessary repetitions while still being able to probabilistically explore values that lie between the designated grids.

Nevertheless, it may be hard to shake off the feeling that even random search “still seems like a bit of unnecessary exploration.” This is because, in both grid search and random search, the process of selecting candidate hyperparameter values to try next doesn’t reflect any prior knowledge of the performance of the hyperparameter values during previous investigations. In Manual Search, on the other hand, prior knowledge is implicitly applied at every turn.

Bayesian Optimization is a methodology that allows you to systematically perform the entire exploration process while still reflecting enough prior knowledge to effectively investigate new hyperparameter values each time.

Bayesian Optimization

In essence, Bayesian Optimization aims to find the optimal solution 
x given an unknown objective function f that maximizes the function 
f(x) given some input value x^∗. We typically assume that we don’t explicitly know the expression of the objective function (i.e., black-box function), and that it takes a long time to calculate one function value f(x). In this situation, the main goal is to quickly and efficiently find the optimal solution that maximizes f(x), x^∗ by sequentially examining the function values for as few candidate input values as possible.

There are two essential elements to Bayesian Optimization. First, a surrogate model makes a probabilistic estimate of the shape of an unknown objective function based on the input value and function value points (x₁,f(x₁)),...,(x_t,f(x_t)) that have been investigated so far. Then the acquisition function recommends the next "most likely to be useful in finding the optimal input x^∗,” input candidates x_t+1, based on the current probabilistic estimation of the objective function.

Surrogate Model

The model that makes a probabilistic estimate of the approximate form of the unknown objective function, based on the input value and function value points (x₁,f(x₁)),...,(x_t,f(x_t)) examined so far, is called the surrogate model. The most popular probabilistic model used as a surrogate model is the Gaussian Process (GP).

Gaussian Processes

Unlike ordinary probability models (which express probability distributions over any given variable), GPs represent probability distributions over a collection of functions, and are characterized by the fact that the joint distribution between their components follows a Gaussian distribution. GP uses a mean function μ and a covariance function k to express the probability distribution over functions.

$f(x)\sim \mathcal{G}\mathcal{P}(\mu (x),k(x,x^{\prime })).$f(x)∼GP(μ(x),k(x,x′)).

To properly understand and use GP, you should have a basic understanding of Bayesian probability and be able to understand complex stochastic/linear algebraic formulas. This post won’t go into any more detail, but will focus on the operating characteristics of GPs and how they can be used for Hyperparameter Optimization.

Given input value-function value points investigated so far (x₁,f(x₁)),...,(x_t,f(x_t)), GP makes a probabilistic estimate of the objective function as shown in the figure below.

In the figure above, if we consider the horizontal axis to be the input value 
x and the vertical axis to be the function value f(x), then the black solid line is estimated based on the points (x₁,f(x₁)),...,(x_t,f(x_t)) examined so far to show the “mean” x at each μμ(x) location, and the blue shaded line corresponds to the “standard deviation” at each σσ(x) location. For μ μ(x), the shape is determined by necessarily passing through the points (x1,f(x1)),...,(xt,f(xt)) that have been investigated so far, with σ(x) being smaller for locations closer to the investigated points and σ σ(x) being larger for locations farther away. The natural implication of this is that the farther x is from the investigated point, the greater the ‘uncertainty’ in the average value estimated for that point.

In the above figure, when it’s t=2 as there are only two input-value points investigated, we can observe that σ(x) is large in most areas that are at least a certain distance from these two points. Meanwhile, as the number of points investigated gradually increases to t=3 t=4, the size of the areas with large σ σ(x) gradually decreases, and the estimation of the actual objective function is gradually compressed. This shows that as the number of points investigated increases, the uncertainty about the estimation of the objective function decreases, and we can assume that as this trend becomes stronger, the likelihood of finding the input value X^∗ that maximizes the objective function numerator will continue to increase.

Surrogate Models other than GP

In addition to GP, any model that can cover the uncertainty in estimating the objective function based on the input value and function value points investigated so far can be used as a surrogate model. Commonly used surrogate models in addition to GP include Tree-structured Parzen Estimators (TPE) and Deep Neural Networks.

In the same context as GP, even if you don’t have a deep understanding of these surrogate models, if you understand the larger context of Bayesian Optimization, you can still perform Bayesian Optimization using related libraries.

Acquisition Function

Based on the surrogate model’s probabilistic estimates of the objective function to date, the function that recommends candidate input values x_t+1
to investigate next is called the acquisition function. It was mentioned that the selection of x_t+1 is ultimately “the most useful” for finding the optimal input value x^∗ to the objective function. Let’s think about what we mean by “useful” in this context. For illustration purposes, we’ve brought back the figure that shows the situation at t=2 during the objective function estimation process using GP.

Given that there are only points (x,f(x)) that have been investigated so far, it’s plausible to predict that the true optimal input value x∗ is more likely to be found near the point with the larger function value (the one on the right in the figure). Naturally, a reasonable strategy to try next would be to test the area around the point with the largest function value among the points investigated so far. This is officially called “exploitation.”

Let’s think about it from a different perspective this time. Intuitively, you can feel that for the area that lies between the two points investigated so far and has a large standard deviation (=uncertainty) Σ Σ(X), it will be very difficult to guarantee that the estimated mean function value in this part will be similar to the actual target function value. From that perspective, it’s plausible to think there’s a possibility that the optimal input value X^∗ exists in this uncertain area, and we should explore it further,” and it’s therefore a reasonable strategy to try next to the point with the largest standard deviation over the objective function estimated so far. This is officially called “exploration.”

While exploration and exploitation strategies are equally important approaches to effectively finding the optimal input value x^∗, the problem is that the nature of the two strategies is a trade-off. Thus, properly adjusting the relative intensity of the exploration/exploitation tradeoff is critical to successfully identifying the optimal input for the actual objective function.

Expected Improvement (EI)

The expected improvement (EI) function is designed to include some aspects of both exploration and exploitation strategies, and is most often used as an acquisition function. Based on the objective function estimated to date, for any candidate input x, taking into account the Probability of Improvement (PI) of producing a function value f(x₁),...,f(x_t) greater than the maximum output f(x⁺)=max_if(x_i) of the points examined to date and the magnitude of the difference between that function value and F(X⁺), the EI outputs a number that represents the “usefulness” of that input value x. Here, let’s take a look at the figure below to understand the concept of PI.

In the figure above, the largest function value f(x⁺) of the points investigated so far occurred at the point on the far right. Here, for the candidate input value x³, which is further to the right, the probability distribution of 
f(x₃) (along the vertical axis) based on the probabilistic estimation can be represented as a skewed Gaussian distribution, as shown in the figure.

Meanwhile, the area of the probability distribution of f(x₃) that corresponds to values greater than f(x⁺) is shaded green in the figure. The larger size of this area indicates that f(x₃) is more likely to be larger than f(x⁺), which leads to the conclusion that taking x3 as the next input value is more likely to yield a larger function value than the existing points, and that for finding the optimal input x∗ to the objective function, x₃ is the “most useful” candidate.

The PI value computed for the input value x₃ is then weighted for the function f(x3), by the difference between the average μ μ(x₃) and f
(x⁺),f(x³)−f(x⁺), to finally compute the EI value for x3. It’s important to find a point that has a higher probability of obtaining a larger function value than the existing points, but if that probability exists, it’s also important to consider how much larger it actually is., and this calculation is meant to reflect that.

For reference, the formula for EI when using GP can be summarized and expressed as follows (after a long derivation process). In the formula below, 
Φ and ϕϕ denote the cumulative distribution function (CDF) and probability distribution function (PDF) of the standard normal distribution, respectively, and ξis a parameter that controls the relative strength between exploration and exploitation. The larger ξi s, the stronger the exploration, and the smaller it is, the stronger the exploitation.

For the situation at t=4 in the objective function estimation process using GP above, the result of calculating the value of EI for each input value x, EI(
x) using the EI formula above, is shown as the green solid line at the bottom of the figure below.

In fact, we can simultaneously observe in the figure that the EI value is large (exploitation strategy) around the point x⁺, which has the largest function value among the points investigated so far, and that the EI value is also large around the point with the largest standard deviation σσ(x) on the objective function estimated so far (exploration strategy).

EI(x)=E[max(f(x)−f(x⁺),0)]={(μ(x)−f(x⁺)−ξ)Φ(Z)+σ(x)ϕ(Z) ifσ(x)>00ifσ(x)=0

Acquisition Functions other than EI

Probability of Improvement (PI) is an acquisition function that was proposed earlier than EI, which reflects only the probability of deriving a function value greater than the maximum function value of the points investigated to date among the considerations of EI. Other commonly used acquisition functions include Upper Confidence Bound (UCB) and Entropy Search (ES).

Performing Bayesian Optimization to explore hyperparameters in deep learning models

So far, we’ve covered the essential elements of Bayesian Optimization and how they basically work. Now, let’s visualize in more detail a scenario where Bayesian Optimization is applied when actually exploring the hyperparameters of a deep learning model. For the sake of convenience, only the learning rate is discussed here as the hyperparameter to explore.

1. Defines the input value, objective function, and other settings.
   1. Input value x: learning value Objective function f(x)
   2. Performance results (e.g., accuracy) on a validation set for a deep learning model learned by applying a set learning rate
   3. Input value x‘s target intervals explored: (a,b).
   4. Number of input value and function value points to be investigated first: n
   5. Maximum number of input value and function value points to be investigated until the last round: N
2. Within the set exploration target interval (a,b), the initially selected n
   input values are randomly sampled and selected.
3. After training the deep learning model by setting the learning rate values for each of the n selected inputs x₁,x₂,...,x_n, calculate the performance results of the learned model using the validation set. Each of these is regarded as a function value f(x₁),f(x₂),...,f(x_n). n input values are randomly sampled and selected.
4. Probabilistic estimation is performed using the surrogate model on the collection of input value and function value points (x₁,f(x₁)),(x₂,f(x₂)),...,(x_n,f(x_n)).
5. Until you reach a total of NN inspected input value and function value points, the process below is repeated for t=n,n + 1,...,N − 1.
   1. Based on the probabilistic estimation results of the Surrogate Model for the collection (x₁,f(x₁)),(x₂,f(x₂)),...,(x_t,f(x_t)) of existing input value and function value points, calculate the value of EI within the input interval (a,b), and select the point with the largest value as the next input value candidate x_t+1.
   2. After training the deep learning model with the following input value candidate x_{t +1} as the learning rate value, use the validation set to calculate the performance result for the learned model and consider it as the f(x_{t +1}) value.
   3. Add the new points (x_t+1, f(x_t+1)) to the existing collection of input value and function value points and perform probabilistic estimation with the surrogate model again on the updated collection of points.

6. Based on the objective function results estimated probabilistically over a total of N input value and function value points, select the optimal solution that maximizes the mean function μ μ(x),x^∗. Later, if you perform learning on a deep learning model using that x^∗ value as the learning rate, you’ll get a model with maximized generalization performance.

    

Conclusion

Hyperparameter Optimization in deep learning refers to the problem of exploring the optimal value of a hyperparameter, a value that must be set in advance to perform learning on a deep learning model. Typical hyperparameters for training deep learning models include learning rate, minibatch size, L2 regularization coefficient.

The simplest and most intuitive method for hyperparameter optimization is the commonly used manual search, which involves subjectively selecting candidate hyperparameter values to try in each round, learning with them, and recording the performance results measured against a validation set. This method has a disadvantage in that it’s relatively difficult to find optimal hyperparameter values due to the experimenter’s implicit bias in the process of finding the optimal hyperparameter. While grid search and random search can compensate for the shortcomings of manual search, they are limited in that they don’t reflect any prior knowledge gained during the hyperparameter investigation.

Bayesian Optimization is a Hyperparameter Optimization methodology that can make the overall exploration process more systematic while still reflecting enough prior knowledge when investigating new hyperparameter values each time. A surrogate model, one of the two components of Bayesian Optimization, makes a probabilistic estimate of some unknown objective function based on the input value and function value points examined to date. A typical example of this is the Gaussian Process (GP). Meanwhile, the acquisition function recommends the next candidate input value that is most likely to be useful in finding the optimal input value based on the current probabilistic estimation of the objective function. A typical example of this is Expected Improvement (EI).

Use Bayesian Optimization for hyperparameter optimization of deep learning models by applying hyperparameters to explore for optimal values as the input value of Bayesian Optimization and using performance results from the validation set of a deep learning model learned by applying specific hyperparameter values as a function value of the objective function.

*In the next part, we’ll build on the understanding gained so far and go through the process of exploring the optimal solution of a simple example function using bayesian-optimization, a Python library for real-world Bayesian Optimization, and then explore the optimal hyperparameters of a real-world deep learning model.

References

• Shahriari, Bobak, et al. “Taking the human out of the loop: A review of bayesian optimization.” Proceedings of the IEEE 104.1 (2016): 148-175.
• Brochu, Eric, Vlad M. Cora, and Nando De Freitas. “A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning.” arXiv preprint arXiv:1012.2599 (2010).
• Bengio, Yoshua. “Practical recommendations for gradient-based training of deep architectures.” Neural networks: Tricks of the trade. Springer, Berlin, Heidelberg, 2012. 437-478.
• Goodfellow, Ian, et al. Deep learning. Vol. 1. Cambridge: MIT press, 2016.
• Bergstra, James, and Yoshua Bengio. “Random search for hyper-parameter optimization.” Journal of Machine Learning Research 13. Feb (2012): 281-305.
• Fernando Nogueira, bayesian-optimization: A Python implementation of global optimization with gaussian processes.
• Hunting Optima, Expected Improvement for Bayesian Optimization: A Derivation. 

$\begin{array}{rl}EI(x)& =\mathbb{E}[max(f(x)-f(x^{+}),0)]\\ & =\{\begin{array}{ll}(\mu (\mathit{x})-f({\mathit{x}}^{+})-\xi )\mathrm{\Phi }(Z)+\sigma (\mathit{x})\varphi (Z)& \text{if}\sigma (\mathit{x})>0\\ 0& \text{if}\sigma (\mathit{x})=0\end{array}\end{array}$$\begin{array}{rl}EI(x)& =\mathbb{E}[max(f(x)-f(x^{+}),0)]\\ & =\{\begin{array}{ll}(\mu (\mathit{x})-f({\mathit{x}}^{+})-\xi )\mathrm{\Phi }(Z)+\sigma (\mathit{x})\varphi (Z)& \text{if}\sigma (\mathit{x})>0\\ 0& \text{if}\sigma (\mathit{x})=0\end{array}\end{array}$$\begin{array}{rl}EI(x)& =\mathbb{E}[max(f(x)-f(x^{+}),0)]\\ & =\{\begin{array}{ll}(\mu (\mathit{x})-f({\mathit{x}}^{+})-\xi )\mathrm{\Phi }(Z)+\sigma (\mathit{x})\varphi (Z)& \text{if}\sigma (\mathit{x})>0\\ 0& \text{if}\sigma (\mathit{x})=0\end{array}\end{array}$$\begin{array}{rl}EI(x)& =\mathbb{E}[max(f(x)-f(x^{+}),0)]\\ & =\{\begin{array}{ll}(\mu (\mathit{x})-f({\mathit{x}}^{+})-\xi )\mathrm{\Phi }(Z)+\sigma (\mathit{x})\varphi (Z)& \text{if}\sigma (\mathit{x})>0\\ 0& \text{if}\sigma (\mathit{x})=0\end{array}\end{array}$