Technische Samenvatting: Zoeken naar een Kortingmodel voor Kwaliteitsdiversiteitsoptimalisatie in Hoogdimensionale Maatruimten

Probleemdefinitie

Kwaliteitsdiversiteits (QD) optimalisatie streeft naar het ontdekken van een verzameling oplossingen die een doelfunctie $f$ maximaliseren, terwijl ze tegelijkertijd een divers scala aan outputs dekken dat wordt gedefinieerd door een door de gebruiker gespecificeerde, vectoriële maatfunctie $m$. Het beeld van $m$ vormt de maatruimte $S$. Een kritieke beperking in hedendaagse QD-algoritmen, met name state-of-the-art methoden zoals Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), is hun onvermogen om effectief te schalen naar hoogdimensionale maatruimten.

In hoogdimensionale ruimten lijden algoritmen onder vervorming, een fenomeen waarbij grote volumes van de oplossingsruimte afbeelden op kleine regio's van de maatruimte. CMA-MAE benadert het QD-doel door het maximaliseren van "archiefverbetering", gedefinieerd als $\Delta(\theta) = f(\theta) - f_A(m(\theta))$, waarbij $f_A$ een kortingfunctie is. CMA-MAE stelt $f_A$ voor als een discreet histogram (een tessellatie van cellen). In hoogdimensionale situaties zorgt vervorming ervoor dat veel verschillende oplossingen in dezelfde histogramcel vallen, waardoor ze identieke kortingswaarden toegewezen krijgen. Bijgevolg kan het algoritme geen onderscheid maken tussen oplossingen met vergelijkbare maten, wat leidt tot onnauwkeurige verbeteringssignalen en zoekstagnatie. Bovendien is het ontwerpen van laagdimensionale maatfuncties voor complexe domeinen (bijvoorbeeld het specificeren van "waar een wandelaar zich bevindt") vaak tijdrovend en niet-intuïtief.

Methodologie: Zoeken naar een Kortingmodel (DMS)

Om deze beperkingen aan te pakken, stellen de auteurs Zoeken naar een Kortingmodel (Discount Model Search, DMS) voor. In plaats van een discreet histogram te gebruiken, maakt DMS gebruik van een neurale netwerken om een gladde, continue representatie van de kortingfunctie $f_A$ te leren.

Kerncomponenten

