Bayesian optimization explained

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

History

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

Strategy

Bayesian optimization is typically used on problems of the form $\backslash max\_\; f(x)$, where $A$ is a set of points, $x$, which rely upon less than 20 dimensions ($\backslash mathbb^d,\; d\; \backslash le\; 20$), and whose membership can easily be evaluated. Bayesian optimization is particularly advantageous for problems where $f(x)$ is difficult to evaluate due to its computational cost. The objective function, $f$, is continuous and takes the form of some unknown structure, referred to as a "black box". Upon its evaluation, only $f(x)$ is observed and its 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

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.

Acquisition functions

Examples of acquisition functions include

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

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 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 a numerical optimization technique, such as Newton's Method or quasi-Newton methods like the Broyden–Fletcher–Goldfarb–Shanno algorithm.

Applications

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] [13]} robotics,^{[14] [15] [16] [17]} sensor networks,^{[18] [19]} automatic algorithm configuration,^{[20] [21]} automatic machine learning toolboxes,^{[22] [23] [24]} reinforcement learning,^[25] planning, visual attention, architecture configuration in deep learning, static program analysis, experimental particle physics,^{[26] [27]} quality-diversity optimization,^{[28] [29] [30]} chemistry, material design, and drug development.^{[31] [32]}

Bayesian Optimization has been applied in the field of facial recognition.^[33] 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.^[33] 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.^[33] 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.^[33]

See also

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

Notes and References

