Riepilogo Tecnico: Distribuzioni di Probabilità Calcolate da Trasformatori Autoregressivi

Enunciato del Problema

Il lavoro teorico esistente sull'espressività dei trasformatori tratta prevalentemente i trasformatori come riconoscitori di linguaggio (classificatori), dove l'input è una stringa completa e l'output è una classificazione binaria (accettare/rifiutare). Tuttavia, l'applicazione pratica primaria dei trasformatori è come modelli linguistici (autoregressori), che generano stringhe token per token prevedendo una distribuzione di probabilità sul simbolo successivo dato un prefisso.

Questo articolo affronta un divario fondamentale: non è chiaro quali risultati teorici riguardanti l'espressività dei trasformatori nel contesto del riconoscimento si trasferiscano al contesto della modellazione linguistica. Nello specifico, gli autori investigano se le classi di equivalenza stabilite per i trasformatori come classificatori booleani (ad esempio, l'equivalenza alla Logica Temporale Lineare o agli automi privi di contatore) valgano quando i trasformatori sono utilizzati come autoregressori a pesi reali o booleani.

Metodologia

Gli autori sviluppano un quadro formale per confrontare i trasformatori come classificatori rispetto agli autoregressori attraverso due domini di pesi:

1. Semianello Booleano ($\mathbb{B}$): I pesi sono $\{0, 1\}$ (Falso/Vero).
2. Semianello Reale ($\mathbb{R}_{\geq 0}$): I pesi sono numeri reali non negativi (probabilità).

Definiscono un codificatore di stato come una funzione che mappa un prefisso di stringa a una sequenza di stati, dove lo stato alla posizione $i$ dipende solo dal prefisso $w_{\leq i}$. Utilizzando questa astrazione, analizzano quattro configurazioni specifiche:

• Classificatori Booleani: Mappano una stringa completa a un valore booleano.
• Autoregressori Booleani: Mappano un prefisso a una distribuzione sul token successivo (pesi booleani).
• Classificatori Reali: Mappano una stringa completa a un peso reale.
• Autoregressori Reali: Mappano un prefisso a una distribuzione di probabilità sul token successivo.

Lo studio si concentra sui Trasformatori con Attenzione Unica Rigida (UHATs) e sui Trasformatori con Attenzione Softmax (SMATs) a precisione fissa. Questi vengono confrontati con:

• Logica Temporale Lineare (LTL) e i suoi frammenti (ad esempio, $TL[P]$, $TL[H]$).
• Automi Finiti Deterministici Privi di Contatore (cfDFA) e Automi Finiti Non Deterministici Privi di Contatore (cfNFA).

La metodologia centrale consiste nel costruire riduzioni tra questi formalismi per determinare se uno possa simulare l'altro sia in modalità classificatore che in modalità autoregressiva.

Contributi e Risultati Chiave

1. Equivalenza tra Classificatori Booleani e Autoregressori