1. Kortingmodel ($\hat{f}_A$): Een neurale netwerk geparametriseerd door $\psi$ dat maatwaarden $s = m(\theta)$ als invoer neemt en een scalair kortingswaarde als uitvoer geeft. De architectuur is flexibel: Multi-Layer Perceptrons (MLP's) worden gebruikt voor laagdimensionale vectormaten, terwijl Convolutional Networks of Transformers geschikt zijn voor hoogdimensionale data zoals afbeeldingen.
2. Archief en Emitters: DMS onderhoudt een archief in de stijl van MAP-Elites dat de beste gevonden oplossingen opslaat. Het maakt gebruik van op CMA-ES gebaseerde emitters die oplossingen samplen uit een Gaussische verdeling. In tegenstelling tot CMA-MAE slaat het archief geen discrete kortingswaarden op; in plaats daarvan wordt het kortingmodel geraadpleegd om verbeteringswaarden te berekenen: $\Delta_i = f(\theta_i) - \hat{f}_A(m(\theta_i))$.
3. Trainen van het Kortingmodel: Het model wordt getraind om de drempel-update regel die in CMA-MAE wordt gebruikt, te benaderen. De trainingsdataset $D_A$ bestaat uit twee bronnen:
   • Emitter-sample's: Voor elke gesamplede oplossing $\theta$ wordt de doelkortingswaarde $t_A$ bijgewerkt op basis van of de doelwaarde van de oplossing $f(\theta)$ de huidige voorspelling van het model $\hat{f}_A(s)$ overschrijdt. Als $f(\theta) > \hat{f}_A(s)$, is het doel een lineaire combinatie van de doelwaarde en de huidige korting, gecontroleerd door een leersnelheid voor het archief $\alpha$.
   • Lege punten: Om te voorkomen dat het model willekeurige hoge waarden toekent aan onverkende regio's van de maatruimte, samplet het algoritme de centra van onbezette archiefcellen en wijst het hen een doelwaarde toe van $f_{min}$ (de minimale doelwaarde). Dit "klemt" het model in onverkende gebieden vast, zodat de emitters worden geleid om nieuwe regio's te verkennen.

Theoretisch Inzicht

Door het discrete histogram te vervangen door een continue functie, kan DMS verschillende kortingswaarden toekennen aan oplossingen, zelfs wanneer ze in een hoogdimensionale ruimte op vergelijkbare maten afbeelden. Dit stelt het algoritme in staat om een gradiënt van verbeteringssignalen te behouden, wat stagnatie voorkomt en verdere exploratie mogelijk maakt lang nadat histogramgebaseerde methoden zouden falen.

Belangrijkste Bijdragen

1. Zoeken naar een Kortingmodel (DMS): Een nieuw QD-algoritme dat een glad, continu kortingmodel gebruikt om exploratie te sturen in vervormde, hoogdimensionale maatruimten.
2. Kwaliteitsdiversiteit met Datasets van Maten (QDDM): De auteurs introduceren een nieuwe setting waarbij gebruikers gewenste maten specificeren via een dataset (bijvoorbeeld een collectie afbeeldingen) in plaats van handmatig een maatfunctie te ontwerpen. Dit behandelt de hoogdimensionale ruimte van de dataset (bijvoorbeeld de ruimte van afbeeldingen) als de maatruimte.
3. Nieuwe Domeinen: Twee QDDM-domeinen worden voorgesteld en geëvalueerd:
   • Driehoekarrangement (TA): Driehoeken rangschikken om afbeeldingen uit MNIST of Fashion MNIST te matchen.
   • Verlichting van Latente Ruimte (LSI) (Wandelaar): Het genereren van gezichtsafbeeldingen van wandelaars in diverse landschappen met StyleGAN3, waarbij de maatruimte de ruimte van landschapsafbeeldingen is.
4. Empirische Validatie: Uitgebreide benchmarks tonen aan dat DMS CMA-MAE, DDS en varianten van MAP-Elites overtreft op standaard benchmarks en de nieuwe QDDM-domeinen.

Experimentele Resultaten

De auteurs evalueerden DMS op 9 standaard benchmarks (inclusief Lineaire Projectie en Arm Repertoire) en 3 QDDM-domeinen.

• Benchmark-domeinen: DMS presteerde significant beter dan alle baselines op de QD-score (som van doelwaarden in het archief) en Dekking (percentage gevulde archiefcellen) in de meeste hoogdimensionale settings (bijvoorbeeld 10D, 20D, 50D LP-benchmarks). Opmerkelijk is dat in de 10D LP (Sfeer) benchmark de dekking van CMA-MAE daalde tot 6,95%, terwijl DMS 89,21% bereikte.
• QDDM-domeinen:
  • In TA (F-MNIST) overtrof DMS alle baselines significant op beide metrieken.
  • In TA (MNIST) kwam DMS qua dekking overeen met CMA-MAE, maar overtrof het varianten van MAP-Elites significant op de QD-score. De auteurs merken op dat DMS hier de QD-score van CMA-MAE niet significant overtrof, en speculeren dat de ruis geïntroduceerd door de neurale netwerkbenadering fijne doeloptimalisatie kan belemmeren in taken met lage vervorming en hoge precisie.
  • In LSI (Wandelaar) overtrof DMS CMA-MAE significant, met een QD-score van 214,91 tegenover 14,61, en een dekking van 3,77% (377 unieke wandelaarafbeeldingen). De auteurs merken op dat varianten van MAP-Elites een hoge dekking bereikten, maar met grote negatieve QD-scores vanwege het genereren van afbeeldingen buiten de trainingsverdeling van de generator.
• Berekeningskosten: DMS brengt hogere berekeningskosten met zich mee dan CMA-MAE vanwege het trainen van het kortingmodel, met name in laagdimensionale benchmarks. Echter, in QDDM-domeinen waar afbeeldingsgeneratie de bottleneck is, is de overhead minder opvallend.

Betekenis en Claims

Het artikel claimt dat DMS twee primaire voordelen biedt:

1. Verbeterde Prestaties: DMS verbetert de prestaties in huidige QD-toepassingen door de vervormingseffecten te overwinnen die hoogdimensionale maatruimten teisteren, en presteert beter dan state-of-the-art black-box algoritmen.
2. Toegankelijkheid en Nieuwe Toepassingen: Door de QDDM-setting in te voeren, maakt DMS QD toegankelijker. Het verlicht de noodzaak voor handmatige, handontworpen maatfuncties, waardoor gebruikers diversiteitsdoelen eenvoudig kunnen specificeren door een dataset te verstrekken. Dit maakt het specificeren van complexe, hoogdimensionale maten (zoals visuele stijlen of semantische locaties) mogelijk, die moeilijk te representeren zijn met laagdimensionale vectoren.

De auteurs concluderen dat, gezien de alomtegenwoordigheid van datasets in machine learning, het formuleren van problemen als QDDM en het oplossen ervan met DMS een veelbelovende richting is. Ze erkennen beperkingen, waaronder de rekenkundige overhead van het trainen van het model en de potentie dat benaderingsruis fijne optimalisatie beïnvloedt, en suggereren toekomstig werk aan geavanceerdere modelarchitecturen en alternatieve trainingsdoelen.