🤖 machine learning

Discount Model Search for Quality Diversity Optimization in High-Dimensional Measure Spaces

Dieser Beitrag stellt Discount Model Search (DMS) vor, einen neuartigen Optimierungsalgorithmus für Qualitätsvielfalt, der diskrete histogrammbasierte Diskontierung durch ein kontinuierliches Modell ersetzt, um Stagnation in hochdimensionalen Messräumen zu überwinden und eine effektive Exploration sowie überlegene Leistung in Benchmarks, einschließlich bildbasierter Domänen, zu ermöglichen.

Ursprüngliche Autoren: Bryon Tjanaka, Henry Chen, Matthew C. Fontaine, Stefanos Nikolaidis

Veröffentlicht 2026-05-04

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Bryon Tjanaka, Henry Chen, Matthew C. Fontaine, Stefanos Nikolaidis

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 sind ein Kunstkurator, der versucht, eine riesige Galerie mit Fotos von Wanderern zu füllen. Ihr Ziel ist es nicht, nur ein perfektes Foto zu finden; Sie möchten eine ganze Sammlung, die sowohl hochwertig (großartige Fotos) als auch vielfältig (Wanderer in jeder möglichen Umgebung: verschneite Berge, sonnige Strände, regnerische Wälder) ist.

Dies ist die Herausforderung der Qualitätsvielfalt-Optimierung (Quality Diversity, QD).

Das Problem: Der Effekt des „überfüllten Raums"

In der Vergangenheit versuchten Computer, dies zu lösen, indem sie die Galerie in winzige, feste Boxen (wie ein Gitter) unterteilten. Wenn ein Foto eines Wanderers in einer „verschneiten Berg"-Umgebung in eine Box fiel, markierte der Computer diese Box als „gefüllt".

Wenn die Umgebungen jedoch komplexer werden (wie beim Versuch, jede spezifische Art von Landschaft zu erfassen), werden die „Boxen" riesig. Plötzlich fallen ein Foto eines Wanderers in den Alpen und ein Foto eines Wanderers in den Rocky Mountains in dieselbe riesige Box. Der Computer denkt: „Oh, diese Box ist bereits voll", und hört auf, nach neuen, einzigartigen Wanderern zu suchen. Er bleibt in einer Sackgasse stecken und glaubt, alles gefunden zu haben, obwohl dies nicht der Fall ist. Dies wird als Verzerrung bezeichnet.

Die alte Lösung: Die „Rabattliste"

Die beste vorherige Methode (CMA-MAE) führte eine Liste von „Rabatten" für jede Box. Wenn eine Box leer war, war der Rabatt hoch (was den Computer ermutigte, sie zu füllen). Wenn eine Box voll war, war der Rabatt niedrig.

Der Fehler: Da die Boxen so groß waren, fielen viele verschiedene Wanderer in dieselbe Box. Alle erhielten denselben „Rabatt"-Score. Der Computer konnte keinen Unterschied zwischen einem Wanderer in den Alpen und einem Wanderer in den Rocky Mountains erkennen und hörte daher auf, nach neuen zu suchen.

Die neue Lösung: Discount Model Search (DMS)

Die Autoren schlagen eine neue Methode namens Discount Model Search (DMS) vor. Anstatt eine starre Liste von Boxen und festen Rabatten zu verwenden, nutzt DMS eine intelligente, glatte Karte (ein neuronales Netzwerk).

Stellen Sie es sich so vor:

Alter Weg: Eine Karte mit großen, blockartigen Zonen. Wenn Sie sich in Zone A befinden, erhalten Sie einen flachen „5 Punkte"-Score. Es spielt keine Rolle, ob Sie am nördlichen oder südlichen Rand von Zone A sind; Sie erhalten denselben Score.
Neuer Weg (DMS): Eine glatte, wellige Landschaft. Selbst wenn zwei Wanderer sehr nahe beieinander sind, kann die Karte ihnen basierend auf ihrem genauen Standort leicht unterschiedliche Scores geben. Dies ermöglicht es dem Computer, winzige Unterschiede zu erkennen und weiterhin nach neuen Wanderern zu suchen, selbst in Bereichen, die überfüllt wirken.