• LTL Completo: Nel semianello booleano, i classificatori LTL e gli autoregressori LTL sono equivalenti. Un trasformatore che agisce come autoregressore booleano può definire gli stessi linguaggi di uno che agisce come classificatore, a condizione che la logica includa gli operatori "Ieri" ($Y$) e "Storicamente" ($H$).
• Complessità della Conversione: Sebbene equivalenti, convertire un autoregressore in un classificatore (in particolare rimuovendo l'operatore $Y$) può richiedere un'esplosione esponenziale nella dimensione della formula. L'articolo dimostra che costruire una trasformazione equivalente in tempo polinomiale per certi frammenti è improbabile a meno che $P = PSPACE$o$P = NP$.

2. Divergenza nei Frammenti Restritti (Booleani)

Quando si restringe l'insieme degli operatori temporali (ad esempio, a $TL[H]$o$TL[P]$ senza $Y$), gli autoregressori diventano strettamente più espressivi dei classificatori.

• Esempio: Il linguaggio $(ab)^*$ è definibile da un autoregressore booleano $TL[\emptyset]$ ma non può essere definito da alcun classificatore $TL[H]$o$TL[Y]$.
• Implicazione: I trasformatori con specifici meccanismi di attenzione (come gli UHATs più a sinistra o gli SMATs a precisione fissa, che corrispondono a questi frammenti) possono riconoscere linguaggi come autoregressori che non riescono a riconoscere come classificatori.

3. Divergenza nei Contesti a Pesi Reali

Nel semianello reale, il panorama dell'espressività cambia significativamente:

• Classificatori vs Autoregressori: Sono incomparabili.
  • Esistono linguaggi pesati esprimibili da autoregressori reali ma non da classificatori reali (ad esempio, $(\frac{1}{2}a)^*$, che richiede pesi distinti infiniti).
  • Esistono linguaggi pesati esprimibili da classificatori reali ma non da autoregressori reali (ad esempio, $(1a)^*$, che non è una distribuzione di probabilità normalizzata).
• UHATs e cfDFA: Nel contesto reale, gli UHATs (e l'LTL) come autoregressori sono equivalenti ai DFA privi di contatore. Tuttavia, sono strettamente meno espressivi degli NFA pesati privi di contatore.
  • L'articolo dimostra un NFA pesato privo di contatore che non è determinizzabile (non può essere convertito in un DFA pesato equivalente), mostrando che il non determinismo nel contesto a pesi reali aggiunge espressività che i trasformatori (modellati come codificatori di stati deterministici) non possono catturare.

4. Impatto degli Operatori di Conteggio

L'articolo rivisita i risultati riguardanti i trasformatori con capacità di conteggio (ad esempio, SMATs con precisione arbitraria all'interno dell'attenzione, equivalenti a $TL[\#]$).

• Lavori precedenti hanno dimostrato che questi trasformatori riconoscono linguaggi specifici come classificatori.
• Questo articolo mostra che come autoregressori, questi modelli sono leggermente più potenti, capaci di riconoscere linguaggi (come $L_{k+2}$) che non riescono a riconoscere come classificatori (limitati a $L_k$). Ciò spiega le discrepanze tra i limiti teorici di riconoscimento e le prestazioni empiriche di previsione dei simboli nella letteratura precedente.

Significato e Affermazioni

L'articolo afferma di fornire un modo principiato per interpretare gli esperimenti esistenti sull'espressività dei trasformatori.

• Validazione: In molti casi (specificamente l'LTL booleano completo), i risultati della letteratura sul riconoscimento del linguaggio si trasferiscono ai modelli linguistici. Ad esempio, poiché gli UHATs non possono riconoscere la PARITÀ come classificatori, non possono farlo nemmeno come autoregressori.
• Avvertenze: Gli autori sottolineano che non si può dare per scontato ciecamente che i risultati di riconoscimento si applichino alla generazione.
  • Pesi Reali: Il passaggio da pesi booleani a pesi reali rompe le equivalenze trovate nel caso booleano (ad esempio, tra DFA e NFA).
  • Autoregressione vs Classificazione: L'autoregressione può aumentare strettamente l'espressività in frammenti logici ristretti (Booleani) e cambia la classe dei linguaggi pesati esprimibili (Reali).
• Direzioni Future: Gli autori suggeriscono che il lavoro futuro dovrebbe estendere questi risultati all'attenzione softmax a precisione logaritmica, alle codifiche posizionali e al ragionamento "catena di pensiero" in contesti a pesi reali, notando che le tecniche attuali per dimostrare l'inesprimibilità negli autoregressori sono limitate.

In sintesi, l'articolo stabilisce che, sebbene i trasformatori come modelli linguistici condividano gran parte della loro fondazione teorica con i trasformatori come riconoscitori, il passaggio all'autoregressione e alle probabilità a valori reali introduce differenze sottili ma critiche nell'espressività computazionale, in particolare riguardo alla potenza del non determinismo e agli specifici operatori temporali disponibili.