Der Gegenangriff der FFT: Eine effiziente Alternative zu Self-Attention

 (arxiv.org)
3 Punkte von GN⁺ 2025-02-27 | 1 Kommentare | Auf WhatsApp teilen
  • Der bestehende Self-Attention-Mechanismus hat eine Komplexität von O(n²) und ist bei langen Sequenzen nur begrenzt skalierbar
  • In dieser Arbeit wird FFTNet vorgeschlagen, das die Fast Fourier Transform (FFT) nutzt
  • FFTNet führt globale Token-Mischung mit einer Zeitkomplexität von O(n log n) aus
  • Im Frequenzbereich werden lernbare Spektralfilter und die modReLU-Aktivierungsfunktion eingeführt, um wichtige Frequenzkomponenten hervorzuheben
  • In Benchmarks auf Long Range Arena (LRA) und ImageNet zeigt es bessere Leistung als bestehende Self-Attention- und feste Fourier-Transformationsmodelle

Verwandte Forschung

  • Komplexität von Self-Attention: Transformer-Modelle benötigen einen Rechenaufwand von O(n²) und sind daher bei der Verarbeitung langer Sequenzen ineffizient
  • Fourier-basierte Ansätze: Modelle wie FNet reduzieren den Rechenaufwand durch feste Fourier-Transformationen, sind jedoch nur begrenzt anpassungsfähig an Eingaben
  • Lineare, spärliche und niedrigdimensionale Approximationsverfahren: Arbeiten wie Performer, Linformer und BigBird schlagen Methoden vor, die Berechnungen von Self-Attention approximieren
  • Orthogonale Matrixzerlegungsverfahren: Die Nutzung orthogonaler Transformationen (einschließlich DFT) verbessert die Stabilität beim Modelltraining
  • Adaptive Spektralfilterung: Durch das Hinzufügen lernbarer Filter zu FFT-basierten Transformationen wird der Ansatz flexibler und ausdrucksstärker als bisherige Verfahren

FFTNet: Verfahren zur adaptiven Spektralfilterung

Motivation

  • Self-Attention hat eine Komplexität von O(n²) und ist bei langen Sequenzen ineffizient
  • FFT arbeitet mit O(n log n) und kann globale Interaktionen effizient kodieren

Methodik

  • Fourier-Transformation (Anwendung von FFT)
    • Die Eingabesequenz wird in den Frequenzbereich transformiert, um globale Abhängigkeiten effizient zu erfassen
  • Anwendung adaptiver Spektralfilter
    • Mithilfe eines globalen Kontextvektors werden lernbare Filter erzeugt, die wichtige Frequenzbänder dynamisch hervorheben
  • modReLU-nichtlineare Aktivierung
    • Eine ReLU-basierte Aktivierung wird im komplexwertigen Frequenzbereich angewendet, um die Ausdrucksstärke zu erhöhen
  • Inverse Fourier-Transformation (IFFT)
    • Nach Filterung und Aktivierung der transformierten Daten werden diese zurück in den Zeitbereich transformiert

Theoretische Grundlage von FFTNet

  • Globale Token-Mischung ist mit einem Rechenaufwand von O(n log n) möglich
  • Adaptive Attention: Lernbare Filter im Frequenzbereich passen Frequenzen abhängig von der jeweiligen Eingabe an
  • Stärkere Ausdruckskraft durch nichtlineare Aktivierung: Durch modReLU wird das Lernen hochdimensionaler Muster möglich, die über einfache lineare Transformationen hinausgehen
  • Stabilitätsgarantie auf Basis des Parseval-Theorems: Die Energie des Signals bleibt erhalten, wodurch Informationsverlust minimiert wird

Experimentelle Ergebnisse

Long Range Arena (LRA)-Benchmark

  • FFTNet erzielt insgesamt eine höhere Genauigkeit als Transformer und FNet
  • Besonders bei den Aufgaben ListOps, Text, Retrieval, Image und Pathfinder zeigt es bessere Leistung und erreicht im Durchschnitt die höchste Punktzahl
  • Transformer zeigte bei einigen Aufgaben hohe Leistung, hatte jedoch Grenzen bei der Verarbeitung langfristiger Abhängigkeiten
  • FNet nutzt zwar FFT, zeigt aber insgesamt geringere Leistung, da der feste Transformationsansatz nicht ausreichend anpassungsfähig ist
  • Insbesondere bei der Path-X-Aufgabe scheiterte der Transformer an einem Speicherüberlauf (OOM), während FFTNet stabile Leistung zeigte

ImageNet-Klassifikationsexperiment

  • Der auf FFTNet basierende Vision Transformer (FFTNetViT) hält eine ähnliche Genauigkeit wie bestehende ViTs aufrecht und reduziert zugleich den Rechenaufwand (FLOPs) deutlich
  • Beim Base-Modell verwendet FFTNetViT rund 38 % weniger FLOPs als ViT und steigert die Genauigkeit dabei leicht
  • Auch bei den Large- und Huge-Modellen hält FFTNetViT bei geringerem Rechenaufwand im Vergleich zu ViT eine ähnliche Leistung
  • Damit lässt sich bestätigen, dass FFTNetViT eine hohe Recheneffizienz bietet

