PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Generative Symbolic Regression with Monte-Carlo-Tree-Search

Pierre-Alexandre Kamienny, Guillaume Lample, Sylvain Lamprier, Marco Virgolin

arXiv:2302.11223v2cs.LG

TL;DR

Symbolic regression requires composing expressions to fit data, while inductive neural approaches lack search to improve for a particular dataset. DGSR-MCTS combines pretrained neural mutations with Monte-Carlo Tree Search and online refinement. The paper reports performance on par with state-of-the-art methods in accuracy-complexity trade-off, with fewer expression evaluations than GP-GOMEA.

  • Problem

    Inductive deep generative symbolic regression can generate expressions in one forward pass but lacks search to improve for a specific dataset, a concern for out-of-distribution data.

    Source: §1 · p. 1

  • Method

    DGSR-MCTS seeds Monte-Carlo Tree Search with pretrained neural mutations and updates the mutation policy and critic online using search results.

    Source: §1 · p. 2

  • Results

    DGSR-MCTS performs on par with state-of-the-art symbolic regression algorithms such as GP-GOMEA in accuracy-complexity trade-off, while using fewer expression evaluations.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The paper presents search as a tool to further improve the performance of inductive deep generative symbolic regression approaches.

    Source: §6 · p. 9

    Large context lengths require significant GPU memory, and sampling mutations with the Transformer is the algorithm’s main latency source.

    Source: §5 · p. 9

Abstract

from arXiv · show

Symbolic regression (SR) is the problem of learning a symbolic expression from numerical data. Recently, deep neural models trained on procedurally-generated synthetic datasets showed competitive performance compared to more classical Genetic Programming (GP) algorithms. Unlike their GP counterparts, these neural approaches are trained to generate expressions from datasets given as context. This allows them to produce accurate expressions in a single forward pass at test time. However, they usually do not benefit from search abilities, which result in low performance compared to GP on out-of-distribution datasets. In this paper, we propose a novel method which provides the best of both worlds, based on a Monte-Carlo Tree Search procedure using a context-aware neural mutation model, which is initially pre-trained to learn promising mutations, and further refined from successful experiences in an online fashion. The approach demonstrates state-of-the-art performance on the well-known \texttt{SRBench} benchmark.

1. Introduction

Symbolic regression seeks interpretable expressions that fit data, but composing operators and variables is difficult, and inductive neural approaches lack a search component for improving on a specific dataset. DGSR-MCTS combines pretrained expression mutations with online search and refinement, and the paper reports state-of-the-art performance with simple, accurate expressions.

1. Introduction

  • Symbolic regression jointly finds an expression’s structure and optimizes its constants to fit experimental data interpretably, producing human-readable expressions useful in natural sciences.The passage names materials science and physics as example application areas.Source: §1 · p. 1
  • Symbolic regression is challenging because it must compose discrete operators and variables to fit data; the optimal composition is intractable, so leading SRBench algorithms use genetic-programming heuristics.Genetic-programming candidates are evaluated on the data to assess fit.Source: §1 · p. 1
  • Inductive deep generative symbolic regression can generate expressions quickly in one forward pass, but without search it cannot improve for the dataset at hand, especially when data are out of distribution.These models are pretrained on synthetic data and take the dataset as input.Source: §1 · p. 1
  • Earlier SR Monte-Carlo Tree Search work used predefined mutations or dataset-independent neural mutations, while the most similar pretrained approach did not fine-tune during search.The paper also reports that prior approaches had not shown competitive performance on SRBench real-world problems.Source: §1 · p. 2
  • DGSR-MCTS seeds Monte-Carlo Tree Search with pretrained deep generative symbolic regression and fine-tunes its mutation policy and critic as search progresses across datasets.The mutation policy expands expressions, while the critic-informed selection policy trades off exploration and exploitation.Source: §1 · p. 2
  • The approach achieves state-of-the-art performance on SRBench and discovers expressions that are both simple and accurate.The paper also positions the approach within a unified view of genetic programming and deep-learning-based symbolic regression.Source: §1 · p. 2

2. Unifying View of of SR

