📊 statistics

Taking the GP Out of the Loop

Dieser Beitrag stellt Epistemic Nearest Neighbors (ENN) vor, ein leichtgewichtiges Surrogatmodell, das Gaußsche Prozesse in der bayesschen Optimierung ersetzt, um eine lineare Skalierung von $\mathcal{O}(N)$ sowohl für die Anpassung als auch für die Akquisition zu erreichen, wodurch die Vorschlagszeit in Szenarien mit bis zu 50.000 Beobachtungen um ein bis zwei Größenordnungen reduziert wird.

Ursprüngliche Autoren: Mehul Bafna, Siddhant anand Jadhav, David Sweet

Veröffentlicht 2026-05-06

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Mehul Bafna, Siddhant anand Jadhav, David Sweet

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, das beste Rezept für einen Kuchen zu finden, haben aber kein Kochbuch. Sie müssen Kuchen backen, sie probieren und aus den Ergebnissen lernen. Genau das macht Bayessche Optimierung (BO): Es ist ein intelligenter Suchalgorithmus, der versucht, die „beste" Lösung (wie den perfekten Kuchen) zu finden, indem er verschiedene Optionen testet und aus den Ergebnissen lernt.

Das Problem: Der „langsame Koch"

In der Vergangenheit waren diese „Back"-Experimente sehr teuer und langsam (wie das Warten auf Tage für eine chemische Reaktion). Daher wurde der Algorithmus so konzipiert, dass er sehr vorsichtig war und nur wenige Kuchen backte. Er nutzte ein komplexes mathematisches Werkzeug namens Gaußscher Prozess (GP), um basierend auf den bereits gebackenen Kuchen zu erraten, wie der nächste Kuchen schmecken sollte.

Das GP-Werkzeug ist jedoch wie ein langsamer, überdenkender Koch. Jedes Mal, wenn Sie einen neuen Kuchen zur Historie hinzufügen, muss der Koch die gesamte Historie von Grund auf neu berechnen, um seine Schätzung zu aktualisieren.

Bei 10 Kuchen ist es schnell.
Bei 1.000 Kuchen dauert es lange.
Bei 50.000 Kuchen (was mit modernen schnellen Computern leicht zu bewerkstelligen ist) gerät der Koch so sehr in Berechnungen, dass der gesamte Prozess zum Stillstand kommt.

Die Arbeit bezeichnet diese Situation als BOMO (Bayessche Optimierung mit vielen Beobachtungen). Die alte Methode konnte mit der Geschwindigkeit moderner Simulationen einfach nicht Schritt halten.

Die Lösung: Die „Nachbarschaftswache"

Die Autoren, Mehul Bafna, Siddhant Anand Jadhav und David Sweet, schlagen eine neue Methode namens TuRBO-ENN vor. Anstatt den langsamen, überdenkenden GP-Koch zu verwenden, nutzen sie einen viel einfacheren, schnelleren Ansatz namens Epistemische Nächste Nachbarn (ENN).

Stellen Sie sich ENN als eine Nachbarschaftswache oder ein lokales Klatschnetzwerk vor:

Funktionsweise: Wenn Sie fragen: „Wie wird dieser neue Kuchen schmecken?", liest ENN nicht die gesamte Historie von 50.000 Kuchen neu durch. Stattdessen betrachtet es nur die K nächsten Nachbarn (die ähnlichsten Kuchen, die Sie bereits gebacken haben).
Die Mathematik: Es berechnet den durchschnittlichen Geschmack dieser wenigen Nachbarn und schätzt den neuen Geschmack. Es schätzt auch, wie unsicher es ist (Unsicherheit), basierend darauf, wie weit der neue Kuchen von diesen Nachbarn entfernt ist.
Die Geschwindigkeit: Da es nur eine kleine Handvoll Nachbarn betrachtet, ist es egal, ob Sie 10 oder 50.000 Kuchen haben. Die Zeit, die für eine Schätzung benötigt wird, bleibt ungefähr gleich. Es skaliert linear, was bedeutet, dass es selbst bei riesigen Datenmengen unglaublich schnell ist.