Der große Sprung: „Maße als Datensätze"

Die Arbeit führt eine neue Möglichkeit ein, dem Computer mitzuteilen, wie „Vielfalt" aussieht. Normalerweise müssen Sie eine komplexe Formel schreiben, um das Alter, die Kleidung oder das Wetter eines Wanderers zu beschreiben. Das ist schwierig und mühsam.

Mit DMS können Sie dem Computer einfach einen Datensatz mit Bildern zeigen.

Die Analogie: Anstatt ein Rezept für „einen Wanderer im Wald" zu schreiben, übergeben Sie dem Computer einfach ein Fotoalbum von Wäldern. Der Computer versucht dann, Wanderer zu generieren, die in diese spezifischen Fotos passen.
Das Ergebnis: Der Computer generierte erfolgreich Wanderer mit dicken Jacken für verschneite Berge und leichten Kleidern für sonnige Strände, einfach weil Sie ihm Bilder dieser Landschaften gezeigt hatten.

Was haben sie herausgefunden?

Die Autoren testeten diese neue Methode auf zwei Arten gegen die alten:

Standardtests: Bei mathematischen Problemen, bei denen bekannt ist, dass der Effekt des „überfüllten Raums" auftritt, fand DMS mehr einzigartige Lösungen und hochwertigere Ergebnisse als die alten Methoden.
Bildtests: Im neuen „Datensatz"-Setup konnte DMS vielfältige Bilder von Wanderern in verschiedenen Landschaften erstellen, wo andere Methoden versagten oder stecken blieben.

Der Kompromiss

Es gibt einen kleinen Preis: DMS benötigt etwas mehr Rechenleistung, da es die glatte Karte während der Suche „lernen" muss. Die Arbeit zeigt jedoch, dass sich dieser zusätzliche Aufwand dadurch lohnt, dass Lösungen gefunden werden, die andere Methoden völlig verpassen, insbesondere in komplexen, hochdimensionalen Räumen.

Kurz gesagt: DMS ersetzt eine starre, blockartige Checkliste durch eine glatte, intelligente Karte und ermöglicht es Computern, eine viel reichhaltigere und vielfältigere Sammlung von Lösungen zu finden, selbst wenn der Suchraum unglaublich komplex ist.

Technische Zusammenfassung: Discount Model Search zur Optimierung von Qualitätsvielfalt in hochdimensionalen Maßräumen

Problemdefinition

Die Optimierung von Qualitätsvielfalt (Quality Diversity, QD) zielt darauf ab, eine Sammlung von Lösungen zu entdecken, die eine Zielfunktion $f$ maximieren und gleichzeitig eine vielfältige Palette von Ausgaben abdecken, die durch eine vom Benutzer spezifizierte, vektorwertige Maßfunktion $m$ definiert sind. Das Bild von $m$ bildet den Maßraum $S$ . Eine kritische Einschränkung bei aktuellen QD-Algorithmen, insbesondere bei State-of-the-Art-Methoden wie Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), ist ihre Unfähigkeit, sich effektiv auf hochdimensionale Maßräume zu skalieren.

In hochdimensionalen Räumen leiden Algorithmen unter Verzerrung (distortion), einem Phänomen, bei dem große Volumina des Lösungsraums auf kleine Regionen des Maßraums abgebildet werden. CMA-MAE adressiert das QD-Ziel durch die Maximierung der „Archivverbesserung", definiert als $\Delta(\theta) = f(\theta) - f_A(m(\theta))$ , wobei $f_A$ eine Diskontierungsfunktion ist. CMA-MAE stellt $f_A$ als diskretes Histogramm (eine Tessellation aus Zellen) dar. In hochdimensionalen Settings führt Verzerrung dazu, dass viele unterschiedliche Lösungen in dieselbe Histogrammzelle fallen und ihnen identische Diskontierungswerte zugewiesen werden. Folglich kann der Algorithmus zwischen Lösungen mit ähnlichen Maßen nicht unterscheiden, was zu ungenauen Verbesserungssignalen und einer Stagnation der Suche führt. Darüber hinaus ist das Entwerfen niedrigdimensionaler Maßfunktionen für komplexe Domänen (z. B. die Spezifikation „wo sich ein Wanderer befindet") oft mühsam und unintuitiv.

