Technische Samenvatting: Kansverdelingen Berekend door Autoregressieve Transformers

Probleemstelling

Bestaand theoretisch werk over transformer-expressiviteit behandelt transformers voornamelijk als taalherkenners (classificators), waarbij de invoer een volledige string is en de uitvoer een binaire classificatie (accepteren/verwerpen). De belangrijkste praktische toepassing van transformers is echter als talenmodellen (autoregressors), die strings token voor token genereren door een kansverdeling over het volgende symbool te voorspellen, gegeven een prefix.

Dit artikel adresseert een fundamentele kloof: het is onduidelijk welke theoretische resultaten met betrekking tot transformer-expressiviteit in de herkenningscontext overdraagbaar zijn naar de context van taalmodellen. Specifiek onderzoeken de auteurs of de equivalentieklassen die voor transformers als Boolese classificators zijn vastgesteld (bijvoorbeeld equivalentie met Lineaire Temporele Logica of teller-vrije automaten) geldig blijven wanneer transformers worden gebruikt als real-gewogen of Boolese autoregressors.

Methodologie

De auteurs ontwikkelen een formeel kader om transformers als classificators versus autoregressors te vergelijken over twee gewichtsdomines:

1. Boolese Semiring ($\mathbb{B}$): Gewichten zijn $\{0, 1\}$ (Onwaar/Waar).
2. Reële Semiring ($\mathbb{R}_{\geq 0}$): Gewichten zijn niet-negatieve reële getallen (kansen).

Ze definiëren een state-encoder als een functie die een string-prefix afbeeldt op een reeks toestanden, waarbij de staat op positie $i$ uitsluitend afhankelijk is van de prefix $w_{\leq i}$. Met behulp van deze abstractie analyseren ze vier specifieke configuraties:

• Boolese Classificators: Beelden een volledige string af op een Boolese waarde.
• Boolese Autoregressors: Beelden een prefix af op een verdeling over het volgende token (Boolese gewichten).
• Reële Classificators: Beelden een volledige string af op een reëel gewicht.
• Reële Autoregressors: Beelden een prefix af op een kansverdeling over het volgende token.

De studie richt zich op Unique Hard Attention Transformers (UHATs) en Softmax Attention Transformers (SMATs) met vaste precisie. Deze worden vergeleken met:

• Lineaire Temporele Logica (LTL) en haar fragmenten (bijvoorbeeld $TL[P]$, $TL[H]$).
• Teller-vrije Deterministische Eindige Automaten (cfDFAs) en Teller-vrije Niet-deterministische Eindige Automaten (cfNFAs).

De kernmethodologie bestaat uit het construeren van reducties tussen deze formalismen om te bepalen of het ene het andere kan simuleren, zowel in de modus van classifier als in die van autoregressor.

Belangrijkste Bijdragen en Resultaten

1. Equivalentie in Boolese Classificators versus Autoregressors

• Volledige LTL: In de Boolese semiring zijn LTL-classificators en LTL-autoregressors equivalent. Een transformer die fungeert als Boolese autoregressor kan dezelfde talen definiëren als een transformer die fungeert als classifier, mits de logica de operatoren "Gisteren" ($Y$) en "Historisch" ($H$) bevat.
• Complexiteit van Conversie: Hoewel equivalent, kan het converteren van een autoregressor naar een classifier (specifiek het verwijderen van de $Y$-operator) leiden tot een exponentiële toename in de grootte van de formule. Het artikel bewijst dat het construeren van een polynomiale tijd-equivalente transformatie voor bepaalde fragmenten onwaarschijnlijk is, tenzij $P = PSPACE$ of $P = NP$.

2. Divergentie in Beperkte Fragmenten (Boolese)

Bij beperking van de set temporele operatoren (bijvoorbeeld tot $TL[H]$ of $TL[P]$ zonder $Y$), worden autoregressors strikt expressiever dan classificators.