Die zwei Modi

Die Arbeit zeigt, dass diese neue Methode in zwei verschiedenen Szenarien funktioniert:

Lautere Welt (Realität): Manchmal liefert das Backen desselben Rezepts zweimal leicht unterschiedliche Ergebnisse (vielleicht schwankte die Ofentemperatur). In diesem Fall führt TuRBO-ENN dennoch eine schnelle Berechnung durch, um herauszufinden, wie viel „Rauschen" in den Daten steckt, und wählt dann den nächsten besten Kuchen zum Backen mit einer einfachen Formel namens UCB aus (die das Ausprobieren neuer Dinge gegen das Festhalten an funktionierenden Lösungen abwägt).
Perfekte Welt (Simulationen): Manchmal ist die Computersimulation perfekt und liefert jedes Mal exakt dasselbe Ergebnis. In diesem Fall ist TuRBO-ENN noch schneller. Es überspringt den Schritt des „Rauschens schätzen" vollständig und sortiert einfach die Optionen, um die besten zu finden, was noch mehr Zeit spart.

Die Ergebnisse

Die Autoren testeten diese neue Methode gegen den alten „langsamen Koch" (TuRBO mit GP) an verschiedenen Problemen, vom Landen eines virtuellen Raumschiffs bis hin zur Optimierung von Roboterbewegungen.

Geschwindigkeit: TuRBO-ENN war bei der Entscheidungsfindung 10- bis 100-mal schneller als die alte Methode.
Qualität: Trotz der viel höheren Geschwindigkeit und Einfachheit fand es Lösungen, die genauso gut waren wie die der langsamen, komplexen Methode.
Skalierbarkeit: Es bewältigte erfolgreich bis zu 50.000 Beobachtungen, ohne langsamer zu werden, während die alte Methode abgestürzt wäre oder Stunden benötigt hätte, nur um eine einzelne Entscheidung zu treffen.

Das Fazit

Die Arbeit sagt im Wesentlichen: „Wir haben einen Weg gefunden, die schweren, langsamen Mathematik aus dem Kreislauf zu entfernen." Indem wir ein komplexes, globales Modell durch einen einfachen, lokalen Ansatz des „Schau auf deine Nachbarn" ersetzen, können wir Dinge viel schneller optimieren, ohne an Qualität zu verlieren. Sie haben dieses Werkzeug sogar als kostenloses Softwarepaket für andere verfügbar gemacht.

Technische Zusammenfassung: Den GP aus dem Loop entfernen

Problemstellung

Die Bayessche Optimierung (BO) wird traditionell für Black-Box-Probleme eingesetzt, bei denen Funktionsauswertungen teuer sind und zu wenigen Beobachtungen ( $N$ ) führen. Eine wachsende Klasse von Problemen, bezeichnet als Bayessche Optimierung mit vielen Beobachtungen (BOMO), umfasst jedoch schnelle, parallelisierbare Auswertungen (z. B. großskalige Simulationen), bei denen $N$ Zehntausende erreichen kann.

Im BOMO-Regime stoßen Standard-BO-Methoden an eine Skalierbarkeitsgrenze. Traditionelle Ansätze verlassen sich auf Gaußsche Prozess- (GP) Surrogate. Obwohl moderne Implementierungen die Komplexität der Akquisitionszeit von $O(N^3)$ auf etwa $O(N^2)$ reduziert haben, bleibt die Notwendigkeit, GP-Hyperparameter in jedem Iterationsschritt anzupassen, eine erhebliche rechnerische Belastung. Dieser Anpassungsprozess, der oft die Rekonstruktion der Kernel-Matrix beinhaltet, skaliert schlecht mit $N$ und behindert die Anwendung von BO auf Probleme mit massiven Beobachtungszahlen.

