Black-Box Optimization

The problem of hyper-parameter tuning is just a subclass of a much more general type of problems: black-box optimizations. A black-box function f(x)

This is a very fascinating class of problems that has produced smart solutions. We will look at three of them: grid search, random search, and Bayesian optimization.

Why is finding the best hyper-parameters for neural networks a black-box problem? Since we cannot calculate information like the gradients of our network output with respect to the hyper-parameters (for example, the number of layers in an FFNN), especially when using complex optimizers or custom functions, we need other approaches to find the best hyper-parameters that maximize the chosen optimizing metric. Note that if we could have the gradients, we could use an algorithm such as gradient descent to find the maximum or minimum.

Consider that you will need to train your network

times if you want to test all possible combinations. If your training takes five minutes, you will need 13.4 weeks of computing time. If the training takes hours or days, it becomes impossible. If the training takes one day for example, you will need 73.9 years to try all the possibilities. Most of the hyper-parameter choices will come from experience; for example, you can safely always use Adam, since it’s the better optimizer out there (in almost all cases). But you will not be able to avoid trying to tune other parameters like the number of hidden layers or the learning rate. You can reduce the number of combinations you need with experience (as with the optimizer), or with some smart algorithms, as you see later in this chapter.

The Problem of Hyper-Parameter Tuning

For category 3 there is not much to do except try all the possibilities. They typically will change the model completely and it’s impossible to model their effect, therefore making a test the only possibility. This is also the category where experience may help the most. It’s widely known that the Adam optimizer is almost always the best choice, so you may concentrate your efforts somewhere else at the beginning. For categories 1 and 2, it’s a bit more difficult, and you need to use some smart approaches to find the best values.

Sample Black-Box Problem

To try our hands at solving a black-box problem, let’s create a “fake” black-box problem. Find the maximum of the function f(x) given by the formula

Figure 6-1 shows how f(x) looks.

The maximum is at an approximate value of x = 69.18 and has a value of 15.027. Our challenge is to find this maximum in the most efficient way possible, without knowing anything about f(x) except its value at any point. When we say “efficient,” we mean with the smallest number of evaluations possible.

Grid Search

The first method we look at, grid search , is also the less “intelligent”. Grid search entails simply trying the function at regular intervals and seeing for which x the function f(x) assumes the highest value. In this example, we want to find the maximum of the function f(x) between two x values, x_min and x_max. What we do is simply take n points equally spaced between x_min and x_max and evaluate the function at those points. We define a vector of points

where we defined Δx = x_max − x_min. Then we evaluate the function f(x) at those points, obtaining a vector f of values

the estimate of the maximum will then be

and supposing the maximum is found at , we will also have

Now, as you may imagine, the more points you use, the more accurate your maximum estimation will be. The problem is that, if the evaluation of f(x) is costly, you will not be able to test as many points as you might like. You will need to find a balance between the number of points and the accuracy. Let’s consider an example with the function f(x) we described earlier. Let’s consider x_max = 80 and x_min = 0 and let’s take n = 40 points. We will have . We can create the vector x easily in Python with the code:

gridsearch = np.arange(0,80,2)

The array gridsearch will look like this

array([ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78])

Figure 6-2 shows the function f(x) as a continuous line, the crosses mark the points we sample in the grid search , and the black square marks the precise maximum of the function. The right plot shows a zoom around the maximum.

You can see how the points we sample in Figure 6-2 get close to the maximum, but don’t get it exactly. Of course, sampling more points would get us closer to the maximum, but would cost us more evaluations of f(x). We can find the maximum easily with the trivial code

x = 0

m = 0.0

for i, val in np.ndenumerate(f(gridsearch)):

    if (val > m):

        m = val

        x = gridsearch[i]

print(x)

print(m)

That gives us

70

14.6335957578

Close to the actual maximum (69.18, 15.027), but not quite right. Let’s try the previous example and vary the number of points we sample. We will vary the number of points sampled n from 4 to 160. For each case, we will find the maximum and its location as described earlier. We can do it with this code

xlistg = []

flistg = []

for step in np.arange(1,20,0.5):

    gridsearch = np.arange(0,80,step)

    x = 0

    m = 0.0

    for i, val in np.ndenumerate(maxim(gridsearch)):

        if (val > m):

            m = val

            x = gridsearch[i]

    xlistg.append(x)

    flistg.append(m)

in the lists xlistg and flistg, we will find the position of the maximum found and the value of the maximum for the various values of n.

