FFT'nin Karşı Atağı: Self-Attention'a Verimli Bir Alternatif

• Mevcut Self-Attention mekanizması O(n²) karmaşıklığa sahiptir ve uzun dizilere ölçeklenebilirliği sınırlıdır
• Bu makale, Fast Fourier Transform (FFT) kullanan FFTNet'i önermektedir
• FFTNet, O(n log n) zaman karmaşıklığıyla küresel token karıştırma gerçekleştirir
• Frekans alanında öğrenilebilir spektral filtreler ve modReLU aktivasyon fonksiyonu tanıtılarak önemli frekans bileşenleri vurgulanır
• Long Range Arena (LRA) ve ImageNet benchmark deneylerinde, mevcut Self-Attention ve sabit Fourier dönüşümü tabanlı modellerden daha iyi performans gösterir

İlgili araştırmalar

• Self-Attention'ın karmaşıklığı: Transformer modelleri O(n²) işlem yükü gerektirir ve bu nedenle uzun dizilerin işlenmesinde verimsizdir
• Fourier tabanlı yaklaşımlar: FNet gibi modeller işlem yükünü azaltmak için sabit Fourier dönüşümü kullanmıştır, ancak girdiye uyum kabiliyeti düşüktür
• Doğrusal, seyrek ve düşük boyutlu yaklaşım teknikleri: Performer, Linformer, BigBird gibi çalışmalar, Self-Attention hesaplamasını yaklaşıklandırma yöntemleri önermiştir
• Ortogonal matris ayrıştırma teknikleri: Ortogonal dönüşümlerden (DFT dahil) yararlanmak model eğitiminin kararlılığını artırır
• Uyarlanabilir spektral filtreleme: FFT tabanlı dönüşümlere öğrenilebilir filtreler eklenerek mevcut yöntemlere göre daha esnek ve daha ifade gücü yüksek bir yapı elde edilir

FFTNet: uyarlanabilir spektral filtreleme tekniği

Motivasyon

• Self-Attention O(n²) karmaşıklığa sahiptir ve uzun dizilerde verimsizdir
• FFT O(n log n) ile çalışır ve küresel etkileşimleri verimli biçimde kodlayabilir

Yöntem

• Fourier dönüşümü (FFT uygulaması)
  • Girdi dizisini frekans alanına dönüştürerek küresel bağımlılıkları verimli biçimde yakalar
• Uyarlanabilir spektral filtre uygulaması
  • Küresel bağlam vektörü kullanılarak öğrenilebilir filtreler üretilir ve önemli frekans bantları dinamik olarak vurgulanır
• modReLU doğrusal olmayan aktivasyonu
  • Karmaşık frekans alanında ReLU tabanlı aktivasyon uygulanarak ifade gücü artırılır
• Ters Fourier dönüşümü (IFFT)
  • Dönüştürülmüş veriye filtreleme ve aktivasyon uygulandıktan sonra tekrar zaman alanına dönüştürülür

FFTNet'in teorik temeli

• O(n log n) işlem maliyetiyle küresel token karıştırma mümkündür
• Uyarlanabilir Attention: frekans alanındaki öğrenilebilir filtreler, verilen girdiye göre frekansları ayarlar
• Doğrusal olmayan aktivasyonun ifade gücünü artırması: modReLU uygulanmasıyla basit doğrusal dönüşümlerin ötesinde yüksek boyutlu örüntüler öğrenilebilir
• Parseval's theorem tabanlı kararlılık güvencesi: sinyal enerjisini koruyarak bilgi kaybını en aza indirir

Deney sonuçları

Long Range Arena (LRA) benchmark'ı

• FFTNet, Transformer ve FNet'e kıyasla genel olarak daha yüksek doğruluk elde eder
• Özellikle ListOps, Text, Retrieval, Image ve Pathfinder görevlerinde daha iyi performans gösterir ve ortalamada en yüksek skoru kaydeder
• Transformer bazı görevlerde yüksek performans göstermiş olsa da uzun vadeli bağımlılıkları işlemede sınırlamalar taşır
• FNet, FFT kullanmasına rağmen sabit dönüşüm yapısının düşük uyarlanabilirliği nedeniyle genel olarak daha düşük performans gösterir
• Özellikle Path-X görevinde Transformer bellek taşması (OOM) nedeniyle başarısız olurken FFTNet kararlı performans sergilemiştir

ImageNet sınıflandırma deneyi

• FFTNet tabanlı Vision Transformer (FFTNetViT), mevcut ViT ile benzer doğruluğu korurken hesaplama miktarını (FLOPs) önemli ölçüde azaltmayı başarmıştır
• Base modelde FFTNetViT, ViT'ye göre yaklaşık %38 daha az FLOPs kullanırken doğrulukta da küçük bir artış sağlar
• Large ve Huge modellerinde de FFTNetViT, ViT'ye kıyasla daha düşük hesaplama maliyetiyle benzer performansı korur
• Bu da FFTNetViT'nin yüksek hesaplama verimliliği sunduğunu göstermektedir

Ablation Study (bileşen bazlı önem analizi)

