🤖 machine learning

LAPLEX: The FFT of Learnable Laplace Kernels

LAPLEX introduit une classe d'opérateurs exacts et entraînables à noyau de Laplace qui atteignent une mise à l'échelle de type FFT pour permettre des interactions globales adaptatives aux données et une modélisation de covariance de haute dimension sans les coûts de stockage des matrices denses, séparant ainsi efficacement l'expressivité des exigences de mémoire.

Auteurs originaux : Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

Publié 2026-05-26

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Łukasz Struski, Hanna Blazhko, Piotr Kubaty, Jacek Tabor

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez d'organiser une bibliothèque massive contenant des milliards de livres. Dans le monde de l'intelligence artificielle moderne, les « livres » ne sont que des nombres (points de données), et « organiser » signifie effectuer des calculs mathématiques complexes pour trouver des motifs.

Habituellement, lorsque l'IA tente de le faire à grande échelle, elle fait face à un choix frustrant :

Le Bibliothécaire Rigide (Géométrie Fixe) : Comme un catalogue de bibliothèque standard, il est rapide et exact, mais les étagères sont fixes. Vous ne pouvez pas déplacer un livre vers un meilleur endroit en fonction de ce que vous recherchez. (C'est comme la FFT ou Transformée de Fourier).
Le Bibliothécaire Flexible mais Lourde (Paramètres Denses) : Ce bibliothécait peut réarranger les étagères comme il le souhaite pour adapter parfaitement les livres, mais pour ce faire, il a besoin d'un immense entrepôt pour stocker les instructions pour chaque livre individuel. Si la bibliothèque devient trop grande, l'entrepôt manque d'espace et le système s'effondre. (Il s'agit d'une Matrice Dense standard).
Le Bibliothécaire Approximatif (Faible Rang/Sketching) : Ce bibliothécaire tente d'économiser de l'espace en ne se souvenant que de la « vibe générale » des livres ou en utilisant un jeu de devinettes aléatoires. C'est rapide et cela tient dans l'entrepôt, mais il perd les détails exacts et ne peut pas apprendre la meilleure organisation.

LAPLEX est un nouveau type de bibliothécaire qui brise ce compromis. Il prétend être la solution « Boucle d'Or » : il est exact, il est entraînable (il peut apprendre la meilleure organisation) et il est léger (il n'a pas besoin d'un immense entrepôt).

Voici comment cela fonctionne, en utilisant des analogies simples :

1. Le Secret : Apprendre les « Coordonnées » au lieu de la « Carte »

Imaginez que vous avez une immense carte d'une ville avec des millions de rues.

L'Ancienne Méthode : Pour connaître la distance entre chaque paire de rues, vous devriez écrire un nombre pour chaque paire individuelle. Pour une ville avec 1 million de rues, cela représente un trillion de nombres. Vous ne pouvez pas stocker cela.
La Méthode LAPLEX : Au lieu d'écrire chaque distance, LAPLEX écrit simplement une liste de « points d'ancrage » (comme des points de repère majeurs). Il utilise ensuite une règle mathématique astucieuse (le Noyau de Laplace) pour calculer la distance entre n'importe deux points en fonction de leur proximité avec ces points de repère.

Parce que la règle est si simple, LAPLEX n'a pas besoin de stocker le trillion de nombres. Il doit seulement stocker la liste des points de repère. Mais voici la magie : il peut apprendre où placer ces points de repère. Si les données suggèrent que « la Rue A » et « la Rue B » sont souvent liées, LAPLEX apprend à déplacer ses points de repère afin que A et B se retrouvent proches l'un de l'autre dans sa logique interne.

2. L'Astuce du « Scan » : Faire des Mathématiques sans le Travail Lourde

L'article affirme que même si LAPLEX agit comme une carte dense et géante, il peut effectuer les calculs incroyablement rapidement.

Pensez-y comme à un tapis roulant dans une usine.

La Méthode Dense : Pour calculer le résultat d'un élément, vous devez vous arrêter, regarder chaque autre élément dans l'entrepôt et effectuer un calcul. Cela devient de plus en plus lent à mesure que l'entrepôt grandit.
La Méthode LAPLEX : Il trie d'abord les éléments sur le tapis roulant. Ensuite, il utilise une technique de « scan ». Imaginez un travailleur marchant le long de la ligne qui doit seulement se souvenir du total cumulé de ce qu'il a vu jusqu'à présent. Parce que les mathématiques du noyau de Laplace sont exponentielles (les choses deviennent très petites très rapidement à mesure que l'on s'éloigne), le travailleur peut calculer le résultat final pour toute la ligne en regardant simplement le « préfixe » (ce qui est venu avant) et le « suffixe » (ce qui vient après).

Cela permet à LAPLEX de gérer des dimensions allant jusqu'à 1 milliard (10⁹) sur des ordinateurs modernes, une taille où la méthode « Dense » manquerait immédiatement de mémoire.

3. Ce qu'il Fait Réellement (Les Expériences)

L'article teste ce « bibliothécaire » dans trois scénarios spécifiques pour prouver qu'il fonctionne :

Le Test « Image Aplatie » : Ils ont pris des photos haute résolution (des millions de pixels), les ont aplaties en une seule longue ligne de nombres (en ignorant la grille 2D), et ont tenté de modéliser les données.
- Résultat : Un modèle « faible rang » standard (le bibliothécaire approximatif) a échoué à voir que les pixels voisins dans la photo originale devraient être liés ; il n'a vu que du bruit. LAPLEX, cependant, a appris à placer ses « points d'ancrage » d'une manière qui préservait les formes des images (comme une plage ou un palmier) même s'il n'avait jamais vu l'image comme une grille. Il a appris la géométrie des données sans qu'on lui dise ce qu'est une grille.
Le Test « Tête de Classification » : Ils ont essayé de remplacer la dernière couche d'un réseau de neurones (la partie qui décide « est-ce un chat ou un chien ? ») par LAPLEX.
- Résultat : En utilisant seulement une infime fraction des paramètres (comme 1 à 5 % de la taille habituelle), LAPLEX a performé presque aussi bien que le réseau massif et pleine taille. Il a appris à acheminer l'information bien mieux que les raccourcis « faible rang » standards.
Le Test « Vitesse » : Ils ont comparé sa vitesse d'exécution sur un supercalculateur (GPU).
- Résultat : LAPLEX est environ 65 fois plus rapide que la méthode standard pour les passages avant et 430 fois plus rapide pour l'entraînement (passage avant + arrière) sur de grands ensembles de données. Il utilise également 100 fois moins de mémoire.

4. Pourquoi Cela Compte (En Termes Simples)

L'article soutient que pendant longtemps, nous pensions devoir choisir entre vitesse/taille et précision/flexibilité.

Si vous vouliez de la vitesse, vous deviez utiliser des règles fixes (comme la FFT) ou des devinettes aléatoires.
Si vous vouliez apprendre les meilleures règles, vous deviez utiliser tellement de mémoire que vous ne pouviez pas l'exécuter sur de grandes données.

LAPLEX dit : « Vous n'avez pas à choisir. » En traitant les coordonnées des données comme des variables apprenables plutôt que comme des emplacements fixes, il crée un système qui est :

Exact : Il ne devine pas ; il calcule la vraie mathématique.
Entraînable : Il s'adapte aux données spécifiques qu'il voit.
Efficace : Il tient sur du matériel qui sinon s'effondrerait.

Analogie de Résumé

Imaginez que vous essayiez d'organiser une immense fête où des millions d'invités doivent trouver leurs places.

Matrice Dense : Vous imprimez un gigantesque plan de salle avec le nom de chaque invité à côté du nom de chaque autre invité. C'est parfait, mais la pile de papier est trop lourde à porter.
Faible Rang/Sketch : Vous dites simplement aux invités de s'asseoir dans la « Zone A » ou la « Zone B » au hasard. C'est léger, mais l'assise est désordonnée et inefficace.
LAPLEX : Vous donnez aux invités quelques « ancres magnétiques » (comme des tables VIP). Vous enseignez aux invités de s'asseoir en fonction de leur proximité avec ces ancres. Les ancres se déplacent pendant la fête pour trouver les meilleurs endroits. Vous n'avez pas besoin d'un gigantesque plan ; vous avez juste besoin de la liste des ancres. Les invités trouvent leurs places instantanément, l'organisation est parfaite, et vous pouvez porter tout le plan dans votre poche.

L'article conclut que cette approche permet à l'IA de gérer des interactions « denses » (où tout parle à tout) à des échelles précédemment impossibles, sans sacrifier la capacité d'apprendre à partir des données.

Résumé Technique : LAPLEX – La FFT des Kernels Laplaciens Apprenables

1. Énoncé du Problème

Les systèmes modernes d'apprentissage automatique opèrent de plus en plus dans des régimes où les dimensions ambiantes atteignent des millions ou des milliards. Dans ces contextes de haute dimension, le goulot d'étranglement réside souvent dans le coût en temps réel et l'empreinte mémoire des opérations linéaires, telles que l'application de matrices denses, le calcul d'opérateurs de Gram et le mélange de caractéristiques.

Les approches existantes pour mettre à l'échelle l'algèbre linéaire sacrifient généralement l'une des trois propriétés souhaitables suivantes : l'exactitude, la capacité d'apprentissage ou une mise à l'échelle quasi-linéaire.

Les méthodes de faible rang (par exemple, LoRA) conservent des interactions denses dépendantes de la base, mais souffrent d'une empreinte mémoire de $O(nk)$ car elles doivent stocker les coefficients pour la base d'entrée, même si le rang de sortie est compressé.
Les esquisses aléatoires et les caractéristiques aléatoires (par exemple, CountSketch, Random Fourier Features) offrent une évolutivité mais agissent sur un indexage fixe ou approximent le noyau, échangeant l'exactitude contre l'efficacité. Elles ne peuvent pas adapter la manière dont les coordonnées sont appariées.
Les méthodes creuses peuvent briser la régularité matérielle et sont difficiles à entraîner de bout en bout.
Les transformées rapides classiques (par exemple, FFT) sont exactes et peu coûteuses ( $O(n \log n)$ ) mais sont fixes à une géométrie de grille spécifique et ne peuvent pas apprendre le système de coordonnées.

La limitation fondamentale identifiée est la dépendance à la base : les opérateurs standards paramètrent directement les valeurs de la matrice, nécessitant un stockage proportionnel à la dimension d'entrée. L'article plaide pour un passage à des opérateurs au niveau de l'index capables d'apprendre la géométrie d'entrée elle-même sans stocker de matrice dense.

2. Méthodologie : LAPLEX

Les auteurs introduisent LAPLEX, une classe d'opérateurs exacts et entraînables basés sur le noyau Laplacien. Une couche LAPLEX est définie implicitement par des ancres de coordonnées apprenables plutôt que par des poids de matrice explicites.

2.1 L'Opérateur

Le primitif de base est la matrice de noyau Laplacien définie par deux ensembles d'ancres apprenables, $a \in \mathbb{R}^n$ et $b \in \mathbb{R}^k$ :
$\text{LAPLEX}(a, b)_{ij} = \exp(-|a_i - b_j|)$
Dans un régime limite naturel (température $t \to 0$ ), cet opérateur encode toutes les permutations de l'ensemble des coordonnées. En ajoutant des paramètres de phase $\phi, \psi$ , l'opérateur peut être étendu à :
$\text{LAPLEX}(a, \phi; b, \psi)_{jk} = \exp(-|a_j - b_k|) \cdot \cos(\phi_j - \psi_k)$
Cela permet à l'opérateur de fonctionner comme une matrice dense et entraînable tout en n'utilisant que $O(n)$ paramètres (les ancres).

2.2 Algèbre de Scan Exacte

La contribution algorithmique clé est un algorithme exact, entièrement parallèle et en $O(n \log n)$ pour les produits matrice-vecteur et Gram, qui ne matérialise jamais la matrice dense.

Cas Symétrique ( $a=b$ ) : Après avoir trié les ancres, la matrice de noyau se décompose en parties triangulaires inférieures et supérieures. Chaque partie peut être calculée via une récurrence de scan-préfixe et scan-suffixe. Par exemple, le produit triangulaire inférieur $y_i = \sum_{j \le i} \exp(a_j - a_i)x_j$ satisfait une récurrence $y_{i+1} = x_{i+1} + \exp(a_i - a_{i+1})y_i$ , qui est évaluée en $O(n)$ travail et $O(\log n)$ profondeur parallèle.
Cas Général ( $a \neq b$ ) : L'algorithme agrège les contributions des ancres $b$ dans des intervalles définis par les ancres $a$ triées. Les contributions locales sont résumées en vecteurs $u$ et $v$ , qui sont ensuite propagés globalement en utilisant le primitif de scan symétrique.
Opérateurs de Gram : La même structure de tri permet le calcul exact de matrices de Gram pondérées $M = A \text{diag}(D) A^\top$ en $O(n^2 + k \log n)$ temps, évitant le coût naïf de $O(n^2 k)$ . Ceci est crucial pour l'optimisation du second ordre et les méthodes à noyaux.

2.3 Expressivité et Limites

L'article établit que LAPLEX est une famille continue interpolant entre différentes classes d'opérateurs :

Limite de Température Zéro : À mesure que le paramètre de température tend vers zéro, le noyau lisse converge vers une matrice de routage d'égalité discrète, retrouvant CountSketch et des permutations arbitraires.
Universalité : Avec des mises à l'échelle diagonales et une réplication creuse, la famille est universelle pour les matrices denses rectangulaires arbitraires.
Relation avec la FFT : Si les ancres sont figées sur une grille uniforme, LAPLEX devient une matrice de Toeplitz, et l'algorithme se réduit à Toeplitz-FFT. Si le noyau est remplacé par un développement spectral fini, il devient Random Fourier Features (RFF). LAPLEX conserve l'exactitude et la différentiabilité par rapport aux ancres, contrairement aux RFF qui souffrent d'une variance de gradient non bornée due à la densité spectrale de Cauchy à queue lourde du noyau Laplacien.

3. Contributions Clés

Identification de la Dépendance à la Base : L'article motive les opérateurs au niveau de l'index, conscients des permutations, comme une alternative fondée sur des principes aux méthodes de faible rang, qui ne peuvent échapper aux empreintes mémoire de $O(nk)$ car elles ne compressent pas la base d'entrée.
Géométrie Apprenable : Il démontre que la matrice de noyau Laplacien encode toutes les permutations de coordonnées dans un régime limite naturel tout en n'utilisant que $O(n)$ paramètres.
Algorithmes Exacts et Évolutifs : Les auteurs fournissent un algorithme exact, entièrement parallèle et en $O(n \log n)$ pour les produits matrice-vecteur et Gram utilisant $O(n)$ de mémoire. Cela permet des dimensions jusqu'à $10^9$ sur les GPU modernes sans matérialiser la matrice.
Validation Empirique : L'article montre que LAPLEX correspond à une mise à l'échelle de classe FFT tout en fonctionnant efficacement comme une couche structurée de remplacement. Il surpasse les bases denses en mémoire et en vitesse, et dépasse les bases de faible rang et de caractéristiques aléatoires en précision et en stabilité du gradient.

4. Résultats Expérimentaux

4.1 Mise à l'Échelle et Performance

Mise à l'Échelle GPU : Sur NVIDIA H100 et RTX 2080, LAPLEX s'étend de manière fluide jusqu'à $n = 2^{20}$ (environ 1 million d'éléments), tandis que les bases denses épuisent la mémoire (OOM) à $n = 2^{14}$ .
Vitesse : À la plus grande taille où les deux méthodes fonctionnent ( $n=2^{14}$ ), LAPLEX est $\sim 65\times$ plus rapide sur le passage avant et $\sim 430\times$ plus rapide sur le passage avant + arrière par rapport au produit matriciel dense.
Mémoire : LAPLEX utilise $\sim 100\times$ moins de mémoire de pointe que la base dense.
Précision Numérique : Bien qu'exécuté en float32, LAPLEX présente une erreur relative plus faible par rapport à une référence float64 que le produit matriciel dense float32 et Toeplitz-FFT. Cela est attribué à la capacité de l'algorithme de scan à maintenir les facteurs d'échelle exponentiels séparés des mantisses, évitant l'accumulation d'erreur $O(n \epsilon)$ de la sommation dense.

