Asking Experiments Which Formula Is True: Structure-Targeted Active Learning for Symbolic Regression

Symbolic regression searches for a mathematical formula that explains data, rather than fitting weights inside a fixed model. The number of candidate formulas grows exponentially with formula length. The consequence that matters here is that, with limited and noisy data, many different formulas fit equally well. They agree where the data lies and disagree, sometimes wildly, outside it. Most search methods hide this ambiguity by returning one winner. The obvious fix is to collect more data, but data that does not separate the competing formulas wastes experiments.

We propose to choose each new measurement so that it best tells apart which formula is true, rather than where predictions are most uncertain. The method works over a weighted set of candidate formulas. Three refinements make it differ from plain prediction disagreement. Formulas that are syntactically different but mathematically identical are merged into one hypothesis. Uncertainty about each formula's fitted constants is subtracted out. Measurement noise is subtracted out. The same weights then give a reported probability that the leading formula is the true law, which serves as a stopping rule. That probability can be checked for calibration against actual exact-recovery outcomes.

Core Claim

Disagreement among candidate formulas comes from three sources that current active learning for symbolic regression treats as one. The first is genuinely different functional structures. The second is the same structure with different constant values. The third is noise in the measurements. Only the first source tells us which law is correct.

The closest prior work is Active Learning in Genetic Programming. It treats a genetic programming population as an ensemble and queries the points where the differential entropy of the members' predictions is highest, found with differential evolution. It shows this beats random sampling on 35 Feynman problems and two Strogatz problems. That signal, however, counts duplicated syntactic variants as independent votes. It spends queries resolving constants instead of structure, and it cannot discount noise.

We claim that an acquisition score equal to the mutual information between the next observation and the identity of the formula will need fewer queries to recover exact laws in noisy settings, at roughly 1–10% noise. Here "the identity of the formula" means its equivalence class, so that all ways of writing the same function count as one hypothesis. The score is computed with constants and noise marginalized. We further claim that the class weights yield a calibrated probability that the top class is correct. Neither prior paper reports such a probability.

In the noise-free case with well-determined constants, our score collapses toward plain disagreement. We therefore expect parity there and predict gains only where the three sources are actually mixed. This prediction is what makes the claim falsifiable.

Research Program

The pipeline has three parts.

The first part is a candidate pool. Any symbolic searcher can supply it. For fairness with the closest baseline we use the genetic programming population itself, and as a second variant the top candidates of a neural-guided searcher such as uDSR. uDSR combines reinforcement-learning-guided generation, pre-training, genetic programming seeding and linear sub-models, but returns a single point estimate.

The second part is collapsing equivalent expressions. We reuse equality graphs from EGG-SR, which embeds symbolic equivalence into symbolic regression search. Our use of equality graphs is different: they define the hypothesis variable for uncertainty, rather than serving as a search speed-up. Each surviving class $k$ gets a weight $w_k$ proportional to a complexity prior times a Laplace approximation of its marginal likelihood. The Laplace approximation fits the constants and places a Gaussian around them. This replaces the scalar Bayesian Information Criterion reward of CADSR, which balances fit against complexity inside a policy-gradient reward but discards the alternatives it penalizes.

The third part is the acquisition score. Each class predicts at input $x$ a Gaussian with mean $\mu_k(x)$. Its variance $s_k^2(x)$ comes from linearizing the formula in its uncertain constants, plus the noise variance $\sigma^2$, which is estimated jointly. The score is

$$a(x)=H\Big[\textstyle\sum_k w_k\,\mathcal N\big(\mu_k(x),\,s_k^2(x)+\sigma^2\big)\Big]-\sum_k w_k\,\tfrac12\log\big(2\pi e\,(s_k^2(x)+\sigma^2)\big).$$

Here $H$ is differential entropy, estimated by Monte Carlo. The first term is total predictive uncertainty. The second is the uncertainty that would remain even if we knew which class was true. Their difference is the expected information about formula identity. We maximize $a(x)$ with differential evolution, exactly as the baseline does, so that the optimizer is not a confound. After each query the pool is re-searched, reweighted and re-collapsed. Search stops when the top class weight exceeds a threshold $\tau$.

The Bayesian framing is motivated by ERRLESS. ERRLESS samples formulas in proportion to their posterior with a maximum-entropy policy and shows that averaging over sampled formulas extrapolates more stably than a single best one. It also reports that its sampler struggles once large datasets make the likelihood very "peaky." That failure constrains our design. It is a reason not to make posterior sampling the core mechanism. It also suggests a side hypothesis that we will test rather than assume: identifying the law from a small, deliberately chosen dataset may sidestep the peaky regime altogether.

Baselines

