Serangan Balik FFT: Alternatif Efisien untuk Self-Attention

 (arxiv.org)
3 poin oleh GN⁺ 2025-02-27 | 1 komentar | Bagikan ke WhatsApp
  • Mekanisme Self-Attention yang ada saat ini memiliki kompleksitas O(n²), sehingga skalabilitasnya terbatas untuk sekuens panjang
  • Makalah ini mengusulkan FFTNet yang memanfaatkan Fast Fourier Transform (FFT)
  • FFTNet melakukan pencampuran token global dengan kompleksitas waktu O(n log n)
  • Dengan memperkenalkan filter spektral yang dapat dipelajari dan fungsi aktivasi modReLU di domain frekuensi, komponen frekuensi yang penting dapat lebih ditonjolkan
  • Dalam eksperimen benchmark Long Range Arena (LRA) dan ImageNet, model ini menunjukkan kinerja yang lebih baik dibandingkan model Self-Attention yang ada serta model transformasi Fourier tetap

Riset terkait

  • Kompleksitas Self-Attention: Model Transformer membutuhkan komputasi O(n²), sehingga tidak efisien untuk memproses sekuens panjang
  • Pendekatan berbasis Fourier: Model seperti FNet memanfaatkan transformasi Fourier tetap untuk mengurangi komputasi, tetapi kurang adaptif terhadap input
  • Teknik aproksimasi linear, sparse, dan berdimensi rendah: Riset seperti Performer, Linformer, dan BigBird mengusulkan cara untuk mengaproksimasi komputasi Self-Attention
  • Teknik dekomposisi matriks ortogonal: Pemanfaatan transformasi ortogonal (termasuk DFT) membantu meningkatkan stabilitas pelatihan model
  • Penyaringan spektral adaptif: Dengan menambahkan filter yang dapat dipelajari pada transformasi berbasis FFT, pendekatan ini menjadi lebih fleksibel dan lebih ekspresif dibandingkan metode sebelumnya

FFTNet: teknik penyaringan spektral adaptif

Motivasi

  • Self-Attention memiliki kompleksitas O(n²) dan tidak efisien pada sekuens panjang
  • FFT bekerja dalam O(n log n) dan dapat mengodekan interaksi global secara efisien

Metodologi

  • Transformasi Fourier (menerapkan FFT)
    • Mengubah sekuens input ke domain frekuensi untuk menangkap ketergantungan global secara efisien
  • Penerapan filter spektral adaptif
    • Menggunakan vektor konteks global untuk menghasilkan filter yang dapat dipelajari, lalu secara dinamis menonjolkan pita frekuensi yang penting
  • Aktivasi nonlinier modReLU
    • Menerapkan aktivasi berbasis ReLU di domain frekuensi kompleks untuk meningkatkan daya representasi
  • Transformasi Fourier invers (IFFT)
    • Setelah filtering dan aktivasi diterapkan pada data yang telah ditransformasikan, data dikembalikan ke domain waktu

Landasan teoretis FFTNet

  • Pencampuran token global dimungkinkan dengan komputasi O(n log n)
  • Attention adaptif: filter yang dapat dipelajari di domain frekuensi menyesuaikan frekuensi berdasarkan input yang diberikan
  • Peningkatan daya representasi dari aktivasi nonlinier: penerapan modReLU memungkinkan pembelajaran pola berdimensi tinggi yang melampaui transformasi linear sederhana
  • Jaminan stabilitas berbasis Parseval's theorem: menjaga energi sinyal agar kehilangan informasi diminimalkan

Hasil eksperimen

Benchmark Long Range Arena (LRA)

  • FFTNet mencatat akurasi yang secara keseluruhan lebih tinggi dibandingkan Transformer dan FNet
  • Khususnya pada tugas ListOps, Text, Retrieval, Image, dan Pathfinder, model ini menunjukkan kinerja yang lebih baik dan mencatat skor rata-rata tertinggi
  • Transformer menunjukkan kinerja tinggi pada beberapa tugas, tetapi memiliki keterbatasan dalam menangani ketergantungan jangka panjang
  • FNet memang memanfaatkan FFT, tetapi karena menggunakan transformasi tetap yang kurang adaptif, performanya secara keseluruhan lebih rendah
  • Khusus pada tugas Path-X, Transformer gagal karena kehabisan memori (OOM), sedangkan FFTNet menunjukkan kinerja yang stabil

Eksperimen klasifikasi ImageNet

  • Vision Transformer berbasis FFTNet (FFTNetViT) berhasil mempertahankan akurasi yang mirip dengan ViT yang ada sambil secara signifikan mengurangi komputasi (FLOPs)
  • Pada model Base, FFTNetViT menggunakan sekitar 38% lebih sedikit FLOPs dibandingkan ViT, sambil sedikit meningkatkan akurasi
  • Pada model Large dan Huge juga, FFTNetViT mempertahankan kinerja serupa dengan ViT dengan komputasi yang lebih rendah
  • Hal ini menunjukkan bahwa FFTNetViT menawarkan efisiensi komputasi yang tinggi

