Abstract
In this chapter we take a closer look at the distribution of symbolic regression models generated by genetic programming in the search space. The motivation for this work is to improve the search for well-fitting symbolic regression models by using information about the similarity of models that can be precomputed independently from the target function. For our analysis, we use a restricted grammar for uni-variate symbolic regression models and generate all possible models up to a fixed length limit. We identify unique models and cluster them based on phenotypic as well as genotypic similarity. We find that phenotypic similarity leads to well-defined clusters while genotypic similarity does not produce a clear clustering. By mapping solution candidates visited by GP to the enumerated search space we find that GP initially explores the whole search space and later converges to the subspace of highest quality expressions in a run for a simple benchmark problem.
Introduction
Symbolic Regression (SR) is a powerful machine learning technique that searches for mathematical formulas to describe datasets. Unlike traditional regression, which optimizes coefficients for a fixed equation, SR evolves the equation's structure itself. However, the search space of all possible mathematical expressions is infinite and complex, often treated as a "black box." This research aims to map this landscape to understand how models cluster and how Genetic Programming (GP) algorithms navigate this terrain.
Methodology
To analyze the search space, the researchers restricted the scope to uni-variate models using a context-free grammar. The complexity was limited to seven variable references, excluding numeric constants. This resulted in approximately 160,000 unique models.
The analysis followed two primary paths to define similarity between models:
- Phenotypic (Behavioral) Similarity: Two models are similar if they produce similar outputs when given the same inputs, measured using Pearson’s correlation.
- Genotypic (Structural) Similarity: Two models are similar if their tree structures are similar, measured using the Sørensen-Dice index on tree nodes.
High-dimensional data was visualized using t-SNE and LargeVis, while HDBSCAN was employed for density-based clustering to group similar models.
Results and Discussion
The study revealed a stark contrast between behavioral and structural organization. Phenotypic mapping produced distinct, well-defined clusters, whereas genotypic mapping resulted in "fuzzier" groupings. This indicates that structural similarity is a poor predictor of behavioral similarity; minor structural changes can lead to drastic output shifts, while vastly different structures can exhibit identical behaviors.
The quality of models within the search space was evaluated against benchmarks like Keijzer-4 and Pagie-1d. As shown in the distribution for Keijzer-4, while the majority of the 160,000 models perform poorly, there are significant clusters of high-quality expressions.
GP Navigation and Search Efficiency
By tracking GP runs, the authors found that the algorithm is remarkably efficient. In the initial generation, the population is scattered across nearly all identified phenotypic clusters. However, by generation 10, the search "zooms in" on a small subset of high-quality clusters, effectively discarding the vast majority of "junk" areas in the search space. This suggests that GP is not wandering aimlessly but quickly identifying productive regions of the phenotypic landscape.
Conclusion
This exhaustive mapping of a restricted SR search space demonstrates that phenotypic clustering provides a more organized view of model behavior than genotypic clustering. The efficiency of GP in navigating this space suggests that pre-computing these phenotypic maps could be used to "warm-start" future searches with diverse, high-quality starting populations. Future research will explore expanding this analysis to multi-variate spaces and incorporating numeric constants.
Summary updated