4.2 Modélisation de Densité en Haute Dimension

Les auteurs ont entraîné un modèle de densité gaussienne sur des images DIV2K aplaties (dimension $3 \cdot 10^6$ ) en utilisant un opérateur de Gram exact.

Configuration : Comparaison d'un facteur LAPLEX (rang 1000, $\sim 14$ M paramètres) contre une base de faible rang dense (rang 4, $\sim 15$ M paramètres).
Résultat : La base dense s'est effondrée en bruit uniforme en raison d'un rang insuffisant. Le modèle LAPLEX a appris des structures spatiales de couleurs cohérentes (régions contiguës, silhouettes) malgré le fonctionnement sur des vecteurs aplatis sans biais convolutif. La vraisemblance logarithmique de test était $4,5\times$ supérieure à celle de la base dense.

4.3 Projections Structurées et Classification

Projections ImageNet10 : Dans un cadre de projection figée (images aplaties de dimension $150\,528$ vers $m \in \{25, \dots, 1000\}$ ), LAPLEX était plus stable que CountSketch et les Projections Aléatoires, et est devenu le meilleur performant pour les grandes valeurs de $m$ .
Têtes Entraînables : Lorsqu'il est utilisé comme tête de classification pour Swin-T et MaxViT-T, LAPLEX correspondait ou dépassait la précision des projections denses non contraintes à la même dimension de sortie, en utilisant $\Theta(m+d)$ paramètres au lieu de $\Theta(md)$ . À faibles rangs, LAPLEX surperformait significativement la factorisation de faible rang (style LoRA).