Ablation Study (Analyse der Bedeutung einzelner Komponenten)

  • Durch das Entfernen verschiedener Elemente von FFTNet wurde analysiert, wie sich diese auf die Modellleistung auswirken
  • Mit dem Entfernen zentraler Komponenten von FFTNet sinkt die Genauigkeit tendenziell
    • Entfernung des Spectral Gating: Die Funktion zur Hervorhebung bestimmter Frequenzen entfällt, wodurch die Genauigkeit leicht sinkt
    • Entfernung des adaptiven Moduls: Die Fähigkeit, Filter abhängig von der Eingabe dynamisch anzupassen, entfällt, was die Genauigkeit weiter verringert
    • Verwendung von Faltung statt FFT: Die effiziente Mischung globaler Informationen entfällt, was zum größten Leistungsabfall führt
  • Daraus wird ersichtlich, dass jede Komponente von FFTNet eine wichtige Rolle für die Leistungssteigerung spielt

Fazit

  • FFTNet ist eine recheneffizientere Alternative zu Self-Attention
  • Die Kombination aus adaptiven Spektralfiltern und modReLU im Frequenzbereich bietet starke Ausdruckskraft
  • Die Experimente zeigen, dass Leistung und Effizienz auf LRA und ImageNet besser sind als bei bestehenden Self-Attention-Modellen
  • Durch O(n log n)-Komplexität bei gleichzeitigem Leistungsniveau auf Self-Attention-Niveau eignet sich der Ansatz besonders für die Verarbeitung langer Sequenzen
  • Auch der auf FFTNet basierende Vision Transformer (FFTNetViT) erreicht mit geringeren FLOPs eine ViT-ähnliche Leistung

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-02-27
Hacker-News-Kommentare

  • Im Grunde nutzt es den Faltungssatz: Teure Faltungen im direkten Raum werden im reziproken Raum zu einfachen Multiplikationen

    • Wenn die Daten eine Faltungsoperation enthalten, werden sie in den konjugierten Bereich transformiert, um diese in eine Multiplikation umzuwandeln
    • Anders gesagt arbeitet man mit den Daten in einem natürlichen Bereich

  • Google stellte 2022 die Idee „FNet: Mixing Tokens with Fourier Transforms“ vor

    • Später stellte man fest, dass ihre TPUs in den meisten Szenarien bei Matrixmultiplikationen schneller als bei FFTs sind

  • Die Fourier-Transformation wird entlang der „Token“-Dimension ausgeführt. In vielen Anwendungen ist diese Dimension jedoch nicht sinnvoll

    • Daher sind Transformer eine hervorragende Option zur Verarbeitung permutationsinvarianter Daten
    • Ich würde gern weitere Experimente mit Fourier-Transformationen über weniger bekannte endliche Gruppen sehen
    • Falls das das nächste große Ding für LLMs wird, frage ich mich, wie leicht Inference-Engines (vLLM, llama.cpp usw.) das integrieren könnten

  • Die Mathematik ist so schwer, dass sie kaum zu verstehen ist. Ich wüsste gern, ob jemand in einfachem Englisch erklären kann, wie das dem Attention-Mechanismus entspricht, von welchen Frequenzen die Rede ist und wie Positionsbeziehungen zwischen Tokens codiert werden

  • Ich sehe nicht, wie sich kausales Masking in dieses Framework einfügen lässt. Es gibt auch keine Erwähnung von Positions-Embeddings, daher scheint die verglichene Self-Attention-Implementierung ein nicht-kausales NoPE zu sein

    • Wenn die Ergebnisse nahe am State of the Art gewesen wären, hätte der Autor das vermutlich erwähnt

  • Es gibt keinen Verweis auf den Hyena Operator, der schon vor einigen Jahren vollständiges Kontext-Mixing in O(n log n) demonstriert hat

  • Ich halte es für einen großen Fehler, im Zeitalter der Telemetrie nicht FFT auf Cloud-Telemetrie anzuwenden, um Epizyklen und metastabile Systeme zu finden, bevor sie für Drama sorgen

    • „SLA-Verletzungen treten 23–25 Minuten nach einem Service-Deployment am wahrscheinlichsten auf. Ich frage mich, warum ... oh nein.“

  • Ich frage mich, ob jemand eine Intuition dafür hat, warum es hilfreich ist, Dinge im Frequenzbereich zu betrachten

    • Den DC-Term verstehe ich, aber ich würde nicht erwarten, dass Eingabedaten so periodisch sind, dass andere Frequenzen sinnvoll wären

  • Ich verstehe die Big-O-Notation einigermaßen, aber wie die meisten Dinge rund um Informatik oder Elektrotechnik ist auch das schwer zu begreifen

    • Als jemand, der in Mathematik sehr schwach ist, beneide ich Menschen, die so etwas verstehen oder lernen können
    • Was ich über FFT weiß, ist, dass sie Signale transformiert, in gewisser Signalverarbeitung genutzt wird und früher eine wichtige Rolle bei der Erkennung von Atomexplosionen spielte

  • Ich verstehe nicht, warum Attention nötig ist. Auch ein vollständig verbundener Layer kann auf alle Eingaben „achten“

    • Bei sehr kleinen Datensätzen (0–500 Tokens) verlängert Attention das Training und verschlechtert die Ergebnisse
    • Der Nutzen scheint sich bei größeren Datensätzen zu zeigen
    • Ich bin KI-Anfänger und arbeite an einem persönlichen KI-Projekt, also ist das keine genaue Referenz