Equality Graph Assisted Symbolic Regression
This addresses efficiency issues in symbolic regression for researchers and practitioners, though it appears incremental as it builds on existing genetic programming methods.
The paper tackles the problem of redundant expression evaluations in genetic programming for symbolic regression, which can account for up to 60% of total evaluations, by proposing SymRegg, a new search algorithm that uses equality graphs to avoid unnecessary computations. The result shows improved search efficiency while maintaining accurate results across datasets with minimal hyperparameters.
In Symbolic Regression (SR), Genetic Programming (GP) is a popular search algorithm that delivers state-of-the-art results in term of accuracy. Its success relies on the concept of neutrality, which induces large plateaus that the search can safely navigate to more promising regions. Navigating these plateaus, while necessary, requires the computation of redundant expressions, up to 60% of the total number of evaluation, as noted in a recent study. The equality graph (e-graph) structure can compactly store and group equivalent expressions enabling us to verify if a given expression and their variations were already visited by the search, thus enabling us to avoid unnecessary computation. We propose a new search algorithm for symbolic regression called SymRegg that revolves around the e-graph structure following simple steps: perturb solutions sampled from a selection of expressions stored in the e-graph, if it generates an unvisited expression, insert it into the e-graph and generates its equivalent forms. We show that SymRegg is capable of improving the efficiency of the search, maintaining consistently accurate results across different datasets while requiring a choice of a minimalist set of hyperparameters.