A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization

Technische Samenvatting: Een Geïntegreerd Kader voor Entropiezoektocht en Verwachte Verbetering in Bayesiaanse Optimalisatie

Probleemstelling
Bayesiaanse Optimalisatie (BO) is een standaardtechniek voor het optimaliseren van dure black-boxfuncties, waarbij gebruik wordt gemaakt van acquisatiefuncties (AF's) om exploratie en exploitatie in evenwicht te brengen. Er bestaan twee dominante paradigma's:

1. Verwachte Verbetering (Expected Improvement - EI): Een op heuristieken gebaseerde AF die de verwachte verbetering ten opzichte van de huidige beste waargenomen waarde maximaliseert. Het is computatie-efficiënt en wijdverbreid in gebruik, maar wordt vaak fundamenteel onderscheiden van methoden gebaseerd op informationele theorie beschouwd.
2. Acquisatiefuncties gebaseerd op Informationele Theorie (bijv. Max-value Entropy Search - MES): Deze methoden beogen de onzekerheid over de locatie of waarde van het globale optimum te verminderen met behulp van op entropie gebaseerde maatstaven. Hoewel ze theoretisch onderbouwd zijn, worden ze vaak als distinct beschouwd van EI vanwege verschillende onderliggende filosofieën.

Het heersende perspectief in de BO-gemeenschap behandelt EI en acquisatiefuncties gebaseerd op informationele theorie als aparte methodologieën. Dit artikel daagt dat standpunt uit en betoogt dat er een diepere theoretische connectie tussen hen bestaat die eerder niet was onderkend.

Methodologie: Variational Entropy Search (VES)
De auteurs introduceren Variational Entropy Search (VES), een geïntegreerd theoretisch kader dat EI interpreteert als een variational inference-benadering van de informationele Max-value Entropy Search (MES).

• Theoretische Unificatie: Het kader stelt een ondergrens vast voor de MES-acquisatiefunctie met behulp van de Barber-Agakov (BA) grens. Door een variational familie $Q$ te definiëren om de conditionele dichtheid $p(y^* | D_t, y_x)$ te benaderen (waarbij $y^*$ de waarde van het globale maximum is), leiden de auteurs een Entropy Search Lower Bound (ESLBO) af.
• Herstel van EI: Wanneer de variational familie $Q$ wordt beperkt tot exponentiële verdelingen, levert de maximalisatie van de ESLBO een oplossing op die identiek is aan de standaard Verwachte Verbetering (EI). Dit bewijst dat EI een speciaal geval is van MES onder een specifieke variational benadering.
• VES-Gamma: Erkenning dat de exponentiële verdeling te star is om de ware structuur van $p(y^* | D_t, y_x)$ vast te leggen (die vaak niet-monotoon is), stellen de auteurs VES-Gamma voor. Deze nieuwe AF maakt gebruik van een Gamma-verdeling als variational familie. De Gamma-verdeling generaliseert de exponentiële verdeling, waardoor een flexibeler benadering mogelijk is die de vorm van de dichtheid beter vastlegt.
• Optimalisatie: Het VES-Gamma-algoritme hanteert een Expectation-Maximization (EM)-achtige aanpak. Het iteratief:
  1. Schat de parameters ($k, \beta$) van de Gamma-verdeling die de ESLBO maximaliseren voor een vast kandidaatpunt $x$.
  2. Update het kandidaatpunt $x$ om de ESLBO te maximaliseren gegeven de huidige parameters.
     De parameters $k$ en $\beta$ worden automatisch bepaald via afgeleide-analyse en regularisatie, waarbij de componenten van de doelfunctie dynamisch in evenwicht worden gebracht.

Belangrijkste Bijdragen

1. Geïntegreerd Kader: De introductie van het VES-kader, dat aantoont dat EI een variational benadering is van MES, waardoor twee eerder distincte paradigma's van acquisatiefuncties worden geünificeerd.
2. Nieuwe Acquisatiefunctie: De voorstelling van VES-Gamma, een AF die de prestatiekracht van EI erf, terwijl het principes van informationele theorie integreert via een flexibelere Gamma-variational benadering.
3. Uitgebreide Evaluatie: Uitgebreide empirische evaluaties over synthetische benchmarks met lage en hoge dimensies, Gaussian Process (GP)-stalen en real-world problemen.

Resultaten
Het artikel evalueert VES-Gamma tegen EI, MES en andere state-of-the-art methoden (zoals UCB en LogEI) over diverse benchmarks:

• Synthetische Benchmarks: Op functies zoals Branin, Levy, Hartmann en Griewank presteert VES-Gamma consistent concurrerend. Het bereikt de beste prestaties op Branin en Hartmann, terwijl het op Levy en Griewank EI evenaart of licht overtreft.
• GP-stalen: In experimenten met 100-dimensionale GP-priors presteert VES-Gamma aanzienlijk beter dan zowel EI als MES voor kleinere lengteschalen ($\ell = 0.05, 0.1, 0.25$), waarbij EI en MES de neiging hebben te convergeren naar suboptimale oplossingen.
• Real-world Benchmarks: Op hoogdimensionale problemen (60D Rover, 124D Mopta08, 180D Lasso-DNA, 388D SVM) toont VES-Gamma robuuste prestaties. Het presteert aanzienlijk beter dan alle andere methoden op de SVM-benchmark en rangschikt zich onder de top-prestators op Mopta08 en Lasso-DNA.
• Theoretische Validatie: Een Kolmogorov-Smirnov-test bevestigt de empirische equivalentie tussen VES-Exp (de exponentiële variant) en EI, met doorloopspercentages die over diverse benchmarks de 90% overschrijden.

Betekenis en Aanspraken
Het artikel beweert dat het VES-kader een nieuw theoretisch inzicht biedt: de populairste acquisatiefunctie (EI) is fundamenteel niet onderscheiden van methoden gebaseerd op informationele theorie, maar is eerder een specifieke variational benadering daarvan.

Door deze perspectieven te overbruggen, presenteren de auteurs VES-Gamma als een robuuste, veelzijdige acquisatiefunctie die effectief de sterktes van zowel EI (prestaties en eenvoud) als MES (onzekerheidsreductie) in evenwicht brengt. De resultaten suggereren dat VES-Gamma een sterke kandidaat is voor diverse optimalisatieproblemen, met name in hoogdimensionale omgevingen waar traditionele methoden moeite kunnen hebben. De auteurs merken op dat hoewel VES-Gamma per iteratie hogere rekenkosten met zich meebrengt dan EI of MES, dit vaak verwaarloosbaar is in vergelijking met de kosten van het evalueren van dure black-boxfuncties in real-world toepassingen. Toekomstig werk wordt geïdentificeerd als het verkennen van alternatieve variational verdelingen en het uitbreiden van het kader naar ruisige omgevingen.