Figure 6-3 shows the a plot of the distributions of the results. The black vertical line is the correct value of the maximum.

As you can see , the results vary quite a lot and can be very far from the correct value, as far as 10. This tells us that using the wrong number of points can return very wrong results. As you can imagine, the best results are the ones with the smallest step Δx, since it’s more likely to be closer to the maximum. Figure 6-4 shows the value of the found maximum varies with the step Δx.

In the zoom in the right plot of Figure 6-4, it’s evident how smaller values of Δx get you better values of . Note that a step of 1.0 means sampling 80 values of f(x). If, for example, the evaluation takes one day, you will need to wait 80 days to get all the measurements you need.

Tip

Grid search is efficient only when the black-box function is cheap. To get good results, a large number of sampling points is usually needed.

To make sure you are really getting the maximum , you should decrease the step Δx, or increase the number of sampling points, until the maximum value you find does not change appreciably anymore. In the previous example, as we see from the right plot in Figure 6-4, we are sure we are close the maximum when our step Δx gets smaller than roughly 2.0, or in other words when the number of sampled points is greater or roughly equal to 40. Remember that 40 may seems like a small number at first sight, but if f(x) evaluates the metric of your deep learning model, and the training takes for example two hours, you are looking at 3.3 days of computer time.

Normally in the deep learning world, two hours is not much for training a model, so make a quick calculation before starting a long grid search. Additionally, keep in mind that when doing hyper-parameter tuning, you are moving in a multi-dimensional space (you are not optimizing only one parameter, but many), so the number of evaluations you need gets big very quickly.

Let’s look at a quick example. Let’s suppose you decide you can afford 50 evaluations of your black-box function. If you decide you want to try the following hyper-parameters:

• Optimizer (RMSProp, Adam or plain GD) (three values)

• Number of epochs (1000, 5000 or 10000) (three values)

You are already looking at nine evaluations. How many values of the learning rate can you then afford to try? Only five! And with five values, it’s not probable that you’ll get close to the optimal value. This shows how grid search is viable only for cheap black-box functions. Remember that, often, time is not the only problem. If you are using the Google Cloud platform to train your network, for example, you are paying the hardware you use by the second. Maybe you have lots of time at your disposal, but costs may go over budget very quickly .

Random Search

A strategy that is as “dumb” as grid search , but that works amazingly better, is a random search. Instead of sampling x points regularly in the range (x_min, x_max), you sample the points randomly. We can do it with this code

import numpy as np

randomsearch = np.random.random([40])*80.0

The randomsearch array will look like this

array([ 0.84639256, 66.45122608, 74.12903502, 36.68827838, 61.71538757, 69.29592273, 48.76918387, 69.81017465, 1.91224209, 21.72761762, 22.17756662, 9.65059426, 72.85707634, 2.43514133, 53.80488236, 5.70717498, 28.8624395 , 33.44796341, 14.51234312, 41.68112826, 42.79934087, 25.36351055, 58.96704476, 12.81619285, 15.40065752, 28.36088144, 30.27009067, 16.50286852, 73.49673641, 66.24748556, 8.55013954, 29.55887325, 18.61368765, 36.08628824, 22.1053749 , 40.14455129, 73.80825225, 30.60089111, 52.01026629, 47.64968904])

Depending on the seed you used, the actual numbers you get may be different. As we have done for grid search, Figure 6-5 shows the plot of f(x), where the crosses mark the sampled points, and the black square is the maximum. On the right plot, you see a zoom around the maximum.

The risk with this method is that, if you are very unlucky, your random chosen points are nowhere close the real maximum. But that probability is quite low. Note that if you take a constant probability distribution for your random points, you have the same probability of getting the points everywhere. Now it is interesting to see how this method performs. Let’s consider 200 different random sets of 40 points, obtained by varying the random seed used in the code. The distributions of the maximum found are plotted in Figure 6-6.

As you can see, regardless of the random sets used, you get very close to the real maximum. Figure 6-7 shows the distributions of the maximum found with random search and by varying the number of points sampled from 10 to 80.

If you compare this with grid search, you can see that random search is better at consistently getting results closer to the real maximum. Figure 6-8 compares the distribution you get for your maximum when using a different number of sampling points n with random and with grid search. In both cases, the plots were generated with 38 different sets, so the total count is the same.

It’s easy to see how, on average, random search is better than grid search. The values you get are consistently closer to the right maximum.