• FFTNet'in çeşitli unsurları çıkarılarak model performansı üzerindeki etkileri analiz edilmiştir
• FFTNet'in temel bileşenleri kaldırıldıkça doğruluğun düşme eğiliminde olduğu görülür
  • Spektral gating'in kaldırılması: belirli frekansları vurgulama işlevi ortadan kalkınca doğrulukta küçük bir düşüş olur
  • Uyarlanabilir modülün kaldırılması: girdiye göre filtreleri dinamik ayarlama işlevi ortadan kalktığı için doğruluk daha da düşer
  • FFT yerine konvolüsyon kullanılması: küresel bilgiyi verimli biçimde karıştırma yeteneği kaybolduğu için en büyük performans düşüşü ortaya çıkar
• Bu da FFTNet'in her bir bileşeninin performans artışında önemli rol oynadığını göstermektedir

Sonuç

• FFTNet, Self-Attention'a göre hesaplama açısından daha verimli bir alternatiftir
• Frekans alanında uyarlanabilir spektral filtreler ile modReLU'yu birleştirerek güçlü bir ifade kapasitesi sunar
• Deney sonuçları, LRA ve ImageNet'te mevcut Self-Attention modellerine göre performans ve verimlilik açısından üstün olduğunu göstermektedir
• O(n log n) karmaşıklığını korurken Self-Attention düzeyinde performans sunması, onu uzun dizilerin işlenmesi için avantajlı kılar
• FFTNet tabanlı Vision Transformer (FFTNetViT) da düşük FLOPs ile ViT'ye benzer performans elde eder

• Kod deposu: GitHub bağlantısı

[GN⁺]

Hacker News yorumu

• Temelde konvolüsyon teoremini kullanıyor: doğrudan uzaydaki pahalı konvolüsyon, karşılık gelen uzayda basit bir çarpıma dönüşüyor

  • Veride bir konvolüsyon işlemi olduğunda, bunu çarpmaya çevirmek için eşlenik domaine dönüştürülüyor
  • Yani verinin doğal domaininde çalışılıyor

• Google, 2022'de "FNet: Mixing Tokens with Fourier Transforms" fikrini tanıttı

  • Daha sonra TPU'larının çoğu senaryoda FFT'den çok matris çarpımında daha hızlı olduğunu fark ettiler

• Fourier dönüşümü "token" boyutunda yapılıyor. Ancak birçok uygulamada bu boyutun bir anlamı yok

  • Bu yüzden dönüştürücüler, permütasyona değişmez verileri işlemek için harika bir seçenek
  • Daha az bilinen sonlu gruplar üzerindeki Fourier dönüşümünü kullanan ek deneyler görmek isterdim
  • Eğer bu, LLM'lerdeki bir sonraki büyük şey olursa, çıkarım motorlarının (vLLM, llama.cpp vb.) bunu entegre etmesinin ne kadar kolay olacağını merak ediyorum

• Matematik fazla zor olduğu için anlaması güç. Birisi bunun dikkat mekanizmasına nasıl eşdeğer olduğunu, hangi frekanslardan bahsedildiğini ve token'lar arasındaki konumsal ilişkinin nasıl kodlandığını basit İngilizceyle açıklayabilir mi diye merak ediyorum

• Bu çerçeveye nedensel maskelemenin nasıl oturtulabileceğini bilmiyorum. Konum gömmelerine dair de bir şey söylenmediği için, karşılaştırılan self-attention uygulaması muhtemelen nedensel olmayan NoPE gibi görünüyor

  • Sonuçlar state-of-the-art seviyesine yakın olsaydı, yazar muhtemelen buna değinirdi

• Birkaç yıl önce zaten O(n log n) tam bağlam karıştırmasını göstermiş olan Hyena Operator'dan hiç bahsedilmemiş

• Telemetri çağında, bulut telemetrisine FFT uygulayıp drama yaratmadan önce episiklleri ve yarı kararlı sistemleri tespit etmemek büyük bir hata gibi geliyor

  • "SLA, servis dağıtımından 23-25 dakika sonra en çok ihlal edilme eğiliminde. Neden olduğunu merak ediyorum... ah, hayır."

• Şeylere frekans domeninde bakmanın neden yardımcı olduğuna dair sezgisi olan biri var mı diye merak ediyorum

  • DC terimini anlıyorum ama girdi verisinin, diğer frekansların anlamlı olacağı kadar periyodik olmasını beklemiyorum

• Big O gösterimini bir dereceye kadar anlıyorum ama bilgisayar ya da elektrik mühendisliğiyle ilgili çoğu şey gibi bunu da anlamak zor

  • Matematikte çok zayıf biri olarak, böyle şeyleri anlayabilen ya da öğrenebilen insanları kıskanıyorum
  • FFT hakkında bildiğim şey, sinyalleri dönüştürdüğü, bazı sinyal işleme işlerinde kullanıldığı ve geçmişte nükleer patlamaların tespitinde önemli rol oynadığı

• Dikkatin neden gerekli olduğunu anlamıyorum. Tam bağlı katmanlar da tüm girdilere "dikkat" edebilir

  • Çok küçük veri kümelerinde (0 - 500 token), dikkat eğitimi daha uzun sürüyor ve sonuçları kötüleştiriyor
  • Avantajlar daha büyük veri kümelerinde ortaya çıkıyor gibi görünüyor
  • Yapay zeka konusunda acemi biri olarak kişisel bir yapay zeka projesi yapıyorum, yani tam olarak güvenilir bir kaynak sayılmam