Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

Resumen Técnico: Comprensión de la Geometría del Espacio de Parámetros de los Transformers que Codifican Funciones Booleanas

Planteamiento del Problema
Los Transformers exhiben una brecha bien documentada entre la expresividad (la existencia de configuraciones de parámetros que pueden computar una función) y la aprendibilidad (la capacidad de los algoritmos de optimización para encontrar esas configuraciones). Si bien el trabajo teórico ha establecido que los transformers pueden expresar ciertas funciones booleanas, la evidencia empírica muestra que fallan consistentemente al aprender funciones sensibles —aquellas donde cambiar un solo bit de entrada es probable que cambie la salida—. Un ejemplo canónico es la función PARITY. Trabajos previos han atribuido esto a un sesgo hacia funciones con baja sensibilidad promedio, pero el mecanismo preciso que vincula la sensibilidad con la geometría del espacio de parámetros sigue sin estar claro. Específicamente, se desconoce si la inaprendibilidad de las funciones sensibles surge porque ocupan un volumen decreciente en el espacio de parámetros, lo que las hace improbables de ser encontradas por una inicialización aleatoria o una optimización basada en gradientes.

Metodología
Los autores analizan la geometría del espacio de parámetros $\Theta$ de los transformers de atención suave (soft-attention) que codifican funciones booleanas sobre un alfabeto binario. El análisis se divide en dos casos basados en la constante de estabilización de la normalización de capa $\epsilon$ en el denominador del término de normalización:

1. Caso $\epsilon > 0$: Los autores establecen primero que cuando $\epsilon$ está acotado lejos de cero, el transformer es uniformemente Lipschitz continuo con respecto a sus parámetros. Esta estabilidad uniforme implica que el "estallido" acumulativo (amplificación de cambios en la entrada) está acotado independientemente de la longitud de la entrada $N$. En consecuencia, para valores de $N$ suficientemente grandes, la influencia de cambiar un solo bit en la salida desaparece ($O(1/N)$). Esto conduce a un argumento de empaquetamiento que muestra que el número de funciones booleanas reconocibles está acotado por una constante independiente de $N$, haciendo que las funciones booleanas no constantes sean asintóticamente irreconocibles.

2. Caso $\epsilon = 0$: Este es el foco principal del artículo. Aquí, el denominador de la normalización de capa puede acercarse a cero, lo que potencialmente causa un estallido no acotado. Los autores desarrollan un marco de teoría de la medida para analizar la probabilidad de que un transformer inicializado aleatoriamente compute una función con propiedades de sensibilidad específicas.

   • Perfil de Sensibilidad: En lugar de depender únicamente de la sensibilidad promedio, los autores introducen el perfil de sensibilidad, definido como la distribución de los valores de sensibilidad a través de todas las cadenas de entrada.
   • Análisis de Estallido (Blowup): Demuestran que, para una cadena de entrada fija $x$, el estallido está acotado con alta probabilidad sobre una perturbación aleatoria de los parámetros, siempre que la varianza de las entradas de la normalización de capa no sea demasiado pequeña.
   • Argumento de Teoría de la Medida: Al cubrir el espacio de parámetros con pequeños cubos y aplicar límites probabilísticos sobre el estallido dentro de cada cubo, extienden el resultado a todo el espacio de parámetros. Utilizan el primer lema de Borel-Cantelli para agregar estos resultados a través de todas las longitudes de entrada $N$ suficientemente grandes.

Contribuciones Clave y Resultados

• Inaprendibilidad de Medida Cero: El resultado teórico central (Teorema 4.5) demuestra que, para cualquier longitud de entrada $N$ suficientemente grande, un transformer inicializado aleatoriamente casi seguramente computa una función que posee un número significativo de cadenas con sensibilidad cero (específicamente, al menos $N^{\frac{D-1}{2L} - 5}$ tales cadenas).
• Restricción del Perfil de Sensibilidad: En consecuencia, cualquier función booleana que carezca de cadenas de sensibilidad cero (es decir, funciones donde cada entrada tiene sensibilidad no nula) ocupa un subconjunto de medida de Lebesgue cero en el espacio de parámetros.
• Inaprendibilidad de Funciones Específicas: Basándose en lo anterior, los autores demuestran que funciones como PARITY, m-SPARSE PARITY y DICTATOR (incluyendo FIRST) son demostrablemente inaprendibles para $N$ grande mediante transformers inicializados aleatoriamente. Estas funciones tienen una sensibilidad mínima $\ge 1$ (o $m$ para variantes dispersas), lo que significa que poseen cero cadenas de sensibilidad cero.
• Distinción de la Sensibilidad Promedio: El análisis revela que la sensibilidad promedio es insuficiente para predecir la aprendibilidad. Por ejemplo, la función FIRST tiene una sensibilidad promedio baja (igual a 1), pero es inaprendible para $N$ grande porque carece de cadenas de sensibilidad cero. Por el contrario, MAJORITY tiene una sensibilidad promedio baja pero posee un número exponencial de cadenas de sensibilidad cero, lo que le permite ocupar una región de medida positiva del espacio de parámetros.
• Conjetura sobre MAJORITY: Los autores conjeturan que MAJORITY es aprendible porque su abundancia de cadenas de sensibilidad cero corresponde a un subconjunto de medida positiva en el espacio de parámetros.
• Validación Empírica: Experimentos con transformers inicializados aleatoriamente y entrenados confirman que los espectros de sensibilidad están fuertemente sesgados hacia cero. Incluso después de entrenar en tareas como PARITY, los modelos fallan en alcanzar el perfil de sensibilidad correcto, mientras que los modelos entrenados en MAJORITY y FIRST (en longitudes moderadas) aprenden las tareas con éxito y exhiben el perfil de sensibilidad predicho.

Significado
El artículo proporciona una explicación teórica para el sesgo inductivo observado en los transformers hacia funciones de baja sensibilidad. Al desplazar el enfoque de la sensibilidad promedio hacia el perfil de sensibilidad completo y analizar las propiedades de la teoría de la medida de los parámetros, los autores demuestran que la inaprendibilidad de funciones como PARITY no es simplemente un fallo de optimización, sino una restricción geométrica fundamental: las configuraciones de parámetros requeridas para representar tales funciones ocupan un conjunto de medida cero. Esto implica que una inicialización aleatoria casi seguramente perderá estas configuraciones, y la optimización basada en gradientes, restringida por la distribución previa de la inicialización, es improbable que las alcance. El trabajo clarifica la frontera entre expresividad y aprendibilidad, mostrando que para entradas suficientemente largas, los transformers son fundamentalmente incapaces de reconocer lenguajes que carecen de cadenas de sensibilidad cero.