Technische Samenvatting: High-dimensional Multi-objective Bayesian Optimization met Learned Variable Interactions (ViaMOBO)

1. Probleemstelling

Multi-objective Bayesian Optimization (MOBO) is een krachtige techniek voor het benaderen van Pareto-fronten in dure black-box problemen, zoals robotica-ontwerp, circuitoptimalisatie en hyperparameter-tuning. De huidige MOBO-benaderingen kampen echter met een belangrijke flessenhals: exponentiële bemonsteringscomplexiteit naarmate de dimensionaliteit van de beslissingsruimte toeneemt.

Huidige state-of-the-art methoden voor high-dimensional MOBO, zoals ReMO en MORBO, lijden aan specifieke beperkingen:

• ReMO vertrouwt op random embedding, uitgaande van de aanname dat slechts enkele dimensies effectief zijn en dat dezelfde dimensies effectief zijn voor alle doelstellingen. Deze aanname is vaak irrationeel voor real-world problemen waarbij verschillende doelstellingen afhankelijk kunnen zijn van verschillende variabelensubsets.
• MORBO maakt gebruik van trust regions om lokale modellen te beheren, maar richt zich primair op het verminderen van de cubische tijdcomplexiteit van datapunten in plaats van het aanpakken van de exponentiële complexiteit van de beslissingsdimensie zelf. Het modelleert niet expliciet de interactiestructuur tussen variabelen.

Bovendien vertonen veel real-world high-dimensional problemen variabele interacties, waarbij de fluctuatie van één variabele anderen beïnvloedt, wat gezamenlijk de objectieve waarden beïnvloedt. Huidige MOBO-methoden negeren deze relaties vaak, wat leidt tot een ernstige afname van de prestaties. De kernuitdaging is om te bepalen of een high-dimensional Multi-Objective Problem (MOP) separable (variabelen kunnen worden gegroepeerd in onafhankelijke subsets) of non-separable is zonder sterke voorafgaande aannames te doen, en om deze structuur te benutten om de bemonsteringscomplexiteit te verminderen.

2. Methodologie: ViaMOBO Framework

Het paper stelt ViaMOBO voor, een generiek framework ontworpen om de vloek van dimensionaliteit te verlichten door de interacties tussen beslissingsvariabelen te leren. Het framework werkt via de volgende stadia:

A. Herdefinitie van Separabiliteit voor MOPs

De auteurs herdefiniëren separabiliteit voor multi-objective contexten. Een MOP wordt als separable beschouwd als elke objectieve functie separable is (volledig of gedeeltelijk). Cruciaal is dat zij een transitieve eigenschap introduceren voor variabele interacties: als variabele $x_i$ interageert met $x_j$, en $x_j$ interageert met $x_k$, dan interageren alle drie. Dit maakt het mogelijk om de beslissingsruimte te partitioneren in disjuncte subgroepen van onderling afhankelijke variabelen.

B. Variable Interaction Learning (Zonder Dure Evaluaties)

Een belangrijke innovatie is de methode voor het detecteren van interacties zonder de kosten van extra dure functie-evaluaties te maken.

