Constraining Genetic Symbolic Regression via Semantic Backpropagation

Maximilian Reissmann, Yuan Fang, Andrew Ooi, Richard D. Sandberg

In the quest to automate scientific discovery, Symbolic Regression (SR) stands out as a holy grail. Unlike "black-box" neural networks, SR aims to find the actual mathematical equations—like $F=ma$—that govern a dataset. However, traditional evolutionary approaches to SR have a glaring weakness: they are "physics-blind." They often propose equations that are mathematically a good fit but physically nonsensical, such as trying to add meters to seconds.

A recent paper, "Constraining Genetic Symbolic Regression via Semantic Backpropagation," introduces a clever way to fix this by integrating "Semantic Backpropagation" into Gene Expression Programming (GEP).

TL;DR

The authors propose a method to enforce physical constraints (like unit consistency) within evolutionary algorithms by "backpropagating" required dimensions through an expression tree. By replacing physically invalid sub-expressions with valid ones from a pre-computed library, they significantly improve the accuracy, simplicity, and noise-robustness of discovered physical laws.

What Problem Does This Paper Address?

Evolutionary algorithms like Gene Expression Programming (GEP) work by randomly mutating and recombining "genes" (mathematical symbols) to find the best-fitting equation. Because this process is inherently stochastic, it frequently generates "junk" solutions that violate the principle of dimensional homogeneity—the rule that you can only add or subtract quantities with the same units.

While neural networks can handle constraints using continuous loss functions and gradients, GEP is discrete and symbolic. Previous attempts to fix this usually involved simply discarding "invalid" equations (which kills population diversity) or adding a penalty to the fitness score (which is often too weak to guide the search effectively). The gap addressed here is: How do we actively correct an invalid equation during evolution rather than just punishing it?

Methods

The authors introduce a framework that treats physical dimensions as a vector representation. In the SI system, any unit can be represented as a vector of seven exponents (Mass, Length, Time, etc.). For example, Velocity ($m/s$) is $[0, 1, -1, 0, 0, 0, 0]$.

The core innovation is the integration of Semantic Backpropagation (SBP):

  1. Forward Pass: The algorithm evaluates the units of an expression tree from the leaves up to the root. If the root's units don't match the target (e.g., the data is for "Force" but the equation yields "Length"), a misalignment is detected.
  2. Backward Pass: Similar to backpropagation in neural networks, the algorithm moves down the tree. It calculates what the "desired" units should be for each branch to make the whole equation valid.
  3. Library Lookup: Instead of just mutating randomly, the algorithm consults a Library of Semantics—a pre-computed database of valid mathematical sub-expressions indexed by their physical units.
  4. Heuristic Correction: It swaps out the "broken" part of the tree with a "correct" one from the library that satisfies the dimensional requirements.

Datasets

The researchers evaluated their approach using SRBench, a standard benchmark for symbolic regression. Specifically, they focused on:

  • The Feynman Symbolic Regression Database: A collection of ~100 equations from the Feynman Lectures on Physics.
  • Synthetic Noise: They tested the model against various noise levels ($\gamma = 0.001$ to $0.1$) to simulate real-world experimental data.

Key Insights and Ideas

  • Correction over Rejection: By fixing equations instead of discarding them, the algorithm maintains a "healthier" population of candidate solutions, preventing the search from stagnating.
  • Pruning the Search Space: Enforcing physical units acts as a massive "filter." The space of all possible equations is infinite, but the space of dimensionally consistent equations is much smaller. This makes the search significantly more efficient.
  • Invariants as Anchors: Noise affects data points, but it doesn't change the underlying physics (units). By anchoring the search in dimensional logic, the algorithm becomes much more robust to messy, noisy data.

Key Results

  • Higher Success Rate: The proposed "SBP-GEP" improved the average symbolic recovery rate of standard GEP by 33% (from a 30.3% success rate to 44.27%).
  • Simpler Equations: The method produced equations that were up to 45% less complex than standard methods. In science, simpler equations (Occam's Razor) are generally preferred as they generalize better.
  • Noise Robustness: In high-noise scenarios, the SBP-GEP approach showed a 13.45% performance boost over standard GEP, proving that physical constraints help the algorithm "see through" the noise.
  • Competitive Performance: The SBP-GEP outperformed several state-of-the-art evolutionary methods (like GP-Gomea and gplearn) on the Feynman dataset.

Limitations and Future Work

  • Library Dependency: The effectiveness of the correction depends on the quality and size of the "Library of Semantics." If the library doesn't contain a suitable sub-expression, the correction fails.
  • Computational Cost: The SBP process and library lookups add overhead. The authors note that their method is roughly 2 to 2.5 times slower per iteration than standard GEP.
  • Future Directions: The authors suggest using Large Language Models (LLMs) or grammar-guided approaches to build more sophisticated libraries or to suggest even more "physically intuitive" mutations. They also aim to extend the framework to handle other constraints, such as mathematical symmetries.

Summary updated

Abstract

Evolutionary symbolic regression approaches are powerful tools that can approximate an explicit mapping between input features and observation for various problems. However, ensuring that explored expressions maintain consistency with domain-specific constraints remains a crucial challenge. While neural networks are able to employ additional information like conservation laws to achieve more appropriate and robust approximations, the potential remains unrealized within genetic algorithms. This disparity is rooted in the inherent discrete randomness of recombining and mutating to generate new mapping expressions, making it challenging to maintain and preserve inferred constraints or restrictions in the course of the exploration. To address this limitation, we propose an approach centered on semantic backpropagation incorporated into the Gene Expression Programming (GEP), which integrates domain-specific properties in a vector representation as corrective feedback during the evolutionary process. By creating backward rules akin to algorithmic differentiation and leveraging pre-computed subsolutions, the mechanism allows the enforcement of any constraint within an expression tree by determining the misalignment and propagating desired changes back. To illustrate the effectiveness of constraining GEP through semantic backpropagation, we take the constraint of physical dimension as an example. This framework is applied to discovering physical equations from the Feynman lectures. Results have shown not only an increased likelihood of recovering the original equation but also notable robustness in the presence of noisy data.
BibTeX
@inproceedings{reissmann2025constraining,
  author = {Maximilian Reissmann and Yuan Fang and Andrew Ooi and Richard D. Sandberg},
  title = {{Constraining Genetic Symbolic Regression via Semantic Backpropagation}},
  booktitle = {Genetic},
  year = {2025},
  doi = {10.1007/s10710-025-09510-z},
}
Figure