Bayes’sche Optimierung

Die Bayes’sche Optimierung (BO, engl. Bayesian Optimization) ist eine sequenzielle Optimierungsmethode für die Optimierung von Black-Box-Funktionen deren Auswertung teuer ist, d. h. in der Regel Minuten oder Stunden dauert.^[1] Dies tritt beispielsweise auf, wenn die zu optimierende Funktion nicht geschlossen darstellbar ist, sondern etwa das Ergebnis einer Simulation ausgibt, die Ergebnisse des Trainings eines Machine-Learning-Modells darstellt (s. Hyperparameteroptimierung) oder das Ergebnis eines experimentellen Versuchs zurückgibt (s. Design of Experiment).

Die Grundidee Bayes’sche Optimierung besteht aus dem Prinzip Exploitation and Exploration.^[2] Dies bedeutet, dass beim Vorschlagen neuer Punkte ein Trade-off zwischen bereits bekannten guten Punkten (Exploitation) und neuen hoffentlich noch besseren Punkten (Exploration) gefunden wird, welcher durch die gewählte Akquisitionsfunktion (acquisition function) beeinflusst wird. Sucht man in der Bayes’schen Optimierung einen Tradeoff für die Maximierung eines Erwartungswertes und die Minimierung der Streuung kann dies als Mehrzieloptimierung betrachtet werden.

Geschichte

Der Begriff wird im Allgemeinen Harold J. Kushner und Jonas Mockus zugeschrieben, welche in den 1960er und 1970er Jahren begannen, dazu zu publizieren.^[3][4]

Ausgangslage

Die Bayes'sche Optimierung wird typischerweise bei Optimierungsproblemen der Form ${\textstyle \max _{x\in A}f(x)}$ eingesetzt, wobei ${\textstyle A}$ die Menge aller zulässigen Punkte ${\textstyle x}$ ist, welche auch zulässige Menge genannt wird. Die Bayes'sche Optimierung ist besonders vorteilhaft für Probleme, bei denen die Berechnung eines Funktionswerts ${\textstyle f(x)}$ der Zielfunktion ${\displaystyle f}$ mit großem Aufwand verbunden ist. Die Zielfunktion ${\textstyle f}$ ist in der Regel stetig und ist ansonsten von unbekannter Struktur, die als „Black Box“ bezeichnet wird. Bei ihrer Auswertung wird nur Funktionswert ${\textstyle f(x)}$ beobachtet und die Ableitungen nicht berechnet.^[5]

Strategie

Da die Zielfunktion ${\displaystyle f}$ unbekannt ist, besteht die Bayes'sche Strategie darin, sie als Zufallsfunktion zu behandeln und ihr einen Prior zuzuweisen. Der Prior gibt die Annahmen über das Verhalten der Funktion wieder. Nach dem Sammeln einer Stichprobe bestehend aus Punkten ${\displaystyle x_{i}}$ und zugehörigen „wahren“ Funktionswerten ${\displaystyle f(x_{i})}$, wird der Prior aktualisiert, um die Posterior-Verteilung über die Zielfunktion zu bilden. Die Posterior-Verteilung wird wiederum verwendet, um eine Akquisitionsfunktion (oft auch als Infill-Sampling-Kriterium bezeichnet) zu konstruieren, die optimiert wird, um den nächsten Abfragepunkt zu bestimmen.

Bayes'sche Optimierung einer Funktion (schwarz) mit Gaußschen Prozessen (lila). Unten sind drei Acquisition Functions (blau) dargestellt.^[6]

In der Optimierung sollen neue Punkte ${\displaystyle x_{t}^{*}}$ vorgeschlagen werden, die ${\displaystyle f}$ maximieren/minimieren.

Surrogatmodell

