Adaptive Candidate Point Thompson Sampling for High-Dimensional Bayesian Optimization

Dit paper introduceert Adaptive Candidate Thompson Sampling (ACTS), een methode die de zoekruimte adaptief verkleint op basis van gradiënten om de dichtheid van kandidaatpunten in hoge dimensies te vergroten en zo de prestaties van Bayesiaanse optimalisatie te verbeteren.

De kern

Stel je voor dat je op zoek bent naar het hoogste punt in een enorm, onbekend berglandschap. Je kunt niet overal tegelijk kijken, en elke keer dat je een nieuwe plek beklimt om te meten, kost dat veel tijd en energie. Dit is precies wat Bayseiaanse Optimalisatie doet: het is een slimme manier om het beste antwoord te vinden in een wereld vol onzekerheid, zonder elke mogelijke optie te hoeven testen.

Deze paper introduceert een nieuwe methode genaamd ACTS (Adaptive Candidate Thompson Sampling). Laten we uitleggen hoe dit werkt, zonder ingewikkelde wiskunde.

Het Probleem: De "Naaimachine" in een Oerwoud

Stel je voor dat je een naaimachine hebt die een kaart tekent van het berglandschap op basis van de plekken die je al hebt bezocht. Je wilt nu een nieuwe plek kiezen om te meten. De slimste manier is om een willekeurige versie van die kaart te tekenen (een "steekproef") en dan te kijken waar die kaart het hoogste punt heeft. Dat is je volgende bestemming.

Maar hier zit het probleem:

• In een klein landschap (bijvoorbeeld 3 dimensies) is het makkelijk om een kaart te tekenen en het hoogste punt te vinden.
• In een gigantisch landschap (met honderden of duizenden dimensies, zoals bij het ontwerpen van nieuwe medicijnen of het trainen van AI), wordt het onmogelijk.

Het is alsof je probeert een naaimachine te gebruiken om een heel oerwoud in kaart te brengen. Als je probeert het hele oerwoud te bedekken met meetpunten, heb je er oneindig veel nodig. De meeste methoden proberen dit op te lossen door een rooster van vaste punten te gebruiken (zoals een raster op een kaart). Maar in een groot landschap wordt dit rooster zo dun, dat je waarschijnlijk precies het hoogste punt mist. Het is alsof je een net over een bos gooit, maar de gaten in het net zijn zo groot dat je de grootste bomen niet vangt.

De Oplossing: ACTS (De Slimme Kompas)

De auteurs van deze paper, Donney Fan en Geoff Pleiss, zeggen: "Waarom proberen we het hele bos te bedekken? Laten we in plaats daarvan kijken waar de wind (de helling) ons naartoe blaast."

Hun nieuwe methode, ACTS, werkt als volgt:

1. Kijk naar de helling: In plaats van willekeurig door het hele bos te zoeken, kijkt de computer eerst naar de "helling" van de kaart op de plek waar je nu staat. Dit is als een kompas dat aangeeft: "De berg gaat hier omhoog!"
2. Verklein de zoekruimte: In plaats van het hele oerwoud te doorzoeken, concentreert ACTS zich alleen op een klein stukje bos dat in de richting van die helling ligt. Het negeert alle andere richtingen die waarschijnlijk naar beneden lopen.
3. Dichtbij netten: Omdat ze nu maar een klein stukje bos hoeven te bedekken, kunnen ze hun "net" (de meetpunten) veel dichter op elkaar leggen. Ze kunnen nu honderden punten in dat ene kleine stukje bos zetten, in plaats van verspreid over het hele continent.
4. Vind het hoogste punt: Met zo'n dicht net is de kans veel groter dat ze het echte hoogste punt in dat stukje bos vinden.

De Creatieve Analogie: De Zoektocht naar de Beste Pizzastand

Stel je voor dat je de beste pizzastand in een grote stad wilt vinden, maar je kunt maar op één plek per dag proeven.

• De oude methode (RAASP): Je gooit een willekeurig rooster van 10.000 plekken over de hele stad. Je eet op die plekken pizza. Omdat de stad zo groot is, heb je misschien net geen enkele pizza gegeten bij de echte beste stand. Je mist hem.
• De ACTS-methode: Je staat op een plek en vraagt aan een lokale: "Waarheen is de geur van de beste pizza het sterkst?" De lokale wijst naar een specifieke straat (de helling).
  • In plaats van de hele stad te doorzoeken, ga je alleen die ene straat in.
  • Omdat je nu alleen die ene straat hoeft te doorzoeken, kun je bij elke deur in die straat een pizza proeven.
  • Je vindt de beste pizza in die straat veel sneller. En omdat de "lokale" (de computer) elke dag een nieuwe willekeurige mening heeft, ga je elke dag een andere straat in. Uiteindelijk heb je de hele stad afgedekt, maar dan op een slimme, gerichte manier.

