Bayesian Optimization Algorithm

Context:
- It can balance exploration and exploitation through the acquisition function which uses the posterior distribution to determine where to sample next.
- It can use an Acquisition Function (like expected improvement, upper confidence bound, and probability of improvement) to measure utility of potential points and guide the exploration-exploitation trade-off.
- It can employ a Posterior Distribution to capture beliefs about the objective function using Bayesian inference, represent uncertainty, and trade off exploration and exploitation.
- It can be implemented by a Bayesian Optimization System (that solve a Bayesian optimization task).
- It can range from being a Bayesian Optimization of a Single Objective to being a Bayesian Optimization with Multiple Objectives (BOMO).
- …
Example(s):
- Sequential Model-Based Optimization (SMBO): SMBO is a general framework for BOA that can be used with a variety of surrogate models and acquisition functions.
- Gaussian Process Optimization (GPO): GPO is a specific type of BOA that uses Gaussian processes as the surrogate model.
- Tree Parzen Estimator (TPE): TPE is another specific type of BOA that uses Tree Parzen Estimators as the surrogate model.
- …
Counter-Example(s):
- a Local Optimization Algorithm, such as: Gradient Descent.
See: Gaussian Process Regression, Upper Confidence Bound Algorithm.

References

(Wikipedia, 2023) ⇒ https://en.wikipedia.org/wiki/Bayesian_optimization Retrieved:2023-10-18.
- Bayesian optimization is a sequential design strategy for global optimization of black-box functions that does not assume any functional forms. It is usually employed to optimize expensive-to-evaluate functions.

(Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Bayesian_optimization#Strategy Retrieved:2019-9-12.
- 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 behaviour 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.

Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. 2012. Practical Bayesian optimization of machine learning algorithms. In Proc. of NIPS .

(Brochu et al., 2010) ⇒ Eric Brochu, Vlad M. Cora, and Nando De Freitas. (2010). “A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning." arXiv preprint arXiv:1012.2599
- ABSTRACT: We present a tutorial on Bayesian optimization, a method of finding the maximum of expensive cost functions. Bayesian optimization employs the Bayesian technique of setting a prior over the objective function and combining it with evidence to get a posterior function. This permits a utility-based selection of the next observation to make on the objective function, which must take into account both exploration (sampling from areas of high uncertainty) and exploitation (sampling areas likely to offer improvement over the current best observation). We also present two detailed extensions of Bayesian optimization, with experiments --- active user modelling with preferences, and hierarchical reinforcement learning --- and a discussion of the pros and cons of Bayesian optimization based on our experiences.