A Comparative Study of Model Selection Criteria for Symbolic Regression

Resumo Técnico: Um Estudo Comparativo de Critérios de Seleção de Modelos para Regressão Simbólica

Declaração do Problema
A Regressão Simbólica (RS), tipicamente resolvida via Programação Genética (PG), visa descobrir expressões matemáticas que equilibrem precisão e complexidade. Embora implementações modernas de PG gerem uma frente de Pareto de soluções candidatas, a seleção automática de um único modelo que generalize bem para dados não vistos permanece um desafio em aberto. A literatura existente oferece várias abordagens baseadas em teoria da informação e Bayesianas, mas comparações empíricas abrangentes de seu desempenho em diferentes regimes de dados são limitadas. Há uma falta de orientação prática sobre qual critério de seleção preferir sob condições específicas para evitar o sobreajuste, mantendo ao mesmo tempo a interpretabilidade.

Metodologia
Os autores conduziram uma comparação empírica sistemática de seis critérios de seleção de modelos amplamente utilizados:

1. Critério de Informação de Akaike (AIC)
2. AIC Corrigido (AICc)
3. Critério de Informação Bayesiano (BIC)
4. Comprimento Mínimo de Descrição (MDL)
5. Estimativa de erro intra-amostra baseada em bootstrap de Efron ($Err_{in}$)
6. Erro Quadrático Médio de Treinamento ($MSE_{train}$) utilizado como linha de base.

Configuração Experimental:

• Conjuntos de Dados: Sete funções de referência sintéticas (comuns na literatura de PG) foram utilizadas. Os dados de treinamento consistiram em 100 pontos com ruído gaussiano adicionado ($\epsilon \sim N(0, (0.1\sigma(y))^2)$), enquanto os dados de teste compreendiam 10.000 pontos livres de ruído.
• Geração de Candidatos: Para desacoplar a avaliação de algoritmos específicos de RS, um pool controlado de expressões candidatas foi gerado perturbando as funções verdadeiras. Um procedimento de mutação substituiu nós aleatórios nas árvores verdadeiras por subárvores aleatórias. Esses candidatos foram ajustados aos dados de treinamento usando otimização BFGS (repetida 100 vezes para evitar ótimos locais). O processo gerou 100 modelos sobreajustados por referência (aqueles com menor MSE de treinamento que o verdadeiro) para testar a capacidade dos critérios de recuperar o modelo verdadeiro a partir de um conjunto de alternativas sobreajustadas.
• Métricas de Avaliação:
  • $MSE_{test}$ Média: Desempenho dos modelos classificados nos top-$k$.
  • Precisão em $k$: A fração dos modelos selecionados nos top-$k$ que pertencem aos verdadeiros top-$k$ com base no erro de teste.
  • Tamanho Médio da Expressão: Complexidade estrutural média (contagem de nós) dos modelos selecionados.
  • Acerto da Verdade: O menor rank $k$ no qual a expressão verdadeira exata é recuperada.

Principais Contribuições e Resultados
O estudo fornece uma classificação detalhada dos critérios de seleção com base nas quatro métricas acima:

• MDL (Comprimento Mínimo de Descrição): Emergiu consistentemente como o critério mais robusto. Identificou modelos com o menor erro de teste para pequenos $k$ em seis de sete referências e produziu as expressões mais parcimoniosas (menores). MDL e BIC demonstraram a maior eficiência na recuperação da expressão verdadeira, com ranks médios de primeiro acerto de 5,14 e 6,00, respectivamente.
• BIC: Desempenhou-se de forma semelhante ao MDL em termos de recuperação da verdade e forneceu resultados intermediários estáveis entre as referências, frequentemente gerando fórmulas concisas.
• AIC e AICc: Geralmente classificaram-se abaixo do MDL e do BIC em relação à generalização. Embora o AICc tenha mostrado ligeiras melhorias sobre o AIC padrão para funções específicas ($f_1, f_2$), ambos tenderam a selecionar modelos mais complexos que o MDL.
• $Err_{in}$ (Erro Intra-Amostra de Bootstrap): Mostrou resultados mistos. Embora tenha alcançado boa precisão e generalização para alguns conjuntos de dados ($f_1, f_2, f_3, f_6, f_7$), desempenhou-se mal em outros ($f_4, f_5$), frequentemente selecionando expressões maiores e falhando em recuperar a verdade de forma eficiente (rank médio 31,71). Os autores atribuem essa inconsistência à dependência das estimativas de variância do ruído do Random Forest.
• $MSE_{train}$: Desempenhou-se consistentemente da pior forma, confirmando que o erro de treinamento não regularizado leva a um sobreajuste severo e à má generalização.

Complexidade Computacional
O artigo analisa a sobrecarga computacional desses critérios:

• AIC, AICc, BIC: Mais eficientes ($O(n)$), exigindo apenas uma única passagem sobre os dados após a estimação dos parâmetros.
• MDL: Ligeiramente mais caro ($O(n \cdot p)$) devido ao cálculo da matriz de informação de Fisher, mas permanece eficiente para tamanhos típicos de expressões de RS.
• $Err_{in}$: Significativamente o mais intensivo computacionalmente, exigindo $B$ iterações de bootstrap (tipicamente 200) e reajustes repetidos de parâmetros, tornando-o potencialmente impraticável para processos iterativos de busca evolutiva.

Significado e Afirmações
Os autores afirmam que suas descobertas oferecem orientação prática para pipelines de RS. Eles concluem que o MDL é uma escolha padrão forte para seleção precoce robusta e modelos compactos, com o BIC como opção secundária. Eles sugerem que o AIC/AICc pode ser preferível apenas quando modelos ligeiramente maiores são aceitáveis e a penalidade do MDL é considerada excessivamente conservadora. Por outro lado, eles não recomendam o $Err_{in}$ devido ao seu alto custo computacional e desempenho inconsistente em seus experimentos.

O estudo observa explicitamente limitações, incluindo o uso de um único nível de ruído para geração de dados e o fato de que os critérios foram avaliados em um pool de candidatos post-hoc em vez de integrados diretamente no loop de busca da PG. Os autores afirmam que trabalhos futuros devem investigar intensidades de ruído variáveis e a integração desses critérios no processo de busca evolutiva.