Fibottention: Inceptive Visual Representation Learning with Diverse Attention Across Heads

Probleemstelling

Vision Transformers (ViT) en hun varianten hebben indrukwekkende resultaten geboekt in visuele perceptietaken. Ze kampen echter met twee fundamentele beperkingen:

1. Quadratische complexiteit: De Multi-Head Self-Attention (MHSA) mechanismen vereisen de berekening van $O(N^2)$ interacties tussen tokens (afbeeldingspatches). Dit beperkt de schaalbaarheid voor grote tokenaantallen (bijv. hoge resolutie beelden of video's).
2. Afhankelijkheid van grote datasets: ViT-modellen presteren vaak slecht in regimes met beperkte trainingsdata, in tegenstelling tot hun sterke prestaties op enorme datasets.

Bestaande oplossingen voor "sparse attention" (waarbij slechts een subset van token-interacties wordt berekend) leiden vaak tot een afname in modelprestaties of zijn specifiek ontworpen voor natuurlijke taal (NLP) en niet optimaal voor visuele data, waarbij lokale en spatiotemporale redundanties anders zijn.

Methodologie: Fibottention

De auteurs stellen Fibottention voor, een nieuwe, deterministische en niet-adaptieve sparse attention-mechanisme dat als drop-in vervanging dient voor volledige MHSA in Vision Transformers. De kern van de methode ligt in de structuur van de sparsiteit.

1. Gebaseerd op de Wythoff-Array en Fibonacci-reeksen:
In plaats van willekeurige of vaste vensters te gebruiken, gebruikt Fibottention gestructureerde sparsiteitspatronen afgeleid van de Wythoff-Array.

• Elke attention-head ($i$) krijgt een uniek, complementair sparsiteitspatroon ($\Omega_i$).
• Deze patronen worden gegenereerd met veralgemeende Fibonacci-reeksen (dilatatie-sequenties) die zijn afgeleid van de rijen in de Wythoff-Array.
• De rijen van de Wythoff-Array hebben de eigenschap dat elk positief gehele getal precies één keer voorkomt in de verzameling van alle rijen. Dit zorgt ervoor dat de overlap tussen de sparsiteitspatronen van verschillende heads minimaal is.

2. Diversiteit en Complementariteit (Inceptie-achtig):
Het ontwerp is geïnspireerd op Inception-modellen in CNN's:

• Head-diversiteit: Omdat elke head een ander sparsiteitspatroon heeft (verschillende dilatatie-sequenties en venstergroottes), worden verschillende schaal-informatie en token-relaties gevangen.
• Lokaal vs. Globaal: De dilatatie-sequenties zorgen ervoor dat heads zowel dichte lokale interacties (kleine afstanden) als verspreide langeafstandsinteracties (grote afstanden) kunnen modelleren, zonder dat alle paren worden berekend.
• Diagonale uitsluiting: Het mechanisme sluit bewust de hoofddiagonaal van de attention-matrix uit (waarbij een token op zichzelf attendeert), aangezien dit vaak redundante informatie bevat.

3. Computational Efficiency:
Door de exponentiële groei van de Fibonacci-reeksen, neemt het aantal te berekenen token-interacties af naarmate de afstand toeneemt.

• De tijdcomplexiteit wordt bewezen te zijn $O(N \log N)$ in plaats van $O(N^2)$.
• In typische instellingen worden slechts 2% van alle mogelijke paarwijze interacties berekend, wat leidt tot aanzienlijke besparingen in FLOPs (Floating Point Operations).

Belangrijkste Bijdragen

1. Nieuwe Sparse Attention Architectuur: Introductie van Fibottention, een methode die gebruikmaakt van de wiskundige eigenschappen van de Wythoff-Array om diverse, niet-overlappende sparsiteitspatronen per attention-head te creëren.
2. Theoretische Bewijzen: Een formele afleiding van de $O(N \log N)$ complexiteit en de eigenschappen van de gebruikte sequenties.
3. Inductieve Bias voor Visuele Data: Het mechanisme introduceert een inductieve bias die specifiek gunstig is voor visuele representaties, vooral in data-schaarse regimes, door het bevorderen van gedesintegreerde en informatieve features.
4. Uitgebreide Validatie: Experimenten over drie domeinen: beeldclassificatie, video-actieherkenning en robot-imitatieleren.

Resultaten

De auteurs hebben Fibottention geëvalueerd op diverse state-of-the-art Transformer-architecturen (zoals ViT-B, Swin-B, ConViT, TimeSformer) en datasets (CIFAR-10/100, ImageNet-1K, Smarthome, Robot-datasets).

• Beeldclassificatie:
  • Op kleine datasets (CIFAR-10/100, Tiny-ImageNet) overtreft Fibottention consistent de baselines met volledige attention, zelfs met 98% pruning.
  • Op ImageNet-1K bereikt het vergelijkbare prestaties als de dichte baselines, terwijl het slechts 2% van de interacties berekent.
  • Het presteert beter dan andere sparse methoden zoals BigBird, Longformer en Top-k attention onder vergelijkbare rekenkosten.
• Video-herkenning:
  • Op de Smarthome en NUCLA datasets verbeterde Fibottention (met een "Modified Wythoff" variant die meer lokale interacties toestaat) de Top-1 nauwkeurigheid van TimeSformer aanzienlijk.
• Robot Learning:
  • Bij behavioral cloning taken (Lift, Can, PushT) bereikte het model de beste gemiddelde taakvoltooiingspercentages, vaak beter dan baselines met BigBird.
• Robuustheid:
  • Modellen met Fibottention tonen een hogere robuustheid tegen beeldcorrupties (zoals ruis, blur, veranderingen in helderheid) vergeleken met dichte ViT-modellen.
• Feature Diversiteit:
  • Analyse toont aan dat Fibottention aanzienlijk meer diversiteit tussen de attention-heads creëert dan andere sparse methoden, wat bijdraagt aan het vermogen om complementaire features te leren.

Significantie en Conclusie

Fibottention biedt een elegante oplossing voor het efficiëntie-prestatie-dilemma in Vision Transformers. Door gebruik te maken van wiskundig gestructureerde, diverse sparsiteitspatronen, slaagt het erin om:

1. De rekencomplexiteit te reduceren van kwadratisch naar logaritmisch ($O(N \log N)$).
2. De prestaties te behouden of zelfs te verbeteren, vooral in situaties met beperkte trainingsdata.
3. Een "Inceptie-achtige" diversiteit in feature-representaties te creëren zonder de extra complexiteit van adaptieve of leerbare masks.

Dit werk suggereert dat de volgende generatie Transformers, die omgaan met miljarden tokens, kan profiteren van dergelijke geoptimaliseerde, gestructureerde architecturen die zowel computationeel efficiënt als data-efficiënt zijn. De code is openbaar beschikbaar, wat reproduceerbaarheid garandeert.