Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

Resumo Técnico: Compreendendo a Geometria do Espaço de Parâmetros de Transformers que Codificam Funções Booleanas

Enunciado do Problema
Os Transformers exibem uma lacuna bem documentada entre expressividade (a existência de configurações de parâmetros que podem computar uma função) e aprendibilidade (a capacidade de algoritmos de otimização encontrarem essas configurações). Embora o trabalho teórico tenha estabelecido que os transformers podem expressar certas funções booleanas, evidências empíricas mostram que eles falham consistentemente em aprender funções sensíveis — aquelas onde a inversão de um único bit de entrada provavelmente altera a saída. Um exemplo canônico é a função PARIDADE (PARITY). Trabalhos anteriores atribuíram isso a um viés para funções com baixa sensibilidade média, mas o mecanismo preciso que liga a sensibilidade à geometria do espaço de parâmetros permanece obscuro. Especificamente, desconhece-se se a não-aprendibilidade de funções sensíveis decorre do fato de elas ocuparem um volume vanishingly pequeno (tendente a zero) no espaço de parâmetros, tornando-as improváveis de serem encontradas por inicialização aleatória ou otimização baseada em gradiente.

Metodologia
Os autores analisam a geometria do espaço de parâmetros $\Theta$ de transformers de atenção suave (soft-attention) que codificam funções booleanas sobre um alfabeto binário. A análise é dividida em dois casos baseados na constante de estabilização da camada de normalização $\epsilon$ no denominador do termo de normalização:

1. Caso $\epsilon > 0$: Os autores estabelecem primeiro que, quando $\epsilon$ está afastado de zero, o transformer é uniformemente Lipschitz contínuo em relação aos seus parâmetros. Esta estabilidade uniforme implica que o "estouro" cumulativo (amplificação de mudanças na entrada) é limitado independentemente do comprimento do input $N$. Consequentemente, para $N$ suficientemente grande, a influência de inverter qualquer bit individual na saída desaparece ($O(1/N)$). Isso leva a um argumento de empacotamento mostrando que o número de funções booleanas reconhecíveis é limitado por uma constante independente de $N$, tornando funções booleanas não-constantes assintoticamente irreconhecíveis.

2. Caso $\epsilon = 0$: Este é o foco principal do artigo. Aqui, o denominador da camada de normalização pode aproximar-se de zero, potencialmente causando um estouro (blowup) ilimitado. Os autores desenvolvem uma estrutura de teoria da medida para analisar a probabilidade de um transformer inicializado aleatoriamente computar uma função com propriedades de sensibilidade específicas.

   • Perfil de Sensibilidade: Em vez de depender apenas da sensibilidade média, os autores introduzem o perfil de sensibilidade, definido como a distribuição dos valores de sensibilidade através de todas as strings de entrada.
   • Análise de Estouro (Blowup Analysis): Eles provam que, para uma string de entrada fixa $x$, o estouro é limitado com alta probabilidade sobre uma perturbação aleatória de parâmetros, desde que a variância das entradas da camada de normalização não se torne muito pequena.
   • Argumento de Teoria da Medida: Ao cobrir o espaço de parâmetros com pequenos cubos e aplicar limites probabilísticos ao estouro dentro de cada cubo, eles estendem o resultado para todo o espaço de parâmetros. Eles utilizam o primeiro lema de Borel-Cantelli para agregar esses resultados através de todos os comprimentos de entrada suficientemente grandes $N$.

Principais Contribuições e Resultados

• Não-Aprendibilidade de Medida Zero: O resultado teórico central (Teorema 4.5) prova que, para qualquer comprimento de entrada $N$ suficientemente grande, um transformer inicializado aleatoriamente quase certamente computa uma função que possui um número significativo de strings com sensibilidade zero (especificamente, pelo menos $N^{\frac{D-1}{2L} - 5}$ tais strings).
• Restrição do Perfil de Sensibilidade: Consequentemente, qualquer função booleana que careça de strings de sensibilidade zero (ou seja, funções onde cada entrada tem sensibilidade não-zero) ocupa um subconjunto de medida de Lebesgue zero no espaço de parâmetros.
• Não-Aprendibilidade de Funções Específicas: Com base no exposto, os autores provam que funções como PARIDADE (PARITY), m-PARIDADE ESPARSA (m-SPARSE PARITY) e funções DITADOR (DICTATOR), incluindo PRIMEIRO (FIRST), são provadamente não-aprendíveis para $N$ grande por transformers inicializados aleatoriamente. Estas funções têm sensibilidade mínima $\ge 1$ (ou $m$ para variantes esparsas), o que significa que possuem zero strings de sensibilidade zero.
• Distinção da Sensibilidade Média: A análise revela que a sensibilidade média é insuficiente para prever a aprendibilidade. Por exemplo, a função PRIMEIRO (FIRST) tem uma sensibilidade média baixa (igual a 1), mas é não-aprendível para $N$ grande porque carece de strings de sensibilidade zero. Inversamente, MAJORITÁRIA (MAJORITY) tem uma sensibilidade média baixa, mas possui um número exponencial de strings de sensibilidade zero, permitindo que ocupe uma região de medida positiva do espaço de parâmetros.
• Conjectura sobre MAJORITÁRIA: Os autores conjecturam que a função MAJORITÁRIA é aprendível porque sua abundância de strings de sensibilidade zero corresponde a um subconjunto de medida positiva no espaço de parâmetros.
• Validação Empírica: Experimentos em transformers treinados e inicializados aleatoriamente confirmam que os espectros de sensibilidade são fortemente enviesados para zero. Mesmo após o treinamento em tarefas como PARIDADE, os modelos falham em alcançar o perfil de sensibilidade correto, enquanto modelos treinados em MAJORITY e FIRST (em comprimentos moderados) aprendem as tarefas com sucesso e exibem o agrupamento de sensibilidade previsto.

Significância
O artigo fornece uma explicação teórica para o viés indutivo observado em transformers em direção a funções de baixa sensibilidade. Ao deslocar o foco da sensibilidade média para o perfil completo de sensibilidade e analisar as propriedades de medida do espaço de parâmetros, os autores demonstram que a não-aprendibilidade de funções como PARIDADE não é meramente uma falha de otimização, mas uma restrição geométrica fundamental: as configurações de parâmetros necessárias para representar tais funções ocupam um conjunto de medida zero. Isso implica que a inicialização aleatória quase certamente perderá essas configurações, e a otimização baseada em gradiente, limitada pelo prior de inicialização, dificilmente as alcançará. O trabalho esclarece a fronteira entre expressividade e aprendibilidade, mostrando que, para entradas suficientemente longas, os transformers são fundamentalmente incapazes de reconhecer linguagens que carecem de strings de sensibilidade zero.