Technische Samenvatting: Exploratie verkennen in Bayesiaanse Optimalisatie

Probleemstelling

Bayesiaanse Optimalisatie (BO) is een standaardmethode voor het maximaliseren van black-boxfuncties door sequentieel probabilistische surrogate-modellen (doorgaans Gaussische Processen) te construeren en nieuwe steekproefpunten te selecteren via een acquisitiefunctie (AF). Een kritiek onderdeel van elk succesvol BO-algoritme is het vermogen van de acquisitiefunctie om exploratie (het verkennen van onontdekte gebieden om globale optima te vinden) en exploitatie (het verfijnen van de zoektocht in veelbelovende gebieden) in evenwicht te brengen.

Hoewel de BO-gemeenschap breed erkent dat verschillende AF's uiteenlopende graden van exploratieve voorkeur vertonen, ontbreekt er aanzienlijk kwantitatief maatwerk om deze kenmerken te definiëren en te vergelijken. Bestaande metrieken, zoals Total Center Distance (TCD) of incumbent-afstand, lijden aan opmerkelijke tekortkomingen: ze kunnen falen wanneer de initiële steekproef het optimum raakt, ze vangen oscillerend gedrag niet op, of ze verwarren afstand tot een specifiek punt met echte exploratie. Bovendien is het vergelijken van AF's uit verschillende families (bijvoorbeeld Upper Confidence Bound versus Informatietheoretische methoden) uitdagend zonder een universele metriek. Deze kloof belemmert de systematische analyse, het ontwerp en de selectie van AF's voor specifieke real-world problemen.

Methodologie

Om het gebrek aan kwantitatieve exploratiemetrieken aan te pakken, stellen de auteurs twee nieuwe benaderingen voor die gebaseerd zijn op de ruimtelijke verdeling van observaties die tijdens het optimalisatieproces zijn geselecteerd:

1. Observation Traveling Salesman Distance (OTSD)

OTSD kwantificeert exploratie door de minimale Euclidische afstand te berekenen die nodig is om alle observatiepunten in de zoekruimte te verbinden, geformuleerd als een Traveling Salesman Problem (TSP).

• Definitie: Gegeven een set van $t$ observatiepunten $X_t$, is OTSD de totale lengte van de kortste route die elk punt precies één keer bezoekt en terugkeert naar het startpunt.
• Normalisatie: Omdat de ruwe OTSD monotoon toeneemt met het aantal observaties en afhankelijk is van de dimensionaliteit, introduceren de auteurs een Genormaliseerde OTSD. Deze wordt afgeleid door de ruwe OTSD te delen door een theoretische bovengrens $\Psi(d, t)$, die afhankelijk is van de dimensie $d$ en het aantal punten $t$. Deze normalisatie maakt vergelijking mogelijk over verschillende probleemdimensies en iteratieaantallen.
• Berekening: Vanwege de NP-moeilijkheid van TSP maken de auteurs gebruik van een insertie-heuristisch algoritme met $O(dT^2)$ complexiteit, wat een tourlengte garandeert die maximaal tweemaal de optimale lengte is.

2. Observation Entropy (OE)

OE kwantificeert exploratie door de uniformiteit van de data-verdeling van de observaties te meten met behulp van informatietheorie.

• Definitie: OE behandelt observatiepunten als steekproeven uit een stochastische variabele en schat de empirische differentiaal-entropie. Hogere entropiewaarden duiden op een uniformere spreiding van punten, wat grotere exploratie weerspiegelt.
• Schatting: De auteurs maken gebruik van de niet-parametrische Kozachenko-Leonenko (KL)-schatter, die gebaseerd is op afstanden tot de dichtstbijzijnde buren. Deze methode is gekozen vanwege de efficiëntie van de steekproef en de toepasbaarheid in ruimtes met gemiddelde dimensionaliteit ($d \le 50$).
• Eigenschappen: In tegenstelling tot OTSD is OE niet-monotoon en kan het positieve of negatieve waarden aannemen. Een toenemende OE over iteraties suggereert dat de AF meer exploratief wordt, terwijl een afname suggereert dat er een verschuiving naar exploitatie plaatsvindt.

Belangrijkste Bijdragen

