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

Resumo Técnico: Generalização Mais Lenta, Memorização Mais Rápida: Um Ponto Ideal no Aprendizado Algorítmico

Definição do Problema
Enquanto as leis de escala empíricas e os estudos de "grokking" sugerem que conjuntos de dados maiores geralmente melhoram o desempenho do modelo e que dados adicionais aceleram a convergência na validação uma vez ultrapassado um limiar de generalização, este artigo investiga se essa intuição se mantém universalmente para tarefas de saída estruturada. Especificamente, os autores perguntam: Após a generalização se tornar possível, o maior conjunto de dados sempre produz a convergência na validação mais rápida sob um protocolo de otimização fixo? O estudo foca na geração de matrizes Needleman–Wunsch (NW), uma tarefa onde um modelo deve prever uma matriz completa de pontuação de programação dinâmica a partir de dois strings de entrada. Diferentemente de tarefas aritméticas escalares, a NW requer a previsão coordenada de muitas células dependentes, criando uma saída estruturada de alta complexidade.

Metodologia
Os autores empregam um protocolo experimental controlado utilizando Transformers apenas com decodificadores treinados na geração de matrizes NW e uma linha de base de multiplicação de três dígitos.

• Tarefa: O modelo mapeia pares de strings de entrada $(x, y)$ para uma matriz alvo $M(x, y)$ gerada pela recorrência de programação dinâmica NW. A correção é medida via acurácia de correspondência exata (todas as entradas da matriz devem estar corretas).
• Variáveis: A variável principal é o tamanho do conjunto de dados ($N$), variado em uma ampla faixa (de 200 a 300.000 exemplos). A profundidade do modelo, as configurações do otimizador (AdamW) e os cronogramas de taxa de aprendizado são mantidos fixos.
• Métricas: O estudo mede o número de atualizações do otimizador necessárias para atingir limiares específicos de acurácia de correspondência exata ($\tau$) tanto para treinamento ($IT$) quanto para validação ($IV$). Esta métrica "baseada em atualizações" distingue a velocidade de convergência da eficiência normalizada por época.
• Sondas: Para desvendar a aprendizagem de regras da memorização, os autores introduzem uma sonda de sufixo aleatório, anexando um sufixo aleatório de quatro bits à matriz alvo. Isso isola informações específicas do exemplo (o sufixo) da estrutura gerada pela regra (a matriz).
• Linhas de Base: A multiplicação de três dígitos serve como uma tarefa de contraste para verificar se os fenômenos observados são específicos da programação dinâmica estruturada ou artefatos da avaliação de correspondência exata.

Principais Contribuições
O artigo faz três contribuições empíricas primárias:

1. Identificação de um Ponto Ideal de Tamanho de Conjunto de Dados: Na geração de matrizes NW, a convergência na validação é mais rápida em um tamanho de conjunto de dados intermediário, não no maior. Isso contradiz a intuição pós-limiar padrão de que "mais dados é sempre mais rápido" uma vez que a generalização é alcançável.
2. Aceleração do Ajuste via Aprendizagem Parcial de Regras: No regime onde a competência fraca na validação aparece pela primeira vez, aumentar o tamanho do conjunto de dados pode na verdade reduzir o número de atualizações necessárias para atingir alta acurácia no treinamento. Isso sugere que a aprendizagem parcial de regras pode acelerar o processo de ajuste, em vez de apenas adicionar uma carga de memorização.
3. Separação Mecanística de Pressões: Os autores propõem uma "conta de duas pressões" onde dados adicionais inicialmente auxiliam a descoberta de regras (melhorando a cobertura estrutural), mas eventualmente aumentam o custo do ajuste exato residual (memorizar detalhes não totalmente determinados pela regra).

Resultados

• Convergência na Validação Não Monotônica: Para a NW, o número de atualizações para atingir limiares estritos de validação (por exemplo, $\tau=0.98$) segue uma curva em forma de U. Conjuntos de dados pequenos falham em generalizar ou exigem longos atrasos. Conjuntos de dados intermediários convergem mais rápido. Conjuntos de dados grandes ainda generalizam, mas exigem significativamente mais atualizações para atingir o mesmo limiar, indicando um "desaceleração pós-limiar".
• Contraste com Multiplicação: A linha de base de multiplicação não exibe esse desaceleração; a convergência na validação permanece plana ou melhora com conjuntos de dados maiores. Isso confirma que o fenômeno está ligado à estrutura específica da tarefa NW (saídas longas e dependentes) e não à métrica de correspondência exata em si.
• Temporização de Treinamento vs. Validação: Perto do início da generalização, conjuntos de dados maiores podem reduzir as atualizações necessárias para alta acurácia no treinamento. Isso indica que memorização e generalização não são estritamente sequenciais; a aquisição parcial de regras pode tornar a tarefa de ajuste restante mais fácil.
• Diagnósticos de Sufixo Aleatório: Em tamanhos de conjunto de dados maiores, o modelo ajusta a matriz gerada pela regra antes de ajustar o sufixo aleatório. Isso apoia a hipótese de que o componente estruturado se beneficia da regra aprendida, enquanto o sufixo não estruturado representa a carga residual de "ajuste exato" que cresce com o tamanho do conjunto de dados.
• Lacuna Treinamento-Validação: A lacuna entre a acurácia de treinamento e validação ($G = A_T - A_R$) torna-se positiva precisamente quando a acurácia na validação começa a subir, sugerindo que o mesmo progresso mediado por regras impulsiona ambos.

Significado e Afirmações
O artigo afirma refinar, em vez de contradizer, a literatura clássica sobre grokking e tamanho crítico de dados.

• Refinando o Tamanho Crítico de Dados: Enquanto o tamanho crítico de dados ($N_c$) marca o início da generalização (quando uma solução se torna identificável), os autores mostram que o tamanho do conjunto de dados que otimiza a velocidade de convergência baseada em atualizações ($N^*$) pode ser distinto de $N_c$ e distinto do conjunto de dados máximo disponível.
• Divergência das Estágios de Aprendizado: Os resultados demonstram que, em tarefas de saída estruturada, "aprender a regra" e "completar o ajuste exato" podem divergir. Uma vez que uma regra útil é descoberta, dados adicionais podem principalmente aumentar a carga de ajustar detalhes residuais, desacelerando a convergência em termos de atualizações de gradiente.
• Escopo: Os autores afirmam modestamente que este fenômeno é específico para tarefas que combinam estrutura algorítmica reutilizável com alta complexidade de saída por exemplo (por exemplo, tabelas de programação dinâmica como distância de edição ou decodificação de Viterbi). Eles não afirmam que isso se aplica a todas as tarefas algorítmicas ou que conjuntos de dados maiores são intrinsecamente prejudiciais para a acurácia assintótica, mas sim que o caminho para a convergência em termos de atualizações do otimizador é não monotônico em configurações estruturadas específicas.

O estudo conclui que, para aprendizado de saída estruturada, a rota mais rápida para a generalização na validação pode ocorrer em um tamanho de conjunto de dados intermediário onde os benefícios da descoberta de regras saturaram, mas os custos do ajuste exato residual ainda não se tornaram dominantes.