PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients

Brenden K. Petersen, Mikel Landajuela, T. Nathan Mundhenk, Claudio P. Santiago, Soo K. Kim, Joanne T. Kim

arXiv:1912.04871v4cs.LGstat.ML

TL;DR

Symbolic regression seeks concise mathematical expressions that fit data, but deep-learning approaches to this search remain underexplored. The paper uses an RNN to generate expressions and a risk-seeking policy gradient to favor high-reward samples. DSR outperforms several baselines in exactly recovering benchmark expressions, while also supporting constrained hierarchical search and broader reinforcement-learning applications.

  • Problem

    Symbolic regression requires searching a large expression space for concise, interpretable functions, while deep-learning approaches to this problem remain underexplored.

  • Method

    DSR uses an RNN to generate mathematical expressions and trains it with a risk-seeking policy-gradient objective that focuses on the top ε fraction of rewards.

  • Results

    DSR significantly outperforms five baselines, including commercial algorithms, in exactly recovering benchmark expressions, with additional comparisons showing it greatly outperforms published results.

  • Takeaways & Limitations

    The framework supports constrained optimization of hierarchical, variable-length objects and is presented as extensible beyond symbolic regression to other reinforcement-learning and molecular-structure search problems.

  • Takeaways & Limitations

    Genetic-programming comparisons remain bounded by known scalability problems and high hyperparameter sensitivity, while equivalent mathematical expressions can correspond to different expression trees.

Abstract

from arXiv · show

Discovering the underlying mathematical expressions describing a dataset is a core challenge for artificial intelligence. This is the problem of $\textit{symbolic regression}$. Despite recent advances in training neural networks to solve complex tasks, deep learning approaches to symbolic regression are underexplored. We propose a framework that leverages deep learning for symbolic regression via a simple idea: use a large model to search the space of small models. Specifically, we use a recurrent neural network to emit a distribution over tractable mathematical expressions and employ a novel risk-seeking policy gradient to train the network to generate better-fitting expressions. Our algorithm outperforms several baseline methods (including Eureqa, the gold standard for symbolic regression) in its ability to exactly recover symbolic expressions on a series of benchmark problems, both with and without added noise. More broadly, our contributions include a framework that can be applied to optimize hierarchical, variable-length objects under a black-box performance metric, with the ability to incorporate constraints in situ, and a risk-seeking policy gradient formulation that optimizes for best-case performance instead of expected performance.

1 INTRODUCTION

Symbolic regression searches for concise mathematical expressions that fit data, offering interpretable relationships but posing a large combinatorial optimization challenge. The paper proposes using a neural network to search this expression space and trains it toward better-fitting expressions with risk-seeking reinforcement learning.

  • Symbolic regression identifies concise mathematical expressions that best fit datasets and can provide interpretable relationships among variables.
  • Symbolic regression provides established benchmarks, baselines such as Eureqa, and computationally efficient rewards for statistically meaningful AutoML evaluation.
  • The expression space is combinatorial, mixing discrete structures with continuous parameters and growing exponentially with expression length.
  • Genetic-programming approaches can scale poorly to larger problems and are highly sensitive to hyperparameters.
  • The proposed framework uses a neural network to search over small symbolic expressions, preserving interpretable outputs without requiring interpretation of the network.
  • DSR samples expressions from an RNN, evaluates dataset fitness as reward, and trains the RNN with a risk-seeking policy gradient.
  • The framework is reported to outperform several baselines while supporting hierarchical, variable-length objects, in situ constraints, and best-case optimization.

2 RELATED WORK

Related work positions DSR among deep-learning approaches to symbolic regression, autoregressive generation, AutoML, program synthesis, and risk-aware reinforcement learning. Its distinguishing focus is autoregressive modeling of hierarchical expressions together with a general objective for best-case performance.

  • Deep learning for symbolic regression: AI Feynman uses neural networks to identify simplifying properties and recursively create subproblems for symbolic regression algorithms.
  • Autoregressive models: Autoregressive models condition each generated token on prior tokens; DSR extends this approach to hierarchical expression trees using depth-first structure.
  • Autoregressive models: DSR uses parent and sibling nodes as RNN inputs, exploiting tree structure and operator-specific child counts during expression generation.
  • Risk-aware reinforcement learning: The expectation problem arises because policy gradients optimize expected performance while symbolic regression and related tasks evaluate the few best samples.
  • Risk-aware reinforcement learning: The paper’s risk-seeking policy gradient is presented as general across reinforcement-learning environments and stochastic batch-trained policy-gradient algorithms.

