Accelerated training of Gaussian processes using banded square exponential covariances

Résumé technique : Accélération de l'entraînement des processus gaussiens à l'aide de covariances exponentielles carrées bandées

Énoncé du problème
La régression par processus gaussien (GP) standard fait face à un goulot d'étranglement computationnel dû à la complexité en $O(n^3)$ requise pour inverser la matrice de covariance $K_{f,f} + \sigma_n^2 I$ lors de l'entraînement et de l'inférence. Bien que les méthodes de GP parcimonieuses (par exemple, l'énergie libre variationnelle (VFE) et le conditionnement de formation indépendant complet (FITC)) réduisent cette complexité à $O(nm^2)$ en introduisant $m \ll n$ variables induites, elles nécessitent souvent un grand nombre de points induits pour modéliser précisément de longues séries temporelles. Cette exigence peut annuler les gains computationnels, particulièrement lorsque la fonction latente présente des structures complexes que les points induits globaux ne parviennent pas à capturer efficacement.

Méthodologie : Covariance d'entraînement bandée (BTC)
Les auteurs proposent une nouvelle approche nommée Bandeau de Covariance d'Entraînement (Banded Training Covariance - BTC), qui exploite la parcimonie approximative inhérente au noyau exponentiel carré (SE). Dans les configurations en 1D avec des noyaux SE, les covariances par paires décroissent exponentiellement vers zéro à mesure que la distance entre les points augmente.

1. Approximation bandée : Au lieu d'utiliser des variables induites, la BTC remplace la matrice de covariance complète $K_{f,f}$ par une approximation $k$-bandée $L_k(K_{f,f})$. L'opérateur $L_k$ définit toutes les entrées $A_{ij}$ comme étant nulles lorsque $|i-j| > k$, supposant ainsi que les observations sont non corrélées au-delà d'une largeur de bande $k$ spécifique.
2. Efficacité computationnelle : En imposant cette structure bandée, l'inverse et la log-déterminante requis pour la log-vraisemblance négative (NLL) peuvent être calculés via une décomposition LU ou de Cholesky à un coût réduit de $O(nk^2)$, évitant ainsi l'introduction de paramètres variationnels.
3. Garanties théoriques : L'article fournit un cadre théorique rigoureux pour déterminer la largeur de bande $k$ optimale garantissant :
   • La positivité définie : La matrice approximée $L_k(K_{f,f}) + \sigma_n^2 I$ reste symétrique et définie positive, une condition préalable pour une modélisation probabiliste valide et une stabilité numérique.
   • Une distribution prédictive valide : La covariance prédictive postérieure résultante reste définie positive.
   • L'indépendance vis-à-vis de la taille de l'échantillon : Crucialement, la borne dérivée pour $k$ dépend des hyperparamètres du noyau (variance du signal $\sigma^2$, longueur d'échelle $\ell$) et de la variance du bruit $\sigma_n^2$, mais non du nombre d'observations $n$. Cela permet à la méthode de s'adapter à de longues séries temporelles sans augmenter la largeur de bande proportionnellement.

Principales contributions

• Nouvelle formulation parcimonieuse : L'introduction de la BTC, une méthode qui atteint l'efficacité des GP parcimonieux sans variables induites, en s'appuyant sur la parcimonie structurelle du noyau SE.
• Bornes théoriques : La dérivation du Lemme 3.1 et du Théorème 3.2, qui fournissent des conditions explicites et une formule (Corollaire 3.3) pour sélectionner la largeur de bande $k$ afin de garantir la positivité définie pour les noyaux SE avec bruit.
• Validation empirique : Des expériences exhaustives démontrant que la BTC égale la précision des GP complets tout en surpassant significativement les méthodes de GP parcimonieuses standards (VFE et FITC) en termes de temps d'exécution et de performance prédictive sur des jeux de données réels.

Résultats expérimentaux
Les auteurs ont évalué la BTC sur deux jeux de données réels : le jeu de données des taches solaires mensuelles (3 315 points) et le jeu de données d'EEG néonatal d'Helsinki (4 000 points).

• Performance vs Temps d'exécution : En termes d'erreur quadratique moyenne normalisée (NMSE) et de densité prédictive logarithmique négative (NLPD), la BTC a obtenu des résultats quasi identiques aux GP complets exacts.
• Comparaison avec les références : La BTC a systématiquement surpassé tant la VFE que la FITC à travers toutes les configurations testées de points induits ($m$) et de largeurs de bande ($k$).
• Robustesse à $k$ : La méthode a démontré une performance robuste à travers une gamme de largeurs de bande valides. Le choix théorique de $k$ (dérivé du Corollaire 3.3) s'est avéré suffisant pour maintenir la positivité définie et une grande précision, confirmant qu'augmenter $k$ au-delà de cette borne théorique n'apporte que des gains de précision négligeables au prix d'une complexité computationnelle plus élevée.
• Validation de la théorie : Des expériences sur des données synthétiques ont confirmé que les valeurs de $k$ dérivées théoriquement préservaient avec succès la positivité définie, même lorsque les hyperparamètres variaient.

Signification et revendications
L'article affirme que la BTC offre une alternative fondée sur des principes et sans paramètres pour la régression GP en 1D avec des noyaux SE. En exploitant la décroissance exponentielle du noyau, la BTC atteint l'efficacité computationnelle des méthodes parcimonieuses ($O(nk^2)$) tout en maintenant la précision des GP complets. Les auteurs soulignent que leur approche élimine le besoin d'optimiser les paramètres variationnels (points induits) et fournit une règle théoriquement fondée pour sélectionner la largeur de bande qui s'adapte indépendamment de la taille du jeu de données.

Les auteurs notent que la méthode actuelle est restreinte au noyau SE et suppose une largeur de bande fixe pendant l'optimisation. Ils identifient l'extension de cette approche aux dimensions supérieures et à d'autres noyaux comme des travaux futurs clés pour élargir leur applicabilité pratique.