Tip

Random search is consistently better than grid search and you should use it every time it’s possible. The difference between random search and grid search becomes even more marked when dealing with a multi-dimensional space for your variable x. Hyper-parameter tuning is nearly always a multi-dimensional optimization problem.

If you are interested in a very good paper on the random search scale at high-dimensional problems, you can read the paper by J. Bergstra and Y. Bengio, “Random Search for Hyper-Parameter Optimization” [1].

Coarse to Fine Optimization

There is still an optimization trick that helps with grid or random search. It is called “coarse to fine optimization .” Let’s suppose we want to find the maximum of f(x) between x_min and x_max. We will look at the idea for random search, but it works in the same way as with grid search. The following steps give you the algorithm you need to follow.

1. 1.

   Do a random search in the region R₁ = (x_min, x_max). Indicate the maximum found with (x₁, f₁).

    
2. 2.

   Consider a smaller region around x₁, R₂ = (x₁ − δx₁, x₁ + δx₁) for some δx₁ (which we discuss later) and do a random search in this region. The hypothesis is of course that the real maximum lies in this region. Indicate the maximum you find here with (x₂, f₂).

    
3. 3.

   Repeat Step 2 around x₂, in the region indicated with R₃ with a δx₂ smaller than δx₁ and indicate the maximum you find in this step with (x₃, f₃).

    
4. 4.

   Repeat step 2 again around x₃, in the region we indicate with R₄ with a δx₃ smaller than δx₂.

    
5. 5.

   Continue the same way as many times as you need until the maximum (x_i, f_i) in the region R_i + 1 does not change any more.

    

Just one or two iterations are typically needed, but theoretically you could go on for a large number of iterations. The problem with this method is that you cannot be sure that your real maximum actually lies in your regions R_i. But this optimization has a big advantage if it does.

Let’s consider the case where we do a standard random search. If we want to have on average a distance between the sampled points of 1% of x_max − x_min we would need around 100 points if we decided to perform only one random search, and consequently we had to perform 100 evaluations. Now let’s consider the algorithm we just described. We could start with just ten points in region R₁ = (x_min,  x_max), where we indicate the maximum we find with (x₁, f₁). Then let’s take and let’s use ten points in region R₂ = (x₁ − δx, x₁ + δx). In the interval (x₁ − δx, x₁ + δx), we will have on average a distance between the points of 1% of x_max − x_min, but we just sampled our functions only 20 times instead of 100, so a factor of five fewer! For example, let’s sample the function we used previously between x_min = 0 and x_max = 80 with ten points with this code

np.random.seed(5)

randomsearch = np.random.random([10])*80

x = 0

m = 0.0

for i, val in np.ndenumerate(f(randomsearch)):

    if (val > m):

        m = val

        x = randomsearch[i]

This gives us the maximum location and value of x₁ = 69.65 and f₁ = 14.89, so not bad, but not as precise as the real ones—69.18 and 15.027. Now let’s sample ten points around the maximum we found in the regions R₂ = (x₁ − 4, x₁ + 4)

randomsearch = x + (np.random.random([10])-0.5)*8

x = 0

m = 0.0

for i, val in np.ndenumerate(maxim(randomsearch)):

    if (val > m):

        m = val

        x = randomsearch[i]

This gives us the result 69.189 and 15.027. Quite a precise result with only 20 evaluations of the function. If we do a plain random search with 500 (25 times more than what we just did) sampling points, we get x₁ = 69.08 and f₁ = 15.022. This result shows how this trick can be really helpful. But remember the risk: If your maximum is not in your regions R_i you will never be able to find it, since you are still dealing with random numbers. So, it is always a good idea to choose the regions (x_i − δx_i, x_i + δx_i) that are relatively big to make sure that they contain your maximum.

How big they need to be depends, as almost everything in the deep learning world, on your dataset and the problem at hand and may be impossible to know in advance. Testing is unfortunately required. Figure 6-9 shows the sampled points on the function f(x). In the plot on the left you see the first ten points, and on the right the region R₂ with the additional ten points. The small rectangle on the left plot marks the x region R₂.

The decision of how many points you should sample at the beginning is crucial. We had luck here. Let’s consider a different seed when choosing our initial ten random points and see what can happen. As you can see in Figure 6-10, choosing the wrong initial points leads to disaster!