The naive reference point is uniform random sampling of the input domain, together with Latin hypercube sampling. Both use the same genetic programming searcher, the same per-round search budget and the same total query budget. This tells us how much any acquisition rule is worth.

The strongest competitor is the differential-entropy acquisition of Active Learning in Genetic Programming. It is the only published method that uses a symbolic ensemble's uncertainty to choose experiments for law discovery, and it already beats random and diversity-based sampling on our exact benchmarks. We will reimplement it on the same genetic programming engine, with identical population size, differential evolution settings, number of rounds and seeds. We will use its Pareto pairing with diversity metrics only where it applies, since its correlation metric fails below three dimensions. There is no reported result on Lacuna for its queries-to-solution figures in the summary available to us, so we will rerun it rather than quote it.

Beating it means two things. The first is a statistically significant reduction in median queries to exact recovery at 1% and 10% noise across the 35 Feynman problems. The second is no worse recovery at zero noise.

The second strong reference is a Gaussian-process surrogate that queries at maximum posterior variance, followed by symbolic regression on the collected data. This is the classical non-symbolic active learner, given the same query budget.

For context on recovery difficulty, AI Feynman reports 100% recovery on the 100 basic Feynman equations and 90% on the bonus set, largely in low-noise, data-rich settings. ERRLESS reports an AUC of 0.924 on the Feynman benchmark. Neither is an active-learning number; we treat them as ceilings on passive performance, not as targets.

Ablations isolate the key ingredient. We remove the equality-graph collapse, so votes count per syntactic variant. We drop the constant-uncertainty term $s_k^2$. We drop the noise term. We replace marginal-likelihood weights with uniform weights. The constant-uncertainty and noise terms are the ones the proposal depends on. If removing them changes nothing, the core claim fails.

Why not just…?

Why not just use the genetic programming ensemble's differential entropy, which already works? This is the real threat. Prior work shows it beats random sampling, and in noise-free problems with determined constants our score should behave almost identically. Our argument rests on noisy regimes. There, a deterministic ensemble's disagreement includes members that differ only in fitted constants, and redundant syntactic copies inflate some hypotheses' votes. The noise-stratified head-to-head and the ablations below settle this directly. If the advantage does not appear at 10% noise, the proposal is wrong.

Why not just run several independent symbolic regression searches with different seeds and query where they disagree? Independent runs are costly because formula evaluation is already the bottleneck, as Wehenkel et al. note. More importantly, independent runs can converge on different spellings of the same formula, or on equally overfit formulas. Seed ensembles inherit exactly the problems our collapse and weighting address. We include a seed ensemble as a candidate-pool variant, plugged into both our score and plain disagreement, so that the pool and the acquisition rule are compared separately.

Why not just fit one best formula and wrap it in conformal prediction? Split conformal intervals around a single formula give valid coverage. They say nothing about whether the formula is the right law, and they cannot point to where a new experiment would separate rivals. If the formula is misspecified, the intervals widen evenly instead of locally. We will report conformal coverage as a secondary output, but it cannot provide a stopping rule for structural identification.

Why not just use a Gaussian process for uncertainty and skip symbols during acquisition? A Gaussian process queries where it is uncertain about the function. That is not where symbolic hypotheses disagree. It also has no notion of extrapolating a periodic or power-law structure. The Gaussian-process baseline above tests whether this matters for recovery speed.

Proposed Experiments and Decisive Checks

The main study uses the 35 Feynman problems and the strogatz_vdp1 and strogatz_barmag1 problems used by the active-learning baseline. Noise is set at 0%, 1% and 10% of target scale. Each method starts from a small random seed set and is allowed up to a fixed number of queries. The 10% level matches the noise regime where CADSR reports its best discovery rate.

We measure four things: queries until exact symbolic recovery (checked by algebraic simplification), recovery rate at fixed budgets, extrapolation error outside the training range, and wall-clock cost.

The structural calibration check is new in this setting. We bin the reported probability that the top class is correct and compare it to the empirical recovery rate in each bin, using expected calibration error and reliability diagrams. We do the same for the stopping threshold $\tau$, so that stopping at $\tau=0.9$ should yield about 90% correct laws. A second calibration study runs on the SRBench ground-truth problems (SRBench++) without active querying, varying passive dataset size. This tests whether the weights are calibrated at all. It also tests whether calibration degrades as data grows, which is the peaky-likelihood effect seen in ERRLESS.

Two outcomes would sink the idea. The first is if, at 10% noise, the mutual-information score does not beat differential entropy on queries to recovery, or the constant-uncertainty ablation erases the gap. The second is if the structural probabilities are badly miscalibrated even at small data sizes, which would make the stopping rule meaningless. A positive result on both would give experimentalists a rule for which measurement to take next and a trustworthy statement of when to stop.