1. Book: Garnett, Roman . Bayesian Optimization . 2023 . Cambridge University Press . 978-1-108-42578-0 .
2. Book: Hennig, P.. Osborne, M. A.. Kersting, H. P.. 2022. Probabilistic Numerics. 243–278. Cambridge University Press. 978-1107163447.
3. Book: Močkus, Jonas . Optimization Techniques IFIP Technical Conference Novosibirsk, July 1–7, 1974 . On bayesian methods for seeking the extremum . 10.1007/3-540-07165-2_55 . Lecture Notes in Computer Science . 1975 . 27 . 400–404 . 978-3-540-07165-5 . free .
4. Jonas . Močkus . On Bayesian Methods for Seeking the Extremum and their Application . IFIP Congress . 1977 . 195–200 .
5. Book: Močkus, J. . Bayesian Approach to Global Optimization . Kluwer Academic . Dordrecht . 1989 . 0-7923-0115-3 .
6. Frazier. Peter I.. 2018-07-08. A Tutorial on Bayesian Optimization. stat.ML. 1807.02811.
7. J. S. Bergstra, R. Bardenet, Y. Bengio, B. Kégl: Algorithms for Hyper-Parameter Optimization. Advances in Neural Information Processing Systems: 2546–2554 (2011)
8. Matthew W. Hoffman, Eric Brochu, Nando de Freitas: Portfolio Allocation for Bayesian Optimization. Uncertainty in Artificial Intelligence: 327–336 (2011)
9. Eric Brochu, Vlad M. Cora, Nando de Freitas: A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning. CoRR abs/1012.2599 (2010)
10. Eric Brochu, Nando de Freitas, Abhijeet Ghosh: Active Preference Learning with Discrete Choice Data. Advances in Neural Information Processing Systems: 409-416 (2007)
11. Eric Brochu, Tyson Brochu, Nando de Freitas: A Bayesian Interactive Optimization Approach to Procedural Animation Design. Symposium on Computer Animation 2010: 103–112
12. Yuki Koyama, Issei Sato, Daisuke Sakamoto, Takeo Igarashi: Sequential Line Search for Efficient Visual Design Optimization by Crowds. ACM Transactions on Graphics, Volume 36, Issue 4, pp.48:1–48:11 (2017). DOI: https://doi.org/10.1145/3072959.3073598
13. Yuki Koyama, Issei Sato, Masataka Goto: Sequential Gallery for Interactive Visual Design Optimization. ACM Transactions on Graphics, Volume 39, Issue 4, pp.88:1–88:12 (2020). DOI: https://doi.org/10.1145/3386569.3392444
14. Daniel J. Lizotte, Tao Wang, Michael H. Bowling, Dale Schuurmans: Automatic Gait Optimization with Gaussian Process Regression . International Joint Conference on Artificial Intelligence: 944–949 (2007)
15. Ruben Martinez-Cantin, Nando de Freitas, Eric Brochu, Jose Castellanos and Arnaud Doucet. A Bayesian exploration-exploitation approach for optimal online sensing and planning with a visually guided mobile robot. Autonomous Robots. Volume 27, Issue 2, pp 93–103 (2009)
16. Scott Kuindersma, Roderic Grupen, and Andrew Barto. Variable Risk Control via Stochastic Optimization. International Journal of Robotics Research, volume 32, number 7, pp 806–825 (2013)
17. Roberto Calandra, André Seyfarth, Jan Peters, and Marc P. Deisenroth Bayesian optimization for learning gaits under uncertainty. Ann. Math. Artif. Intell. Volume 76, Issue 1, pp 5-23 (2016) DOI:10.1007/s10472-015-9463-9
18. Niranjan Srinivas, Andreas Krause, Sham M. Kakade, Matthias W. Seeger: Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting. IEEE Transactions on Information Theory 58(5):3250–3265 (2012)
19. Garnett . Roman . Osborne . Michael A. . Roberts . Stephen J. . Abdelzaher . Tarek F. . Voigt . Thiemo . Wolisz . Adam . Bayesian optimization for sensor set selection . https://scholar.archive.org/work/wfgahthp2vgcnaafcxa3isieom . 10.1145/1791212.1791238 . 209–219 . ACM . Proceedings of the 9th International Conference on Information Processing in Sensor Networks, IPSN 2010, April 12–16, 2010, Stockholm, Sweden . 2010.
20. Frank Hutter, Holger Hoos, and Kevin Leyton-Brown (2011). Sequential model-based optimization for general algorithm configuration, Learning and Intelligent Optimization
21. J. Snoek, H. Larochelle, R. P. Adams Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems: 2951-2959 (2012)
22. J. Bergstra, D. Yamins, D. D. Cox (2013).Hyperopt: A Python Library for Optimizing the Hyperparameters of Machine Learning Algorithms.Proc. SciPy 2013.
23. Chris Thornton, Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown: Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms. KDD 2013: 847–855
24. Jasper Snoek, Hugo Larochelle and Ryan Prescott Adams. Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems, 2012
25. Safe Exploration in Reinforcement Learning: Theory and Applications in Robotics . ETH Zurich . 2019 . Doctoral Thesis . 10.3929/ethz-b-000370833 . en . Felix . Berkenkamp. 20.500.11850/370833 .
26. Philip Ilten, Mike Williams, Yunjie Yang. Event generator tuning using Bayesian optimization. 2017 JINST 12 P04028. DOI: 10.1088/1748-0221/12/04/P04028
27. Evaristo Cisbani et al. AI-optimized detector design for the future Electron-Ion Collider: the dual-radiator RICH case 2020 JINST 15 P05009. DOI: 10.1088/1748-0221/15/05/P05009
28. Kent . Paul . Gaier . Adam . Mouret . Jean-Baptiste . Branke . Juergen . 2023-07-19 . BOP-Elites, a Bayesian Optimisation Approach to Quality Diversity Search with Black-Box descriptor functions . math.OC . 2307.09326. Preprint: Arxiv.
29. Book: Kent . Paul . Branke . Juergen . Proceedings of the Genetic and Evolutionary Computation Conference . Bayesian Quality Diversity Search with Interactive Illumination . 2023-07-12 . https://dl.acm.org/doi/10.1145/3583131.3590486 . GECCO '23 . New York, NY, USA . Association for Computing Machinery . 1019–1026 . 10.1145/3583131.3590486 . 979-8-4007-0119-1. 259833672 .
30. Gaier . Adam . Asteroth . Alexander . Mouret . Jean-Baptiste . 2018-09-01 . Data-Efficient Design Exploration through Surrogate-Assisted Illumination . Evolutionary Computation . 26 . 3 . 381–410 . 10.1162/evco_a_00231 . 29883202 . 47003986 . 1063-6560. free . 1806.05865 .
31. Gomez-Bombarelli et al. Automatic Chemical Design using a Data-Driven Continuous Representation of Molecules. ACS Central Science, Volume 4, Issue 2, 268-276 (2018)
32. Griffiths et al. Constrained Bayesian Optimization for Automatic Chemical Design using Variational Autoencoders Chemical Science: 11, 577-586 (2020)
33. Mohammed Mehdi Bouchene: Bayesian Optimization of Histogram of Oriented Gradients (Hog) Parameters for Facial Recognition. SSRN (2023)