In Figure 6-10, note how the algorithm finds the maximum at around 16, since in the initial sampled points the maximum value is around x = 16, as you can see on the plot on the left in Figure 6-10. No points are close to the real maximum around x = 69. The algorithm finds a maximum really well, simply not the absolute maximum. That is the danger you face when using this trick. It can even go worse than that. Consider Figure 6-11, where we just sampled one single point at the beginning. You can see on the plot on the left of Figure 6-11, how the algorithm completely misses any maximum. It simply gives as a result the highest value of the points marked by crosses on the points on the right plot: (58.4, 9.78).

If you decide to use this method, keep in mind that you will still need a good number of points at the beginning to get close to the maximum before refining your search. After you are relatively sure you have points around the maximum, you can use this technique to refine your search.

Bayesian Optimization

Nadaraya-Watson Regression

To understand Bayesian optimization, we have to look at some new mathematical concepts. Let’s start with the Nadaraya-Watson regression , an idea from 1964[2]. The basic idea is quite simple. Given an unknown function y(x) and given N points x_i = 1, …, N, we indicate with y_i = f(x_i) with i = 1, …, N the value of the function calculated at the different x_i. The idea of the Nadaraya-Watson regression is that we can evaluate the unknown function f at an unknown point x using the formula

where w_i(x) are weights that are calculated according to the formula

where K(x, x_i) is called a kernel. Note that given how the weights are defined we have

In the literature, you can find several kernels but the one we are interested in is the Gaussian one, often called the Radial Basis Function (RBF)

The parameter l makes the Gaussian shape wider or narrower. The σ is typically the variance of your data, but in this case, it plays no role since the weights are normalized to 1. This is at the base of Bayesian optimization, as you will see later.

Gaussian Process

Before talking about Gaussian processes , we must define what a random process is. We talk of a random process when for any point x ∈ ℝ^d we assign a random variable f(x) ∈ ℝ. A random process is Gaussian if for any finite number of points, their joint distribution is normal. That means that ∀n ∈ ℕ, and for ∀x₁, …x_n ∈ ℝ^d then the vector

where with the notation we intend that the vector components follow a normal distribution, indicated with . Remember that a random variable with a Gaussian distribution is said to be normally distributed. From here comes the name Gaussian process. The probability distribution of the normal distribution is given by the function

where μ is the mean or expectation of the distribution and σ is the standard deviation. We will use the following notation from here on

and the covariance of the random values will be indicated by K

the choice of the letter K is purposeful. We will assume in what follows that the covariance will have a Gaussian shape, and we will use for K the RBF function we defined earlier.

Stationary Process

For simplicity we will consider only stationary processes . A random process is stationary if its joint probability distribution does not change with time. That means that the mean and variance also will not change when shifted in time. We will also consider a process for which its distribution depends only on the relative position of the points. This leads to these conditions

Note that to apply the method we are describing, you must convert your data to be stationary, eliminating seasonality or trends in time for example.

Prediction with Gaussian Processes

Now we have reached the interesting part: given the vector f, how can we estimate f(x) at an arbitrary point x? Since we are dealing with random processes, we will estimate the probability that the unknown function assumes a given value f(x). Mathematically we will predict the following quantity

Or, in other words, the probability of getting the value f(x) given the vector f, composed by all the points f(x₁), …, f(x_n).

Assuming that f(x) is a stationary Gaussian process with m = 0, the prediction can be shown to be given by

where with we have indicated the normal distribution calculated on the points with an average of 0 and a covariance matrix of dimensions n + 1 × n + 1, since we have n + 1 points in the numerator. The derivation is somewhat involved and is based on several theorems, such as Bayes’ theorem. For more details you can refer to the (advanced) explanation by C.B. Do [3]. To understand what Bayesian optimization is, we can simply use the formula without derivation. C will have dimensions n × n since we have only n points in the denominator.

We have

And

where we have defined

It can be shown² that the ratio of two normal distributions is again a normal distribution, which means we can write

With

The derivation of the exact form for μ and σ is quite long and would go beyond the scope of the book. Basically, now we know that, on average, our unknown function will assume the value μ in x with a variance σ. Let’s now see how this method works in practice in Python. Let’s define our kernel K(x)

def K(x, l, sigm = 1):

    return sigm**2*np.exp(-1.0/2.0/l**2*(x**2))

Let’s simulate our unknown function with an easy one

that can be implemented as follows

def f(x):

    return x**2-x**3+3+10*x+0.07*x**4

Let’s consider the function in the range (0, 12). Figure 6-12 shows how the function looks.