Die Bayes'sche Optimierung beruht darauf, dass ein Surrogatmodell ${\displaystyle {\hat {f}}}$ an der Stelle ${\displaystyle x\in A}$ leichter auszuwerten ist als die echte Black-Box Funktion ${\displaystyle f}$. Typischerweise werden als Surrogatmodelle Gauß-Prozesse, Parzen-Tree Estimator, Random Forests oder andere bootstrap aggregated models verwendet. Gemeinsam haben diese Schätzmodelle, dass sie eine Varianzschätzung (und damit eine Schätzung der Verteilung) erlauben. Diese Varianzsschätzung wird anschließend in der Akquisitionsfunktion verwendet, um nicht nur das (mittlere, erwartete) Optimum zu finden, sondern zusätzlich einen Erwartungswert-Varianz-Trade-off einzugehen: Punkte ${\displaystyle x}$ mit hoher Varianz in der Vorhersage des Surrogatmodells könnten beispielsweise einen deutlich höheren echten Wert ${\displaystyle f}$ aufweisen als das Modell ${\displaystyle {\hat {f}}}$ bisher modelliert hat. Punkte mit hoher Chance auf eine mögliche Verbesserung (gemessen durch die Akquisitionsfunktion) werden als neue Punkte zur Auswertung von ${\displaystyle f}$ vorgeschlagen.

Vorschlagen neuer Punkte

Jedes Mal, wenn eine Auswertung erfolgt, wird das neue Wertepaar ${\displaystyle (x,f(x))}$ in das Trainingsset des Surrogatmodells aufgenommen. Es ergeben sich dann neue Punkte mit hoher Chance auf eine mögliche Verbesserung und der Vorgang wird bis zur Konvergenz wiederholt, wobei keine Konvergenz im mathematischen Sinne erwartet wird, sondern die Methode beispielsweise nach einer bestimmten Anzahl von Iterationen aus Budget-Gründen endet oder ein vorzeitiger Abbruch vorgenommen wird, falls sich in den letzten Iterationen keine Verbesserung mehr feststellen ließ.

Mit Kenntnis der durch das Surrogatmodell geschätzten bedingten Wahrscheinlichkeitsdichte ${\displaystyle {\hat {p}}(f|x_{i})}$ kann die Akquisitionsfunktion iterativ optimiert werden. Der nächste zu überprüfenden Punkt ist ${\displaystyle x_{t}={\text{argmax}}_{x}{\text{Acquisition function}}(x)}$ (wenn die Akquisitionsfunktion maximiert werden soll). Die argmax Funktion kann näherungsweise für eine endliche Menge an zufälligen Punkten ${\displaystyle \{x_{1},\dots x_{n}\}}$ausgewertet werden. Die Näherung an argmax ist dann der x-Wert, welcher den größten Wert der Akquisitionsfunktion hat.

Pseudocode

Die folgende algorithmische Grundidee der Bayes'schen Optimierung wird wie folgt in Anlehnung an die Literatur dargestellt.^[2]

FOR ${\displaystyle n=1,2,\ldots }$ DO
  Wähle einen neuen Punkt ${\displaystyle x_{n+1}}$ durch Optimierung der Akquisitionsfunktion ${\displaystyle \alpha }$: ${\displaystyle x_{n+1}=\arg \max \alpha (x;{\cal {D_{n})}}}$
  Evaluiere den Zielfunktionswert: ${\displaystyle y_{n+1}=f(x_{n+1})}$
  Erweitere den Datensatz um den neuen Punkt:${\displaystyle {\cal {D_{n+1}=\{{\cal {D_{n},(x_{n+1},y_{n+1})\}}}}}}$
  Aktualisiere das zugrundeliegende statistische Modell
END FOR

Exotische Bayes'sche Optimierung

Probleme, die von der oben gemachten Annahme der leichten Auswertung abweichen, werden als exotische Bayes'sche Optimierungsprobleme bezeichnet. Optimierungsprobleme können exotisch werden, wenn bekannt ist, dass es Rauschen gibt, die Auswertungen parallel durchgeführt werden, die Qualität der Auswertungen von einem Kompromiss zwischen Schwierigkeit und Genauigkeit abhängt, zufällige Umgebungsbedingungen vorhanden sind oder die Auswertung Ableitungen beinhaltet.^[5]