Methodik: Discount Model Search (DMS)

Um diese Einschränkungen zu adressieren, schlagen die Autoren Discount Model Search (DMS) vor. Anstelle eines diskreten Histogramms verwendet DMS ein neuronales Netzwerk, um eine glatte, kontinuierliche Darstellung der Diskontierungsfunktion $f_A$ zu erlernen.

Kernkomponenten

Diskontierungsmodell ( $\hat{f}_A$ ): Ein neuronales Netzwerk, parametrisiert durch $\psi$ , das Maßwerte $s = m(\theta)$ als Eingabe erhält und einen skalaren Diskontierungswert ausgibt. Die Architektur ist flexibel: Multi-Layer Perceptrons (MLPs) werden für niedrigdimensionale vektorielle Maße verwendet, während Convolutional Networks oder Transformer für hochdimensionale Daten wie Bilder geeignet sind.
Archiv und Emittenten: DMS verwaltet ein im MAP-Elites-Stil gehaltenes Archiv, das die besten gefundenen Lösungen speichert. Es nutzt CMA-ES-basierte Emittenten, die Lösungen aus einer Gaußverteilung sampeln. Im Gegensatz zu CMA-MAE speichert das Archiv keine diskreten Diskontierungswerte; stattdessen wird das Diskontierungsmodell abgefragt, um Verbesserungswerte zu berechnen: $\Delta_i = f(\theta_i) - \hat{f}_A(m(\theta_i))$ .
Training des Diskontierungsmodells: Das Modell wird trainiert, um die in CMA-MAE verwendete Schwellenwert-Aktualisierungsregel zu approximieren. Der Trainingsdatensatz $D_A$ $D_{A}$ besteht aus zwei Quellen:
- Emittenten-Samples: Für jede gesampelte Lösung $\theta$ wird der Ziel-Diskontierungswert $t_A$ aktualisiert, basierend darauf, ob der Zielwert der Lösung $f(\theta)$ die aktuelle Vorhersage des Modells $\hat{f}_A(s)$ übersteigt. Wenn $f(\theta) > \hat{f}_A(s)$ , ist das Ziel eine lineare Kombination aus dem Zielwert und dem aktuellen Diskontierungswert, gesteuert durch eine Archiv-Lernrate $\alpha$ .
- Leere Punkte: Um zu verhindern, dass das Modell willkürlich hohe Werte für unerforschte Regionen des Maßraums zuweist, sampelt der Algorithmus die Zentren unbesetzter Archivzellen und weist ihnen einen Zielwert von $f_{min}$ (dem minimalen Zielwert) zu. Dies „drückt" das Modell in unerforschten Bereichen herunter und stellt sicher, dass die Emittenten zur Exploration neuer Regionen geleitet werden.

Theoretische Einsicht

Durch den Ersatz des diskreten Histogramms durch eine kontinuierliche Funktion kann DMS auch dann unterschiedliche Diskontierungswerte für Lösungen zuweisen, wenn diese in einem hochdimensionalen Raum auf ähnliche Maße abgebildet werden. Dies ermöglicht dem Algorithmus, einen Gradienten von Verbesserungssignalen aufrechtzuerhalten, verhindert Stagnation und ermöglicht eine fortgesetzte Exploration lange nachdem histogrammbasierte Methoden versagt hätten.

Hauptbeiträge

Discount Model Search (DMS): Ein neuartiger QD-Algorithmus, der ein glattes, kontinuierliches Diskontierungsmodell verwendet, um die Exploration in verzerrten, hochdimensionalen Maßräumen zu steuern.
Qualitätsvielfalt mit Datensätzen von Maßen (QDDM): Die Autoren führen ein neues Setting ein, in dem Benutzer gewünschte Maße über einen Datensatz (z. B. eine Sammlung von Bildern) spezifizieren, anstatt eine Maßfunktion von Hand zu entwerfen. Dies behandelt den hochdimensionalen Raum des Datensatzes (z. B. den Raum der Bilder) als Maßraum.
Neue Domänen: Zwei QDDM-Domänen werden vorgeschlagen und evaluiert:
- Dreiecksanordnung (Triangle Arrangement, TA): Anordnung von Dreiecken, um Bilder aus MNIST oder Fashion MNIST zu matchen.
- Latent Space Illumination (LSI) (Hiker): Generierung von Gesichtsimages von Wanderern in vielfältigen Landschaften unter Verwendung von StyleGAN3, wobei der Maßraum der Raum der Landschaftsbilder ist.
Empirische Validierung: Umfassende Benchmarks zeigen, dass DMS CMA-MAE, DDS und MAP-Elites-Varianten sowohl auf Standard-Benchmarks als auch auf den neuen QDDM-Domänen übertrifft.