1. Nieuwe Kwantificatiemetrieken: De introductie van OTSD en OE als de eerste toegewijde, kwantitatieve maatstaven om het exploratiegedrag van acquisitiefuncties te karakteriseren op basis van hun geselecteerde observaties.
2. Empirische Taxonomie: Het creëren van de eerste empirische taxonomie van acquisitiefunctie-exploratie. Door OTSD en OE toe te passen op diverse benchmarks, stellen de auteurs een partiële ordening van AF's vast (bijvoorbeeld Random Search $\succeq$ UCB (hoge $\beta$) $\succeq$ Informatietheoretisch $\approx$ KG $\succeq$ EI $\succeq$ PI $\succeq$ UCB (lage $\beta$) $\succ$ Deterministische Selectie).
3. Uitgebreide Evaluatie: Uitgebreide experimenten op synthetische en real-world benchmarks (variërend van lage tot hoge dimensionaliteit, $d=2$ tot $d=180$) en diverse AF-varianten (inclusief gebatchte evaluaties, Trust Regions en RAASP-steekproeven).
4. Theoretische Grenzen: Het afleiden van theoretische boven- en ondergrenzen voor de ware OTSD- en OE-waarden, waardoor een statistische basis wordt geboden voor de voorgestelde schatters.

Resultaten

De experimenten valideren de effectiviteit van OTSD en OE in het vastleggen van exploratiegedrag:

• Consistentie: OTSD en OE correleren sterk over benchmarkproblemen, wat hun betrouwbaarheid kruisvalidatie. Beide metrieken onderscheiden succesvol bekende exploratieve (bijvoorbeeld Random Search, UCB met hoge $\beta$) en exploitatieve (bijvoorbeeld PI, Deterministische Selectie) strategieën.
• Invloed van Dimensionaliteit: De studie onthult dat dimensionaliteit het exploratiegedrag significant beïnvloedt. Zo is Thompson Sampling (TS) matig exploratief in lage dimensies, maar wordt het buitensporig exploratief in hoge dimensies, waarbij het OTSD vaak Random Search overtreft. Omgekeerd is Expected Improvement (EI) in lage dimensies meer exploratief dan UCB, maar minder in hoge dimensies.
• Invloed van Technieken:
  • Batching: Verhoogt exploratie (hogere OTSD/OE) omdat grotere batchgroottes de selectie van diverse punten afdwingen.
  • Trust Regions (TR's) en RAASP: Verminderen consistent exploratie, wat leidt tot meer exploitatief gedrag.
• Correlatie met Prestaties: De resultaten suggereren dat de best presterende methoden over het algemeen geen extreme hoeveelheden exploratie vertonen. In plaats daarvan handhaven ze een gebalanceerde Trade-Off tussen Exploratie en Exploitatie (EETO). Buitensporig exploratieve methoden (zoals TS in hoge dimensies) of buitensporig exploitatieve methoden leveren vaak suboptimale optimalisatieprestaties op.

Betekenis en Claims

Het artikel beweert dat deze nieuwe maatstaven een fundament bieden voor het sturen van het ontwerp van acquisitiefuncties op een meer principieel en systematisch manier. Door exploratie te kwantificeren, kunnen practitioners:

• AF-gedrag diagnosticeren: Identificeren of een AF te exploratief is (bijvoorbeeld TS in hoge dimensies) of te exploitatief voor een specifiek probleem, wat mogelijk kan dienen als waarschuwingssignaal.
• Portefeuilles samenstellen: Geschikte AF's of combinaties selecteren (bijvoorbeeld het toevoegen van RAASP aan een zeer exploratieve AF) op basis van het vereiste niveau van exploratie.
• Vroegtijdig stoppen: Detecteren wanneer een AF lokale minima heeft uitgeput (aangegeven door een verschuiving in OTSD/OE-trends), wat suggereert dat het optimalisatieproces mogelijk klaar is om te worden beëindigd.

De auteurs benadrukken dat hoewel hun resultaten empirisch robuust zijn, deze beperkt zijn tot continue domeinen en momenteel geen rekening houden met de specifieke effecten van GP-hyperparameters. Toekomstig werk heeft tot doel deze taxonomieën uit te breiden naar niet-Euclidische domeinen en het invloed van kernel- en likelihood-hyperparameters te onderzoeken.