Beispiele für Akquisitionsfunktionen

Akquisitionsfunktionen stellen einen Kompromiss (Trade-off) zwischen Erkundung und Ausnutzung dar, um die Anzahl der Funktionsabfragen zu minimieren. Die Bayes'sche Optimierung eignet sich daher gut für Funktionen, deren Auswertung teuer ist.

Beispiele für Akquisitionsfunktionen (engl. acquisition function) sind:

• obere (${\displaystyle \kappa >0}$), bzw. untere (${\displaystyle \kappa <0}$) Konfidenzgrenzen ${\displaystyle CB(x)={\hat {\mu }}(x)+\kappa {\hat {\sigma }}(x)}$,
• die Verbesserungswahrscheinlichkeit ${\displaystyle p(f(x)>f(x^{\dagger })+\kappa )}$,
• die erwartete Verbesserung,
• die erwarteten Verluste nach Bayes,
• Thompson-Sampling und Mischformen davon.^[7]

Erwartete Verbesserung

Die erwartete Verbesserung (expected improvement) ist ${\displaystyle EI(x)=E[f|x]-f(x^{\dagger })}$^[8]. Hierbei ist ${\displaystyle f(x^{\dagger })}$ der bisher tatsächlich beobachtete Maximalwert der Blackbox-Funktion ${\displaystyle f}$. Der bedingte Erwartungswert berechnet sich durch ${\displaystyle E[f|x]=\int _{\mathbb {R} }fp(f|x)df}$.

In der Literatur gibt es auch andere nicht äquivalente Definitionen der erwarteten Verbesserung:

${\displaystyle EI(x)=\int _{\mathbb {R} }\max(f-f(x^{\dagger }),0)p(f|x)df}$^[9].

Für einen Gauss-Prozess folgt aus der Definition^[10]:

${\displaystyle EI(x)=\left({\hat {\mu }}(x)-f(x^{\dagger })\right)\Phi \left({\frac {{\hat {\mu }}(x)-f(x^{\dagger })}{{\hat {\sigma }}(x)}}\right)+{\hat {\sigma }}(x)\phi \left({\frac {{\hat {\mu }}(x)-f(x^{\dagger })}{{\hat {\sigma }}(x)}}\right),}$

wobei ${\displaystyle \Phi }$ die Verteilungsfunktion der Normalverteilung ist und ${\displaystyle \phi }$ die Wahrscheinlichkeitsdichtefunktion der Normalverteilung ist. Die erwartete Verbesserung ermöglicht somit den Vorschlag von Punkten ${\displaystyle x}$ für die ${\displaystyle {\hat {\mu }}(x)<f(x^{\dagger })}$, bei denen aber ${\displaystyle {\hat {\sigma }}(x)}$ groß ist. Somit ermöglicht diese Akquisitionsfunktion die Exploration.

Die erwartete Verbesserung wählt im Vergleich zur Akquisionsfunktion mit Konfidenzgrenzen einen gewissen Explorations-Exploitation Trade-off ohne weiteren expliziten Hyperparameter ${\displaystyle \kappa }$ (welcher bei LCB or UCB als Akquisitionsfunktion vorliegt).

Lösungsmethoden

Die Maximierung der Akquisitionsfunktion erfolgt durch Verfahren der mathematischen Optimierung (Newtonverfahren, Quasi-Newton-Methoden wie dem Broyden-Fletcher-Goldfarb-Shanno-Algorithmus …) oder durch Random Sampling, das heißt dem Auswerten der Akquisitionsfunktion an zufällig gezogenen Punkten der zulässigen Menge ${\displaystyle A}$.

Anwendungsgebiete