3 METHODS

DSR represents mathematical expressions as traversals of expression trees, generates them autoregressively with an RNN under in situ constraints, evaluates and optimizes constants, and trains toward high-reward samples. Its risk-seeking objective focuses updates on the top-performing fraction rather than average reward.

  • Generating expressions with a recurrent neural network: Expressions are represented as pre-order traversals of symbolic expression trees, enabling sequential generation of hierarchical, variable-length objects.
  • Generating expressions with a recurrent neural network: The RNN generates one token at a time, conditioning each categorical token distribution on previously sampled tokens.
  • Generating expressions with a recurrent neural network: Parent and sibling representations provide hierarchical context when adjacent traversal tokens are distant in the expression tree.
  • Generating expressions with a recurrent neural network: A pre-order traversal plus each node’s child count uniquely reconstructs the expression tree, although equivalent expressions can have different trees.
  • Generating expressions with a recurrent neural network: Constraints limit expression length, exclude redundant constant or inverse-operator structures, and restrict nested trigonometric operators.
  • Generating expressions with a recurrent neural network: During sampling, invalid token probabilities are zeroed so every generated expression satisfies the constraints without post hoc rejection.
  • Reward function: The reward is based on normalized root-mean-square error, transformed as R(τ) = 1/(1 + NRMSE) to bound its value.
  • Constant optimization: Constant placeholders are optimized for each sampled expression before the reward is used in training.

4 RESULTS AND DISCUSSION

DSR is evaluated on the 12-expression Nguyen benchmark suite against five baselines, using exact symbolic recovery as the primary criterion. It consistently outperforms baselines across clean, noisy, and reward-noise settings, while risk-seeking training favors best-case expressions over average reward.

  • Evaluation setup and main results: The evaluation uses 12 Nguyen benchmarks, with training data for rewards, test data for final evaluation, and ground truth for exact recovery.Each benchmark specifies a ground-truth expression, training and test datasets, and allowed operators.
  • Evaluation setup and main results: DSR evaluates sampled expressions by dataset fitness, optimizing constants before computing rewards and updating an RNN with the top ε fraction.The algorithm samples expressions, optimizes placeholder constants, computes a (1 − ε)-quantile threshold, and applies the risk-seeking gradient.
  • Evaluation setup and main results: DSR significantly outperforms all five baselines in exactly recovering benchmark expressions.The comparison includes PQT, VPG, GP, Eureqa, and Wolfram, with recovery defined by exact symbolic equivalence using a computer algebra system.
  • Risk-seeking objective: Risk-seeking training produces better top-ε and best-expression rewards, while standard policy gradient achieves higher final full-batch mean reward on Nguyen-8.The reported pattern is consistent with optimizing best-case rather than average performance; standard policy-gradient best-case performance plateaus earlier.
  • Ablations: Combinations of ablations can substantially degrade recovery, although no single ablation causes catastrophic failure.Figure 3 reports recovery for ablations of Algorithm 1 across the Nguyen benchmarks.
  • Robustness: DSR consistently outperforms all baselines across dataset sizes and noise levels, while its recovery remains stable under high reward noise on Nguyen-4.The data-noise experiments use exact symbolic equivalence on expressions along the reward-complexity Pareto front; reward-noise comparisons are against PQT.

5 CONCLUSION AND FUTURE WORK

The paper concludes that reinforcement learning can recover exact symbolic expressions while supporting flexible searches over hierarchical, variable-length objects. It identifies hybrid evolutionary methods and applications beyond symbolic regression as future directions.

  • Conclusion: DSR outperforms state-of-the-art baselines in recovering exact expressions on benchmark tasks.The conclusion presents this as the central result of the reinforcement-learning approach.
  • Future work: The framework supports in situ constraints over hierarchical, variable-length objects and is extensible to other search domains.Suggested applications include control policies and organic molecular structures.
  • Future work: Hybrid methods combining DSR with evolutionary operations are identified as a future opportunity because both generate expression trees.The proposed example places evolutionary operations within the inner optimization loop.

APPENDIX A PSEUDOCODE FOR ADDITIONAL ALGORITHMS AND SUBROUTINES

