Technische Samenvatting: Preisach-Attention: Een Hysteretisch Model voor Sequentiële Geheugen

Probleemstelling

Huidige dominante architecturen voor sequentiemodeling, met name de Transformer, vertrouwen op attentiemechanismen die ofwel temporair zijn (vervalend met afstand) ofwel positioneel (geïndexeerd op tokenlocatie). Hoewel theoretische analyses de Turing-volledigheid van hard-attention Transformers hebben vastgesteld, vereisen ze $O(\log n)$ diepte om dit te bereiken, en komt standaard softmax-attention overeen met beperkte fragmenten van eerste-orde logica. Een kritieke beperking die Transformers, Recurrente Neuronale Netwerken (RNN's) en State Space Models (SSM's) gemeen hebben, is het ontbreken van een geheugenmechanisme gebaseerd op de betekenis van eerdere invoer in plaats van hun recentie of absolute positie. Er is behoefte aan een architectuur die in staat is tot het behouden van een lang episodisch geheugen, waarbij de output afhankelijk is van de reeks lokale extremen van de invoerhistorie, onafhankelijk van de temporele afstand.

Methodologie

Het artikel introduceert de Preisach-Attention Layer (PAL), een nieuwe architectuur voor sequentiemodeling die is gebaseerd op de klassieke Preisach-hysterese-operator uit de mathematische fysica.

Kernmechanisme: De Preisach-operator

De Preisach-operator aggregeert de output van binaire relais $\hat{\gamma}_{\alpha\beta}$, elk gekenmerkt door een activeringsdrempel $\alpha$ en een deactiveringsdrempel $\beta$. In de context van sequentiemodeling:

1. Binair Relais: Voor een invoersequentie $u$ schakelt de relaisstatus naar 1 als $u_n \geq \alpha$ en naar 0 als $u_n \leq \beta$. Anders behoudt het zijn vorige status.
2. Extremumstapel: Een fundamenteel gevolg van de "wiping property" (wis-eigenschap) is dat de output van de operator uitsluitend afhankelijk is van de huidige extremumstapel ($\Pi_n$). Deze stapel slaat alternerende lokale maxima en minima op. Een nieuw extremum wist alle eerdere extremen met een kleinere magnitude, waardoor een natuurlijk, op betekenis gebaseerd vergeetmechanisme ontstaat.
3. Snelheidsonafhankelijkheid: De output hangt uitsluitend af van de reeks lokale extremen, niet van de absolute tijd of positie van tokens.

Architectuurdefinitie

• PAL-laag: De laag berekent een gewogen som van binaire relaisoutput over een gediskretiseerd maat $\mu$ op het drempelvlak $(\alpha, \beta)$.
• Multi-Head PAL (MPAL): Breidt de scalaire PAL uit naar vectorwaarde sequenties door invoer te projecteren naar scalaire signalen, deze te verwerken via meerdere heads, en ze terug te projecteren.
• PAL-Transformer: Een standaard Transformer encoder-decoder structuur waarbij het standaard attentiemechanisme wordt vervangen door MPAL. Het behoudt sinusvormige positie-encoding (PE) en MLP-lagen, maar het kerngeheugenmechanisme is hysteretisch.

Belangrijkste Bijdragen en Resultaten

1. Turing-volledigheid bij $O(1)$ diepte

Het artikel bewijst dat een enkellaags PAL-Transformer Turing-volledig is.

• Mechanisme: De architectuur simuleert een willekeurige two-stack pushdown automaton (2-PDA), wat equivalent is aan een Turing-machine.
• Codering: Alfabettekens en stapeldieptes worden gecodeerd in de extremumstapel met behulp van "Cantor-depth encoding".
• Dieptevoordeel: Deze simulatie wordt bereikt met $O(1)$ diepte (één MPAL-laag en één MLP-laag). Dit staat in contrast met standaard hard-attention Transformers, die $O(\log n)$ diepte vereisen om Turing-volledigheid te bereiken (Pérez et al., 2021).
• Vector PAL (vPAL): Een variant die een tweedimensionale signaalprojectie gebruikt, bereikt Turing-volledigheid met één enkele head ($H=1$), wat aantoont dat signaaldimensie en head-aantal uitwisselbare middelen zijn in PAL.

2. Expressiviteitsseparatie

Het artikel stelt vast dat de functieklassen die door PAL en Transformers berekenbaar zijn, onvergelijkbaar zijn.