5. Signification et Revendications

L'article revendique que LAPLEX sépare l'expressivité du coût de stockage. Il se comporte comme une matrice entraînable dense mais est représentée et appliquée via un petit ensemble structuré de paramètres (ancres).

Séparation de l'Expressivité et du Stockage : Une géométrie dense peut être apprise sans stocker de matrice dense. Cela permet des interactions globales adaptatives aux données dans des régimes où les couches denses ordinaires sont irréalisables.
Exactitude vs Approximation : Contrairement aux Random Fourier Features ou aux méthodes de Nyström, LAPLEX fournit une application de noyau exacte et un calcul de Gram. Il évite les compromis valeur/gradients des caractéristiques aléatoires, en particulier la variance non bornée dans les gradients d'ancres causée par la densité spectrale de Cauchy.
Transformées Rapides Apprenables : Le travail démontre que les transformées rapides n'ont pas à vivre sur des systèmes de coordonnées fixes. En paramétrant un opérateur dense via des ancres Laplaciennes apprenables, la géométrie elle-même devient un paramètre différentiable.

6. Limitations

Les auteurs reconnaissent les limitations suivantes :

Dimensionnalité : La construction actuelle utilise des ancres Laplaciennes unidimensionnelles et des algorithmes basés sur le tri. Étendre cette exactitude à des géométries d'ancres de dimensions supérieures et à des noyaux plus riches est une direction mathématique ouverte.
Maturité des Systèmes : L'implémentation démontre le régime algorithmique, mais les blocs d'attention à grande échelle, les optimiseurs et les modèles génératifs nécessiteront des noyaux spécialisés et une conception d'architecture minutieuse.
Portée : La méthode est actuellement limitée au noyau Laplacien et à sa décomposition spécifique basée sur le scan.

En résumé, LAPLEX offre une alternative fondée sur des principes aux méthodes de faible rang et aléatoires, permettant une algèbre linéaire exacte, apprenable et évolutive dans les régimes de haute dimension en passant de la paramétrisation des matrices à la paramétrisation des interactions d'index.