The appendix specifies how DSR samples valid expression traversals and optimizes their constants. It combines autoregressive RNN sampling, hierarchical parent-sibling inputs, in situ constraints, and an inner constant-optimization loop.

  • Expression sampling: Algorithm 2 samples a pre-order expression traversal autoregressively from RNN token probabilities until the expression is complete.The RNN updates its state, emits categorical probabilities, samples a token, and tracks unfinished nodes using token arity.
  • Expression sampling: ParentSibling computes the parent and sibling tokens supplied as hierarchical context for the next token.For an operator, the current node is the parent; otherwise the routine searches backward through the partial traversal.
  • Constant optimization: The constant optimizer maximizes reward with respect to placeholder constants and substitutes the optimized values into the expression.The inner optimization may use a black-box optimizer such as BFGS.
  • In situ constraints: ApplyConstraints zeros probabilities for tokens that would violate user-specified constraints before categorical sampling.The adjusted probabilities are renormalized after invalid token probabilities are set to zero.

APPENDIX B PROOF OF POLICY GRADIENT FOR RISK-SEEKING OBJECTIVE (PROPOSITION 1)

The appendix derives the policy gradient for DSR’s risk-seeking objective by selecting the top ε fraction of reward outcomes. The resulting gradient weights log-probability updates by reward above the current threshold.

  • Relation to CVaR: The derivation extends the CVaR policy-gradient proof by replacing the lower-tail condition with a top-tail condition.The quantile and inequality changes reverse the integration limits, with the resulting sign change canceling in the final expression.
  • Objective: The risk-seeking objective is the conditional expectation of rewards among the top ε fraction of samples.Its threshold Rε is the (1 − ε)-quantile of rewards under the current policy.
  • Derivation: The proof defines the integration domain as rewards above the quantile threshold and differentiates it using the Leibniz rule.The domain depends on the policy parameters, so the standard gradient interchange is insufficient.
  • Gradient: The final gradient is an expectation over selected trajectories of (R(τ) − Rε) times the trajectory log-probability gradient.Only trajectories satisfying R(τ) ≥ Rε contribute to the conditional expectation.

APPENDIX C DESCRIPTIONS OF BASELINE ALGORITHMS

The appendix describes baseline implementations and explains why several symbolic-regression methods were excluded. Baselines differ in search strategy, constraint handling, and support for exact symbolic recovery.

  • Baseline algorithms: PQT replaces DSR’s risk-seeking policy gradient with priority queue training over the top k rewards encountered during training.The priority queue objective does not scale terms by rewards.
  • Baseline algorithms: VPG uses DSR’s framework but substitutes standard policy gradients and an exponentially weighted moving-average reward baseline.
  • Baseline algorithms: GP evolves expressions with population initialization, tournament selection, mutation, and crossover, while rejecting constraint-violating offspring post hoc.Post hoc rejection creates a tradeoff between search-space reduction and sample diversity.
  • Baseline algorithms: Eureqa uses a GP-based approach and was run through DataRobot with DSR’s token library and the longest available runtime mode.Eureqa is described as the gold standard for symbolic regression.
  • Baseline algorithms: Wolfram’s FindFormula combines Markov chain Monte Carlo sampling with nonlinear regression, but its operator restrictions require a modified token library.Subtraction and division were represented using addition, multiplication, and power transformations.
  • Notable exclusions: GSGP and EQL were excluded because expression growth or operator restrictions undermine exact recovery and interpretability, while AIF still requires an underlying discrete-search method for difficult subproblems.AIF is positioned as a preprocessing simplifier rather than a replacement for the discrete search evaluated here.

APPENDIX D ADDITIONAL EXPERIMENT DETAILS

The appendix specifies benchmark construction, validity and recovery criteria, hyperparameter tuning, implementation details, and ablation definitions. It also describes how noisy-data overfitting is handled through reward–complexity Pareto fronts.

  • Benchmark details: Expressions causing overflow or other floating-point errors on the input domain are invalid and receive reward 0 for non-commercial algorithms.Commercial algorithms use their own handling strategies.
  • Hyperparameter selection: Hyperparameters were selected on Nguyen-7 and Nguyen-10 using 10 runs per combination, maximizing average recovery rate and then minimizing average NRMSE.The selected settings were reused across all experiments and benchmark expressions.
  • Benchmark details: Benchmarks define a ground-truth expression, training and test datasets, and allowed operators; training reward, test performance, and exact recovery use separate evaluation roles.
  • Hyperparameter selection: RNN-based algorithms vary algorithm-specific settings such as DSR’s risk factor, PQT’s queue size, and VPG’s EWMA coefficient alongside batch size, learning rate, and entropy weight.
  • Hyperparameter selection: GP tuning spans population, tournament, mutation, crossover, and post hoc-constraint settings across 800 combinations, while commercial software exposes no tunable hyperparameters.Wolfram’s six performance-goal and specificity-goal combinations were tested across 100 random seeds.
  • Recovery and overfitting: For noisy experiments, recovery is exact symbolic equivalence of any expression on the final reward–complexity Pareto front, with complexity computed from token costs but not used during training.Eureqa instead uses a proprietary complexity measure.