Let’s build first our f vector with five points

randompoints = np.random.random([5])*12.0

f_ = f(randompoints)

where we have used the seed 42 for the random numbers: np.random.seed(42). Figure 6-13 shows the random points marked with a cross on the plot.

We can apply the method described earlier with the following code

xsampling = np.arange(0,14,0.2)

ybayes_ = []

sigmabayes_ = []

for x in xsampling:

    f1 = f(randompoints)

    sigm_ = np.std(f1)**2

    f_ = (f1-np.average(f1))

    k = K(x-randompoints, 2 , sigm_)

    C = np.zeros([randompoints.shape[0],

                  randompoints.shape[0]])

    Ctilde = np.zeros([randompoints.shape[0]+1,

                       randompoints.shape[0]+1])

    for i1,x1_ in np.ndenumerate(randompoints):

        for i2,x2_ in np.ndenumerate(randompoints):

            C[i1,i2] = K(x1_-x2_, 2.0, sigm_)

    Ctilde[0,0] = K(0, 2.0, sigm_)

    Ctilde[0,1:randompoints.shape[0]+1] = k.T

    Ctilde[1:,1:] = C

    Ctilde[1:randompoints.shape[0]+1,0] = k

    mu = np.dot(np.dot(np.transpose(k), np.linalg.inv(C)), f_)

    sigma2 = K(0, 2.0,sigm_)-

             np.dot(np.dot(np.transpose(k),

                           np.linalg.inv(C)), k)

    ybayes.append(mu)

    sigmabayes_.append(np.abs(sigma2))

ybayes = np.asarray(ybayes_)+np.average(f1)

sigmabayes = np.asarray(sigmabayes_)

Take some time to study this so you understand it. In the ybayes list, we will find the values of μ(x) evaluated on the values contained in the xsampling array. Here are some hints that will help you understanding the code:

• We loop over a range of x points where we want to evaluate our function, with the code for x in xsampling.

• We build our k and f vectors with the code for each element of the vectors: k = K(x-randompoints, 2, sigm_) and f1 = f(randompoints). For the kernel, we chose a value for the parameter l as defined in the function of 2. We subtracted in the vector f the average to obtain m(x) = 0 to be able to apply the formulas as derived.

• We build the matrices C and .

• We calculate μ with mu = np.dot(np.dot(np.transpose(k), np.linalg.inv(C)), f_) and the standard deviation.

• We reapply all the transformation that we did to make our process stationary in the opposite order, simply adding the average of f(x) back to the evaluated surrogate function ybayes = np.asarray(ybayes_)+np.average(f1).

Figure 6-14 shows how this method works. The dashed line is the predicted function obtained by plotting μ(x) as calculated in the code, when we have five points (n = 5). The gray area is the region between the estimated function and +/- σ.

Given the few points we have, this is actually not a bad result. Keep in mind that you still need a few points to be able to get a reasonable approximation. Figure 6-15 shows the result when we have only two points. The result is not as good. The gray area is the region around the estimated function and +/- σ. You can see that the farther you are from the points, the higher the uncertainty, or the variance, of the predicted function.

Let’s stop for a second and think about why we do all this. The idea behind it is to find a surrogate function that approximates our function f and that has the property

This surrogate function must have another very important property: it must be cheap to evaluate. That way, we can easily find the maximum of and, by using the previous property, we will have the maximum of f, that by hypothesis is costly.

As you have seen, it may be very difficult to know if we have enough points to find the right value of the maximum. After all, by definition, we do not have any idea how our black-box function looks. So how do we solve this problem?

The main idea behind the method can be described by the following algorithm:

1. 1.

   Start with a small number of randomly chosen sample points (how many points will depend on your problem).

    
2. 2.

   Use this set of points to get a surrogate function, as described previously.

    
3. 3.

   Add a point to the set, with a specific method that we discuss later, and reevaluate the surrogate function.

    
4. 4.

   If the maximum found with the surrogate function continues to change, continue adding points as in Step 3 until the maximum does not change or you run out of time or budget and cannot perform any more evaluations.

    

If the method we hinted at in Step 3 is smart enough, you will be able to find the maximum relatively quickly and accurately.

Acquisition Function

How do you choose the additional points mentioned in Step 3 in the previous section? The idea is to use an acquisition function. The algorithm works in this way:

1. 1.

   Choose a function (and we will see a few possibilities in a moment) called an “acquisition function.”

    