1. Perturbatie-strategie: Het algoritme selecteert een beslissingsvector $x$ die een specifieke doelstelling maximaliseert. Vervolgens perturbeert het deze vector op twee dimensies ($i$ en $j$) om nieuwe vectoren ($x'_i, x'_j, x'_{ij}$) te creëren.
2. Binaire Classificatie: In plaats van de ware objectieve functie te evalueren voor deze geperturbeerde vectoren (wat duur zou zijn), traint ViaMOBO een binaire classifier (SVM) op bestaande data. Deze classifier leert de grootte-relatie tussen de objectieve waarden van twee beslissingsvectoren.
3. Interactie Detectie: De getrainde SVM voorspelt de relatie tussen de geperturbeerde vectoren. Als er een dominantierelatie bestaat tussen de geperturbeerde sets (bijv. $[f(x'_i), f(x'_j)]$ domineert $[f(x), f(x'_{ij})]$), dan worden de variabelen $x_i$ en $x_j$ als interagerend beschouwd.
4. Partitionering: Gebruikmakend van de transitiviteitsdefinitie groepeert het algoritme alle interagerende variabelen in disjuncte subruimtes ($\Omega_i$). Als de MOP als non-separable wordt gevonden, schakelt het framework over naar andere high-dimensional methoden (bijv. MORBO).

C. Additive Kernel Structure en Lokale Optimalisatie

Zodra de beslissingsruimte is gepartitioneerd in disjuncte subgroepen $\Omega_i$:

• Additive GP Modeling: Het framework gaat uit van een additieve structuur voor het surrogaatmodel. Elke objectieve functie $f_i(x)$ wordt gemodelleerd als een som van sub-functies, elk gedefinieerd over een specifieke subgroep $\Omega_i$.
• Lokale Bayesian Optimization: In plaats van te optimaliseren in de volledige $D$-dimensionale ruimte, wordt de acquisitiefunctie onafhankelijk geoptimaliseerd binnen elke low-dimensional subruimte $\Omega_i$. Dit vermindert de computationele complexiteit van de maximalisatie van de acquisitiefunctie drastisch.
• Batch Sampling: Om een batch kandidaten te selecteren, gebruikt de methode strategieën zoals qUCB, qEI of qEHVI. Het maakt gebruik van een "virtuele afgeleide" observatietechniek om over-exploratie aan de grenzen van de zoekruimte te voorkomen.

3. Belangrijkste Bijdragen

1. ViaMOBO Framework: Een algemeen MOBO-framework dat een additieve kernelstructuur introduceert in multi-objective settings, waarbij expliciet rekening wordt gehouden met de sample-efficiëntie van de acquisitiefunctie in high-dimensional ruimtes.
2. Interaction Learning Strategie: Een innovatieve strategie die de separabiliteit van high-dimensional MOPs bepaalt door variabele interacties te leren. Het vermijdt dure functie-evaluaties tijdens de leerfase door een binaire classifier te gebruiken om de relaties tussen objectieve waarden te voorspellen.
3. Empirische Validatie: Uitgebreide verificatie tegen state-of-the-art MOBO-methoden (inclusief ReMO, MORBO, ParEGO, DGEMO, etc.) op zowel synthetische benchmarks (DTLZ2) als real-world problemen (vleugelprofielontwerp, trajectplanning).

4. Experimentele Resultaten

De auteurs evalueerden ViaMOBO op synthetische problemen met dimensies variërend van 10 tot 100, en real-world problemen met dimensies van 20, 40 en 60.

• Synthetische Benchmarks (DTLZ2):

  • 10D: ViaMOBO bereikte bijna optimale Pareto-front benaderingen, met een definitieve Hypervolume (HV) die slechts 0,024% lager was dan de beste performer (DGEMO), maar met een runtime die ongeveer 5,6 keer sneller was.
  • 30D: ViaMOBO behield competitieve prestaties, waarbij een definitieve HV van slechts 0,118% onder DGEMO werd bereikt, terwijl er ongeveer één kwart van de runtime nodig was.
  • 100D: ViaMOBO demonstreerde superieure vroege en intermediaire convergentie, waarbij de hoogste HV@500 en HV@1000 werd bereikt. Hoewel DGEMO uiteindelijk een iets hogere definitieve HV bereikte, vereiste dit 10,5 keer meer runtime. ViaMOBO presteerde aanzienlijk beter dan MORBO wat betreft convergentiesnelheid en AUC-HV.

• Real-World Problemen:

  • Vleugelprofielontwerp (20D & 40D): ViaMOBO was de snelste surrogate-gebaseerde methode. In het 20D geval had het slechts ~21% van de runtime van TSEMO en ~12% van qParEGO nodig, terwijl het een concurrerende definitieve oplossingkwaliteit behield. In het 40D geval was het de meest computationeel efficiënte methode, waarbij het slechts ~1/7e van de runtime van MORBO nodig had voor een concurrerende definitieve HV.
  • Trajectplanning (60D): Op dit probleem met sterke sequentiële koppeling presteerde ViaMOBO goed, maar werd het overtroffen door MORBO en NSGA-II. De auteurs merken op dat dit een toepasbaarheidsgrens aangeeft: ViaMOBO is het best geschikt voor problemen met identificeerbare groepsstructuren of zwakke inter-groep koppeling, in plaats van sterk gekoppelde sequentiële taken.

• Ablatie-studies:

  • Classificatie Nauwkeurigheid: De binaire classifier behield een algehele groeperingsnauwkeurigheid boven de 73% zelfs bij 100 dimensies, hoewel de nauwkeurigheid afnam naarmere de dimensionaliteit toenam.
  • Acquisitiefuncties: Voor 2-objectieve problemen presteerde EHVI het best. Echter, voor 3-objectieve problemen leed EHVI aan numerieke instabiliteit en hoge computationele kosten. EI en UCB boden een betere balans tussen convergentie, efficiëntie en robuustheid voor het ViaMOBO-framework.

5. Betekenis en Claims

Het paper claimt dat ViaMOBO een significante vooruitgang biedt in het aanpakken van dure, high-dimensional multi-objective problemen door weg te bewegen van rigide aannames (zoals random embedding) naar data-gedreven structurele leerprocessen.

• Efficiëntie: Door de high-dimensional ruimte te decomponeren in kleinere, onafhankelijke subruimtes op basis van geleerde interacties, vermijdt ViaMOBO de exponentiële complexiteit die geassocieerd wordt met globale optimalisatie in hoge dimensies.
• Kosteneffectiviteit: Het gebruik van een binaire classifier om interacties te infereren elimineert de noodzaak voor kostbare extra functie-evaluaties tijdens de structurele analysefase.
• Praktische Bruikbaarheid: Het framework biedt een gunstige trade-off tussen oplossingkwaliteit en computationele kosten, waardoor het bijzonder geschikt is voor real-world engineering toepassingen waar computationele budgetten beperkt zijn.

De auteurs erkennen bescheiden dat ViaMOBO primair is afgestemd op separable of zwak gekoppelde problemen. Voor sterk gekoppelde, non-separable problemen kan het voordeel van ViaMOBO afnemen, wat wijst op een richting voor toekomstig werk met betrekking tot meer expressieve interactiemodellering en adaptieve variabele groepering.