Bayes'sche Optimierung

Die Bayes'sche Optimierung ist eine sequentielle, modellbasierte Strategie zur globalen Optimierung von Black-Box -Zielfunktionen, deren Auswertung aufwändig ist. ^{[ 1 ] [ 2 ] [ 3 ]} Sie wird häufig eingesetzt, wenn für eine einzelne Beobachtung ein Experiment, eine technische Berechnung, eine numerische Simulation oder ein Machine-Learning-Lauf erforderlich ist und wenn Ableitungen nicht verfügbar oder unzuverlässig sind. Die Zielfunktion muss keine geschlossene Form besitzen.

Das Verfahren erstellt ein probabilistisches Modell der unbekannten Funktion, häufig einen Gaußprozess (GP), und verwendet die resultierende Vorhersageverteilung, um den nächsten Auswertungspunkt zu bestimmen. Diese Bestimmung erfolgt durch Optimierung eines Abtastkriteriums, auch Akquisitionsfunktion genannt. ^{[ 3 ] [ 2 ]}

Zu den gängigen Anwendungsgebieten gehören die Hyperparameteroptimierung im maschinellen Lernen , wo jeder Versuch das Training und die Validierung eines Modells erfordern kann ^{[ 4 ] [ 5 ]} , sowie ingenieurtechnische Konstruktionsprobleme, die durch aufwändige numerische Simulationen bedingt sind. ^{[ 6 ] [ 2 ]}

Frühe Bayes'sche Ansätze zur globalen Optimierung umfassen Arbeiten von Harold J. Kushner zur Lokalisierung von Extrema verrauschter Funktionen und Arbeiten von Jonas Mockus zu Bayes'schen Methoden zur Extremasuche. ^{[ 7 ] [ 8 ] [ 9 ] [ 1 ]}

Die erwartete Verbesserung ist ein wichtiges Auswahlkriterium in diesem Forschungsgebiet. 1998 führten Donald R. Jones, Matthias Schonlau und William J. Welch den effizienten globalen Optimierungsalgorithmus (EGO) ein, der ein Kriging- oder Gaußprozessmodell mit erwarteter Verbesserung für rechenintensive Black-Box-Funktionen verwendet. ^{[ 6 ]}

Spätere Arbeiten erweiterten die Bayes'sche Optimierung auf verrauschte Beobachtungen, Nebenbedingungen, Batch- und Parallelauswertungen, mehrere Zielsetzungen sowie gemischte oder hochdimensionale Suchräume. ^{[ 3 ] [ 10 ]}

In einem standardmäßigen Einzelziel-Szenario sucht die Bayes'sche Optimierung nach einem Punkt

${\displaystyle x^{\star }\in \operatorname {arg\,min} _{x\in {\mathcal {X}}}f(x)}$

Hierbei ist ein Suchraum und eine unbekannte Zielfunktion. Ein Maximierungsproblem lässt sich in derselben Form durch Minimierung von formulieren . Obwohl der Suchraum prinzipiell stetig, diskret, kategorisch oder gemischt sein kann, ist die Standardformulierung am direktesten auf stetige Bereiche niedriger bis mittlerer Dimension anwendbar. Neuere Methoden versuchen, diese Einschränkungen zu lockern, indem sie gemischte Variablen, hochdimensionale Räume, Nebenbedingungen, parallele Auswertungen und mehrere Zielfunktionen berücksichtigen. ^{[ 3 ] [ 10 ]}${\displaystyle {\mathcal {X}}}$${\displaystyle f}$${\displaystyle -f}$

Eine sinnvolle Unterscheidung besteht zwischen rauschfreier und verrauschter Optimierung. Viele reale Anwendungen beinhalten zudem Nebenbedingungen, parallele Auswertungen oder mehrere Zielsetzungen. Diese Varianten verändern die Definition des probabilistischen Modells, der aktuellen Lösung und des Sampling-Kriteriums. ^{[ 3 ] [ 10 ]}

Ein typisches Bayes'sches Optimierungsverfahren erzeugt eine Folge von Auswertungspunkten. ^{[ 3 ] [ 2 ]} Ausgehend von einem initialen Entwurf erzeugt der Algorithmus weitere Auswertungspunkte . Nach sequenziellen Auswertungen bezeichnet man die ausgewerteten Punkte und die zugehörigen Beobachtungen. Der nächste Punkt oder eine Gruppe von Punkten wird durch Optimierung eines aus dem aktuellen probabilistischen Modell berechneten Stichprobenkriteriums ausgewählt. ${\displaystyle X_{0}}$${\displaystyle x_{1},x_{2},\ldots }$${\displaystyle n}$${\displaystyle X_{n}=X_{0}\cup \{x_{1},\ldots ,x_{n}\}}$${\displaystyle {\mathcal {D}}_{n}}$${\displaystyle x_{n+1}}$