Experimentelle Ergebnisse

Die Autoren evaluierten DMS auf 9 Standard-Benchmarks (einschließlich Linear Projection und Arm Repertoire) und 3 QDDM-Domänen.

Benchmark-Domänen: DMS übertraf in den meisten hochdimensionalen Settings (z. B. 10D, 20D, 50D LP-Benchmarks) alle Baselines signifikant beim QD-Score (Summe der Zielwerte im Archiv) und der Abdeckung (Prozentsatz der gefüllten Archivzellen). Bemerkenswert ist, dass bei dem 10D LP (Sphere)-Benchmark die Abdeckung von CMA-MAE auf 6,95 % sank, während DMS 89,21 % erreichte.
QDDM-Domänen:
- In TA (F-MNIST) übertraf DMS alle Baselines in beiden Metriken signifikant.
- In TA (MNIST) entsprach DMS CMA-MAE in der Abdeckung, übertraf MAP-Elites-Varianten jedoch signifikant beim QD-Score. Die Autoren stellen fest, dass DMS CMA-MAE hier beim QD-Score nicht signifikant übertraf, und spekulieren, dass das durch die neuronale Netzwerk-Approximation eingeführte Rauschen die feingranulare Zieloptimierung bei Aufgaben mit geringer Verzerrung und hoher Präzision behindern könnte.
- In LSI (Hiker) übertraf DMS CMA-MAE signifikant und erreichte einen QD-Score von 214,91 im Vergleich zu 14,61 sowie eine Abdeckung von 3,77 % (377 eindeutige Wanderer-Bilder). Die Autoren stellen fest, dass MAP-Elites-Varianten eine hohe Abdeckung erreichten, jedoch mit stark negativen QD-Scores aufgrund der Generierung von Bildern außerhalb der Trainingsverteilung des Generators.
Rechenkosten: DMS verursacht aufgrund des Trainings des Diskontierungsmodells höhere Rechenkosten als CMA-MAE, insbesondere bei niedrigdimensionalen Benchmarks. In QDDM-Domänen, bei denen die Bildgenerierung der Engpass ist, ist dieser Overhead jedoch weniger spürbar.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass DMS zwei primäre Vorteile bietet:

Verbesserte Leistung: DMS verbessert die Leistung in aktuellen QD-Anwendungen, indem es die Verzerrungseffekte überwindet, die hochdimensionale Maßräume plagen, und State-of-the-Art-Blackbox-Algorithmen übertrifft.
Zugänglichkeit und neue Anwendungen: Durch die Einführung des QDDM-Settings macht DMS QD zugänglicher. Es nimmt die Notwendigkeit manueller, von Hand entworfener Maßfunktionen ab und ermöglicht es Benutzern, Diversitätsziele einfach durch Bereitstellung eines Datensatzes zu spezifizieren. Dies ermöglicht die Spezifikation komplexer, hochdimensionaler Maße (wie visuelle Stile oder semantische Standorte), die sich schwer durch niedrigdimensionale Vektoren darstellen lassen.

Die Autoren schließen, dass angesichts der Allgegenwart von Datensätzen im maschinellen Lernen die Formulierung von Problemen als QDDM und deren Lösung mit DMS eine vielversprechende Richtung ist. Sie räumen Einschränkungen ein, darunter den Rechenaufwand für das Training des Modells und die potenzielle Beeinträchtigung der Feinoptimierung durch Approximationsrauschen, und schlagen zukünftige Arbeiten zu fortschrittlicheren Modellarchitekturen und alternativen Trainingszielen vor.