Der Ansatz wurde zur Lösung einer Vielzahl von Problemen angewandt,^[11] darunter Hyperparameteroptimierung, Rangordnungslernen,^[12] Computergrafik und visuelles Design,^[13][14][15] Robotik,^{[16][17][18][19]} Sensornetzwerke,^[20][21] automatische Algorithmenkonfiguration,^[22][23] automatische Toolboxen für maschinelles Lernen,^[24][25][26] Reinforcement Learning, Planung, visuelle Aufmerksamkeit, Architekturkonfiguration beim Deep Learning, statische Programmanalyse, experimentelle Teilchenphysik,^[27][28] Chemie, Materialdesign^[29][30][31] und Arzneimittelentwicklung.^[5][32][33]

Literatur

• Bobak Shahriari et al.: Taking the Human Out of the Loop: A Review of Bayesian Optimization, Proceedings of the IEEE, Volume: 104, Issue: 1, January 2016
• Peter I. Frazier: A Tutorial on Bayesian Optimization, arXiv.org

Weblinks

• Spearmint, a Python implementation focused on parallel and cluster computing.
• SMAC, an implementation of random-forest-based Bayesian optimization for general algorithm configuration.
• MOE MOE is a Python/C++/CUDA implementation of Bayesian Global Optimization using Gaussian Processes.
• scikit-optimize, a Python implementation of Bayesian optimization.
• BoTorch, a modular and modern PyTorch-based open-source library for Bayesian optimization research with support for GPyTorch.
• GPflowOpt, a TensorFlow-based open-source package for Bayesian optimization.
• OMLT und ENTMOOT: Pakete zur Optimierung trainierter ML-Modelle, etwa zum Einsatz in der Bayes'schen Optimierung

Einzelnachweise

