Bayesian optimization

 Bayesian optimization is a sequential design strategy for global optimization of black-box functions^[1] that does not assume any functional forms. It is usually employed to optimize expensive-to-evaluate functions.

HistoryEdit

The term is generally attributed to Jonas Mockus and is coined in his work from a series of publications on global optimization in the 1970s and 1980s.^[2][3][4]

StrategyEdit

Bayesian optimization of a function (black) with Gaussian processes (purple). Three acquisition functions (blue) are shown at the bottom.^[5]

Bayesian optimization is typically used on problems of the form ${\textstyle \max _{x\in A}f(x)}$, where ${\textstyle A}$ is a set of points whose membership can easily be evaluated. Bayesian optimization is particularly advantageous for problems where ${\textstyle f(x)}$ is difficult to evaluate, is a black box with some unknown structure, relies upon less than 20 dimensions, and where derivatives are not evaluated.^[6]

Since the objective function is unknown, the Bayesian strategy is to treat it as a random function and place a prior over it. The prior captures beliefs about the behavior of the function. After gathering the function evaluations, which are treated as data, the prior is updated to form the posterior distribution over the objective function. The posterior distribution, in turn, is used to construct an acquisition function (often also referred to as infill sampling criteria) that determines the next query point.

There are several methods used to define the prior/posterior distribution over the objective function. The most common two methods use Gaussian Processes in a method called Kriging. Another less expensive method uses the Parzen-Tree Estimator to construct two distributions for 'high' and 'low' points, and then finds the location that maximizes the expected improvement.^[7]

Standard Bayesian optimization relies upon each ${\displaystyle x\in A}$ being easy to evaluate, and problems that deviate from this assumption are known as exotic Bayesian optimization problems. Optimization problems can become exotic if it is known that there is noise, the evaluations are being done in parallel, the quality of evaluations relies upon a tradeoff between difficulty and accuracy, the presence of random environmental conditions, or if the evaluation involves derivatives.^[6]

ExamplesEdit

Examples of acquisition functions include probability of improvement, expected improvement, Bayesian expected losses, upper confidence bounds (UCB), Thompson sampling and hybrids of these.^[8] They all trade-off exploration and exploitation so as to minimize the number of function queries. As such, Bayesian optimization is well suited for functions that are expensive to evaluate.

Solution methodsEdit

The maximum of the acquisition function is typically found by resorting to discretization or by means of an auxiliary optimizer. Acquisition functions are typically well-behaved and are often maximized with implementations of Newton's Method such as Broyden–Fletcher–Goldfarb–Shanno algorithm or the Nelder-Mead method.

ApplicationsEdit

The approach has been applied to solve a wide range of problems,^[9] including learning to rank,^[10] computer graphics and visual design,^[11][12] robotics,^{[13][14][15][16]} sensor networks,^[17][18] automatic algorithm configuration,^[19][20] automatic machine learning toolboxes,^[21][22][23] reinforcement learning, planning, visual attention, architecture configuration in deep learning, static program analysis, experimental particle physics,^[24][25] chemistry, material design, and drug development.^[6][26][27]

This article uses material from the Wikipedia article  Metasyntactic variable, which is released under the  Creative Commons Attribution-ShareAlike 3.0 Unported License.