Optimally-Weighted Herding is Bayesian Quadrature

Probleemstelling
Een fundamentele uitdaging in statistisch machine learning is het berekenen van verwachtingswaarden van functies over kansverdelingen, uitgedrukt als $Z_{f,p} = \int f(x)p(x)dx$. Hoewel Monte Carlo-methoden dit benaderen via willekeurige bemonstering met een convergentiesnelheid van $O(1/\sqrt{N})$, lijden zij aan stochastische variantie. Quasi-Monte Carlo-methoden bieden een deterministisch alternatief door pseudo-monsters te genereren om de discrepantie tussen de empirische verdeling van de monsters en de doelverdeling $p(x)$ te minimaliseren. Twee prominente deterministische methoden zijn Kernel Herding, die de Maximum Mean Discrepancy (MMD) minimaliseert om monsters te selecteren, en Bayesian Quadrature (BQ), die een posterieure verdeling over de integraand $f$ afleidt om de integraal te schatten. Het artikel behandelt de theoretische verbinding tussen deze twee methoden en onderzoekt of een gewogen benadering van monsterneming de standaard herding kan overtreffen.

Methodologie
De auteurs vestigen een theoretische link tussen Kernel Herding en Bayesian Quadrature door de objectieve functies te analyseren die door elk worden geminimaliseerd.

1. Equivalentie van criteria: Het artikel toont aan dat het criterium dat wordt geminimaliseerd in Kernel Herding (MMD) wiskundig equivalent is aan de posterieure variantie van de integraalschatting in Bayesian Quadrature, uitgaande van een Gaussische Proces (GP) prior op $f$. Specifiek komt de verwachte fout in BQ overeen met de MMD tussen de doelverdeling $p$ en een discrete verdeling gedefinieerd door de monsters en hun gewichten.
2. Sequential Bayesian Quadrature (SBQ): Terwijl standaard Herding uniforme gewichten ($1/N$) aan monsters toekent, wijst BQ optimale gewichten toe die afgeleid zijn van de GP-posterieur. De auteurs stellen Sequential Bayesian Quadrature (SBQ) voor, een gulzig (greedy) algoritme dat monsterlocaties selecteert om de posterieure variantie te minimaliseren (equivalent aan het minimaliseren van MMD met optimale gewichten).
3. Gewichtsanalyse: Het artikel analyseert de eigenschappen van BQ-gewichten en merkt op dat deze niet noodzakelijkerwijs positief zijn en niet samen één vormen. Deze gewichten zijn aangetoond optimaal te zijn in een minimax-zin over de Reproducing Kernel Hilbert Space (RKHS) gedefinieerd door de kernel.
4. Submodulariteit: De auteurs onderzoeken de convergentie-eigenschappen van SBQ door het selectieproces te relateren aan het probleem van de ijle woordenboekselectie (sparse dictionary selection). Ze bewijzen dat de objectieve functie "bij benadering submodulair" is, wat theoretische grenzen mogelijk maakt voor de prestaties van de gulzige selectiestrategie, hoewel deze grenzen zwakker zijn dan die voor strikt submodulaire functies.

Belangrijkste bijdragen

1. Theoretische unificatie: Het artikel bewijst dat de verliesfunctie die door Kernel Herding wordt geminimaliseerd, identiek is aan de verwachte fout (posteriore variantie) in Bayesian Quadrature. Bij consequentie wordt BQ geframed als een gewogen versie van Kernel Herding waarbij de gewichten optimaal zijn voor de gegeven RKHS.
2. Optimaliteit van gewichten: Er wordt aangetoond dat de uit BQ afgeleide gewichten de uniform gewogen Herding en andere niet-optimaal gewogen herding-methoden domineren in termen van convergentiesnelheid.
3. Algoritmische verbinding: Het werk verbindt de gulzige selectie van monsters in BQ met het probleem van de ijle woordenboekselectie, waarbij wordt vastgesteld dat de objectieve functie bij benadering submodulair is.
4. Empirische validatie: De auteurs leveren empirisch bewijs dat SBQ een convergentiesnelheid bereikt die sneller is dan $O(1/N)$, waarmee zowel standaard Herding als i.i.d. willekeurige bemonstering overtreft in termen van Maximum Mean Discrepancy en integraalschattingfout.

Resultaten

• Convergentiesnelheden: In experimenten met een 2D mengeling van Gaussische verdelingen demonstreerde SBQ een convergentiesnelheid die superieur is aan de $O(1/N)$ snelheid die gewoonlijk geassocieerd wordt met Herding in eind-dimensionale ruimten. Hoewel de exacte theoretische snelheid voor SBQ in oneindig-dimensionale ruimten onbekend blijft, suggereren empirische resultaten dat het sneller is dan $O(1/N)$.
• Monster-efficiëntie: Het artikel illustreert dat een klein aantal SBQ-monsters (bijv. 8) met optimale gewichten dezelfde schattingsfout kan bereiken als een groter aantal Herding-monsters (bijv. 20) met uniforme gewichten.
• Robuustheid: Experimenten op functies buiten de veronderstelde RKHS lieten zien dat hoewel de theoretische garanties rusten op het feit dat de functie tot de RKHS behoort, de relatieve prestatierangorde van de methoden (SBQ > Herding > i.i.d.) consistent bleef, zelfs voor "out-of-model" functies.
• Foutgrenzen: De MMD biedt een bewijsbaar bovengrens op de empirische fout van de BQ-schatting, die snel afnam met het aantal monsters.

Betekenis en claims
Het artikel claimt dat Sequential Bayesian Quadrature een significante vooruitgang vormt ten opzichte van Kernel Herding door optimale weging te integreren in het monsternemingsproces. Door BQ te beschouwen als een optimaal gewogen Herding-methode, bieden de auteurs een verenigd theoretisch kader dat de superieure prestaties van BQ verklaart. Het werk benadrukt dat hoewel BQ een hogere computationele kosten met zich meebrengt ($O(N^3)$ voor gewichtsberekening versus $O(N^2)$ voor Herding), de snellere convergentiesnelheid het in scenario's waar functie-evaluaties duur zijn, efficiënter kan maken. De auteurs merken bescheiden op dat hoewel zij een bovengrens op de empirische fout vaststellen en een snellere-dan-$O(1/N)$ convergentie empirisch demonstreren, de theoretisch optimale convergentiesnelheid voor SBQ in oneindig-dimensionale ruimten een open vraag blijft voor toekomstig onderzoek. Het artikel concludeert dat de keuze van de methode afhangt van de afweging tussen computationele kosten en de kosten van het evalueren van de integraand $f$.