Random Symbolic Boosting: A Geometric Approach to Symbolic Regression
Authors: José R. Ortegaa, José Manuel Muñoz Contreras, Leonardo Trujillo
Organizations: Tecnológico Nacional de México/Instituto Tecnológico de Tijuana, Blvd. Limón Padilla (Industrial) y Ave. ITR Tijuana s/n, Mesa de Otay, 22500, Tijuana, Baja California, México · Universidad Autónoma de Baja California, Unidad Valle de las Palmas, Calzada Universidad 14418, Parque Industrial Internacional Tijuana, 22427, Tijuana, Baja California, México · LASIGE, Department of Informatics, Faculty of Sciences, University of Lisbon, Campo Grande, 1749-016, Lisbon, Portugal
Symbolic models offer interpretability, but their construction through generational evolution can be computationally expensive. This article presents Random Symbolic Boosting (RSB), a method that constructs explicit additive symbolic models via boosting over populations of randomly generated syntax trees, eliminating the need for generational evolution. The idea combines two observations: high-dimensional spaces can be spanned by enough linearly independent vectors, and the semantics of syntax trees can be directly manipulated as such vectors. It is shown that, for Ordinary Least Squares, the boosting process guarantees a monotonic reduction of the training error for both regression and classification. Furthermore, an adaptive geometric early stopping mechanism is introduced. It is based on the angle between the prediction and target vectors, is independent of the problems scale, and requires no adjustments across tasks. Evaluated on a standard benchmark for symbolic regression, the method is located at the Pareto-optimal point between predictive accuracy and training time, ranking first on the real-world datasets. Additionally, it was tested on a large tabular classification benchmark with 200 problems, achieving competitive results.
Figures & tables
Component
Label
Stork Category
Technical Description
Init_Single_Rand
Single candidate (random)
Random selection of a single initial candidate within the valid search space.
Init_Single_Know
Single candidate (knowledge)
Selection of an initial candidate guided by empirical domain knowledge or a priori evaluation.
Initialization
Init_Set_Rand
Set of candidates (random)
Initialization of a candidate set through uniform random sampling to favor spatial exploration.
Init_Set_Know_DOE
Set of candidates (knowledge/DOE)
Initialization of a candidate set employing design of experiments (DOE) or prior knowledge of the problem.
Init_Comp_Rand
Algorithm components (random)
Initial random selection of search operators or low-level heuristics.
Init_Comp_Pre
Algorithm components (predefined)
Initial configuration based on a predefined algorithm architecture and fixed search operators.
Table 1: Definition of matrix variables based on the Stork taxonomy.
Algorithm
Initialization
Generation
Selection
Control
GP
Random population of syntax trees ( Init_Set_Rand ).
Crossover and mutation ( Gen_Pop_Set ).
Tournament selection ( Sel_Func_Prob ).
Fixed population size and operator rates ( Ctrl_Basic ).
MRGP
Random population of syntax trees ( Init_Set_Rand ).
Evolution of trees with internal linear regression ( Gen_Pop_Set ).
Tournament selection ( Sel_Func_Prob ).
Fixed evolutionary parameters ( Ctrl_Basic ).
MEGP
Population mapped to MAP-Elites grid ( Init_Set_Rand ).
Evolutionary operators on grid elites ( Gen_Pop_Set ).
Elitist replacement per grid cell ( Sel_Imp_Best ).
KPCA and cosine similarity mapping ( Ctrl_Soph_Pop ).
GSGP
Random population of syntax trees ( Init_Set_Rand ).
Geometric semantic crossover and mutation ( Gen_Pop_Set ).
Tournament selection ( Sel_Func_Prob ).
Fixed mutation steps and rates ( Ctrl_Basic ).
SBP-GP
Random population of syntax trees ( Init_Set_Rand ).
Fixed population size, generations, and operator rates ( Ctrl_Basic ).
FFX
Expansion of basis functions ( Init_Set_Know_DOE ).
Pathwise Regularized Learning ( Gen_MultiStage ).
Nondominated filtering for Pareto-optimal set ( Sel_Func_Det ).
Fixed regularization path logic ( Ctrl_Basic ).
Table 2: Functional classification of components based on the Stork et al. taxonomy.
Figure 1: Jaccard similarity matrix quantifying the overlap of algorithmic components across the 13 algorithms in Table 2 .
Figure 2: Visualization of the geometric dynamics of RSB. The subspace Hk (magenta surface) is generated at each level. It shows the initialization (black dot), the target y (red star), the previous residual rk−1 (red dashed line), and the new residual rk (orange dotted line) after the projection ηu(k) (blue vector). The historical trajectory is traced in gray.
Dataset
Features
Samples
Description
Concrete
8
1030
High-performance concrete strength
EECooling
8
768
Building energy cooling load
EEHeating
8
768
Building energy heating load
Housing
13
506
Housing prices and air quality
Tower
25
4999
Unknown real-world relationship
Yacht
6
308
Yacht hull design and performance
Table 3: Regression benchmark datasets ( Yeh, 1998 ; Tsanas and Xifara, 2012 ; Harrison and Rubinfeld, 1978 ; Vladislavleva et al., 2009 ; Gerritsma et al., 1981 ) .
Figure 3: Robustness and global convergence analysis projected onto a latent space (PCA-2D) for the datasets described in Table 3 . The green dots indicate the initial state of 250 independent simulations, the gray lines their trajectories, and the orange cross ( × ) denotes the average convergence point with respect to the target (red star).
Parameter
Values
m
{0.1,0.25,0.5,1,1.5,2,2.5,3,3.5,4,8,10}
K
{1,5,10,25,50}
dmax
{1,2,3,4,5}
η
{0.05,0.1,0.25,0.5,1}
Basic Function Set
+ , − , × , AQ
Regularization
None ( λ=0 )
Table 4: Hyperparameter search space and fixed configurations used for the fANOVA analysis.
Figure 4: Marginal effect of m on the normalized R2 . The solid red line represents the mean response across multiple datasets, while the shaded region denotes the variability ( ±1 SD).
Figure 5: Average hyperparameter importance across datasets using fANOVA (evaluated as the fraction of explained variance, FU ). Error bars represent the standard deviation ( ±1 SD).
Figure 6: Sensitivity analysis of computational cost for RSB. Each line represents a unique configuration averaged over 30 evaluations (6 runs × 5 folds). The color scale indicates the execution time in seconds.
Parameter
Pearson ( r )
Spearman ( ρ )
m
0.315998
0.607864
K
0.251069
0.618799
dmax
0.070535
0.203032
η
−0.000057
−0.000133
Table 5: Statistical correlation analysis of hyperparameters with respect to execution time.
Algorithm
Configuration
RSB
m=8 , K=50 , η=0.1 , dmax=3
RF
Nest=100 , Library defaults
XGB
Nest=100 , Library defaults
LGBM
Nest=100 , Library defaults
CatBoost
Nest=100 , Library defaults
Table 6: Hyperparameter settings for the comparative feature importance analysis.
Figure 7: Comparison of feature importance between tree-based algorithms and RSB. The markers represent the mean importance.
Variant
R2
Nodes ( ×103 )
Time (s)
OLS
0.429
157.1
3.74
Ridge
0.973
151.8
0.69
Lasso
0.965
41.9
1.20
ENet
0.953
61.3
5.82
OLS+ES (angle)
0.902
35.7
0.92
Ridge+ES (angle)
0.970
53.6
0.33
Table 7: Median test R2 , number of nodes, and training time for OLS, Ridge, Lasso, and ENet without ES; with angle-based ES; and with RMSE-based ES. Each value is the median across the six datasets of the per-dataset median over 30 runs. Bold indicates the best value per column.
Reg. (wins/losses/ns)
Angle-based ES vs. no ES
RMSE-based ES vs. no ES
Angle-based ES vs. RMSE-based ES
Method
R2
Nodes
Time
R2
Nodes
Time
R2
Nodes
Time
R2
Nodes
Time
OLS
0/9/9
1/17/0
7/11/0
3/0/3
6/0/0
6/0/0
3/0/3
6/0/0
6/0/0
0/0/6
0/0/6
0/0/6
Ridge
9/0/9
5/13/0
17/1/0
0/2/4
5/0/1
5/0/1
0/5/1
6/0/0
6/0/0
2/0/4
0/4/2
0/2/4
Lasso
4/4/10
18/0/0
10/7/1
0/4/2
6/0/0
6/0/0
0/5/1
6/0/0
6/0/0
3/0/3
0/3/3
0/4/2
ENet
4/4/10
12/6/0
1/16/1
0/4/2
6/0/0
6/0/0
0/5/1
6/0/0
6/0/0
3/0/3
0/3/3
0/5/1
Table 8: Summary of pairwise comparisons (Nadeau–Bengio corrected t -test with Holm correction per dataset and metric, α=0.05 ; 30 runs per dataset). Reg.: each method without ES vs. the other three (wins/losses/ns over 18 comparisons). Angle-based ES / RMSE-based ES vs. no ES: datasets where each ES criterion is better/worse/ns than no ES (higher R2 , fewer nodes, or lower time). Angle- vs. RMSE-based ES: datasets where angle-based ES is better/worse/ns than RMSE-based ES. Bold indicates the best result per metric within the Reg. block.
Hyperparameter
Evaluated Values
m
{1,5,25}
K
50
η
0.1
dmax
{1,3}
λ,ρ
0.02 , 0
Operators
{+,−,×,AQ,sin}
Table 9: Hyperparameter search space used for the evaluation in SRBench.
Figure 8: Comparison of the RSB algorithm against baseline methods in SRBench: (a) normalized R2 test score, (b) training time, and (c) model size.
Figure 9: Rankings of methods by R 2 test score on the black-box problems (lower is better). Results are bi-clustered by algorithm and dataset. Darker cells indicate that a method performs well on that dataset relative to its competitors.
Figure 10: Statistical significance heatmaps using the pairwise Wilcoxon signed-rank test with Bonferroni correction ( α=0.05 ).
Figure 11: Pareto front between predictive accuracy ( R2 Ranking) and computational cost (Training Time Ranking).
Hyperparameter
Binary Classification
Multiclass Classification
m
8
{0.25,0.5,1,2}
K
200
200
η
{0.1,0.5,1}
0.1
dmax
5
{1,3}
λ,ρ
0.02 , 0
0.02 , 0
Operators
{+,−,×,AQ,sin}
{+,−,×,AQ,sin}
Table 10: Hyperparameter search space used for the evaluation in the TALENT benchmark.
Figure 12: Accuracy results (normalized) in the TALENT benchmark.
Symbolic regression is the problem of finding an expression that fits a dataset. Solving it requires searching a combinatorial space of candidate expressions. Neural symbolic regression can amortize that search by training a model once on synthetic data and then predicting expressions for a new dataset. But existing models still underperform genetic programming on real, noisy data. We argue that the deficit lies in the training rather than in the paradigm, and present RASR (Reinforced Amortized Symbolic Regression), a method with two key changes to the training recipe. First, we design a synthetic prior that narrows the gap with real-world data: inputs come from the prior of a tabular foundation model; constants are sampled bottom-up, conditioned on the data; targets carry heteroscedastic and structured noise; and everything is standardized. Second, we split training into two stages. Supervised pre-training maximizes the token-level likelihood of a reference expression. This is followed by reinforcement-learning post-training that aligns the model with its inference-time use by rewarding held-out fit and penalizing expression size. On the black-box track of SRBench 2.0, RASR achieves the best mean test R2 rank of all evaluated methods. Three RASR variants, trained with different size penalties, make up most of the accuracy-complexity Pareto front. On Strogatz, our method recovers more ground-truth expressions than any baseline, and on Feynman it is competitive with the best-performing methods.
David Otte, Jörg K. H. Franke, Frank Hutter
LMU Munich · Munich Center for Machine Learning (MCML) · University of Freiburg +3
Symbolic regression is the problem of finding an algebraic expression describing a stochastic dependence of a target variable on a set of inputs. Unlike forms of regression that fit parameters assuming a fixed model structure, symbolic regression is a search problem over the space of expressions, represented, for example, as abstract syntax trees using a library of operators. Symbolic regression is typically used in settings with limited, noisy data in the natural sciences. However, searching for a single best-fitting expression fails to capture the epistemic uncertainty about the expression, which motivates a Bayesian perspective that enables uncertainty quantification and specification of natural priors to constrain the search space. In this work, we propose ERRLESS (Entropy-Regularized Reinforcement Learning for Expression Structure Sampling), a scalable approach for sampling from the posterior distribution over expressions given data using maximum-entropy reinforcement learning. ERRLESS learns a neural policy that constructs expressions sequentially by building up their abstract syntax trees. At convergence, the policy samples expressions from the posterior. At test time, expressions can be sampled by rollouts of this policy. We demonstrate that ERRLESS achieves competitive results on the Feynman benchmark while producing short and interpretable expressions. Additionally, we demonstrate that the mean of the posterior predictive approximated by ERRLESS achieves a high coefficient of determination (R2) compared to an SMC baseline, highlighting the benefits of the Bayesian perspective in symbolic regression.
Oussama Boussif, Mohammed Mahfoud, Younesse Kaddar +6
Mila – Québec AI Institute · Université de Montréal · Independent +5
Symbolic regression (SR) seeks to discover parsimonious mathematical laws from observational data, yet conventional approaches often struggle with the vast combinatorial search space of physically meaningful expressions. We present InsightSR, a framework that embeds Large Language Models (LLMs) as a guiding layer around the PySR genetic programming engine. Rather than relying on LLMs to generate expressions directly, InsightSR uses LLMs to progressively transform the search space itself through two complementary pathways: a Semantic Seed Pathway that proposes dimensionally consistent functional skeletons, and a Structural Feature Pathway that recommends nonlinear feature transformations. These transformations accumulate over iterations, broadening the input space and shifting the symbolic search from constructing deep expression trees over raw variables to assembling shallow trees over a rich, semantically informed feature set. A post-generation feedback loop evaluates candidates, categorizes features by their empirical utility, and refines the guidance for the next iteration, transforming the discovery process from open-ended generation into iterative, self-correcting refinement. Across three benchmarks, InsightSR achieves a 95% exact recovery rate on the Feynman benchmark and 80.18% accuracy on the LLM-SRBench LSR-Transform task, substantially outperforming state-of-the-art genetic programming and neural-symbolic methods while maintaining strong out-of-distribution generalization on real-world datasets.