Source-linked AI summary
Bayesian Symbolic Regression
Ying Jin, Weilin Fu, Jian Kang, Jiadong Guo, Jian Guo
TL;DR
Symbolic regression must search a rapidly growing space of expressions while estimating parameters, and genetic programming can produce complex expressions and has difficulty incorporating prior knowledge. BSR uses Bayesian priors and posterior sampling over symbolic trees in an additive model; simulations report better accuracy on most tasks and more concise expressions than GP. The authors also identify ongoing work on improving BSR's sampling efficiency, hyperparameter optimization, and distributed computing.
Problem
Symbolic regression must search a large space of possible expressions while estimating their parameters, and traditional genetic programming can produce overly complicated expressions and has difficulty incorporating prior knowledge.
Source: Introduction · p. 1Method
BSR models the response as a linear combination of concise symbolic-tree expressions, with priors on tree structures and MCMC posterior sampling.
Source: Introduction · p. 2, Find the Signal: Linear Mixture of… · p. 3Results
BSR outperforms GP on most simulation tasks, with expressions generally closer to ground truth and shorter and more comprehensible.
Source: Accuracy and Generalization Abilities · p. 6, Complexity of Expressions · p. 6Takeaways & Limitations
Compared with traditional GP, BSR offers better model interpretability, a simpler way to incorporate prior knowledge, and more cost-effective memory use.
Source: Conclusions and Future Research · p. 7BSR assumes the signal can be represented as a linear combination of simple expressions, with only a small number playing a significant role.
Source: Find the Signal: Linear Mixture of… · p. 3
Abstract
from arXiv · showhide
Interpretability is crucial for machine learning in many scenarios such as quantitative finance, banking, healthcare, etc. Symbolic regression (SR) is a classic interpretable machine learning method by bridging X and Y using mathematical expressions composed of some basic functions. However, the search space of all possible expressions grows exponentially with the length of the expression, making it infeasible for enumeration. Genetic programming (GP) has been traditionally and commonly used in SR to search for the optimal solution, but it suffers from several limitations, e.g. the difficulty in incorporating prior knowledge; overly-complicated output expression and reduced interpretability etc. To address these issues, we propose a new method to fit SR under a Bayesian framework. Firstly, Bayesian model can naturally incorporate prior knowledge (e.g., preference of basis functions, operators and raw features) to improve the efficiency of fitting SR. Secondly, to improve interpretability of expressions in SR, we aim to capture concise but informative signals. To this end, we assume the expected signal has an additive structure, i.e., a linear combination of several concise expressions, whose complexity is controlled by a well-designed prior distribution. In our setup, each expression is characterized by a symbolic tree, and the proposed SR model could be solved by sampling symbolic trees from the posterior distribution using an efficient Markov chain Monte Carlo (MCMC) algorithm. Finally, compared with GP, the proposed BSR(Bayesian Symbolic Regression) method saves computer memory with no need to keep an updated 'genome pool'. Numerical experiments show that, compared with GP, the solutions of BSR are closer to the ground truth and the expressions are more concise. Meanwhile we find the solution of BSR is robust to hyper-parameter specifications such as the number of trees.
Introduction
Symbolic regression searches a large space of expressions while estimating their parameters, making fitting difficult without a prespecified structure. The paper introduces a Bayesian approach that represents expressions as trees and uses priors and posterior sampling to fit interpretable models.
Introduction
- Without a prespecified model structure, symbolic regression must search a large expression space while estimating parameters, making fitting challenging.Source: Introduction · p. 1
- Traditional genetic programming faces high computational complexity, overly complicated outputs, and sensitivity to initialization.Source: Introduction · p. 1
- BSR represents expressions as symbolic trees, combines multiple expressions linearly, and uses informative priors and MCMC posterior sampling.The authors present the framework as a way to incorporate prior knowledge and improve interpretability.Source: Introduction · p. 2
- The paper presents its model, an MCMC-based posterior computation algorithm, and numerical experiments comparing the method with existing alternatives.Source: Introduction · p. 2
Bayesian Symbolic Regression with Linearly-Mixed Tree Representations
BSR represents expressions as symbolic trees and models the response as a linear combination of relatively simple expressions. Priors govern tree growth, operators, and features, while the additive structure is intended to capture concise signals.
Choice of Basic Operators
- The model uses a user-specified set of basic operators, including +, ×, exp(), inv(), neg(), and linear transformation lt().Operators and features can be assigned user-specified preferences; the default priors are uniform.Source: Choice of Basic Operators · p. 2, Priors on Tree Representations · p. 2
From Expressions to Trees
- A symbolic tree has operation nodes and feature-bearing terminal nodes; its structure, selected features, and operator parameters specify an expression.Unary operators have one child and binary operators have two; the tree need not be complete.Source: From Expressions to Trees · p. 2
Priors on Tree Representations
- Tree priors grow nodes recursively, with nonterminal probability α(1 + dη)^−β and user-weighted operator choices; terminal nodes select features using feature weights.Uniform operator and feature weights are defaults, while users can specify preferences.Source: Priors on Tree Representations · p. 2, Prior of Tree Structure T · p. 3, Prior of Terminal Nodes M · p. 3
Find the Signal: Linear Mixture of Simpler Trees
- The model targets prominent, concise signals because overly complicated expressions make interpretation challenging and may trade off simplicity against accuracy.Its additive formulation assumes the real-world signal may combine simple signals, with only a few playing a significant role.Source: Find the Signal: Linear Mixture of… · p. 3
- The model represents the response as a linear combination of k relatively simple tree expressions, with their coefficients fit by OLS.The assumed signal may combine simple components, with only a small number playing a significant role.Source: Find the Signal: Linear Mixture of… · p. 3
Posterior Inference
The method samples symbolic-tree structures and parameters with sequential Metropolis-Hastings updates, using reversible-jump MCMC when tree changes alter parameter dimensionality. Its proposal and acceptance steps govern how candidate structures are explored and retained.
Posterior Inference
- For each of k trees, the method proposes a structure change and accepts it with Metropolis-Hastings probability; changing parameter dimension is handled with reversible-jump MCMC.A tree also has parameters for lt() nodes and a variance parameter sampled from an inverse-gamma prior.Source: Posterior Inference · p. 4
Structure Transition Kernel
- Seven reversible actions—Stay, Grow, Prune, Delete, Insert, ReassignOperator, and ReassignFeature—propose changes to tree structure and selected features.Grow and Prune alter sub-trees top-down, while Delete and Insert alter how higher-level blocks combine bottom-up.Source: Structure Transition Kernel · p. 4
- Transition probabilities penalize complex structures, including trees with many lt() nodes; Grow and Prune change sub-trees, while Delete and Insert alter how blocks combine.The constants in the proposal probabilities can be changed to favor particular transitions.Source: Structure Transition Kernel · p. 4
Jump between Spaces of Parameters
- When a proposed structure changes the number of lt() nodes, reversible-jump transformations add or remove parameters and auxiliary variables while preserving total dimension.When the number of lt() nodes stays the same, an ordinary Metropolis-Hastings step suffices.Source: Jump between Spaces of Parameters · pp. 4–5
Accepting New Candidates
- A candidate is accepted with probability min{1, R}; after acceptance, the next tree update starts from the candidate, otherwise it starts from the current model.The acceptance ratio incorporates the model likelihood, priors, and proposal probabilities.Source: Accepting New Candidates · p. 5
Experiments
The experiments compare BSR with GP on simulated symbolic-regression tasks and apply BSR to financial data. BSR generally performs better on simulations while producing more concise expressions, and the tested results show limited sensitivity to the number of additive components once K is large enough.
Simualtion Designs
- Simulation experiments use six benchmark formulas, 100 training samples and three 30-sample test sets per formula, with predictors drawn from specified uniform ranges.Both methods use the same basis-function pool; GP generates 200,000 trees and BSR 100,000, with K=2 additive components and 50 independent runs per task.Source: Benchmark Problems · p. 5, Datasets · pp. 5–6, Parameter Settings · p. 6
Simualtion Results
- BSR outperforms GP in most simulation tasks, except Equation (8), whose structure is far from BSR’s linear-structure assumption.The comparison uses RMSE on training and testing data.Source: Accuracy and Generalization Abilities · p. 6, Table 1 · p. 6
- BSR’s trees have significantly fewer nodes than GP’s, and typical simulated expressions are generally closer to ground truth, shorter, and more comprehensible.Table 2 summarizes mean and standard deviation of node counts over 50 replications; only two typical cases are shown in Table 3.Source: Complexity of Expressions · p. 6, Table 2 · p. 6, Table 3 · p. 7
- Testing RMSEs decrease as K grows, but gains become insignificant when K is large enough; BSR can also consolidate components or assign redundant trees small coefficients.The study reports average test RMSE across 50 replications for different K values.Source: Sensitivity to the Number of… · p. 7, Table 4 · p. 7
Experiments on Real World Data
- Across 200 financial-data runs, 15 posterior-mode expressions exceeded 0.5 accuracy on both training and test sets; the displayed expression achieved 0.539 and 0.518, respectively.The data comprise 3,586 CSI 300 records from 2004–2019, with 2004–2016 for training and 2017–2019 for testing; the displayed signal relates open and low prices to return direction.Source: Experiment Result · p. 7, Datasets and Experimental Setting · p. 7
Conclusions and Future Research
The paper proposes Bayesian symbolic regression as an alternative to genetic programming, with advantages in interpretability, prior-knowledge incorporation, and memory use. Future work targets sampling efficiency, hyperparameter optimization, and distributed computing.
Conclusions
- Compared with traditional GP, BSR is presented as offering better interpretability, simpler incorporation of prior knowledge, and more cost-effective memory usage.The method avoids maintaining an updated genome pool.Source: Conclusions and Future Research · p. 7
Future Research
- Future work will study new MCMC algorithms to improve search and sampling efficiency.Source: Conclusions and Future Research · p. 7
- The authors also plan to study dynamic empirical Bayes for hyperparameter optimization and extend BSR to distributed computing for computational efficiency.Source: Conclusions and Future Research · p. 7
Pseudo-codes of BSR
The pseudo-code initializes multiple tree models from the prior, fits linear coefficients, and iteratively proposes and accepts models to form a chain. Its inputs specify the data, model-component and acceptance counts, proposal kernel, prior, and likelihood.
Inputs and output
- The algorithm takes datapoints and labels, component count K, acceptance count N, a proposal kernel, prior distributions, and a likelihood as inputs, and outputs a chain of accepted models.Source: Pseudo-codes of BSR · p. 9
Initialization
- It independently generates K tree models from the prior, then computes initial linear regression coefficients by ordinary least squares.Source: Pseudo-codes of BSR · p. 9
Sampling loop
- For each iteration, the algorithm proposes a model and computes linear coefficients and an acceptance ratio, using ordinary least squares in the indicated branches.Source: Pseudo-codes of BSR · p. 9
- When a proposal is accepted, the algorithm updates the component states and coefficients before continuing until the acceptance count is reached.Source: Pseudo-codes of BSR · p. 9
Simulation results
The section identifies visualizations comparing BSR and GP on simulated-data accuracy and complexity, alongside typical-expression examples. The supplied captions identify training plots for several target formulas but do not report their plotted outcomes.
Performance visualizations
- The performance visualizations compare BSR and GP on simulated data using accuracy and complexity.Source: Performance visualizations · p. 9
- The listed training plots cover RMSE and complexity for f3, f4, f5, and f6.Source: Performance visualizations · p. 9
- Additional training plots are labeled for RMSE and complexity on f5 and f6.Source: Performance visualizations · p. 9
Typical expressions
- The section also presents typical-expression examples in Table 5.Source: Typical expressions · p. 10, Table 5 · p. 10
Expressions for Financial data
The financial-data results report training and testing accuracy with the corresponding expression found by BSR. Table 6 is identified as covering accuracy and expressions in real-data analysis.
Financial-data results
- The financial-data results include training accuracy, testing accuracy, and the corresponding expression found by BSR.Source: Expressions for Financial data · p. 10
- Table 6 is titled as reporting accuracy and expressions in real-data analysis.Source: Table 6 · p. 10
- The reported financial-data analysis pairs accuracy results with a corresponding BSR expression.Source: Table 6 · p. 10