Bayesian optimization

Bayesian optimizationis asequential designstrategy forglobal optimizationofblack-boxfunctionsthat does not assume any functional forms. It is usually employed to optimize expensive-to-evaluate functions.

History

The term is generally attributed toJonas Mockusand is coined in his work from a series of publications on global optimization in the 1970s and 1980s.

Strategy

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

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,${\textstyle x}$,which rely upon less than 20dimensions(${\textstyle \mathbb {R} ^{d},d\leq 20}$), and whose membership can easily be evaluated. Bayesian optimization is particularly advantageous for problems where${\textstyle f(x)}$is difficult to evaluate due to its computational cost. The objective function,${\textstyle f}$,is continuous and takes the form of some unknown structure, referred to as a "black box". Upon its evaluation, only${\textstyle f(x)}$is observed and itsderivativesare not evaluated.

Since the objective function is unknown, the Bayesian strategy is to treat it as a random function and place apriorover 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 theposterior distributionover 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 useGaussian processesin a method calledkriging.Another less expensive method uses theParzen-Tree Estimatorto construct two distributions for 'high' and 'low' points, and then finds the location that maximizes the expected improvement.

Standard Bayesian optimization relies upon each$x\in A$being easy to evaluate, and problems that deviate from this assumption are known asexotic Bayesian optimizationproblems. 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.

Acquisition functions

Examples of acquisition functions include

• probability of improvement
• expected improvement
• Bayesian expected losses
• upper confidence bounds (UCB) or lower confidence bounds
• Thompson sampling

and hybrids of these.They all trade-offexploration and exploitationso as to minimize the number of function queries. As such, Bayesian optimization is well suited for functions that are expensive to evaluate.

Solution methods

The maximum of the acquisition function is typically found by resorting to discretization or by means of an auxiliary optimizer. Acquisition functions are maximized using anumerical optimization technique,such asNewton's Methodor quasi-Newton methods like theBroyden–Fletcher–Goldfarb–Shanno algorithm.

Applications

The approach has been applied to solve a wide range of problems,includinglearning to rank,computer graphicsand visual design,robotics,sensor networks,automatic algorithm configuration,automatic machine learningtoolboxes,reinforcement learning,planning, visual attention, architecture configuration indeep learning,static program analysis, experimentalparticle physics,quality-diversity optimization,chemistry, material design, and drug development.

Bayesian Optimization has been applied in the field of facial recognition.The performance of the Histogram of Oriented Gradients (HOG) algorithm, a popular feature extraction method, heavily relies on its parameter settings. Optimizing these parameters can be challenging but crucial for achieving high accuracy.A novel approach to optimize the HOG algorithm parameters and image size for facial recognition using a Tree-structured Parzen Estimator (TPE) based Bayesian optimization technique has been proposed.This optimized approach has the potential to be adapted for other computer vision applications and contributes to the ongoing development of hand-crafted parameter-based feature extraction algorithms in computer vision.

See also

• Multi-armed bandit
• Kriging
• Thompson sampling
• Global optimization
• Bayesian experimental design
• Probabilistic numerics
• Pareto optimum
• Active learning (machine learning)
• Multi-objective optimization