Cluster Analysis of a Symbolic Regression Search Space

Gabriel Kronberger, Lukas Kammerer, Bogdan Burlacu, Stephan M. Winkler, Michael Kommenda, Michael Affenzeller

How does a Genetic Programming (GP) algorithm actually "find" a solution? We know it evolves a population of mathematical expressions, but the "search space" it navigates is often treated as a black box. In their paper, "Cluster Analysis of a Symbolic Regression Search Space," Gabriel Kronberger and his team at the Heuristic and Evolutionary Algorithms Laboratory (HEAL) pull back the curtain. By exhaustively mapping a simplified search space, they reveal how mathematical expressions cluster together and how GP navigates this terrain to find the best fit.

TL;DR

Researchers mapped out a search space of 160,000 symbolic regression models to see how they "clump" together based on their behavior (phenotype) versus their structure (genotype). They discovered that while behavioral clustering is highly organized and helps predict model quality, structural clustering is messy; furthermore, they showed that Genetic Programming quickly "zooms in" on high-quality behavioral clusters within just a few generations.

What Problem Does This Paper Address?

Symbolic Regression (SR) is a type of machine learning that searches for mathematical formulas to describe a dataset. Unlike linear regression, where you just find the best coefficients for a fixed equation, SR tries to find the equation itself.

The problem is that the "search space" (the set of all possible mathematical expressions) is infinite and incredibly complex. We don't really know what this space "looks like." Are similar-looking equations actually similar in behavior? Does a GP algorithm wander aimlessly, or does it follow a specific path? By understanding the structure of the search space, researchers hope to make SR algorithms faster and more efficient.

Methods

To make the study feasible, the authors restricted the scope to uni-variate models (one variable, $x$) and used a context-free grammar to generate expressions. They limited the complexity to a maximum of seven variable references and excluded numeric constants.

  1. Exhaustive Enumeration: They generated all possible unique expressions within these constraints, resulting in a set of roughly 160,000 unique models.
  2. Phenotypic vs. Genotypic Similarity:
    • Phenotypic (Behavioral): Two models are similar if they produce similar outputs when given the same inputs. This was measured using Pearson’s correlation.
  3. Genotypic (Structural): Two models are similar if their "tree structures" (the way the math is written) are similar. This was measured using the Sørensen-Dice index on tree nodes.
  4. Visualization and Clustering: To visualize this high-dimensional data in 2D, they used t-SNE and LargeVis. To group similar models, they used HDBSCAN (a density-based clustering algorithm).
  5. GP Tracking: They ran a standard GP on a benchmark problem and "mapped" where each individual in the population fell within the pre-computed clusters over time.

Datasets

The study used five well-known symbolic regression benchmark functions to evaluate the quality of the generated models:

  • Keijzer-4 and Keijzer-9
  • Pagie-1d
  • Nguyen-5 and Nguyen-6

These are synthetic mathematical functions used to test how well an algorithm can "rediscover" the underlying law from data points.

Key Insights and Ideas

  • Phenotype is more "organized" than Genotype: When the 160,000 models were mapped based on their behavior (phenotype), they formed distinct, clear clusters. However, when mapped by their structure (genotype), the clusters were much "fuzzier" and less distinct.
  • Structure doesn't always dictate behavior: The authors found that small changes in an equation's structure (genotype) can lead to massive changes in its output (phenotype)—for example, multiplying a large term by zero. Conversely, very different-looking equations can behave identically.
  • The "Search Path" of GP: By tracking a GP run on the map, they saw that in the first generation, the population is scattered across almost all 16,000 identified clusters. However, by generation 10, the algorithm had already narrowed its focus to a few "high-quality" clusters.
  • Pre-computation potential: Because the phenotypic map is based on the relationship between models (and not the target data), it only needs to be calculated once. This map could potentially be used to "warm-start" future GP runs by picking diverse starting points from different clusters.

Key Results

  • Cluster Quality: For the Keijzer-4 and Pagie-1d problems, the search space contained clusters where the average $R^2$ (a measure of fit) was above 0.95.
  • Efficiency of GP: The visualization showed that GP is remarkably efficient at discarding "junk" areas of the search space. It reduced the "active" search area from nearly the entire space to a small subset of clusters in just a few iterations.
  • Complexity: The authors identified that even with a small limit on expression length, the search space is vast, but the number of functionally distinct behaviors is smaller than the number of possible equations.

Limitations and Future Work

  • Dimensionality: The study was limited to uni-variate (1D) functions. Adding more variables increases the search space exponentially, making exhaustive enumeration impossible.
  • Constants: The exclusion of constants (like $y = 2.5x$) is a significant simplification, as real-world data often requires precise coefficients.
  • Discontinuity: The grammar produced many "broken" functions (e.g., division by zero). Filtering these out could refine the map.
  • Future Direction: The authors suggest using these insights to create "pre-evolved" populations—starting a search with a diverse set of "building block" models chosen from across the phenotypic map to speed up convergence on new problems.

Summary updated

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.
BibTeX
@inproceedings{kronberger2018cluster,
  author = {Gabriel Kronberger and Lukas Kammerer and Bogdan Burlacu and Stephan M. Winkler and Michael Kommenda and Michael Affenzeller},
  title = {{Cluster Analysis of a Symbolic Regression Search Space}},
  booktitle = {GPTP},
  year = {2018},
  url = {https://openreview.net/forum?id=t3rmwVz_t86},
}

Loading related content...

Figure