1. Peter I. Frazier: A Tutorial on Bayesian Optimization. arxiv:1807.02811. 
2. Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, Nando de Freitas: Taking the Human Out of the Loop: A Review of Bayesian Optimization. In: Proceedings of the IEEE. Band 104, Nr. 1, Januar 2016, S. 148–175, doi:10.1109/jproc.2015.2494218 (ox.ac.uk [PDF; abgerufen am 22. Januar 2024]). 
3. Jonas Mockus: On Bayesian Methods for Seeking the Extremum. Optimization Techniques 1974: 400-404, doi:10.1007/3-540-07165-2_55
4. H. J. Kushner: A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. In: Journal of Basic Engineering. Band 86, Nr. 1, 1. März 1964, S. 97–106, doi:10.1115/1.3653121. 
5. Peter I. Frazier: A Tutorial on Bayesian Optimization. 8. Juli 2018, doi:10.48550/arXiv.1807.02811. 
6. Samuel Wilson: Parallelizable Bayesian Optimization (Paketbeschreibung auf GitHub). 22. November 2019, abgerufen am 14. Juni 2022. 
7. Matthew W. Hoffman, Eric Brochu, Nando de Freitas: Portfolio Allocation for Bayesian Optimization. Uncertainty in Artificial Intelligence: 327–336 (2011)
8. skopt
9. Acquisition functions in Bayesian Optimization
10. https://predictivesciencelab.github.io/data-analytics-se/lecture23/hands-on-23.4.html
11. 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)
12. Eric Brochu, Nando de Freitas, Abhijeet Ghosh: Active Preference Learning with Discrete Choice Data. Advances in Neural Information Processing Systems: 409-416 (2007)
13. Eric Brochu, Tyson Brochu, Nando de Freitas: A Bayesian Interactive Optimization Approach to Procedural Animation Design. Symposium on Computer Animation 2010: 103–112
14. Yuki Koyama, Issei Sato, Daisuke Sakamoto, Takeo Igarashi: Sequential Line Search for Efficient Visual Design Optimization by Crowds. ACM Transactions on Graphics, Band 36, Nummer 4, S. 48:1–48:11 (2017). doi:10.1145/3072959.3073598
15. Yuki Koyama, Issei Sato, Masataka Goto: Sequential Gallery for Interactive Visual Design Optimization. ACM Transactions on Graphics, Band 39, Nummer 4, S. 88:1–88:12 (2020). doi:10.1145/3386569.3392444, arXiv:2005.04107.
16. Daniel J. Lizotte, Tao Wang, Michael H. Bowling, Dale Schuurmans: Automatic Gait Optimization with Gaussian Process Regression (Memento vom 12. August 2017 im Internet Archive). International Joint Conference on Artificial Intelligence: 944–949 (2007)
17. 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. Band 27, Nummer 2, S. 93–103 (2009) doi:10.1007/s10514-009-9130-2.
18. Scott Kuindersma, Roderic Grupen, and Andrew Barto. Variable Risk Control via Stochastic Optimization. International Journal of Robotics Research, volume 32, number 7, S. 806–825 (2013)
19. Roberto Calandra, André Seyfarth, Jan Peters, and Marc P. Deisenroth: Bayesian optimization for learning gaits under uncertainty. Ann. Math. Artif. Intell. Band 76, Nummer 1, S. 5–23 (2016) DOI:10.1007/s10472-015-9463-9
20. 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)
21. Roman Garnett, Michael A. Osborne, Stephen J. Roberts: Bayesian optimization for sensor set selection@1@2Vorlage:Toter Link/www.academia.edu (Seite nicht mehr abrufbar, festgestellt im Juni 2023. Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis.. ACM/IEEE International Conference on Information Processing in Sensor Networks: 209–219 (2010)
22. Frank Hutter, Holger Hoos, and Kevin Leyton-Brown (2011). Sequential model-based optimization for general algorithm configuration, Learning and Intelligent Optimization
23. J. Snoek, H. Larochelle, R. P. Adams Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems: 2951-2959 (2012)
24. J. Bergstra, D. Yamins, D. D. Cox (2013). Hyperopt: A Python Library for Optimizing the Hyperparameters of Machine Learning Algorithms. Proc. SciPy 2013.
25. Chris Thornton, Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown: Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms. KDD 2013: 847–855
26. Jasper Snoek, Hugo Larochelle and Ryan Prescott Adams. Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems, 2012
27. Philip Ilten, Mike Williams, Yunjie Yang. Event generator tuning using Bayesian optimization. 2017 JINST 12 P04028. DOI: 10.1088/1748-0221/12/04/P04028
28. 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
29. Tsuyoshi Ueno, Trevor David Rhone, Zhufeng Hou, Teruyasu Mizoguchi, Koji Tsuda: COMBO: An efficient Bayesian optimization library for materials science. In: Materials Discovery. Band 4, Juni 2016, S. 18–21, doi:10.1016/j.md.2016.04.001. 
30. Hud Wahab, Vivek Jain, Alexander Scott Tyrrell, Michael Alan Seas, Lars Kotthoff: Machine-learning-assisted fabrication: Bayesian optimization of laser-induced graphene patterning using in-situ Raman analysis. In: Carbon. Band 167, Oktober 2020, S. 609–619, doi:10.1016/j.carbon.2020.05.087. 
31. Yuki K. Wakabayashi, Takuma Otsuka, Yoshiharu Krockenberger, Hiroshi Sawada, Yoshitaka Taniyasu: Machine-learning-assisted thin-film growth: Bayesian optimization in molecular beam epitaxy of SrRuO 3 thin films. In: APL Materials. Band 7, Nr. 10, 1. Oktober 2019, S. 101114, doi:10.1063/1.5123019. 
32. 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). doi:10.1021/acscentsci.7b00572
33. Griffiths et al. Constrained Bayesian Optimization for Automatic Chemical Design using Variational Autoencoders, Chemical Science: 11, 577–586 (2020), doi:10.1039/C9SC04026A