Resumo Técnico: Distribuições de Probabilidade Computadas por Transformadores Autoregressivos

Declaração do Problema

O trabalho teórico existente sobre a expressividade dos transformadores trata predominantemente os transformadores como reconhecedores de linguagem (classificadores), onde a entrada é uma string completa e a saída é uma classificação binária (aceitar/rejeitar). No entanto, a principal aplicação prática dos transformadores é como modelos de linguagem (autoregressores), que geram strings token a token, prevendo uma distribuição de probabilidade sobre o próximo símbolo dado um prefixo.

Este artigo aborda uma lacuna fundamental: não está claro quais resultados teóricos sobre a expressividade dos transformadores no cenário de reconhecimento se transferem para o cenário de modelagem de linguagem. Especificamente, os autores investigam se as classes de equivalência estabelecidas para transformadores como classificadores Booleanos (por exemplo, equivalência à Lógica Temporal Linear ou autômatos livres de contagem) se mantêm quando os transformadores são usados como autoregressores com pesos reais ou Booleanos.

Metodologia

Os autores desenvolvem um framework formal para comparar transformadores como classificadores versus autoregressores em dois domínios de pesos:

1. Semirring Booleano ($\mathbb{B}$): Pesos são $\{0, 1\}$ (Falso/Verdadeiro).
2. Semirring Real ($\mathbb{R}_{\geq 0}$): Pesos são números reais não negativos (probabilidades).

Eles definem um codificador de estado como uma função que mapeia um prefixo de string para uma sequência de estados, onde o estado na posição $i$ depende apenas do prefixo $w_{\leq i}$. Usando essa abstração, eles analisam quatro configurações específicas:

• Classificadores Booleanos: Mapeiam uma string completa para um valor Booleano.
• Autoregressores Booleanos: Mapeiam um prefixo para uma distribuição sobre o próximo token (pesos Booleanos).
• Classificadores Reais: Mapeiam uma string completa para um peso real.
• Autoregressores Reais: Mapeiam um prefixo para uma distribuição de probabilidade sobre o próximo token.

O estudo foca em Transformadores de Atenção Dura Única (UHATs) e Transformadores de Atenção Softmax (SMATs) com precisão fixa. Estes são comparados com:

• Lógica Temporal Linear (LTL) e seus fragmentos (por exemplo, $TL[P]$, $TL[H]$).
• Autômatos Finitos Determinísticos Livres de Contagem (cfDFAs) e Autômatos Finitos Não Determinísticos Livres de Contagem (cfNFAs).

A metodologia central envolve a construção de reduções entre essas formalidades para determinar se uma pode simular a outra em ambos os modos de classificador e autoregressivo.

Principais Contribuições e Resultados

1. Equivalência em Classificadores Booleanos vs. Autoregressores

• LTL Completa: No semirring Booleano, classificadores LTL e autoregressores LTL são equivalentes. Um transformador atuando como um autoregressor Booleano pode definir as mesmas linguagens que um atuando como classificador, desde que a lógica inclua os operadores "Ontem" ($Y$) e "Historicamente" ($H$).
• Complexidade de Conversão: Embora equivalentes, converter um autoregressor em um classificador (especificamente removendo o operador $Y$) pode exigir uma explosão exponencial no tamanho da fórmula. O artigo prova que construir uma transformação equivalente em tempo polinomial para certos fragmentos é improvável, a menos que $P = PSPACE$ ou $P = NP$.

2. Divergência em Fragmentos Restritos (Booleano)

Ao restringir o conjunto de operadores temporais (por exemplo, para $TL[H]$ ou $TL[P]$ sem $Y$), autoregressores tornam-se estritamente mais expressivos que classificadores.

• Exemplo: A linguagem $(ab)^*$ é definível por um autoregressor Booleano $TL[\emptyset]$, mas não pode ser definida por nenhum classificador $TL[H]$ ou $TL[Y]$.
• Implicação: Transformadores com mecanismos de atenção específicos (como UHATs mais à esquerda ou SMATs de precisão fixa, que correspondem a esses fragmentos) podem reconhecer linguagens como autoregressores que não conseguem reconhecer como classificadores.

3. Divergência em Cenários com Pesos Reais

No semirring real, o panorama da expressividade muda significativamente:

• Classificadores vs. Autoregressores: Eles são incomparáveis.
  • Existem linguagens ponderadas expressíveis por autoregressores reais, mas não por classificadores reais (por exemplo, $(\frac{1}{2}a)^*$, que requer pesos distintos infinitos).
  • Existem linguagens ponderadas expressíveis por classificadores reais, mas não por autoregressores reais (por exemplo, $(1a)^*$, que não é uma distribuição de probabilidade normalizada).
• UHATs e cfDFAs: No cenário real, UHATs (e LTL) como autoregressores são equivalentes a DFAs livres de contagem. No entanto, eles são estritamente menos expressivos que NFAs ponderados livres de contagem.
  • O artigo demonstra um NFA ponderado livre de contagem que não é determinizável (não pode ser convertido em um DFA ponderado equivalente), mostrando que o não determinismo no cenário com pesos reais adiciona expressividade que os transformadores (modelados como codificadores de estado determinísticos) não conseguem capturar.

4. Impacto dos Operadores de Contagem

O artigo revisita resultados sobre transformadores com capacidades de contagem (por exemplo, SMATs com precisão arbitrária dentro da atenção, equivalentes a $TL[\#]$).

• Trabalhos anteriores mostraram que esses transformadores reconhecem linguagens específicas como classificadores.
• Este artigo mostra que, como autoregressores, esses modelos são ligeiramente mais poderosos, capazes de reconhecer linguagens (como $L_{k+2}$) que não conseguem reconhecer como classificadores (limitados a $L_k$). Isso explica discrepâncias entre limites teóricos de reconhecimento e desempenho empírico de previsão de símbolos na literatura anterior.

Significado e Alegações

O artigo afirma fornecer uma maneira principiante de interpretar experimentos existentes sobre a expressividade dos transformadores.

• Validação: Em muitos casos (especificamente LTL Booleana completa), resultados da literatura de reconhecimento de linguagem transferem-se para modelos de linguagem. Por exemplo, como UHATs não podem reconhecer PARIDADE como classificadores, eles não podem fazê-lo como autoregressores também.
• Cuidados: Os autores enfatizam que não se pode assumir cegamente que resultados de reconhecimento se aplicam à geração.
  • Pesos Reais: A mudança de pesos Booleanos para pesos reais quebra equivalências encontradas no caso Booleano (por exemplo, entre DFAs e NFAs).
  • Autoregressão vs. Classificação: A autoregressão pode aumentar estritamente a expressividade em fragmentos lógicos restritos (Booleano) e altera a classe de linguagens ponderadas expressíveis (Real).
• Direções Futuras: Os autores sugerem que trabalhos futuros devem estender esses resultados para atenção softmax de precisão logarítmica, codificações posicionais e raciocínio de "cadeia de pensamento" em cenários com pesos reais, observando que as técnicas atuais para provar inexorabilidade em autoregressores são limitadas.

Em resumo, o artigo estabelece que, embora os transformadores como modelos de linguagem compartilhem grande parte de sua fundação teórica com os transformadores como reconhecedores, a mudança para autoregressão e probabilidades de valor real introduz diferenças sutis, mas críticas, na expressividade computacional, particularmente no que diz respeito ao poder do não determinismo e aos operadores temporais específicos disponíveis.