Accelerated training of Gaussian processes using banded square exponential covariances

Technische Zusammenfassung: Beschleunigtes Training von Gauß-Prozessen mittels gebundener quadratischer Exponentialkovarianzen

Problemstellung
Die Standard-Gauß-Prozess-Regression (GP) steht vor einem Rechenengpass durch die $O(n^3)$-Komplexität, die für die Invertierung der Kovarianzmatrix $K_{f,f} + \sigma_n^2 I$ während des Trainings und der Inferenz erforderlich ist. Während dünnbesetzte (sparse) GP-Methoden (z. B. Variational Free Energy (VFE) und Fully Independent Training Conditional (FITC)) diese Komplexität durch die Einführung von $m \ll n$ induzierenden Variablen auf $O(nm^2)$ reduzieren, erfordern sie oft eine große Anzahl an induzierenden Punkten, um lange Zeitreihen genau zu modellieren. Diese Anforderung kann die rechnerischen Vorteile zunichtemachen, insbesondere wenn die latente Funktion komplexe Strukturen aufweist, die globale induzierende Punkte nicht effizient erfassen können.

Methodik: Banded Training Covariance (BTC)
Die Autoren schlagen einen neuartigen Ansatz namens Banded Training Covariance (BTC) vor, der die inhärente approximative Sparsity des quadratischen Exponentialkerns (Square Exponential Kernel, SE) ausnutzt. In 1D-Konfigurationen mit SE-Kernen zerfallen die paarweisen Kovarianzen exponentiell gegen Null, wenn der Abstand zwischen den Punkten zunimmt.

1. Banded-Approximation: Anstatt induzierende Variablen zu verwenden, ersetzt BTC die volle Kovarianzmatrix $K_{f,f}$ durch eine $k$-gebundene Approximation $L_k(K_{f,f})$. Der Operator $L_k$ setzt alle Einträge $A_{ij}$ auf Null, falls $|i-j| > k$, was implizit davon ausgeht, dass Beobachtungen jenseits einer bestimmten Bandbreite $k$ unkorreliert sind.
2. Effizienz der Berechnung: Durch das Erzwingen dieser gebundenen Struktur können die Inversion und die Log-Determinante, die für die negative Log-Likelihood (NLL) benötigt werden, mittels LU- oder Cholesky-Zerlegung zu einem reduzierten Aufwand von $O(nk^2)$ berechnet werden, wodurch die Einführung von Variationsparametern vermieden wird.
3. Theoretische Garantien: Die Arbeit liefert einen rigorosen theoretischen Rahmen, um die optimale Bandbreite $k$ zu bestimmen, die sicherstellt:
   • Positive Definitheit: Die approximierte Matrix $L_k(K_{f,f}) + \sigma_n^2 I$ bleibt symmetrisch und positiv definit, eine Voraussetzung für valide probabilistische Modellierung und numerische Stabilität.
   • Valide prädiktive Verteilung: Die resultierende prädiktive Kovarianz der Posterior-Verteilung bleibt positiv definit.
   • Unabhängigkeit von der Stichprobengröße: Entscheidend ist, dass die abgeleitete Schranke für $k$ von den Kernel-Hyperparametern (Signanzvarianz $\sigma^2$, Längenskala $\ell$) und der Rauschvarianz $\sigma_n^2$ abhängt, jedoch nicht von der Anzahl der Beobachtungen $n$. Dies ermöglicht es der Methode, auf lange Zeitreihen zu skalieren, ohne die Bandbreite proportional zu erhöhen.

Zentrale Beiträge

• Neuartige Sparse-Formulierung: Die Einführung von BTC, einer Methode, die die Effizienz dünnbesetzter GPs ($O(nk^2)$) erreicht, ohne induzierende Variablen zu benötigen, indem sie sich auf die strukturelle Sparsity des SE-Kerns stützt.
• Theoretische Schranken: Die Ableitung von Lemma 3.1 und Theorem 3.2, die explizite Bedingungen und eine Formel (Korollar 3.3) zur Auswahl der Bandbreite $k$ liefern, um die positive Definitheit für SE-Kerne mit Rauschen zu garantieren.
• Empirische Validierung: Umfassende Experimente, die zeigen, dass BTC die Genauigkeit exakter voller GPs erreicht und gleichzeitig Standard-Sparse-Methoden (VFE und FITC) in Bezug auf Laufzeit und prädiktive Leistung auf realen Datensätzen übertrifft.

Experimentelle Ergebnisse
Die Autoren evaluierten BTC auf zwei realen Datensätzen: dem monatlichen Sonnenflecken-Datensatz (3.315 Punkte) und dem Helsinki-Neonatal-EEG-Datensatz (4.000 Punkte).

• Leistung vs. Laufzeit: In Bezug auf den normalisierten mittleren quadratischen Fehler (NMSE) und die negative Log-prädiktive Dichte (NLPD) erzielte BTC Ergebnisse, die nahezu identisch mit exakten vollen GPs sind.
• Vergleich mit Benchmarks: BTC übertraf sowohl VFE als auch FITC konsistent über alle getesteten Konfigurationen von induzierenden Punkten ($m$) und Bandbreiten ($k$) hinweg.
• Robustheit gegenüber $k$: Die Methode zeigte eine robuste Performance über einen Bereich valider Bandbreiten $k$. Die theoretische Wahl von $k$ (abgeleitet aus Korollar 3.3) erwies sich als ausreichend, um die positive Definitheit und hohe Genauigkeit aufrechtzuerhalten; zudem wurde gezeigt, dass eine Erhöhung von $k$ über diese theoretische Schranke hinaus vernachlässigbare Genauigkeitsgewinne auf Kosten einer höheren Komplexität liefert.
• Validierung der Theorie: Experimente mit synthetischen Daten bestätigten, dass die theoretisch abgeleiteten $k$-Werte die positive Definitheit erfolgreich bewahrten, selbst wenn die Hyperparameter variierten.

Bedeutung und Behauptungen
Die Autoren behaupten, dass BTC eine fundierte, parameterfreie Alternative zu Inducing-Point-Methoden für die 1D-GP-Regression mit SE-Kernen bietet. Durch die Nutzung des exponentiellen Abfalls des Kerns erreicht BTC die rechnerische Effizienz von Sparse-Methoden ($O(nk^2)$) bei gleichzeitiger Beibehaltung der Genauigkeit voller GPs. Die Autoren betonen, dass ihr Ansatz die Notwendigkeit der Optimierung von Variationsparametern (induzierende Punkte) eliminiert und eine theoretisch fundierte Regel zur Auswahl der Bandbreite bereitstellt, die unabhängig von der Datensatzgröße skaliert.

Die Autoren merken an, dass die aktuelle Methode auf den SE-Kern beschränkt ist und eine feste Bandbreite während der Optimierung annimmt. Sie identifizieren die Erweiterung des Ansatzes auf höhere Dimensionen und andere Kerne als zentrale zukünftige Arbeiten, um die praktische Anwendbarkeit zu verbreitern.