Accelerated training of Gaussian processes using banded square exponential covariances

Technische Samenvatting: Versnelde Training van Gaussische Processen met Gebandeerde Square Exponential Covarianten

Probleemstelling
Standaard Gaussische Proces (GP) regressie kampt met een computationele bottleneck door de $O(n^3)$ complexiteit die vereist is voor het inverteren van de covariantie-matrix $K_{f,f} + \sigma_n^2 I$ tijdens training en inferentie. Hoewel sparse GP-methoden (zoals Variational Free Energy (VFE) en Fully Independent Training Conditional (FITC)) deze complexiteit verminderen naar $O(nm^2)$ door het introduceren van $m \ll n$ inducerende variabelen, vereisen zij vaak een groot aantal inducerende punten om lange tijdreeksen nauwkeurig te modelleren. Deze vereiste kan de computationele winst tenietdoen, met name wanneer de latente functie complexe structuren vertoont die globale inducerende punten niet efficiënt kunnen vangen.

Methodologie: Banded Training Covariance (BTC)
De auteurs stellen een nieuwe aanpak voor genaamd Banded Training Covariance (BTC), die gebruikmaakt van de inherente benaderde ijlheid van de Square Exponential (SE) kernel. In 1D-instellingen met SE-kernels nemen de paarwijze covarianten exponentieel af naar nul naarmate de afstand tussen de punten toeneemt.

1. Gebandeerde Benadering: In plaats van inducerende variabelen te gebruiken, vervangt BTC de volledige covariantie-matrix $K_{f,f}$ door een $k$-gebandeerde benadering $L_k(K_{f,f})$. De operator $L_k$ zet alle vermeldingen $A_{ij}$ op nul waar $|i-j| > k$, wat impliceert dat observaties buiten een specifieke bandbreedte $k$ ongecorreleerd zijn.
2. Computationele Efficiëntie: Door deze gebandeerde structuur af te dwingen, kunnen de inverse en de log-determinant die vereist zijn voor de negatieve log-likelihood (NLL) worden berekend via LU- of Cholesky-decompositie tegen een gereduceerde kosten van $O(nk^2)$, zonder de introductie van variatiemparameters.
3. Theoretische Garanties: Het artikel biedt een rigoureus theoretisch kader om de optimale bandbreedte $k$ te bepalen die garandeert:
   • Positieve Definietheid: De benaderde matrix $L_k(K_{f,f}) + \sigma_n^2 I$ blijft symmetrisch en positief definit, een vereiste voor geldige probabilistische modellering en numerieke stabiliteit.
   • Geldige Voorspellende Distributie: De resulterende posterior predictieve covariantie blijft eveneens positief definit.
   • Onafhankelijkheid van Steekproefomvang: Cruciaal is dat de afgeleide grens voor $k$ afhankelijk is van kernel-hyperparameters (signaalvariantie $\sigma^2$, lengteschaal $\ell$) en ruisvariantie $\sigma_n^2$, maar niet van het aantal observaties $n$. Dit stelt de methode in staat om te schalen naar lange tijdreeksen zonder dat de bandbreedte proportioneel hoeft toe te nemen.

Belangrijkste Bijdragen

• Nieuwe Sparse Formulering: De introductie van BTC, een methode die de efficiëntie van sparse GP's bereikt ($O(nk^2)$) zonder inducerende variabelen, door gebruik te maken van de structurele ijlheid van de SE-kernel.
• Theoretische Grenzen: De afleiding van Lemma 3.1 en Theorem 3.2, die expliciete voorwaarden en een formule (Corollary 3.3) bieden voor het selecteren van de bandbreedte $k$ om positieve definitie voor SE-kernels met ruis te garanderen.
• Empirische Validatie: Uitgebreide experimenten die aantonen dat BTC de nauwkeurigheid van exacte full GPs evenaart, terwijl het standaard sparse methoden (VFE en FITC) aanzienlijk overtreft in zowel runtime als voorspellende prestaties op real-world datasets.

Experimentele Resultaten
De auteurs hebben BTC geëvalueerd op twee real-world datasets: de maandelijkse sunspots dataset (3.315 punten) en de Helsinki neonataal EEG dataset (4.000 punten).

• Prestaties vs. Runtime: Wat betreft de Normalized Mean Squared Error (NMSE) en Negative Log Predictive Density (NLPD), behaalde BTC resultaten die vrijwel identiek zijn aan exacte full GPs.
• Vergelijking met Benchmarks: BTC presteerde consistent beter dan zowel VFE als FITC over alle geteste configuraties van inducerende punten ($m$) en bandbreedtes ($k$).
• Robuustheid van $k$: De methode toonde robuuste prestaties over een reeks geldige bandbreedtes. De theoretische keuze van $k$ (afgeleid uit Corollary 3.3) bleek voldoende om positieve definitie en hoge nauwkeurigheid te behouden, wat bevestigt dat het vergroten van $k$ voorbij deze theoretische grens slechts marginale winst in nauwkeurigheid oplevert tegen hogere computationele kosten.
• Validatie van Theorie: Experimenten met synthetische data bevestigden dat de theoretisch afgeleide $k$-waarden succesvol de positieve definitie behielden, zelfs wanneer hyperparameters varieerden.

Betekenis en Claims
Het artikel claimt dat BTC een geprincipeerd, parameter-vrij alternatief biedt voor inducing-point methoden voor 1D GP-regressie met SE-kernels. Door gebruik te maken van de exponentiële afname van de kernel, bereikt BTC de computationele efficiëntie van sparse methoden ($O(nk^2)$) terwijl het de nauwkeurigheid van full GPs behoudt. De auteurs benadrukken dat hun aanpak de noodzaak elimineert om variatiemparameters (inducerende punten) te optimaliseren en een theoretisch onderbouwde regel biedt voor het selecteren van de bandbreedte die onafhankelijk schaalt van de datasetgrootte.

De auteurs merken op dat de huidige methode beperkt is tot de SE-kernel en een vaste bandbreedte tijdens optimalisatie veronderstelt. Zij identificeren het uitbreiden van de aanpak naar hogere dimensies en andere kernels als cruciaal toekomstig werk om de praktische toepasbaarheid te vergroten.