Waarom is dit belangrijk?

Deze methode is een "drop-in" oplossing. Dat betekent dat je het kunt gebruiken in plaats van de oude methoden, zonder alles opnieuw te hoeven bouwen.

• Snelheid: Het werkt net zo snel als de oude methoden, maar is veel effectiever.
• Schaalbaarheid: Het werkt wonderbaarlijk goed in zeer complexe problemen (zoals het ontwerpen van nieuwe moleculen of het optimaliseren van robotbewegingen), waar andere methoden vastlopen.
• Veiligheid: Hoewel ze zich concentreren op een klein gebied, garanderen de auteurs dat ze niet "vast komen te zitten" in een lokale top. Ze blijven uiteindelijk het hele landschap verkennen, maar dan op een slimme manier.

Conclusie

Kortom: ACTS is als het hebben van een slim kompas dat je niet door het hele bos laat dwalen, maar je direct naar het meest veelbelovende stukje bos leidt. Daar kun je dan heel gedetailleerd zoeken, waardoor je de beste oplossing veel sneller vindt dan wie dan ook. Het is een slimme manier om de "verwarring" van hoge dimensies om te zetten in een gerichte zoektocht.

Technische samenvatting

Titel: Adaptive Candidate Point Thompson Sampling voor Hoge-Dimensionale Bayesiaanse Optimalisatie

Auteurs: Donney Fan en Geoff Pleiss (University of British Columbia & Vector Institute)

---

1. Het Probleem

Bayesiaanse optimalisatie (BO) is een krachtig raamwerk voor het optimaliseren van dure, zwarte-doos functies. Een populaire strategie binnen BO is Thompson Sampling (TS), waarbij het volgende evaluatiepunt wordt geselecteerd door te maximaliseren op een steekproef uit de posterijorverdeling van de doelwitfunctie.

Het grootste probleem bij het toepassen van TS met Gaussian Process (GP)-surrogaten in hoge dimensies (honderden tot duizenden variabelen) is de curse of dimensionality:

• Het is onmogelijk om een continue functie uit een GP te bemonsteren. In de praktijk wordt dit opgelost door te werken met een discrete set van $M$ kandidaatpunten.
• Om een ruimte effectief te dekken, moet het aantal benodigde punten exponentieel groeien met de dimensie $d$. Zelfs met $10^4$ punten (een standaard budget) wordt de verdeling in hoge dimensies extreem schaars.
• Bestaande methoden gebruiken strategieën zoals sparsiteit (perturberen in slechts een paar dimensies, zoals RAASP) of lokaliteit (trust regions), maar deze lossen het fundamentele probleem van de schaarse discretisatie niet volledig op, wat leidt tot suboptimale steekproeven van het maximum.

2. Methodologie: Adaptive Candidate Thompson Sampling (ACTS)

De auteurs introduceren ACTS, een methode die de dichtheid van kandidaatpunten verhoogt door de zoekruimte adaptief te verkleinen op basis van de gradiënt van een steekproef van het GP-model.

Kernidee:
In plaats van kandidaatpunten willekeurig over de hele ruimte te verspreiden, gebruikt ACTS de gradiënt van een steekproef van de posterijorfunctie ($\nabla f(x_0)$) om een kleinere, veelbelovende zoekruimte te definiëren.

Het Algorithmische Proces:

1. Gradiëntbemonstering: Er wordt een steekproef genomen van de gradiënt van de GP-posterijor op het huidige beste punt (incumbent $x_0$). Dit gebeurt via een "Jacobian GP Model", dat een gezamenlijke verdeling modelleert over functiewaarden en hun afgeleiden.
2. Adaptieve Zoekruimte ($T_{\nabla f(x_0)}$): Op basis van deze gradiënt wordt een as-gealigneerde kegel gedefinieerd die uitstraalt vanaf $x_0$ in de richting van de gradiënt.
   • Formeel: $T_{\nabla f(x_0)} = \{x_0 + v \odot \nabla f(x_0) \mid 0 \preceq v \in \mathbb{R}^d\} \cap \mathcal{X}$.
   • Deze ruimte is aanzienlijk kleiner dan de oorspronkelijke domein (bijv. een factor $2^{100}$ kleiner in 100 dimensies), wat de dichtheid van kandidaatpunten enorm verhoogt binnen dit gebied.