Ablation Study (analisis pentingnya tiap komponen)

  • Dengan menghapus berbagai elemen FFTNet, peneliti menganalisis dampaknya terhadap kinerja model
  • Semakin banyak komponen utama FFTNet yang dihilangkan, akurasi cenderung menurun
    • Menghapus spectral gating: saat fungsi untuk menonjolkan frekuensi tertentu hilang, akurasi sedikit menurun
    • Menghapus modul adaptif: saat fungsi untuk menyesuaikan filter secara dinamis berdasarkan input hilang, akurasi turun lebih jauh
    • Menggunakan konvolusi alih-alih FFT: karena kemampuan mencampur informasi global secara efisien hilang, penurunan kinerja terbesar terjadi
  • Ini menunjukkan bahwa setiap elemen FFTNet berperan penting dalam peningkatan kinerja

Kesimpulan

  • FFTNet adalah alternatif yang lebih efisien secara komputasi dibandingkan Self-Attention
  • Dengan menggabungkan filter spektral adaptif dan modReLU di domain frekuensi, model ini memberikan daya representasi yang kuat
  • Hasil eksperimen menunjukkan bahwa kinerja dan efisiensinya lebih baik daripada model Self-Attention yang ada pada LRA dan ImageNet
  • Dengan tetap mempertahankan kompleksitas O(n log n), model ini memberikan kinerja setara tingkat Self-Attention, sehingga cocok untuk pemrosesan sekuens panjang
  • Vision Transformer berbasis FFTNet (FFTNetViT) juga mencapai kinerja yang mirip dengan ViT dengan FLOPs yang lebih rendah

Bacaan terkait

1 komentar

 
GN⁺ 2025-02-27
Komentar Hacker News

  • Pada dasarnya ini memanfaatkan teorema konvolusi: konvolusi yang mahal di ruang langsung menjadi perkalian sederhana di ruang dual

    • Saat ada operasi konvolusi pada data, data tersebut diubah ke domain konjugat untuk mengubahnya menjadi perkalian
    • Artinya, bekerja pada data di domain yang alami baginya

  • Google memperkenalkan ide berjudul "FNet: Mixing Tokens with Fourier Transforms" pada 2022

    • Belakangan mereka menemukan bahwa TPU mereka lebih cepat untuk perkalian matriks daripada FFT di sebagian besar skenario

  • Transformasi Fourier dilakukan pada dimensi "token". Namun, pada banyak aplikasi dimensi ini tidak memiliki makna

    • Karena itu, transformator merupakan opsi yang sangat baik untuk menangani data yang invarian terhadap permutasi
    • Ingin melihat eksperimen tambahan menggunakan transformasi Fourier pada grup hingga yang kurang dikenal
    • Jika ini menjadi hal besar berikutnya untuk LLM, saya penasaran seberapa mudah mesin inferensi (vLLM, llama.cpp, dll.) mengintegrasikannya

  • Matematikanya terlalu sulit sehingga susah dipahami. Saya penasaran apakah ada yang bisa menjelaskan dengan bahasa Inggris sederhana bagaimana ini setara dengan mekanisme attention, frekuensi seperti apa yang dimaksud, dan bagaimana hubungan posisi antar token dienkodekan

  • Saya tidak tahu bagaimana causal masking bisa dimasukkan ke dalam kerangka ini. Juga tidak ada penyebutan tentang embedding posisi, jadi implementasi self-attention yang dibandingkan tampaknya adalah NoPE non-kausal

    • Jika hasilnya mendekati state of the art, mungkin penulis akan menyebutkannya

  • Tidak ada penyebutan tentang Hyena Operator, yang sudah mendemonstrasikan pencampuran seluruh konteks O(n log n) beberapa tahun lalu

  • Menurut saya ini kesalahan besar di era telemetri jika tidak menerapkan FFT pada telemetri cloud untuk menemukan episiklus dan sistem kuasi-stabil sebelum memicu drama

    • "SLA paling mungkin dilanggar 23-25 menit setelah deployment layanan. Saya penasaran kenapa... oh, tidak."

  • Saya penasaran apakah ada yang punya intuisi mengapa melihat sesuatu di domain frekuensi itu membantu

    • Saya paham suku DC, tetapi saya tidak berharap data masukan cukup periodik sehingga frekuensi lain punya arti

  • Saya cukup memahami notasi Big O, tetapi seperti kebanyakan hal yang berhubungan dengan komputer atau teknik elektro, ini juga sulit dipahami

    • Sebagai orang yang sangat lemah dalam matematika, saya iri pada orang-orang yang bisa memahami atau mempelajari hal seperti ini
    • Yang saya tahu tentang FFT adalah bahwa ia mengubah sinyal, digunakan untuk beberapa pemrosesan sinyal, dan dulu berperan penting dalam mendeteksi ledakan nuklir

  • Saya tidak mengerti mengapa attention diperlukan. Layer fully connected juga bisa "memperhatikan" semua input

    • Pada dataset yang sangat kecil (0 - 500 token), attention membuat pelatihan lebih lama dan hasilnya lebih buruk
    • Keuntungannya tampaknya muncul pada dataset yang lebih besar
    • Sebagai pemula AI, saya sedang mengerjakan proyek AI pribadi jadi ini bukan referensi yang akurat