In the following paragraph from the book Automated Machine Learning: Methods, Systems, Challenges (by Frank Hutter et al.)

In this section we first give a brief introduction to Bayesian optimization, present alternative surrogate models used in it, describe extensions to conditional and constrained configuration spaces, and then discuss several important applications to hyperparameter optimization.

What is an "alternative surrogate model"? What exactly does "alternative" mean?


What is Bayesian optimization?


Bayesian optimization (BO) is an optimization technique used to model an unknown (usually continuous) function $f: \mathbb{R}^d \rightarrow Y$, where typically $d \leq 20$, so it can be used to solve regression and classification problems, where you want to find an approximation of $f$. In this sense, BO is similar to the usual approach of training a neural network with gradient descent combined with the back-propagation algorithm, so that to optimize an objective function. However, BO is particularly suited for regression or classification problems where the unknown function $f$ is expensive to evaluate (that is, given the input $\mathbf{x} \in \mathbb{R}^d$, the computation of $f(x) \in Y$ takes a lot of time or, in general, resources). For example, when doing hyper-parameter tuning, we usually need to first train the model with the new hyper-parameters before evaluating the specific configuration of hyper-parameters, but this usually takes a lot of time (hours, days or even months), especially when you are training deep neural networks with big datasets. Moreover, BO does not involve the computation of gradients and it usually assumes that $f$ lacks properties such as concavity or linearity.

How does Bayesian optimization work?

There are three main concepts in BO

  • the surrogate model, which models an unknown function,
  • a method for statistical inference, which is used to update the surrogate model, and
  • the acquisition function, which is used to guide the statistical inference and thus it is used to update the surrogate model

The surrogate model is usually a Gaussian process, which is just a fancy name to denote a collection of random variables such that the joint distribution of those random variables is a multivariate Gaussian probability distribution (hence the name Gaussian process). Therefore, in BO, we often use a Gaussian probability distribution (the surrogate model) to model the possible functions that are consistent with the data. In other words, given that we do not know $f$, rather than finding the usual point estimate (or maximum likelihood estimate), like in the usual case of supervised learning mentioned above, we maintain a Gaussian probability distribution that describes our uncertainty about the unknown $f$.

The method of statistical inference is often just an iterative application of the Bayes rule (hence the name Bayesian optimization), where you want to find the posterior, given a prior, a likelihood and the evidence. In BO, you usually place a prior on $f$, which is a multivariate Gaussian distribution, then you use the Bayes rule to find the posterior distribution of $f$ given the data.

What is the data in this case? In BO, the data are the outputs of $f$ evaluated at certain points of the domain of $f$. The acquisition function is used to choose these points of the domain of $f$, based on the computed posterior distribution. In other words, based on the current uncertainty about $f$ (the posterior), the acquisition function attempts to cleverly choose points of the domain of $f$, $\mathbf{x} \in \mathbb{R}^d$, which will be used to find an updated posterior. Why do we need the acquisition function? Why can't we simply evaluate $f$ at random domain points? Given that $f$ is expensive to evaluate, we need a clever way to choose the points where we want to evaluate $f$. More specifically, we want to evaluate $f$ where we are more uncertain about it.

There are several acquisition functions, such as expected improvement, knowledge-gradient, entropy search, and predictive entropy search, so there are different ways of choosing the points of the domain of $f$ where we want to evaluate it to update the posterior, each of which deals with the exploration-exploitation dilemma differently.

What can Bayesian optimization be used for?

BO can be used for tuning hyper-parameters (also called hyper-parameter optimisation) of machine learning models, such as neural networks, but it has also been used to solve other problems.

What is an alternative surrogate model?

In the book Automated Machine Learning: Methods, Systems, Challenges (by Frank Hutter et al.) that you are quoting, the authors say that the commonly used surrogate model Gaussian process scales cubically in the number of data points, so sparse Gaussian processes are often used. Moreover, Gaussian processes also scale badly with the number of dimensions. In section, the authors describe some alternative surrogate models to the Gaussian processes, for example, alternatives that use neural networks or random forests.

| improve this answer | |

A surrogate model is a simplified model. It is a mapping $y_S=f_S(x)$ that approximates the original model $y=f(x)$, in a given domain, reasonably well. Source: Engineering Design via Surrogate Modelling: A Practical Guide

In the context of Bayesian optimization, one wants to optimize a function $y=f(x)$ which is expensive (very time consuming) to evaluate, therefore one optimizes the surrogate model $y_S=f_S(x)$ which is cheaper (faster) to evaluate.

| improve this answer | |
  • $\begingroup$ Forgive my ignorance, but why exactly is yS=fS(x) faster to evaluate? $\endgroup$ – Goose Mar 8 at 20:07
  • 1
    $\begingroup$ Imagine that the original model is computed from Finite Element simulations (x would be some geometric parameter or material constant for instance and f(x) some quantity of interest) and f_S is a polynomial approximation like a0 + a1x + a2x^2. f(x) can take some hours to evaluate whereas f_S(x) can be calculated pretty fast $\endgroup$ – Javier-Acuna Mar 9 at 21:10

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.