3. Generatie van Kandidaten: Een bestaande beleid (zoals Sobol of RAASP) wordt toegepast, maar dan beperkt tot deze kleine kegel.
4. Selectie: De TS-steekproef wordt gemaximaliseerd over deze dichte set van kandidaten. Het resultaat is een punt dat dichter bij het werkelijke maximum van de GP-steekproef ligt.

Belangrijke Eigenschappen:

• Exactheid: Hoewel de kandidaatset adaptief is, blijft de resulterende steekproef een geldige realisatie van de GP-posterijor.
• Global Consistency: De auteurs bewijzen theoretisch dat ACTS niet vastloopt in lokale optima. Omdat de gradiënt een willekeurige steekproef is, zal de zoekruimte op de lange termijn elke regio van de ruimte bezoeken, wat garandeert dat het globale maximum wordt gevonden.
• Compatibiliteit: ACTS is een "drop-in replacement" voor bestaande TS-methoden en werkt naadloos samen met Trust Regions (zoals in TuRBO) en Batch-optimalisatie.

3. Belangrijkste Bijdragen

1. Nieuwe Paradigma: In plaats van de discretisatie te verbeteren door meer rekenkracht te gebruiken (schaalbare GP-benaderingen), verkleint ACTS de zoekruimte adaptief om de bestaande rekenkracht effectiever te benutten.
2. Gradiëntgeleidde Zoekruimte: Het gebruik van de gradiënt van een GP-steekproef om een zoekkegel te definiëren is een unieke en effectieve strategie om de curse of dimensionality te omzeilen.
3. Theoretische Garantie: Het paper levert een bewijs voor de globale consistentie van ACTS, wat een kritieke theoretische zwakte in veel lokale BO-methoden wegneemt.
4. Implementatie: Een open-source implementatie die compatibel is met bestaande frameworks zoals BoTorch.

4. Resultaten

De auteurs evalueren ACTS op een breed scala aan synthetische en real-world benchmarks, variërend van 12 tot 1000 dimensies.

• Middelhoge Dimensies (12D - 32D): Op taken zoals Lunar Lander en Robot Pushing presteert ACTS consistent beter dan bestaande methoden (RAASP, Cylindrical TS, Pathwise TS).
• Hoge Dimensies (60D - 1000D): Op benchmarks zoals MOPTA08, SVM-tuning en moleculair ontwerp (GuacaMol) overtreft ACTS state-of-the-art methoden zoals SAASBO, BAxUS en LogEI.
  • In vergelijking met RAASP (de huidige standaard voor hoge dimensies) toont ACTS een duidelijk voordeel, vooral op complexe taken.
• Batch Optimalisatie: ACTS behoudt zijn superieure prestaties ook in parallelle (batch) settings, waarbij het diversiteit in de zoekruimte behoudt door verschillende gradiëntsteekproeven voor verschillende batches.
• Ablatie Studies:
  • Het tonen aan dat de prestatieverbetering komt door de specifieke verdeling van kandidaatpunten en niet alleen door het verkleinen van de ruimte (vergeleken met TuRBO alleen).
  • De keuze voor een "kegel" als zoekruimte bleek robuuster dan een eendimensionale lijnzoeking.

5. Betekenis en Impact

Deze paper biedt een fundamentele verbetering voor Bayesiaanse optimalisatie in hoge dimensies.

• Efficiëntie: Het maakt TS schaalbaar naar duizenden dimensies zonder de noodzaak van complexe, onnauwkeurige GP-benaderingen.
• Praktische Toepasbaarheid: Omdat het een "drop-in" oplossing is, kunnen onderzoekers en ingenieurs bestaande BO-pipelines direct verbeteren door ACTS te integreren.
• Theoretische Diepgang: Het bewijs van globale consistentie geeft vertrouwen dat deze lokale, gradiëntgeleide strategie niet ten koste gaat van de garantie op het vinden van het globale optimum.

Kortom, ACTS lost het probleem van schaarse discretisatie in hoge dimensies op door slimme, adaptieve verkleining van de zoekruimte, wat leidt tot snellere en betere optimalisatie in complexe, real-world scenario's.