2. 2.

   Then choose as additional point x, the one at which the acquisition function has a maximum.

    

There are several acquisition functions we can use. We will describe only one that we will use to see how this method works, but there are several that you may want to check out, including entropy search, probability of improvement, expected improvement, and upper confidence bound.

Upper Confidence Bound (UCB)

In the literature you find two variations of this acquisition function. We can write the function as

where we indicate with the “expected” value of the surrogate function on the x-range we have in our problem. The expected value is nothing more than the average of the function over the given x range. σ(x) is the variance of the surrogate function that we calculate with our method at the point x. The new point we select is the one where a_UCB(x) is maximum. η > 0 is a tradeoff parameter. This acquisition function basically selects the points where the variance is biggest. Look at Figure 6-15 again. The method would select the points where the variance is greater, so points as far as possible from the points we have already. In this way the approximation tends to get better and better. Another variation of the UCB acquisition function is the following

This time, the acquisition function will make a tradeoff between choosing points around the surrogate function maximum and points where its variance is the biggest. This second method works best to quickly find good approximation of the maximum of f, while the first tends to give good approximation of f over the entire x range. The next section explains how these methods work.

Example

Let’s start with the complex trigonometric function, as described at the beginning of the chapter and consider the x range [0, 40]. Our goal is to find its maximum and approximate the function. To facilitate the code, let’s define two functions: one to evaluate the surrogate function and one to evaluate the new point. To evaluate the surrogate function, we can use the following function

def get_surrogate(randompoints):

    ybayes_ = []

    sigmabayes_ = []

    for x in xsampling:

        f1 = f(randompoints)

        sigm_ = np.std(f_)**2

        f_ = (f1-np.average(f1))

        k = K(x-randompoints, 2.0, sigm_ )

        C = np.zeros([randompoints.shape[0],

                      randompoints.shape[0]])

        Ctilde = np.zeros([randompoints.shape[0]+1,

                           randompoints.shape[0]+1])

        for i1,x1_ in np.ndenumerate(randompoints):

            for i2,x2_ in np.ndenumerate(randompoints):

                C[i1,i2] = K(x1_-x2_, 2.0, sigm_)

        Ctilde[0,0] = K(0, 2.0)

        Ctilde[0,1:randompoints.shape[0]+1] = k.T

        Ctilde[1:,1:] = C

        Ctilde[1:randompoints.shape[0]+1,0] = k

        mu = np.dot(np.dot(np.transpose(k),

                           np.linalg.inv(C)), f_)

        sigma2 = K(0, 2.0, sigm_)

                 - np.dot(np.dot(np.transpose(k),

                                 np.linalg.inv(C)), k)

        ybayes_.append(mu)

        sigmabayes_.append(np.abs(sigma2))

    ybayes = np.asarray(ybayes_)+np.average(f1)

    sigmabayes = np.asarray(sigmabayes_)

    return ybayes, sigmabayes

This function has the same code as we discussed in the example in the previous sections, but it’s packed in a function that returns the surrogate function, contained in the array ybayes, and the σ², contained in the array sigmabayes. Additionally, we need a function that evaluates the new points using the acquisition function a_UCB(x). We can get it with this function

def get_new_point(ybayes, sigmabayes, eta):

    idxmax = np.argmax(np.average(ybayes)

             +eta*np.sqrt(sigmabayes))

    newpoint = xsampling[idxmax]

    return newpoint

To make things simpler, we define the array that contains all the x values we want at the beginning outside the functions. Let’s start with six randomly selected points. To see how this method is doing, let’s start with some definitions

xmax = 40.0

numpoints = 6

xsampling = np.arange(0,xmax,0.2)

eta = 1.0

np.random.seed(8)

randompoints1 = np.random.random([numpoints])*xmax

In the randompoints1 array, we have our first six selected random points. We can easily get the surrogate function with our function with

ybayes1, sigmabayes1 = get_surrogate(randompoints1)

Figure 6-16 shows the result. The dotted line is the acquisition function a_UCB(x) normalized to fit in the plot.

The surrogate function is not very good yet, since we don’t have enough points, and the big variance (the gray area) makes this evident. The only region that is well approximated is the region x ≳ 35. You can see how the acquisition function is big when the surrogate function is not approximating the black-box function well, and small when it does, as for example with x ≳ 35. So choosing a new point where a_UCB(x) is at its maximum is equivalent to choosing the points where the function is less well approximated, or in more mathematical terms, where the variance is bigger. For a comparison, Figure 6-17 shows the same plot as in Figure 6-16, but with the acquisition function and with η = 3.0.

