Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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?
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.
There are three main concepts in BO
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.
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.
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 1.3.2.2., the authors describe some alternative surrogate models to the Gaussian processes, for example, alternatives that use neural networks or random forests.
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.
Recently, I've been thinking this question as well. After reading several papers, finally came up with some thoughts about the surrogate model. In FEM(finite element method), we try to find a weak form to approximate the strong form so that we can solve the weak form analytically. (weak form: approximation equation; strong form: PDE in real world) In my opinion, the surrogate model can be regarded as 'weak form'. There are many methods can form a surrogate model. And if we use a NN model as the surrogate model, the training process is equivalent to 'solving analytically'.