Das Verfahren hat folgende Form:

1. Wählen Sie ein erstes Design , oft durch ein raumfüllendes Design oder eine Zufallsstichprobe.${\displaystyle X_{0}}$
2. Bewerten Sie die Zielfunktion und gegebenenfalls vorhandene Nebenbedingungen an den anfänglichen Entwurfspunkten.
3. Erstellen oder aktualisieren Sie ein probabilistisches Modell anhand der beobachteten Daten .${\displaystyle {\mathcal {D}}_{n}}$
4. Definiere ein Stichprobenkriterium, auch Akquisitionsfunktion oder Auffüllkriterium genannt, aus dem probabilistischen Modell.
5. Optimieren Sie das Stichprobenkriterium, um oder eine Gruppe von Punkten zur Auswertung auszuwählen.${\displaystyle x_{n+1}}$
6. Werten Sie den oder die ausgewählten Punkte aus und aktualisieren Sie den Datensatz.
7. Wiederholen Sie den Vorgang, bis ein Bewertungsbudget, ein Konvergenzkriterium oder eine Abbruchregel erreicht ist.

Die Bayes'sche Strategie behandelt die unbekannte Zielfunktion als Zufallsfunktion und legt eine A-priori- Verteilung fest. Diese A-priori-Verteilung enthält Annahmen über das Verhalten der Funktion. Nach der Datenerfassung wird die A-priori-Verteilung aktualisiert, um eine A-posteriori-Verteilung über die Zielfunktion zu bilden. Mithilfe dieser A-posteriori-Verteilung wird dann das Stichprobenkriterium konstruiert, das den nächsten Abfragepunkt bestimmt.

Die Bayes'sche Optimierung erfordert ein probabilistisches Modell der unbekannten Zielfunktion und, falls vorhanden, der unbekannten Nebenbedingungen. Ausgehend von den bisherigen Auswertungen liefert das Modell eine Vorhersageverteilung für noch nicht ausgewertete Punkte im Suchraum. Aus dieser Vorhersageverteilung werden Stichprobenkriterien abgeleitet, sodass das Modell sowohl vorhergesagte Zielfunktionswerte als auch Unsicherheitsabschätzungen liefert. ^{[ 3 ] [ 2 ]} Solche probabilistischen Modelle werden häufig als Ersatzmodelle oder Metamodelle bezeichnet, da sie anstelle direkter Auswertungen der rechenintensiven Zielfunktion bei der Auswahl von Kandidatenpunkten verwendet werden.

Die Gaußprozessregression ist das Standardmodell in klassischen Darstellungen der Bayes'schen Optimierung und findet weiterhin gängige Anwendung. Eine Gaußprozess-Priorverteilung definiert eine Verteilung über Funktionen. Nach der Datenerfassung werden der vorhergesagte Mittelwert und die Varianz der Posteriorverteilung für Stichprobenkriterien wie erwartete Verbesserung, Wahrscheinlichkeit einer Verbesserung und obere Konfidenzgrenzen verwendet. ^{[ 6 ] [ 3 ]} Andere probabilistische Modelle können eingesetzt werden, wenn der Suchraum, die Dimensionalität oder die Datengröße eine andere Darstellung begünstigen. ^{[ 10 ] [ 2 ]}

Die Bayes'sche Optimierung wird oft anhand eines rauschfreien, einzieligen Problems beschrieben, aber der gleiche modellbasierte Ablauf wird an verschiedene verwandte Anwendungsfälle angepasst.

Bei der verrauschten Bayes'schen Optimierung liefern Auswertungen Beobachtungen wie beispielsweise Δ anstelle exakter Werte der latenten Zielfunktion. Das probabilistische Modell kann sowohl Unsicherheiten als auch Beobachtungsrauschen abbilden. Die klassische erwartete Verbesserung gegenüber dem besten beobachteten Wert ist ein rauschfreies Kriterium. In verrauschten Umgebungen können Empfehlungsregeln und Stichprobenkriterien für die latente Zielfunktion, für zukünftige verrauschte Beobachtungen oder für den Informationswert definiert werden. Beispiele hierfür sind wissensgradientenbasierte und informationstheoretische Kriterien. ^{[ 3 ] [ 11 ] [ 12 ] [ 13 ]}${\displaystyle y=f(x)+\varepsilon }$${\displaystyle f}$

