La contre-attaque de la FFT : une alternative efficace au Self-Attention

• Le mécanisme classique de Self-Attention présente une complexité de O(n²), ce qui limite sa capacité à passer à l’échelle sur les longues séquences
• Cet article propose FFTNet, qui exploite la Fast Fourier Transform (FFT)
• FFTNet réalise un mélange global des tokens avec une complexité temporelle de O(n log n)
• Il introduit des filtres spectraux entraînables et la fonction d’activation modReLU dans le domaine fréquentiel afin de mettre en avant les composantes de fréquence importantes
• Sur les benchmarks Long Range Arena (LRA) et ImageNet, il surpasse les modèles classiques à base de Self-Attention ainsi que les modèles à transformée de Fourier fixe

Travaux liés

• Complexité du Self-Attention : les modèles Transformer nécessitent une charge de calcul en O(n²), ce qui les rend inefficaces pour traiter de longues séquences
• Approches fondées sur Fourier : des modèles comme FNet ont réduit le coût de calcul en utilisant une transformée de Fourier fixe, mais manquent d’adaptabilité à l’entrée
• Techniques d’approximation linéaires, clairsemées et de faible rang : des travaux comme Performer, Linformer et BigBird proposent des méthodes pour approximer les calculs du Self-Attention
• Méthodes de décomposition en matrices orthogonales : l’utilisation de transformations orthogonales (y compris la DFT) améliore la stabilité de l’apprentissage
• Filtrage spectral adaptatif : l’ajout de filtres entraînables aux transformations basées sur la FFT offre une approche plus flexible et plus expressive que les méthodes précédentes

FFTNet : une méthode de filtrage spectral adaptatif

Motivation

• Le Self-Attention a une complexité de O(n²) et devient inefficace sur les longues séquences
• La FFT fonctionne en O(n log n) et permet d’encoder efficacement les interactions globales

Méthodologie

• Transformation de Fourier (application de la FFT)
  • La séquence d’entrée est convertie dans le domaine fréquentiel afin de capturer efficacement les dépendances globales
• Application d’un filtre spectral adaptatif
  • Un filtre entraînable est généré à l’aide d’un vecteur de contexte global, afin de mettre dynamiquement en avant les bandes de fréquence importantes
• Activation non linéaire modReLU
  • Une activation de type ReLU est appliquée dans le domaine fréquentiel complexe pour accroître la capacité de représentation
• Transformation de Fourier inverse (IFFT)
  • Après application du filtrage et de l’activation sur les données transformées, celles-ci sont reconverties dans le domaine temporel

Fondements théoriques de FFTNet

• Le mélange global des tokens est possible avec une charge de calcul de O(n log n)
• Attention adaptatif : dans le domaine fréquentiel, des filtres entraînables ajustent les fréquences en fonction de l’entrée fournie
• Renforcement du pouvoir de représentation grâce à l’activation non linéaire : l’application de modReLU permet d’apprendre des motifs de haut niveau au-delà d’une simple transformation linéaire
• Garantie de stabilité fondée sur le théorème de Parseval : l’énergie du signal est préservée afin de minimiser la perte d’information

Résultats expérimentaux

Benchmark Long Range Arena (LRA)

• FFTNet obtient globalement une précision supérieure à celle de Transformer et de FNet
• Il affiche notamment de meilleures performances sur les tâches ListOps, Text, Retrieval, Image et Pathfinder, avec le meilleur score moyen
• Transformer montre de bonnes performances sur certaines tâches, mais présente des limites pour traiter les dépendances à long terme
• FNet utilise bien la FFT, mais sa transformation fixe manque d’adaptabilité, ce qui se traduit par des performances globalement inférieures
• En particulier, sur la tâche Path-X, Transformer a échoué à cause d’un dépassement mémoire (OOM), tandis que FFTNet a conservé des performances stables

Expérience de classification sur ImageNet

• Le Vision Transformer basé sur FFTNet (FFTNetViT) parvient à réduire fortement le volume de calcul (FLOPs) tout en conservant une précision comparable à celle du ViT classique
• Pour le modèle Base, FFTNetViT utilise environ 38 % de FLOPs en moins que ViT, tout en améliorant légèrement la précision
• Sur les modèles Large et Huge également, FFTNetViT conserve des performances similaires à celles de ViT avec une charge de calcul plus faible
• Cela confirme que FFTNetViT offre une très forte efficacité de calcul

Ablation Study (analyse de l’importance des composants)