• PAL $\setminus$ Transformer: PAL kan historische reeksstatistieken berekenen (bijv. $max(u) - min(u)$) in $O(1)$ lagen. Standaard Transformers met beperkte diepte kunnen dit niet exact berekenen vanwege lagere grenzen voor circuitcomplexiteit (MAX zit niet in $AC^0$).
• Transformer $\setminus$ PAL: Transformers kunnen exacte random-access ophaalbewerkingen uitvoeren (bijv. het ophalen van het token op positie $p$). PAL kan dit niet, omdat de snelheidsonafhankelijkheid impliceert dat als een token geen lokaal extremum is, zijn waarde wordt "gewist" uit de invloed van de stapel, waardoor positie-gebaseerde ophaalbewerkingen onmogelijk zijn zonder hulpstaten.
• Scheidende Eigenschap: Snelheidsonafhankelijkheid wordt geïdentificeerd als de fundamentele eigenschap die de twee klassen scheidt. PAL-outputs zijn invariant ten opzichte van tijdsrescaling van de invoersequentie, terwijl standaard attention dit niet is.

3. Logische Karakterisering

Het artikel definieert Extremum First-Order Logic (EFO), een uitbreiding van eerste-orde logica die kwantificatie toestaat uitsluitend over lokale extremale posities en een extremum-aggregatie-operator omvat.

• Stelling: Een functie is berekenbaar door een beperkt-diepte PAL-Transformer dan en slechts dan als deze definieerbaar is in EFO.
• Implicatie: EFO is een strikt fragment van de logica die overeenkomt met standaard Transformers (FO + Aggregate), wat bevestigt dat PAL willekeurige positionele logica niet kan uitdrukken, maar uitblinkt in aggregatie op basis van extremen.

4. Connectie met Fysica en Complexiteit

• RFIM-equivalentie: Het artikel toont aan dat PAL een geleerde, sequentiële, niet-evenwichtsgeneralisatie is van het Random-Field Ising Model (RFIM) bij $T=0$. De extremumstapel komt overeen met de minimale toereikende statistiek van de RFIM-historie.
• Complexiteit: PAL-inferentie heeft een totale tijdscomplexiteit van $O(n \log n)$ (door stapelupdates en binaire zoekopdrachten) en geheugen $O(kd)$, in vergelijking met $O(n^2)$ voor standaard attention.
• Faseovergangen: Geput uit RFIM-theorie, suggereert het artikel dat PAL-lagen die opereren nabij een kritieke onruststerkte, gedrag aan de "rand van chaos" kunnen vertonen, waarbij de gevoeligheid voor invoerveranderingen wordt gemaximaliseerd terwijl een gestructureerd geheugen behouden blijft.

Betekenis en Claims

Het artikel beweert dat PAL een fundamenteel ander geheugenmechanisme biedt voor sequentiemodeling, met een verschuiving van op recentie of positie gebaseerd geheugen naar op betekenis gebaseerd geheugen.

• Theoretische Vooruitgang: Het biedt een nieuw punt in de ruimte van sequentiemodellen dat onvergelijkbaar is met bestaande architecturen, met $O(1)$ diepte Turing-volledigheid en een unieke logische karakterisering (EFO).
• Efficiëntie: Door te vertrouwen op de extremumstapel, reduceert PAL de inferentiecomplexiteit van kwadratisch naar bijna lineair ($O(n \log n)$), wat het theoretisch geschikt maakt voor taken die lang episodisch geheugen vereisen.
• Taakgeschiktheid: De auteurs stellen dat PAL naar verwachting standaard attention zal overtreffen op taken die snelheidsonafhankelijk zijn en vertrouwen op historische reeksstatistieken, zoals:
  • Het volgen van entiteitstoestanden over lange documenten.
  • Het detecteren van anomalieën in tijdreeksen op basis van historische reeksen.
  • Redeneren over geordende gebeurtenissen zonder positionele gevoeligheid.
  • Energie-markt dispatch waarbij beslissingsdrempels het gedrag sturen.

Het artikel concludeert dat PAL, hoewel het geen random access kan uitvoeren, door zijn vermogen om een minimale toereikende statistiek van de invoerhistorie te behouden voor alle snelheidsonafhankelijke functionalen, een natuurlijke architectuur is voor problemen waarbij de betekenis van eerdere gebeurtenissen belangrijker is dan hun recentie of absolute positie. Het werk blijft theoretisch, met empirische validatie en leerdynamica (specifiek met betrekking tot criticaliteit) geïdentificeerd als open vragen voor toekomstig onderzoek.