Bei der eingeschränkten Bayes'schen Optimierung wird die Zielfunktion unter Berücksichtigung von Machbarkeitsbeschränkungen optimiert. Sind die Beschränkungen ebenfalls unbekannte Black-Box-Funktionen, können separate probabilistische Modelle für die Zielfunktion und die Beschränkungen erstellt werden, und das Stichprobenkriterium kann die vorhergesagte Verbesserung mit der Wahrscheinlichkeit der Machbarkeit kombinieren. ^{[ 14 ]}

Bei der Batch- oder parallelen Bayes'schen Optimierung schlägt die Methode mehrere Kandidatenpunkte vor, bevor die entsprechenden Beobachtungen vorliegen. Batch-Methoden sind nützlich, wenn Experimente, Simulationen oder Machine-Learning-Aufgaben gleichzeitig ausgeführt werden können. Sie können ein gemeinsames Stichprobenkriterium optimieren oder Punkte sequenziell auswählen und dabei ausstehende Auswertungen berücksichtigen. ^{[ 15 ]}

Bei der multikriteriellen Bayes'schen Optimierung werden mehrere Zielfunktionen gleichzeitig optimiert, wobei das Ergebnis typischerweise eine Annäherung an eine Pareto-Front darstellt . Zu den Methoden gehören Skalarisierungsverfahren wie ParEGO, die das Problem auf eine Sequenz von Teilproblemen mit jeweils einem Ziel reduzieren, sowie indikatorenbasierte Ansätze, die Kriterien wie die erwartete Hypervolumenverbesserung verwenden. ^{[ 16 ] [ 17 ]} Die eingeschränkte multikriterielle Bayes'sche Optimierung kombiniert diese Erweiterungen, indem sie Ziele und Nebenbedingungen modelliert und Stichprobenkriterien verwendet, die auf erweiterten Dominanzregeln und der erwarteten Hypervolumenverbesserung basieren. ^{[ 18 ]}

Ein Sampling-Kriterium, in der Literatur zum maschinellen Lernen auch Akquisitionsfunktion oder in der surrogatebasierten Optimierung als Infill-Kriterium bezeichnet, bewertet Kandidatenpunkte anhand der aktuellen Vorhersageverteilung. Es ist in der Regel kostengünstig zu evaluieren und wird anstelle der rechenintensiven Zielfunktion optimiert. Sampling-Kriterien drücken den Exploration-Exploitation-Kompromisse aus , indem sie Punkten mit einem niedrigen vorhergesagten Zielfunktionswert, hoher Unsicherheit oder beidem hohe Werte zuweisen. ^{[ 3 ] [ 2 ]} Ein grundlegendes Beispiel im rauschfreien Szenario ist die erwartete Verbesserung, die einen Kandidatenpunkt anhand des a posteriori erwarteten Gewinns gegenüber dem bisher besten beobachteten Wert bewertet. ^{[ 6 ] [ 3 ]} Weitere Kriterien umfassen die Wahrscheinlichkeit einer Verbesserung, ^{[ 7 ]} Kriterien mit oberer oder unterer Konfidenzgrenze wie GP-UCB, ^{[ 19 ]} Thompson-Sampling , ^{[ 20 ]} Wissensgradientenkriterien, ^{[ 11 ]} informationstheoretische Kriterien einschließlich des IAGO-Minimierer-Entropie-Kriteriums, der Entropiesuche und der prädiktiven Entropiesuche, ^{[ 12 ] [ 13 ] [ 21 ]} sowie Portfolios oder Hybride mehrerer Kriterien. ^{[ 22 ]}

Die erwartete Verbesserung (EI) wurde im effizienten globalen Optimierungsalgorithmus (EGO) verwendet und ist nach wie vor ein Standardreferenzkriterium für die rauschfreie Bayes'sche Optimierung. ^{[ 6 ]} Im Kontext der rauschfreien Minimierung sei der bisher beste beobachtete Zielfunktionswert und die Datenmenge. Die erwartete Verbesserung an einem Kandidatenpunkt ist ${\displaystyle f_{\min }}$${\displaystyle {\mathcal {D}}}$${\displaystyle x}$

${\displaystyle \operatorname {EI} (x)=\mathbb {E} [\max(f_{\min }-f(x),0)\mid {\mathcal {D}}]}$Die

Wenn die Modellvorhersageverteilung bei einer Gaußverteilung ist, und , dann hat EI die geschlossene Form ${\displaystyle x}$${\displaystyle f(x)\mid {\mathcal {D}}\sim {\mathcal {N}}(\mu (x),\sigma ^{2}(x))}$${\displaystyle \sigma (x)>0}$

${\displaystyle \operatorname {EI} (x)=(f_{\min }-\mu (x))\Phi (z)+\sigma (x)\phi (z),\quad z={\frac {f_{\min }-\mu (x)}{\sigma (x)}}}$,