As you can see, tends to have a maximum around the maximum of the surrogate function. Keep in mind that if η is big, then the maximum of the acquisition function will shift toward regions with high variance. But this acquisition function tends to find “a” maximum slightly faster. I said “a” since it depends on where the maximum of the surrogate function is, and not where the maximum of the black-box function is.

Let’s see now what happens while using a_UCB(x) with η = 1.0. For the first additional point, we need to run the following three lines of code

newpoint = get_new_point(ybayes1, sigmabayes1, eta)

randompoints2 = np.append(randompoints1, newpoint)

ybayes2, sigmabayes2 = get_surrogate(randompoints2)

For the sake of simplicity, we name each array for each step differently, instead of creating a list. But typically, you should make these iterations automatic. Figure 6-18 shows the result with the additional point, marked with a black circle.

The new point is around x ≈ 27. Let’s continue to add points. Figure 6-19 shows the results after adding five points.

Look at the dashed line. The surrogate function now approximates the black-box function quite well, especially around the real maximum. Using this surrogate function, we can find a very good approximation of our original function with just 11 evaluations in total! Keep in mind we don’t have any additional information about f, except the 11 evaluations.

Now let’s see what happens with the acquisition function , and let’s check how fast we can find the maximum. In this case, let’s use η = 3.0, to get a better balance between the surrogate function’s maximum and its variance. Figure 6-20 shows the result after adding one additional point, marked by a black circle. We already have a good approximation of the real maximum!

Now let’s add another point. Figure 6-21 shows that the additional point is still close to the maximum but has shifted in the direction of the area with a high variance around 30.

If we chose a smaller η, the point would be closer to the maximum, and if we chose a bigger one, the point would be closer to the point with the highest variance between 25 and roughly 32. Let’s add another point and see what happens. Figure 6-22 shows how the method now chooses a point close to another region with high variance, between 10 and roughly 22, again marked by a black circle.

And finally, the method refines the maximum area around 15, as you can see in Figure 6-23, adding a point around 14, marked by the black circle.

As this discussion and comparison of the behavior of the two types of acquisition functions should have made clear by now, choosing the right acquisition function is dependent on which strategy you want to apply to approximate your black-box function.

Note

Different types of acquisition functions will give different strategies in approximating the black-box function. For example, a_UCB(x) will add points in regions with the highest variance, while will add points finding a balance, regulated by η, between the maximum of the surrogate function and areas with high variance.

An analysis of all the different types of acquisition function would go far beyond the scope of this book. A good deal of research and reading published papers is required to get enough experience and to understand how different acquisition functions work and behave.

If you want to use Bayesian optimization with your TensorFlow model, you do not have to develop the method completely from scratch. You can try the library called GPflowOpt from N. Knudde et al. [4].

Sampling on a Logarithmic Scale

There is a last small subtlety that we need to discuss. Sometimes you will find yourself in a situation where you want to try a big range of possible values for a parameter, but you know from experience that the best value is probably in a specific range. Let’s suppose you want to find the best value for the learning rate for your model, and you decide to test values from 10⁻⁴ to 1, but you know, or at least expect, that your best value lies between 10⁻³ and 10⁻⁴. Now let’s suppose you are working with grid search and you sample 1,000 points. You may think you have enough points, but you will get

• 0 points between 10⁻⁴ and 10⁻³

• 8 points between 10⁻³ and 10⁻²

• 89 points between 10⁻¹ and 10⁻²

• 899 points between 1 and 10⁻¹

You get a lot more points in the less interesting ranges, and none where you want them. Figure 6-24 shows the distribution of the points. Note that the x-axis uses a logarithm scale. You can clearly see how you get many more points for bigger values of the learning rate.

You probably want to sample in a much finer way for smaller values of the learning rate than for bigger ones. What you should do is sample your points on a logarithmic scale. The basic idea is that you want to sample the same number of points between 10⁻⁴ and 10⁻³, 10⁻³ and 10⁻², 10⁻¹ and 10⁻², and 10⁻¹ and 1. To do that, you can use the following Python code. First select a random number between 0 and a negative of the absolute value of the highest number of the power of 10 you have; in this case it’s -4.

r = - np.arange(0,1,0.001)*4.0

Then your array with the selected points can be created with the following

points2 = 10**r

