Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning

Resumen Técnico: Generalización más Lenta, Memorización más Rápida: Un Punto Óptimo en el Aprendizaje Algorítmico

Definición del Problema
Mientras que las leyes de escalado empíricas y los estudios de "grokking" sugieren que conjuntos de datos más grandes mejoran generalmente el rendimiento del modelo y que los datos adicionales aceleran la convergencia de validación una vez superado un umbral de generalización, este artículo investiga si esta intuición se mantiene universalmente para tareas de salida estructurada. Específicamente, los autores preguntan: Después de que la generalización se vuelve posible, ¿el conjunto de datos más grande siempre produce la convergencia de validación más rápida bajo un protocolo de optimización fijo? El estudio se centra en la generación de matrices Needleman–Wunsch (NW), una tarea donde un modelo debe predecir una matriz completa de puntuación de programación dinámica a partir de dos cadenas de entrada. A diferencia de las tareas aritméticas escalares, NW requiere la predicción coordinada de muchas celdas dependientes, creando una salida estructurada de alta complejidad.

Metodología
Los autores emplean un protocolo experimental controlado utilizando Transformers solo de decodificador entrenados en la generación de matrices NW y una línea base de multiplicación de tres dígitos.

• Tarea: El modelo mapea pares de cadenas de entrada $(x, y)$ a una matriz objetivo $M(x, y)$ generada por la recurrencia de programación dinámica NW. La corrección se mide mediante precisión de coincidencia exacta (todas las entradas de la matriz deben ser correctas).
• Variables: La variable principal es el tamaño del conjunto de datos ($N$), barrido a lo largo de un amplio rango (desde 200 hasta 300,000 ejemplos). La profundidad del modelo, la configuración del optimizador (AdamW) y los calendarios de tasa de aprendizaje se mantienen fijos.
• Métricas: El estudio mide el número de actualizaciones del optimizador requeridas para alcanzar umbrales específicos de precisión de coincidencia exacta ($\tau$) tanto para entrenamiento ($IT$) como para validación ($IV$). Esta métrica "basada en actualizaciones" distingue la velocidad de convergencia de la eficiencia normalizada por épocas.
• Sondas: Para desentrañar el aprendizaje de reglas de la memorización, los autores introducen una sonda de sufijo aleatorio, añadiendo un sufijo aleatorio de cuatro bits a la matriz objetivo. Esto aísla la información específica del ejemplo (el sufijo) de la estructura generada por la regla (la matriz).
• Líneas base: La multiplicación de tres dígitos sirve como tarea de contraste para verificar si los fenómenos observados son específicos de la programación dinámica estructurada o artefactos de la evaluación de coincidencia exacta.

Contribuciones Clave
El artículo hace tres contribuciones empíricas principales:

1. Identificación de un Punto Óptimo de Tamaño de Conjunto de Datos: En la generación de matrices NW, la convergencia de validación es más rápida en un tamaño de conjunto de datos intermedio, no en el más grande. Esto contradice la intuición estándar post-umbral de que "más datos siempre es más rápido" una vez que la generalización es alcanzable.
2. Aceleración del Ajuste mediante Aprendizaje Parcial de Reglas: En el régimen donde aparece por primera vez una competencia débil de validación, aumentar el tamaño del conjunto de datos puede en realidad reducir el número de actualizaciones necesarias para alcanzar una alta precisión de entrenamiento. Esto sugiere que el aprendizaje parcial de reglas puede acelerar el proceso de ajuste, en lugar de simplemente añadir una carga de memorización.
3. Separación Mecanística de Presiones: Los autores proponen un "cuento de dos presiones" donde los datos adicionales inicialmente ayudan al descubrimiento de reglas (mejorando la cobertura estructural) pero eventualmente aumentan el costo del ajuste exacto residual (memorizar detalles no determinados completamente por la regla).

Resultados

• Convergencia de Validación No Monótona: Para NW, el número de actualizaciones para alcanzar umbrales estrictos de validación (por ejemplo, $\tau=0.98$) sigue una curva en forma de U. Los conjuntos de datos pequeños no logran generalizar o requieren largos retrasos. Los conjuntos de datos intermedios convergen más rápido. Los conjuntos de datos grandes aún generalizan pero requieren significativamente más actualizaciones para alcanzar el mismo umbral, indicando una "ralentización post-umbral".
• Contraste con la Multiplicación: La línea base de multiplicación no exhibe esta ralentización; la convergencia de validación permanece plana o mejora con conjuntos de datos más grandes. Esto confirma que el fenómeno está ligado a la estructura específica de la tarea NW (salidas largas y dependientes) en lugar de a la métrica de coincidencia exacta en sí misma.
• Tiempo de Entrenamiento vs. Validación: Cerca del inicio de la generalización, los conjuntos de datos más grandes pueden reducir las actualizaciones necesarias para una alta precisión de entrenamiento. Esto indica que la memorización y la generalización no son estrictamente secuenciales; la adquisición parcial de reglas puede hacer que la tarea de ajuste restante sea más fácil.
• Diagnósticos de Sufijo Aleatorio: En tamaños de conjunto de datos más grandes, el modelo ajusta la matriz generada por la regla antes de ajustar el sufijo aleatorio. Esto respalda la hipótesis de que el componente estructurado se beneficia de la regla aprendida, mientras que el sufijo no estructurado representa la carga residual de "ajuste exacto" que crece con el tamaño del conjunto de datos.
• Brecha Entrenamiento-Validación: La brecha entre la precisión de entrenamiento y validación ($G = A_T - A_R$) se vuelve positiva precisamente cuando la precisión de validación comienza a subir, sugiriendo que el mismo progreso mediado por reglas impulsa ambos.

Significado y Afirmaciones
El artículo afirma refinar, en lugar de contradecir, la literatura clásica sobre grokking y tamaño crítico de datos.

• Refinamiento del Tamaño Crítico de Datos: Mientras que el tamaño crítico de datos ($N_c$) marca el inicio de la generalización (cuando una solución se vuelve identificable), los autores muestran que el tamaño del conjunto de datos que optimiza la velocidad de convergencia basada en actualizaciones ($N^*$) puede ser distinto de $N_c$ y distinto del conjunto de datos máximo disponible.
• Divergencia de Etapas de Aprendizaje: Los resultados demuestran que en tareas de salida estructurada, "aprender la regla" y "completar el ajuste exacto" pueden divergir. Una vez que se descubre una regla útil, más datos pueden principalmente aumentar la carga de ajustar detalles residuales, ralentizando la convergencia en términos de actualizaciones de gradiente.
• Alcance: Los autores afirmodestamente que este fenómeno es específico de tareas que combinan estructura algorítmica reutilizable con alta complejidad de salida por ejemplo (por ejemplo, tablas de programación dinámica como la distancia de edición o la decodificación de Viterbi). No afirman que esto se aplique a todas las tareas algorítmicas ni que los conjuntos de datos más grandes sean intrínsecamente dañinos para la precisión asintótica, sino más bien que el camino hacia la convergencia en términos de actualizaciones del optimizador es no monótono en configuraciones estructuradas específicas.

El estudio concluye que para el aprendizaje de salida estructurada, la ruta más rápida hacia la generalización de validación puede ocurrir en un tamaño de conjunto de datos intermedio donde los beneficios del descubrimiento de reglas se han saturado, pero los costos del ajuste exacto residual aún no se han vuelto dominantes.