Methodik

Die Autoren schlagen TuRBO-ENN vor, eine Methode, die den GP-Surrogat im Trust-Region-Bayesschen-Optimierungs-Rahmen (TuRBO) durch eine leichte Alternative namens Epistemische Nächste-Nachbarn (ENN) ersetzt.

1. Epistemische Nächste-Nachbarn (ENN)

ENN ist ein auf K-Nächste-Nachbarn (KNN) basierendes Surrogat, das entwickelt wurde, um sowohl Funktionswerte als auch Unsicherheit (epistemisch und aleatorisch) mit linearer Skalierung zu schätzen.

Surrogat-Konstruktion: Für einen Abfragepunkt $x$ identifiziert ENN die $K$ nächsten Nachbarn im Beobachtungssatz $D$ . Jeder Nachbar wird als unabhängige Schätzung des Funktionswerts behandelt.
Unsicherheitsquantifizierung:
- Aleatorische Varianz ( $\sigma_a^2$ ): Wird als Summe eines Basis-Rauschniveaus ( $s_0^2$ ) und der spezifischen Rauschskala der Beobachtung ( $s_m^2$ ) modelliert.
- Epistemische Varianz ( $\sigma_e^2$ ): Wird als proportional zum quadrierten euklidischen Abstand zwischen dem Abfragepunkt und dem Nachbarn ( $c_e d^2(x, x_m)$ ) modelliert.
Aggregation: Die endgültige Mittelwertschätzung $\mu(x)$ und die Varianzschätzungen werden unter Verwendung eines präzisionsgewichteten Durchschnitts (Inverse-Varianz-Gewichtung) der $K$ Nachbarn berechnet. Dies vermeidet die für GPs erforderlichen $O(N^2)$ paarweisen Kovarianzberechnungen.
Komplexität: Das Finden der $K$ nächsten Nachbarn unter Verwendung eines Max-Heaps oder der Faiss-Bibliothek erfordert $O(N \ln K)$ pro Abfrage. Die Anpassung der Hyperparameter ( $s_0, c_e$ ) erfolgt über Typ-II-Maximum-Likelihood-Schätzung (MLE) auf einer Pseudo-Wahrscheinlichkeit des Leave-One-Out-Cross-Validation (LOOCV), die unter Verwendung einer Teilstichprobe fester Größe approximiert wird, um eine $O(N)$ -Skalierung beizubehalten.

2. TuRBO-ENN-Integration

Die Methode integriert ENN in den TuRBO-Algorithmus, der eine Vertrauensregion nutzt, um Suchaufwendungen zu konzentrieren.

Verrauschte Ziele: Für Probleme mit Rauschen passt die Methode ENN-Hyperparameter an und verwendet die Upper Confidence Bound (UCB)-Akquisitionsfunktion: $UCB(x) = \mu(x) + \sigma(x)$ .
Rauschfreie Ziele: Für deterministische Probleme schlagen die Autoren eine anpassungsfreie Variante vor. Da eine Hyperparameter-Anpassung unnötig ist, wenn bekanntermaßen kein Rauschen vorliegt, wählt die Methode Kandidaten über Non-Dominated Sorting (NDS) über das Paar $(\mu(x), \sigma(x))$ aus. Dies eliminiert den Anpassungsschritt vollständig und reduziert die Vorschlagszeit weiter.
Pseudo-Bayessche Optimierung (PBO): Die Autoren verifizieren, dass TuRBO-ENN die Bedingungen für Pseudo-Bayessche Optimierung (Chen & Lam, 2025) erfüllt und somit theoretische Konvergenzgarantien sicherstellt.

Hauptbeiträge