APPENDIX E COMPARISONS TO LITERATURE-REPORTED RESULTS

The appendix compares DSR with literature-reported symbolic-regression results, while noting that inconsistent setups and undisclosed random seeds limit direct comparisons. Across several comparisons, DSR reports stronger recovery or error performance, including exact recovery of a harmonic-series approximation.

  • Comparison limitations: Inconsistent libraries, benchmarks, recovery criteria, and metrics make direct comparison with prior symbolic-regression results difficult.Some prior studies use arbitrary error thresholds rather than exact symbolic equivalence and report metrics that cannot be converted without raw data.
  • Comparison limitations: Undisclosed random-number generators and seeds make comparisons imperfect for benchmarks with randomly sampled points.The appendix therefore mimics prior experimental setups where source code or implementation details are unavailable.
  • Semantics-based symbolic regression: DSR’s average recovery rate is more than twice as high as SSR’s across the overlapping Nguyen-1 through Nguyen-10 benchmarks.The comparison uses 30 independent DSR training runs and exact symbolic recovery.
  • GrammarVAE: DSR achieves 0.0105 ± 0.0149 on the GrammarVAE performance metric, versus GrammarVAE’s 3.47 ± 0.24.Across 100 trials, DSR exactly recovers the ground-truth expression in 19% of runs, whereas GrammarVAE never does.
  • Neat-GP: DSR outperforms Neat-GP on seven of the nine Neat benchmarks.The comparison uses median test-data RMSE over 30 independent trials.
  • Neat-GP: DSR discovers a harmonic-series approximation whose extrapolation error is less than 0.000001%.The recovered expression includes the Euler–Mascheroni constant γ, which the paper notes emerged naturally.

APPENDIX F ADDITIONAL RESULTS ON NGUYEN BENCHMARKS

Additional Nguyen experiments test harder functional forms, real-valued constants, recovery, NRMSE, and training behavior. DSR significantly outperforms the baselines on the altered benchmarks, reaches 100% recovery with constants, and generally leads on NRMSE under tractable expression-length limits.

  • Variations of Nguyen benchmarks: DSR significantly outperforms all five baselines on altered Nguyen benchmarks and achieves 100% recovery when real-valued constants are introduced.The additional variants test both more challenging functional forms and the constant optimizer.
  • NRMSE comparisons: DSR outperforms all algorithms on each benchmark set in test-data NRMSE except Eureqa on the original Nguyen set.Eureqa’s lower average NRMSE is attributed to Nguyen-12 expressions of roughly 100 tokens, while non-commercial baselines were limited to length 30.
  • NRMSE comparisons: GP sometimes achieves lower NRMSE on Nguyen-7 and Nguyen-12, where recovery rates are low or zero.The paper suggests GP may overfit by making incremental expression corrections that reduce dataset error without recovering the correct functional form.
  • Training curves: Figure 6 plots best reward, 1/(1 + NRMSE), against expressions evaluated, averaged across training runs.A reward of 1.0 means all training runs recovered the correct expression; shaded bands show standard deviation.
  • Training curves: Figure 7 plots the fraction of independent runs that correctly recover each benchmark as a function of expressions evaluated.A recovery rate of 100% means every training run recovered the benchmark expression.

APPENDIX G RUNTIMES OF NON-COMMERCIAL ALGORITHMS

Runtime comparisons use identical total expression-evaluation budgets and distinguish full-budget execution from time until recovery. GP is fastest without early stopping, while DSR is fastest when early stopping is allowed because it recovers more often.

  • Runtime comparison: All methods receive an identical total number of evaluated expressions in the experiments.This standardizes the main computational budget across methods.
  • Runtime comparison: Without early stopping, GP is the fastest non-commercial method because it does not require neural-network training.The reported metric measures runtime to process all 2M expressions.
  • Runtime comparison: With early stopping, DSR is the fastest because its higher recovery rate triggers stopping more often.The second runtime metric measures time until the benchmark expression is recovered.
  • Training diagnostics: Figures 8 and 9 compare reward distributions and training curves with full-batch versus top-ε-batch policy-gradient updates.Figure 9 distinguishes full-batch mean reward, top-ε mean reward, and best-so-far reward.
Loading 1912.04871v4…