The section frames symbolic regression as choosing an initial distribution over expressions and then updating it through a bounded search process. It compares how existing methods define these stages, including context-aware neural generation and iterative search.

2. Unifying View of of SR

  • The general objective is to minimize expected loss at step T across datasets, by defining an initial expression distribution and an iterative process that updates it.The section identifies negative R² as a typical loss.Source: §2 · p. 2

2.1. Pre-training: How to define P 0

  • Because the dataset distribution is unknown during pre-training, generative models are trained on large synthetic datasets built from randomly generated expressions.Many such models learn to predict ground-truth expressions autoregressively.Source: §2.1 · p. 3
  • Context-conditioned DGSR can produce expressions by one-shot sampling, but accuracy gains may stop after about 50 samples and performance can be poor out of domain.The cited example for the 50-sample plateau is Kamienny et al. (2022).Source: §2.1 · p. 3

2.2. Search Process: How to build P T

  • At search time, algorithms iteratively sample from and update the expression distribution using sample statistics such as expression accuracy, until a stopping condition is met.Stopping conditions can include exceeding a runtime budget or reaching satisfactory accuracy.Source: §2.2 · p. 3
  • GP uses an evolving expression population, while EDAs explicitly factorize the expression distribution and use GP-like procedures to update it.GP uses stochastic crossover and mutation followed by selection; EDA factorization choices can model terms independently or jointly.Source: §2.2 · p. 3
  • DSR uses policy gradients to update expression probabilities but was reported to produce short, low-accuracy SRBench expressions; the proposed algorithm expands expressions over time and learns during search.The proposed approach combines expression expansion like GP with pre-training and learning over time.Source: §2.2 · pp. 3–4

3. Method

DGSR-MCTS uses Monte-Carlo Tree Search to sample expressions through learned mutations, then refines its mutation and critic networks by imitation learning from search experience. Its mutation policy is conditioned on both the dataset and current expression, and is pretrained on mutation sequences reconstructed from synthetic ground-truth expressions.

3. Method

  • DGSR-MCTS derives its expression distribution from Monte-Carlo Tree Search and iteratively refines it by imitation learning on successful search samples.The search uses mutations of existing expressions rather than greedy token concatenation, enabling systematic evaluation of intermediate solutions.Source: §3 · p. 4

3.1. MCTS Sampling

  • Each search trial repeats selection, mutation-based expansion, and back-propagation 1,000 times, using a critic to estimate whether expressions can lead to a solution.Expressions meeting R2 ≥ 0.99 receive value 1; other expressions are scored by the critic rather than simply by accuracy, which the authors say can give deceptive rewards.Source: §3.1 · pp. 4–5

3.2. Learning critic Cψ and Mθ

  • After each trial, the mutation policy and critic are updated from stored search data, while continued training on synthetic pretraining examples helps prevent mode collapse.Search can run across multiple datasets so the networks can leverage shared information; the mutation policy can adapt to dataset-dependent mutation sizes, including learning size-1 mutations after pretraining on arguments around size 10.Source: §3.2 · p. 5

3.3. Mutation Policy

  • The mutation policy samples transformations represented by a node, operation, and optional new expression, and conditions each mutation on both the dataset and current expression.It is pretrained by dismantling synthetic ground-truth expression trees and training on the reversed mutation sequences; mutations strictly increase expression size, with generation limited to fewer than 60 operators and basic arithmetic without nested operations beyond those operators.Source: Figure 1 · p. 5, §3.3 · p. 6

4. Experiments

DGSR-MCTS combines search with learned mutations and is evaluated through synthetic-data analyses and SRBench comparisons. On SRBench, it reaches the rank-0 Pareto front on both black-box and Feynman datasets, while ablations identify contributions from synthetic training and multi-dataset training.

