Controlling Functional Complexity for Overfitting Avoidance in Genetic Programming

Abstract

A Programação Genética (PG) é uma técnica versátil no campo da Computação Evolucionária que oferece soluções para uma ampla variedade de problemas. Este trabalho foca-se numa aplicação comum da PG - a Regressão Simbólica (RS) - que tem como objetivo descobrir funções matemáticas que descrevam as relações entre variáveis de input e output de um dataset. Embora a PG se destaque pela sua capacidade de evoluir expressões diversas sem tamanho ou forma pré-definida, um desafio central é o sobreajuste (ou overfitting, como é normalmente chamado), fenómeno que se verifica quando as funções se ajustam demasiado aos dados de treino, comprometendo a sua capacidade de generalização em novos dados. Apesar das técnicas de regularização tradicionalmente usadas para combate de overfitting estarem amplamente estudadas na literatura, estas são difíceis de aplicar diretamente à PG devido à sua estrutura flexível e ausência de otimização de parâmetros. Posto isto, este estudo propõe uma abordagem inovadora para minimizar o overfitting em PG, que se baseia numa otimização dupla ao longo da evolução: a minimização do erro e a penalização da complexidade funcional das expressões evoluídas, recorrendo a mecanismos de seleção multi-objetivo. Enquanto a minimização do erro é um objetivo comum em PG, a penalização da complexidade funcional é um passo extra que procura evitar a evolução de expressões excessivamente complexas e sobreajustadas. A medida de complexidade funcional utilizada neste estudo aproxima a curvatura de uma função, refletindo a sua tendência para sobreajustar os dados de treino. Resultados experimentais em oito conjuntos de dados de RS demonstram a eficácia das duas variantes do método proposto na redução de overfitting, por comparação com os resultados de referência da PG padrão. O estudo realça a importância de equilibrar a redução de complexidade com a capacidade preditiva nos modelos evoluídos pela PG, de forma a garantir que tanto funções precisas como simples são selecionadas. Além disso, são analisados os impactos de diferentes hiperparâmetros numa das variantes do método proposto, assim como são analisadas várias características das funções evoluídas, como a sua curvatura e tamanho. É também estabelecida, de modo formal, uma correlação entre a complexidade funcional e o overfitting, e os benefícios do método proposto para a interpretabilidade dos modelos e seleção de variáveis e redução de bloat são discutidos.

Genetic programming (GP) is a versatile technique within the field of Evolutionary Computation (EC), offering solutions to a wide range of problems. This work focuses on Symbolic Regression (SR), a common application of GP that aims to discover mathematical functions describing the relationships between input and target variables of a given dataset. While GP stands out for evolving diverse functions with no constraints in size or shape, a key challenge is overfitting, where models become too adjusted to the training data, compromising their generalization to new, unseen data. Although traditional regularization techniques are widely studied in the literature, they are challenging to apply directly to GP due to its flexible structure and lack of parameter optimization. Therefore, this work proposes a novel approach to mitigate overfitting in GP, involving a dual optimization process throughout evolution: minimizing error and penalizing the functional complexity of expressions using multiobjective selection mechanisms. While error minimization is a common goal in GP, penalizing functional complexity is an additional step aimed at avoiding overly complex functions. The functional complexity measure used in this study approximates the curvature of an expression, reflecting its tendency to overfit the training data. Experimental results on eight SR datasets demonstrate the effectiveness of two variants of the proposed method in reducing overfitting, as evidenced by a comparison to the baseline results of Standard GP (StdGP). The study explores and emphasizes the importance of balancing complexity reduction with overall predictive accuracy of evolved models, ensuring the selection of both accurate and simple functions. Additionally, the impact of different hyperparameters on the proposed method is analyzed, along with various characteristics of the evolved functions, such as their curvature and size. Finally, a formal correlation between functional complexity and overfitting is established, and the benefits of the proposed method for model interpretability, feature selection and bloat reduction are discussed.