📊 statistics

Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces

Dieser Beitrag stellt BAxUS vor, eine adaptive Methode zur bayesschen Optimierung, die verschachtelte zufällige Teilräume nutzt, um hochdimensionale Probleme effektiv zu behandeln, und die im Vergleich zu bestehenden State-of-the-Art-Methoden sowohl theoretische Garantien als auch überlegene empirische Leistung bietet.

Ursprüngliche Autoren: Leonard Papenmeier, Luigi Nardi, Matthias Poloczek

Veröffentlicht 2026-05-15

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Leonard Papenmeier, Luigi Nardi, Matthias Poloczek

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 absolut beste Rezept für einen Kuchen zu finden. Doch es gibt einen Haken: Sie können den Kuchen erst probieren, wenn er vollständig gebacken ist, und das Backen eines Kuchens dauert einen ganzen Tag. Sie haben nur genügend Zutaten und Zeit, um etwa 1.000 Kuchen zu backen, bevor Ihnen das Geld ausgeht.

Stellen Sie sich nun vor, dieses Rezept umfasst hunderte Zutaten (Variablen): Mehlsorte, Zuckermenge, Ofentemperatur, Rührgeschwindigkeit, Luftfeuchtigkeit usw. Das ist es, was Informatiker als hochdimensionales Problem bezeichnen.

Das Problem: Sich in der „Küche" verirren

Traditionelle Methoden zur Suche nach dem besten Rezept (genannt Bayessche Optimierung) funktionieren hervorragend, wenn Sie nur wenige Zutaten haben. Doch wenn Sie hunderte haben, beginnen sie zu versagen. Es ist, als würde man versuchen, ein bestimmtes Sandkorn an einem Strand zu finden, der jedes Mal größer wird, wenn man ihn betrachtet.

Einige bestehende Methoden versuchen, dieses Problem zu lösen, indem sie davon ausgehen, dass das Rezept wirklich nur von wenigen „geheimen" Zutaten abhängt (wie nur Zucker und Mehl). Sie raten, welche das sind, und ignorieren den Rest.

Das Risiko: Wenn sie falsch raten, verpassen sie den besten Kuchen vollständig.
Das Ratespiel: Sie zwingen Sie zudem, zu raten, wie viele geheime Zutaten es gibt. Wenn Sie zu niedrig raten, verpassen Sie den Geschmack. Wenn Sie zu hoch raten, verschwenden Sie Zeit mit dem Backen nutzloser Kuchen.