ENN-Surrogat: Einführung eines leichten KNN-Surrogats, das Funktionswerte und Unsicherheit mit $O(N)$ Anpassungs- und Abfragezeit schätzt, im Gegensatz zur $O(N^2)$ - oder $O(N^3)$ -Skalierung von GPs.
TuRBO-ENN-Algorithmus: Entwicklung einer BO-Methode, die den GP und das Thompson-Sampling von TuRBO durch ENN und UCB (oder NDS für rauschfreie Fälle) ersetzt.
Empirische Validierung: Nachweis, dass TuRBO-ENN die Vorschlagszeit (Anpassung + Akquisition) im Vergleich zu TuRBO-GP bei Problemen mit bis zu 50.000 Beobachtungen um ein bis zwei Größenordnungen reduziert, ohne die Lösungsqualität zu beeinträchtigen.
Theoretische Garantie: Verifizierung, dass TuRBO-ENN als PBO-Methode qualifiziert ist und Konvergenzgarantien erbt.
Open Source: Veröffentlichung des Python-Pakets ennbo.

Experimentelle Ergebnisse

Die Autoren haben TuRBO-ENN gegen State-of-the-Art-Methoden (TuRBO-GP, Optuna, SMAC, CMA-ES, DNGO, Vecchia GP) an fünf Simulationstasks (LunarLander, Hopper, BipedalWalker, Push) und einer Hyperparameter-Optimierungsaufgabe (LASSO-DNA) mit Dimensionen von 12 bis 180 getestet.

Skalierung: Während GP-basierte Methoden (z. B. turbo-one, ucb) eine ungefähr $O(N^2)$ -Skalierung der Vorschlagszeit aufwiesen, skalierte TuRBO-ENN linear ( $O(N)$ ).
Beschleunigung: TuRBO-ENN erzielte Beschleunigungen von 8,5x bis 151x gegenüber TuRBO-GP, wobei größere Gewinne bei höheren Beobachtungszahlen ( $N$ ) und in eingefrorenen Rausch- (rauschfreien) Einstellungen beobachtet wurden, bei denen die Hyperparameter-Anpassung weggelassen wurde.
Lösungsqualität: TuRBO-ENN entsprach in allen getesteten Aufgaben der Optimierungsleistung (Lösungsqualität) von TuRBO-GP.
Anpassungsaufgaben: Bei reinen Regressionsaufgaben (synthetische Daten) war ENN um Größenordnungen schneller anzupassen als exakte GPs, SVGP und neuronale Netzwerk-Surrogate, während gleichzeitig wettbewerbsfähige Log-Wahrscheinlichkeiten auf Testsets erhalten blieben.

Bedeutung und Behauptungen

Die Arbeit argumentiert, dass mit dem Wachstum der Simulationsfähigkeiten die Engstelle in der Bayesschen Optimierung von den Kosten der Funktionsauswertung zu den rechnerischen Kosten des Optimierungsalgorithmus selbst (Vorschlagszeit) verschoben wird. Durch das Entfernen des Gaußschen Prozesses aus dem Loop ermöglicht TuRBO-ENN eine Skalierung der BO auf Regime mit Zehntausenden von Beobachtungen, in denen traditionelle Methoden rechnerisch untragbar werden.

Die Autoren behaupten bescheiden, dass ihre Methode eine praktische, skalierbare Alternative für BOMO-Probleme bietet, die eine „anpassungsfreie" Option für deterministische Simulationen und eine linear skalierende Option für verrauschte bietet, während gleichzeitig die theoretischen Konvergenzeigenschaften der Bayesschen Optimierung erhalten bleiben. Sie weisen darauf hin, dass sie zwar Konvergenzgarantien über PBO-Axiome erreichen, aber keine spezifischen Regret-Schranken bereitstellen. Als zukünftige Arbeitsrichtungen werden die Anpassung von ENN an Approximate-Nearest-Neighbor-Algorithmen für eine $O(\ln N)$ -Skalierung und die Erforschung dimensionspezifischer Gewichtung im Distanzmetrik vorgeschlagen.