Dabei sind und die kumulative Verteilungsfunktion bzw. die Wahrscheinlichkeitsdichtefunktion der Standardnormalverteilung. Der EI-Wert ist daher groß, wenn das Modell einen niedrigen Zielwert vorhersagt, wenn die Unsicherheit hoch ist oder beides zutrifft. ^{[ 3 ] [ 2 ]}${\displaystyle \Phi }$${\displaystyle \phi }$

Das Sampling-Kriterium ist im Vergleich zum Zielkriterium meist kostengünstig zu evaluieren, seine Optimierung kann jedoch ein nichtkonvexes Hilfsproblem darstellen. Sein Optimum wird häufig durch Diskretisierung, lokale Optimierung mit mehreren Startpunkten oder deterministische numerische Verfahren wie das Newton-Verfahren und Quasi-Newton-Verfahren wie den Broyden-Fletcher-Goldfarb-Shanno-Algorithmus gesucht . Auch stochastische Verfahren werden für diese Hilfssuche eingesetzt, insbesondere bei multimodalen oder gemischt-variablen Kriterien. Beispiele hierfür sind genetische Algorithmen und andere evolutionäre Algorithmen sowie sequentielle Monte-Carlo- Methoden. ^{[ 3 ] [ 2 ] [ 18 ]}

Mehrere ableitungsfreie Optimierungsverfahren verwenden Wahrscheinlichkeitsverteilungen, ohne die unbekannte Zielfunktion selbst zu modellieren. Algorithmen zur Schätzung von Verteilungen erstellen und ziehen Stichproben aus expliziten Wahrscheinlichkeitsmodellen ausgewählter Kandidatenlösungen. ^{[ 23 ]} Die Kreuzentropie-Methode und CMA-ES aktualisieren ebenfalls parametrische Stichprobenverteilungen, wobei CMA-ES den Mittelwert, die Schrittweite und die Kovarianzmatrix einer multivariaten Normalverteilung anpasst. ^{[ 24 ] [ 25 ]} Diese Methoden verwenden Zielfunktionswerte, um eine Verteilung über Kandidatenpunkte zu aktualisieren. In der Bayes'schen Optimierung repräsentiert das Wahrscheinlichkeitsmodell stattdessen die Zielfunktion oder die Nebenbedingungen, und der nächste Punkt wird durch Optimierung eines aus diesem Modell abgeleiteten Kriteriums ausgewählt.

Die sequentielle Gaußprozess-Designmethode wird auch in der Zuverlässigkeitsanalyse zur Abschätzung der Ausfallwahrscheinlichkeit eingesetzt. Für eine Grenzzustandsfunktion , einen Zufallseingang und einen Schwellenwert kann das Ziel oder allgemeiner das Maß einer Exkursionsmenge sein. Strategien zur schrittweisen Unsicherheitsreduktion wählen Auswertungen, um die Unsicherheit über diese Wahrscheinlichkeit zu verringern, anstatt den Minimierer oder Maximierer von zu finden . ^{[ 26 ]}${\displaystyle f}$${\displaystyle X}$${\displaystyle t}$${\displaystyle \mathbb {P} (f(X)\leq t)}$${\displaystyle f}$

Die Bayes'sche Optimierung ist auch mit Multi-Armed-Bandit- Problemen verwandt. Beide untersuchen sequentielle Entscheidungen, die Exploration und Exploitation gegeneinander abwägen, und Kriterien wie obere Konfidenzgrenzen und Thompson-Sampling finden in beiden Kontexten Anwendung. ^{[ 19 ] [ 20 ]} Ein wesentlicher Unterschied besteht darin, dass Bandit-Algorithmen oft so formuliert sind, dass sie das kumulative Bedauern über eine Aktionssequenz kontrollieren, während die Bayes'sche Optimierung häufig darauf abzielt, nach einem geringen Auswertungsbudget einen guten Optimierer für eine rechenintensive Funktion zu finden. ^{[ 3 ] [ 2 ]}

Bayes'sche Optimierung findet Anwendung in Bereichen, in denen objektive Auswertungen aufwändig sind. Beispiele aus Übersichtsartikeln und Lehrbüchern umfassen Hyperparameteroptimierung und Algorithmenkonfiguration, Konstruktion und simulationsbasierte Optimierung im Ingenieurwesen ^{[ 27 ]} , Robotik, Sensornetzwerke und Versuchsplanung in den Naturwissenschaften ^{[ 3 ] [ 2 ] [ 10 ] .}

• Mehrfacharmiger Bandit
• Kriging
• Thompson-Probenahme
• Globale Optimierung
• Bayes'sche Versuchsplanung
• Wahrscheinlichkeitsnumerik
• Pareto-optimal
• Aktives Lernen (maschinelles Lernen)
• Mehrzieloptimierung