Die Lösung: BAXUS (Die „wachsende Karte"-Strategie)

Die Autoren dieses Papiers schlagen eine neue Methode namens BAXUS vor. Anstatt die Anzahl der wichtigen Zutaten zu raten oder an einer kleinen, festen Karte festzuhalten, verwendet BAXUS eine clevere Strategie: Klein beginnen, dann wachsen.

So funktioniert es, unter Verwendung einer kreativen Analogie:

1. Die verschachtelten Teilräume (Die russischen Puppen)

Stellen Sie sich eine Reihe von russischen Matroschka-Puppen vor.

Die kleine Puppe: Sie beginnen damit, in einer winzigen Küche mit nur zwei Arbeitsflächen zu backen. Sie können immer nur zwei Zutaten gleichzeitig mischen. Das ist schnell und einfach. Sie finden schnell einen „hinreichend guten" Kuchen innerhalb dieses winzigen Raums.
Die wachsenden Puppen: Während Sie mehr lernen, bleibt BAXUS nicht einfach in der winzigen Küche. Es öffnet sanft die nächste Schicht der Puppe. Plötzlich haben Sie 4 Arbeitsflächen. Dann 8. Dann 16.
Die Magie: Wenn sich die Küche erweitert, wirft BAXUS nicht alle bereits gebackenen Kuchen weg. Es behält sie! Es nimmt die Kuchen, die Sie in der 2-Arbeitsflächen-Küche gebacken haben, und überträgt sie auf die neue 4-Arbeitsflächen-Küche. Sie verlieren Ihren Fortschritt nicht; Sie erhalten lediglich mehr Raum zur Exploration.

2. Der „Aufteilungs"-Trick

Wie erweitert es sich, ohne Daten zu verlieren?
Stellen Sie sich vor, Ihre aktuelle Küche hat eine große Arbeitsfläche, auf der Sie Mehl und Zucker zusammen mischen. Sie merken, dass Sie sie trennen müssen, um einen besseren Kuchen zu erhalten.

Die Aufteilung: BAXUS nimmt diese eine Arbeitsfläche und teilt sie in zwei neue Arbeitsflächen auf.
Die Kopie: Es nimmt exakt dieselbe Mischung, die Sie vorher hatten, und platziert sie auf beiden neuen Arbeitsflächen.
Das Ergebnis: Sie haben nun zwei separate Orte, um Mehl und Zucker unabhängig voneinander zu justieren, aber Sie haben die Daten Ihrer vorherigen Versuche nicht verloren. Sie haben sich lediglich mehr „Freiheitsgrade" gegeben, um eine bessere Lösung zu finden.

3. Das Sicherheitsnetz (Vertrauensbereiche)

Um sicherzustellen, dass es nicht überwältigt wird, wenn die Küche riesig wird, verwendet BAXUS einen „Vertrauensbereich". Denken Sie daran wie an einen Zaun.

Anstatt die gesamte riesige Küche auf einmal zu betrachten, betrachtet der Roboter-Koch nur einen kleinen, eingezäunten Bereich um den bisher besten Kuchen herum.
Wenn der Koch einen besseren Kuchen findet, erweitert sich der Zaun, um den neuen Bereich einzuschließen.
Wenn der Koch weiterhin versagt, einen besseren Kuchen zu finden, verkleinert sich der Zaun, um sich intensiv auf diesen spezifischen Punkt zu konzentrieren.
Dies verhindert, dass sich der Koch in der Weite der 1.000-Zutaten-Küche verirrt.

Warum ist das besser?

Das Papier behauptet, BAXUS sei überlegen, weil:

Kein Raten: Sie müssen dem Computer nicht sagen, wie viele „geheime Zutaten" existieren. Es ermittelt dies, indem es den Raum nur so schnell vergrößert, wie es nötig ist.
Sicherheit: Es garantiert, dass die Methode auch bei riesigen Problemen nicht einfach „versagt", weil sie die falsche Startgröße geraten hat. Sie passt sich an.
Effizienz: Sie erzielt die besten Ergebnisse bei einer Vielzahl von Tests (vom Autodesign bis zur Optimierung chemischer Reaktionen) im Vergleich zu den derzeit besten Methoden.

Das Fazit

Denken Sie an BAXUS als an einen klugen Entdecker, der damit beginnt, ein kleines Dorf zu kartieren. Während er das Gelände lernt, hört er nicht einfach auf; er erweitert seine Karte allmählich, um das ganze Land abzudecken, und trägt dabei seine alten Notizen mit sich. Er wird nie von der Größe des Landes überwältigt, weil er sich immer auf den Bereich direkt um die Stelle konzentriert, an der er bisher den besten Schatz gefunden hat.

Dies ermöglicht es ihm, komplexe, hochdimensionale Rätsel zu lösen, bei denen andere Methoden entweder aufgeben oder stecken bleiben, während sie raten.

Technische Zusammenfassung: BAXUS – Adaptive Bayessche Optimierung in verschachtelten Teilräumen

Problemstellung

Die hochdimensionale Bayessche Optimierung (HDBO) zielt darauf ab, teure zu evaluierende Black-Box-Funktionen mit Dutzenden bis Hunderten von Eingangsdimensionen zu optimieren. Während jüngste Fortschritte den Anwendungsbereich der Bayesschen Optimierung (BO) auf Bereiche wie Lebenswissenschaften, Suche nach neuronalen Architekturen und Robotik erweitert haben, stoßen die fortschrittlichsten Methoden bei steigender Dimensionalität an erhebliche Grenzen.

Bestehende Ansätze lassen sich im Allgemeinen in zwei Kategorien einteilen, die beide kritische Nachteile aufweisen:

Vertrauensbereichsmethoden (z. B. TURBO): Diese optimieren über lokale, begrenzte Bereiche (Vertrauensbereiche) innerhalb des gesamten Eingangsraums. Obwohl sie für moderate Dimensionen effektiv sind, verschlechtert sich ihre Leistung bei sehr hohen Dimensionen, da die Vertrauensbereiche die volle Dimensionalität des Problems beibehalten und somit unter dem Fluch der Dimensionalität leiden.
Methoden zur linearen Einbettung (z. B. REMBO, HESBO, ALEBO): Diese gehen von der Existenz eines niedrigdimensionalen „aktiven Teilraums" aus und projizieren den hochdimensionalen Eingangsraum in einen niedrigdimensionalen Zielraum. Diese Methoden erfordern jedoch, dass der Benutzer die effektive Dimensionalität ( $d_e$ ) des aktiven Teilraums „rät". Ist die gewählte Zieldimensionalität ( $d$ ) zu klein, kann der Teilraum das globale Optimum nicht repräsentieren; ist $d$ zu groß, verlangsamt sich die Optimierung aufgrund des Fluchs der Dimensionalität. Darüber hinaus verlassen sich Methoden wie HESBO auf zufälliges Hashing, das im Vergleich zu anderen Einbettungen geringere Worst-Case-Garantien für die Enthaltung eines Optimums bietet.

Die Kernherausforderung besteht darin, eine HDBO-Methode zu entwickeln, die globale Optima zuverlässig findet, ohne dass Vorwissen über die Dimensionalität des aktiven Teilraums erforderlich ist, und dabei die mit hochdimensionalen Suchräumen verbundene Leistungsverschlechterung vermeidet.

Methodik: BAXUS

Die Autoren schlagen BAXUS (Bayesian optimization with adaptively expanding subspaces) vor, einen theoretisch fundierten Ansatz, der die Dimensionalität des Optimierungsraums dynamisch anpasst.

1. Adaptive verschachtelte Teilräume

Anstatt die Zieldimensionalität festzulegen, arbeitet BAXUS mit einer Familie von verschachtelten zufälligen Teilräumen. Der Algorithmus beginnt mit einem niedrigdimensionalen Zielraum ( $d_{init}$ ) und erhöht die Dimensionalität schrittweise, während mehr Daten gesammelt werden.

Initialisierung: BAXUS startet mit einer kleinen Zieldimension $d_0$ .
Expansion: Im Verlauf der Optimierung wird die Zieldimensionalität durch „Aufspalten" bestehender Zieldimensionen erhöht. Dieser Prozess setzt sich fort, bis die Zieldimensionalität die Eingangsdimensionalität $D$ ungefähr erreicht oder das Evaluierungsbudget erschöpft ist.
Beibehaltung von Beobachtungen: Ein entscheidendes Merkmal von BAXUS ist die Fähigkeit, Beobachtungen aus niedrigdimensionalen Räumen beim Übergang zu höherdimensionalen Räumen beizubehalten. Wenn eine Zieldimension aufgespalten wird, werden die beitragenden Eingangsdimensionen der ursprünglichen Dimension und neuen Bins neu zugewiesen. Die Funktionswerte (Beobachtungen) werden in die neuen Dimensionen kopiert, wodurch sichergestellt wird, dass in der niedrigdimensionalen Phase gesammelte Daten in der höherdimensionalen Phase gültig bleiben.

2. Die sparse BAXUS-Einbettung

BAXUS nutzt eine neuartige sparse lineare Einbettung, um den Zielraum $Y \in \mathbb{R}^d$ auf den Eingangsraum $X \in \mathbb{R}^D$ abzubilden.

Struktur: Die Einbettungsmatrix $S^\top \in \{0, \pm 1\}^{d \times D}$ ist sparse, was bedeutet, dass jede Spalte (Eingangsdimension) genau einen von Null verschiedenen Eintrag hat.
Bin-Ausgleich: Im Gegensatz zu HESBO, das Eingangsdimensionen gleichmäßig zufällig Zieldimensionen zuweist (was zu variablen Bin-Größen führt), erzwingt BAXUS, dass sich die Anzahl der beitragenden Eingangsdimensionen pro Zieldimension (Bin-Größe) höchstens um eins unterscheidet. Diese „ausgeglichene" Zuweisung wird erreicht, indem Eingangsdimensionen permutiert und in $d$ Bins aufgeteilt werden.
Theoretischer Vorteil: Die Autoren beweisen, dass diese ausgeglichene sparse Einbettung eine strikt höhere Worst-Case-Erfolgswahrscheinlichkeit (die Wahrscheinlichkeit, dass der Zielraum ein globales Optimum enthält) bietet als die HESBO-Einbettung für endliche Eingangsdimensionen. Wenn $D \to \infty$ , konvergiert die Erfolgswahrscheinlichkeit von BAXUS zu der von HESBO.

3. Vertrauensbereich und Aufspaltungsstrategie

BAXUS integriert die Erweiterung der Einbettung mit einem Vertrauensbereichs-Ansatz (Trust Region, TR), der TURBO ähnelt:

Vertrauensbereiche: Die Optimierung erfolgt innerhalb hyperrechteckiger Vertrauensbereiche im Zielraum, skaliert durch GP-Längenskalen.
Auslöser für Expansion: Die Zieldimensionalität wird erhöht, wenn die Basisseitenlänge des Vertrauensbereichs unter einen Mindestschwellenwert fällt (was darauf hindeutet, dass der aktuelle Bereich zu klein ist oder der Algorithmus feststeckt).
Fehlerkontrolle: Die Anzahl der zulässigen „Fehler" (aufeinanderfolgende Iterationen ohne Verbesserung), bevor eine Aufspaltung erfolgt, wird basierend auf der aktuellen Zieldimensionalität herabgesetzt. Dies stellt sicher, dass der Algorithmus innerhalb eines festen Evaluierungsbudgets hohe Dimensionen erreichen kann.
Konvergenz: Es wird bewiesen, dass der Algorithmus eine globale Konvergenz erreicht. Sobald die Zieldimensionalität die Eingangsdimensionalität $D$ erreicht, verhält sich BAXUS wie TURBO, von dem bekannt ist, dass es global konvergiert.

Hauptbeiträge

Algorithmenentwicklung: Die Autoren stellen BAXUS vor, das auf einer breiten Palette hochdimensionaler Aufgaben zuverlässig hervorragende Lösungen erzielt und dabei aktuelle fortschrittlichste Methoden übertrifft.
Neue Einbettungstheorie: Sie präsentieren eine neue Familie von verschachtelten zufälligen Einbettungen mit drei Schlüsseleigenschaften:
- Sie bietet eine größere Worst-Case-Garantie für die Enthaltung eines globalen Optimums im Vergleich zur HESBO-Einbettung.
- Sie ist eine optimale sparse Einbettung, was bedeutet, dass keine andere sparse Einbettung für dieselben Eingangs-, Ziel- und effektiven Dimensionen eine höhere Worst-Case-Erfolgswahrscheinlichkeit aufweist.
- Ihre Wahrscheinlichkeit, ein Optimum zu enthalten, konvergiert gegen die HESBO-Wahrscheinlichkeit, wenn die Eingangsdimensionalität $D \to \infty$ .
Umfassende Evaluierung: Die Arbeit liefert umfangreiche empirische Belege, die die Überlegenheit von BAXUS gegenüber TURBO, SAASBO, ALEBO, HESBO, CMA-ES und zufälliger Suche über diverse Benchmarks hinweg belegen.

Experimentelle Ergebnisse

Die Autoren evaluierten BAXUS an einer Sammlung von 388-dimensionalen Hyperparameter-Optimierungsaufgaben, 124-dimensionalen Designproblemen und Benchmarks mit bekannten aktiven Teilräumen (LASSO, MOPTA08, BRANIN, HARTMANN).

Leistung: BAXUS übertraf konsistent fortschrittlichste Methoden. Beim 388D-SVM-Benchmark passte sich BAXUS der geeigneten Zieldimensionalität an und fand schneller bessere Lösungen als TURBO und CMA-ES. Beim 1000D-LASSO-HARD-Benchmark erzielte BAXUS deutlich bessere Lösungen als alle Konkurrenten, einschließlich Methoden, die auf Annahmen über aktive Teilräume basieren (SAASBO, ALEBO, HESBO), die es versäumten, von der Struktur des aktiven Teilraums zu profitieren.
Robustheit: BAXUS zeigte Robustheit gegenüber Beobachtungsrauschen und behielt eine starke Leistung bei verrauschten Varianten von Benchmarks bei, bei denen Konkurrenten wie SAASBO und CMA-ES signifikant nachließen.
Ablationsstudien: Der Ersatz der BAXUS-Einbettung durch eine verschachtelte HESBO-Einbettung führte zu deutlich schlechterer Leistung, was bestätigt, dass die ausgeglichene Binning-Strategie ein Schlüsselfaktor für den Erfolg ist.
Vergleich mit festen Einbettungen: BAXUS übertraf die Ausführung von TURBO mit einer festen Zieldimensionalität, was zeigt, dass die adaptive Expansionsstrategie überlegener ist als statische Wahl von $d$ .

Bedeutung und Behauptungen

Die Arbeit behauptet, dass BAXUS die kritischen Grenzen aktueller HDBO-Methoden adressiert, indem es die Notwendigkeit beseitigt, dass Praktiker die effektive Dimensionalität des Problems „raten" müssen. Durch die adaptive Erweiterung des Suchraums nutzt BAXUS die Effizienz der niedrigdimensionalen Optimierung, garantiert jedoch gleichzeitig, dass der Suchraum schließlich den gesamten Eingangsraum abdeckt, wodurch sichergestellt wird, dass das globale Optimum erreichbar ist.

Die Autoren behaupten, dass BAXUS ein „gebrauchsfertiger" (out-of-the-box) Optimierer ist, der robuste Leistung über eine breite Palette hochdimensionaler Aufgaben hinweg erzielt, ohne spezifische Annahmen über die Problemstruktur (wie achsenparallele aktive Teilräume) zu erfordern. Die Arbeit zielt darauf ab, die hochdimensionale Bayessche Optimierung für Anwendungen in Wissenschaft und Industrie zugänglicher und zuverlässiger zu machen, wo die Anzahl der justierbaren Parameter groß ist und ihre effektive Dimensionalität unbekannt ist.