• Voorbeeld: De taal $(ab)^*$ is definieerbaar door een Boolese $TL[\emptyset]$-autoregressor, maar kan niet worden gedefinieerd door enige $TL[H]$- of $TL[Y]$-classifier.
• Implicatie: Transformers met specifieke aandachtsmechanismen (zoals linkse UHATs of SMATs met vaste precisie, die overeenkomen met deze fragmenten) kunnen talen herkennen als autoregressors die ze niet kunnen herkennen als classificators.

3. Divergentie in Reëel-Gewogen Contexten

In de reële semiring verandert het landschap van expressiviteit aanzienlijk:

• Classificators versus Autoregressors: Ze zijn onvergelijkbaar.
  • Er zijn gewogen talen die uitdrukbaar zijn door reële autoregressors maar niet door reële classificators (bijvoorbeeld $(\frac{1}{2}a)^*$, wat oneindig veel verschillende gewichten vereist).
  • Er zijn gewogen talen die uitdrukbaar zijn door reële classificators maar niet door reële autoregressors (bijvoorbeeld $(1a)^*$, wat geen genormaliseerde kansverdeling is).
• UHATs en cfDFAs: In de reële setting zijn UHATs (en LTL) als autoregressors equivalent aan teller-vrije DFAs. Ze zijn echter strikt minder expressief dan gewogen teller-vrije NFAs.
  • Het artikel demonstreert een teller-vrije gewogen NFA die niet determiniseerbaar is (niet kan worden omgezet in een equivalente gewogen DFA), wat aantoont dat de niet-determinisme in de reëel-gewogen setting expressiviteit toevoegt die transformers (gemodelleerd als deterministische state-encoders) niet kunnen vangen.

4. Impact van Teller-Operatoren

Het artikel herneemt resultaten met betrekking tot transformers met telcapaciteiten (bijvoorbeeld SMATs met willekeurige precisie binnen de aandacht, equivalent aan $TL[\#]$).

• Eerdere studies toonden aan dat deze transformers specifieke talen herkennen als classificators.
• Dit artikel toont aan dat als autoregressors, deze modellen iets krachtiger zijn en in staat zijn talen te herkennen (zoals $L_{k+2}$) die ze niet kunnen herkennen als classificators (beperkt tot $L_k$). Dit verklaart discrepanties tussen theoretische herkenningsgrenzen en empirische prestaties bij symboolvoorspelling in eerdere literatuur.

Betekenis en Claims

Het artikel claimt een principiële manier te bieden om bestaande experimenten over transformer-expressiviteit te interpreteren.

• Validatie: In veel gevallen (specifiek volledige Boolese LTL) transfereren resultaten uit de literatuur over taalherkenning naar taalmodellen. Bijvoorbeeld, aangezien UHATs PARITY niet kunnen herkennen als classificators, kunnen ze dat ook niet als autoregressors.
• Voorbehoud: De auteurs benadrukken dat men niet blindelings mag aannemen dat herkenningsresultaten van toepassing zijn op generatie.
  • Reële Gewichten: De verschuiving van Boolese naar reële gewichten breekt equivalenties die in het Boolese geval werden gevonden (bijvoorbeeld tussen DFAs en NFAs).
  • Autoregressie versus Classificatie: Autoregressie kan de expressiviteit strikt verhogen in beperkte logische fragmenten (Boolese) en verandert de klasse van uitdrukbare gewogen talen (Reële).
• Toekomstige Richtingen: De auteurs suggereren dat toekomstig werk deze resultaten moet uitbreiden naar log-precisie softmax-aandacht, positionele coderingen en "chain of thought"-redenering in reëel-gewogen settings, waarbij wordt opgemerkt dat huidige technieken voor het bewijzen van niet-expressiviteit in autoregressors beperkt zijn.

Kortom, het artikel stelt vast dat hoewel transformers als taalmodellen veel van hun theoretische fundament delen met transformers als herkenners, de verschuiving naar autoregressie en reëel-waardige kansen subtiele maar kritieke verschillen introduceert in computationele expressiviteit, met name wat betreft de kracht van niet-determinisme en de specifieke beschikbare temporele operatoren.