Grid Search vs Bayesian Optimization TPE

Tree-Structured Parzen Estimator (TPE) is a type of Bayesian optimization methods that can help user implement “informed” searches via the use of past information. 

To illustrate, consider a scenario where we need to minimize the loss function by testing different estimator sizes in a Random Forest. 

Based on the picture below with several initial runs’ results, using human visual judgment, we probably will think that smaller estimator sizes, like those in the red circle are more likely to yield lower loss. 

This is exactly the “intelligence” of Bayesian tuning method: unlike grid-search, instead of blindly running every single combination defined by the user without “learning” anything from each run’s result, or wasting resources by searching all over the place, it learns from past evaluation results to help user narrow down the search space to combinations that are likely to perform well.

In essence, Bayesian hyperparameter optimization is the process of:

“Build[ing] a probability model of the objective function to propose smarter choices for the next set of hyperparameters to evaluate.” (Koehrsen, 2018)

The probability model for the objective function is also called a “surrogate”, which is expressed by the probability of score (y) given hyperparameters (x):

P (y | x) = P (score | hyperparameters)

The optimization process can be understood as the following steps by making use of the surrogate and keeping track of past evaluation results:

1. Build a surrogate probability model of the objective function

2. Find the hyperparameters that perform best on the surrogate

3. Apply these hyperparameters to the objective function

4. Update the surrogate model incorporating the new results

5. Repeat steps 2-4 until max iterations or time is reached

As the number of iterations of the above-described process increase, the surrogate approximation will become closer to the objective function. Therefore, by selecting hyperparameters that maximize/minimize the surrogate, it will likely maximize/minimize the objective function. 

Above are the illustrations of the process. 

The black line is the surrogate model with uncertainty region in grey. 

The red line is the true objective function.

We see how the surrogate approximation becomes closer to the objective function from 2 evaluations (left figure) to 8 evaluations (right figure).

Specifically, l(x) and g(x) are Gaussian Mixture Models (GMM).  TPE fits and updates these two distributions on every trial, for every parameter