• L’étude analyse l’impact sur les performances du modèle lorsque différents éléments de FFTNet sont retirés
• Plus les composants clés de FFTNet sont supprimés, plus la précision tend à diminuer
  • Suppression du spectral gating : la disparition du mécanisme mettant en avant certaines fréquences entraîne une légère baisse de précision
  • Suppression du module adaptatif : la disparition de l’ajustement dynamique du filtre en fonction de l’entrée fait encore davantage baisser la précision
  • Utilisation d’une convolution à la place de la FFT : la capacité à mélanger efficacement l’information globale disparaît, ce qui provoque la plus forte dégradation des performances
• Cela montre que chacun des composants de FFTNet joue un rôle important dans l’amélioration des performances

Conclusion

• FFTNet constitue une alternative au Self-Attention offrant une meilleure efficacité de calcul
• La combinaison de filtres spectraux adaptatifs et de modReLU dans le domaine fréquentiel fournit une forte capacité de représentation
• Les résultats expérimentaux montrent des performances et une efficacité supérieures à celles des modèles classiques à base de Self-Attention sur LRA et ImageNet
• En conservant une complexité en O(n log n) tout en offrant des performances de niveau Self-Attention, FFTNet est bien adapté au traitement des longues séquences
• Le Vision Transformer fondé sur FFTNet (FFTNetViT) atteint lui aussi des performances proches de celles de ViT avec moins de FLOPs

• Dépôt de code : Lien GitHub

[GN⁺]

Commentaires Hacker News

• Cela s’appuie fondamentalement sur le théorème de convolution : une convolution coûteuse dans l’espace direct devient une simple multiplication dans l’espace dual

  • Lorsqu’il y a une opération de convolution sur les données, on les transforme dans le domaine conjugué pour convertir cela en multiplication
  • Autrement dit, on travaille sur les données dans leur domaine naturel

• Google a présenté en 2022 l’idée intitulée "FNet: Mixing Tokens with Fourier Transforms"

  • Ils ont ensuite découvert que leurs TPU étaient plus rapides en multiplication matricielle qu’en FFT dans la plupart des scénarios

• La transformée de Fourier est appliquée sur la dimension des « tokens ». Or, dans de nombreuses applications, cette dimension n’a pas de signification particulière

  • Les transformeurs constituent donc une excellente option pour traiter des données invariantes par permutation
  • J’aimerais voir davantage d’expériences utilisant des transformées de Fourier sur des groupes finis moins connus
  • Si cela devient la prochaine grande avancée pour les LLMs, je me demande à quel point il sera facile pour les moteurs d’inférence (vLLM, llama.cpp, etc.) de l’intégrer

• Les maths sont trop difficiles à suivre. Je me demande si quelqu’un pourrait expliquer en anglais simple en quoi cela est équivalent au mécanisme d’attention, de quelles fréquences il s’agit, et comment les relations de position entre les tokens sont encodées

• Je ne vois pas comment intégrer un masquage causal dans ce framework. Il n’y a pas non plus de mention des embeddings de position, donc j’ai l’impression que l’implémentation de self-attention utilisée pour la comparaison est un NoPE non causal

  • Si les résultats avaient été proches de l’état de l’art, l’auteur l’aurait probablement mentionné

• Il n’y a aucune mention de l’Hyena Operator, qui avait déjà démontré il y a quelques années un mélange de contexte global en O(n log n)

• À l’ère de la télémétrie, je pense que ne pas appliquer la FFT à la télémétrie cloud pour repérer des épicycles et des systèmes quasi stables avant qu’ils ne déclenchent du drame est une grosse erreur

  • "Les SLA ont le plus de chances d’être violés 23 à 25 minutes après le déploiement du service. Je me demande pourquoi... oh non."

• Je me demande si quelqu’un a une intuition sur la raison pour laquelle il peut être utile d’observer les choses dans le domaine fréquentiel

  • Je comprends le terme DC, mais je ne m’attends pas à ce que les données d’entrée soient suffisamment périodiques pour que d’autres fréquences aient un sens

• Je comprends à peu près la notation grand O, mais comme pour la plupart des choses liées à l’informatique ou au génie électrique, cela reste difficile à saisir

  • Comme je suis très faible en maths, j’envie les gens capables de comprendre ou d’apprendre ce genre de choses
  • Ce que je sais de la FFT, c’est qu’elle transforme les signaux, qu’elle sert dans certains traitements du signal, et qu’elle a joué un rôle important autrefois dans la détection des explosions nucléaires

• Je ne comprends pas pourquoi l’attention est nécessaire. Une couche entièrement connectée peut aussi « prêter attention » à toutes les entrées

  • Sur des jeux de données très petits (0 à 500 tokens), l’attention allonge l’entraînement et donne de moins bons résultats
  • Les avantages semblent apparaître sur des jeux de données plus grands
  • Je débute en IA et je travaille sur un projet d’IA personnel, donc ce n’est pas une référence très fiable