4.1. Analysis on synthetic datasets

  • The synthetic evaluation uses 1,000 unseen expressions, split evenly between in-domain and out-of-domain cases, with each search run limited to 24 hours.Out-of-domain expressions have up to 40 operators rather than 25; the section also reports 12 days of pretraining on eight GPUs.Source: §4.1 · pp. 6–7
  • Sampling K between 8 and 16 is reported as the best compromise between breadth and depth on in-domain and out-of-domain synthetic datasets.The comparison omits constant optimization and equalizes the number of expressions considered across configurations.Source: §4.1 · p. 7, Table 3 · p. 7
  • Mutation size 10 performs better than size 1 both in-domain and out-of-domain, while DGSR-MCTS@∞ does not generalize to out-of-domain datasets.DGSR-MCTS@∞ predicts the target expression from scratch in a single iteration.Source: Table 4 · p. 7, §4.1 · p. 7
  • Constant optimization substantially improves performance, but doing it after every mutation reduces speed.The experiment stores non-optimized expressions in the search tree because optimized constants may be out-of-distribution for the pretrained mutation model.Source: §4.1 · p. 7, Table 5 · p. 8

4.2. SRBench results

  • DGSR-MCTS reaches the rank-0 Pareto front on both black-box and Feynman datasets, among the best approaches for simple-yet-accurate models.The comparison considers test accuracy and expression size; GP-GOMEA and DGSR-MCTS switch places in their trade-off across the two dataset types.Source: Figure 2 · p. 8, §4.2 · pp. 8–9
  • As evaluated expressions increase, DGSR-MCTS is consistently better on training data, while its late-search test performance is similar to GP-GOMEA's.The caption attributes the test-set pattern to a larger generalization gap for larger expressions.Source: Figure 3 · p. 8
  • On black-box datasets, DGSR-MCTS achieves test accuracy 0.846 and expression size 41, versus E2E's 0.797 and 61, respectively.On Feynman datasets, DGSR-MCTS reaches R2 ≥0.99 on 80% of datasets at expression size 33, versus E2E's 87% at size 121.Source: §4.2 · p. 9
  • Synthetic-data ablations suggest that synthetic training especially benefits Feynman results, while simultaneous multi-dataset training appears better than synthetic-only training on black-box datasets.The authors attribute these patterns to synthetic/Feynman similarities and possible gradient sharing across datasets; both components contribute to DGSR-MCTS's performance.Source: §4.2 · p. 9, Table 6 · p. 9

5. Limitations

The approach inherits Transformer limitations that make large-context learning challenging and resource-intensive. Mutation sampling is its main latency source.

5. Limitations

  • Learning with large context lengths is challenging and requires significant GPU memory resources.The authors note that Transformers designed for large inputs, such as LongFormer, could circumvent this limitation.Source: §5 · p. 9
  • Sampling mutations by forwarding the Transformer is the algorithm's main source of latency.The authors note that GPUs can batch mutation generation, while GP approaches can run on CPU only.Source: §5 · p. 9
  • The latency constraint is shared with other DGSR methods that use large pretrained Transformers.Source: §5 · p. 9

6. Conclusion

DGSR-MCTS incorporates search to improve inductive DGSR and performs on par with state-of-the-art SR algorithms on the accuracy-complexity trade-off, using fewer expression evaluations. The authors identify meta-learning as a possible future direction for reducing the search budget.

6. Conclusion

  • DGSR-MCTS performs on par with state-of-the-art SR algorithms such as GP-GOMEA on the accuracy-complexity trade-off.The paper positions the method within a unifying view of SR algorithms.Source: §6 · p. 9
  • DGSR-MCTS uses fewer expression evaluations than state-of-the-art SR algorithms while matching their accuracy-complexity trade-off.Source: §6 · p. 9
  • Future work may extend the approach to meta-learning, with pre-training intended to reduce the search budget across a broad family of target datasets.Source: §6 · p. 9

A. Data generation

The synthetic data-generation procedure samples feature observations and random expression trees to create ground-truth examples, then derives mutation sequences from those expressions. Its expressions are smaller and use fewer constants than in Kamienny et al. (2022).