Figure 6-25 shows how the distributions of the points contained in the array points2 is now completely flat, as we wanted.

You get 250 points in each region, and you can easily check this code for the range 10⁻³ and 10⁻⁴. For the other ranges simply change the numbers in the code.

print(np.sum((alpha <= 1e-3) & (alpha > 1e-4)))

Now you can see how you have the same number of points between the different powers of ten. With this simple trick you can ensure that you get enough points in region of your chosen range, where otherwise you would get almost no points. Remember that in this example, with 1,000 points, we get zero points between 10⁻³ and 10⁻⁴ using the standard method . This range is the most interesting for the learning rate, so you want to have enough points in this range to optimize your model. Note that the same applies to random search. It works in the exact same way.

Hyper-Parameter Tuning with the Zalando Dataset

To give you a concrete example of how hyper-parameter tuning works, let’s apply what you have learned in a simple case. Let’s start with the data, as usual. Let’s use the Zalando dataset from Chapter 3. For a complete discussion, refer to that chapter. Let’s quickly load and prepare the data and then discuss tuning.

Remember we have 60,000 observations in the train dataset and 10,000 in the dev dataset. After executing the command, we have two NumPy matrices (trainX and testX) containing all the pixel values that describe each of the training and test images and two NumPy arrays (trainY and testY) containing the associated labels.

Remember that 784 represents the gray values of the image pixels (that have a size of 28 × 28 pixels).

Now we need to modify the data to obtain a “flattened” version of each image, meaning an array of 754 pixels, instead of a matrix of 28x28 pixels.

Now we have prepared the data as we need. For a complete discussion, refer to Chapter 3, where we spend a lot of time preparing the data for this dataset. Now let’s move on to the model. Let’s start with something easy. As a metric, let’s use for this example the accuracy, since the dataset is balanced. Let’s consider a network with just one layer and see what number of neurons provides the best accuracy.

Additionally, we evaluate the accuracy on the train and dev datasets and return the values to the caller. In this way we can run a loop for several values of the number of neurons in the hidden layer and get the accuracies. Note that this time the function has an additional input parameter: number_neurons. We need to pass this number to the function that builds the model.

Let’s suppose we choose the following parameters: mini-batch size = 50, we train for 100 epochs, learning rate λ = 0.001, and we build our model with 15 neurons in the hidden layer.

Not surprisingly, more neurons deliver better accuracy, with no signs of overfitting of the train dataset, since the accuracy on the dev dataset is almost equal to the one on the train dataset. Figure 6-26 shows a plot of the accuracy on the test dataset vs. the number of neurons in the hidden layer. Note that the x-axis uses a logarithmic scale, to make the changes more evident.

You will find that the combinations with 44 epochs, 36 neurons in each layer, a learning rate of 0.07537, and a mini-batch size of 54 gives you an accuracy on the dev dataset of 0.86. Not bad, considering that this run took 1.5 minutes, so 23 times faster than the model with one layer and 3,000 neurons. And it’s 2% better. Our naïve initial test gave us an accuracy of 0.84, so with hyper-parameter tuning, we got 2% better than our initial guess. In the deep learning, this is considered a good result. What we did should give you an idea of how powerful hyper-parameter tuning can be if it’s done properly. Keep in mind that you should spend quite some time doing it, and especially thinking about how to do it.

The point of this last section is not to get the best model possible, but to give you an idea about how the tuning process may work. You could continue trying different optimizers (for example Adam), considering wider ranges for the parameters, more parameter combinations, and so on.

A Quick Note about the Radial Basis Function

Before finishing this chapter, let’s discuss a minor point about the Radial Basis Function

It is important that you understand the role of the parameter l. In our examples, we chose l = 2 but we did not discuss why. Choosing an l that’s too small will make the acquisition function develop very narrow peaks around the points we already have, as you can see in the left plot of Figure 6-27. Big values of l will have a smoothing effect on the acquisition function, as you can see in the middle and right plots of Figure 6-27.

Usually it’s good practice to avoid values for l that are too small or too big, to be able to have a variance that varies in a smooth way between known points, as in Figure 6-27 for l = 1. Having a very small l will make the variance between points almost constant and therefore make the algorithm almost always choose the middle point between points, as you can check from the acquisition function. While choosing an l that’s too big will make the variance small, and therefore difficult to use. As you can see for l = 5 in Figure 6-27, the acquisition function is almost constant. Typical values are around 1 or 2.

Exercises

References