A. Data generation

  • Each synthetic example pairs sampled feature observations with a ground-truth expression built from a random unary-binary tree.The feature count is sampled uniformly from 1 to 10, and trees have 5 to 25 internal nodes before operators, variables, or constants are assigned and the expression is simplified with SymPy.Source: A. Data generation · p. 13
  • Compared with Kamienny et al. (2022), generated expressions are smaller, allow variables to be omitted, and use fewer constants.The changes are intended to let the model learn feature selection and provide more interpretable expressions; model size is divided by 2.Source: A. Data generation · p. 13
  • Mutation examples are generated by iteratively removing parts of a ground-truth expression until reaching the empty expression.At each step, a sufficiently large subtree is removed through a backward mutation; when the remainder is too small, the mutation is 0 → B.Source: A. Data generation · p. 13

B. Data representation

The model represents expressions, datasets, and mutation actions as token sequences, combining the expression and dataset to represent a state. Model inputs are limited to 100 data points and datasets with at most 10 variables.

B. Data representation

  • A state combines a Polish-notation expression with a dataset represented by concatenated tokenized input-output pairs.Constants use three tokens for sign, mantissa, and exponent; actions encode the target node, operator, and, for binary operators, the tokenized expression B.Source: B. Data representation · p. 13
  • Mutation actions encode the node index, operator, and the tokenized expression B when the operator is binary.Source: B. Data representation · p. 13

C. Model details

  • Because of transformer context limits, the model uses at most 100 sampled input data points per expansion and is trained on datasets with at most 10 variables.Source: C. Model details · p. 13

D. Exceptions detected ablations

About 90% of sampled mutations produce valid expressions, while malformed mutations account for less than 1% of errors. The method also discards expressions that violate complexity constraints.

D. Exceptions detected ablations

  • About 90% of sampled mutations result in valid expressions, while malformed mutations represent less than 1% of errors.Malformed cases include invalid node indices, unparseable arguments, or missing arguments for binary operators.Source: D. Exceptions detected ablations · p. 13
  • The method discards expressions with more than 60 operators, variables, or constants, or with nested complicated operators such as cos(cos(X)) or log(log(X)).These constraints are used to promote simpler expressions and produce an accuracy-complexity trade-off.Source: D. Exceptions detected ablations · p. 13
  • The complexity constraints result in 9% of expressions being discarded.Source: D. Exceptions detected ablations · p. 13

E.1. Definition of satisfactory expressions

Expressions with R2 ≥ 0.99 were treated as satisfactory because this threshold gave high-quality samples while reducing search time relative to perfect fitting. Constant optimization used BFGS with batch size 256, stopping after 10 iterations without accuracy improvement or after a 1-second timeout.

E.1. Definition of satisfactory expressions

  • R2 ≥ 0.99 was the satisfactory-expression threshold, selected for high-quality samples and shorter search times than perfect fitting.Systematically estimating achievable accuracy at a given complexity would require an oracle algorithm under the same complexity constraints.Source: §E.1 · p. 13
  • Validation-set accuracy was not a reliable alternative because SRBench dataset accuracy can vary greatly with the split.The authors tried estimating accuracy by fitting XGBoost on a training set.Source: §E.1 · p. 13

E.2. Constant optimization

  • BFGS constant optimization used batch size 256, with early stopping after 10 iterations without accuracy improvement and a 1-second timeout.Source: §E.2 · pp. 13–14

E.3. Search hyper-parameters

Search hyperparameters are sampled from predefined ranges at the start of each trial rather than fixed, addressing changing model behavior, dataset-specific optima, and costly tuning. The parameters include mutation-decoding settings and search-process choices.

E.3. Search hyper-parameters

  • Hyperparameters are sampled from predefined ranges at each search trial because optima may change with model evolution, vary by dataset, and be costly to tune.A distributed learning architecture similar to Lample et al. (2022) is used, with a controller sampling the settings.Source: §E.3 · p. 14
  • K, the number of samples per expansion, is drawn uniformly from [8,16], while decoding temperature is drawn uniformly from [0.5, 1.0].Source: §E.3 · p. 14
  • Decoding length penalty is drawn uniformly from [0, 1.2].Source: §E.3 · p. 14
  • Depth penalty is drawn from discrete values [0.8, 0.9, 0.95, 1] and exponentially decays backup values with depth to favor breadth or depth.Source: §E.3 · p. 14
  • The exploration setting is the PUCT constant, listed as 1.Source: §E.3 · p. 14

Related papers

Loading 2302.11223v2…