Symbolic regression via MDLformer-guided search: from minimizing prediction error to minimizing description length

## \thesubsection Symbolic Regression on Black-Box Problems

[24]r7cm
\includegraphics[width=7cm]figs/blackbox.pdf
We also test our method on 122 black-box problems from SRbench. Unlike ground-truth problems, in these problems, there are no underlying formulas describing the patterns in data. Therefore, we split the data of each problem into $75\%$ training set and $25\%$ test set, and, instead of recovery rate, we evaluate the results using the Pareto front that balances the test set accuracy and the formula complexity, which is a common practice in SR tasks \citetcavalab2022srbench. For the baseline methods, in addition to the three types of methods considered in the ground-truth problem set, we also consider decision tree-based methods (see Appendix LABEL:sec:baselines for details), where the constructed decision trees are treated as a generalized formula tree that uses conditional selection as operators and the number of nodes in the trees are used as the formula complexity.
The overall performance of our method and other baselines is shown in Figure \thefigure, where we can see that, our method achieves a higher test set $R^{2}$ with lower model complexity than other methods and is thus sharing the first rank of the Pareto front with three other search algorithms, that is, Operon \citepburlacu2020operon, GP-GPMEA \citepvirgolin2021improving, and DSR \citeppetersen2021deep.
In contrast, decision tree methods or regression methods usually construct formulas that are too complex and lack interpretability to describe the given data; while generative methods are unable to iteratively optimize the results and thus have low test set accuracy.
\thesubsection MDLformer Performance
{wraptable}
[4]r4.3cm
\topruleRMSE
$R^{2}$
AUC
\midrule3.9105
0.9035
0.8859
\bottomrule
We report the prediction performance of MDLformer by evaluating it on $K=1024$ pairs of symbolic formulas and numeric data generated as described in Section LABEL:sec:pretrainData, where the independent variables $x$ are sampled from GMM.
Given that the relative relationship of predicted values is more important than their absolute magnitudes when using MDLformer to guide symbolic regression, we consider ranking metrics in addition to the commonly used root mean squared error (RMSE) and coefficient of determination ($R^{2}$). Particularly, we consider the area under the ROC curve (AUC) \citepfawcett2006introduction, which assesses the likelihood that the predicted values and true values maintain consistent ordering when randomly selecting pairs (formalized in Appendix LABEL:sec:metrics).
where $\mathbb{I}$ is the indicator function.
As shown in Table \thefigure, the RMSE metric indicates an average error of $3.9$, which is only $15\%$ of the average formula length of $25$. The $R^{2}$ and AUC are also close to $1.0$, demonstrating the excellent performance of MDLformer in predicting the complexity of formulas corresponding to the data. We also provide the results of the other three metrics in Appendix LABEL:sec:metrics.
{wrapfigure}[29]r7cm
\includegraphics[width=7cm]figs/caseStudy.pdf
MDLformer indicates correct search directions.
Here we use a case study to illustrate that the minimum description length (MDL) estimated by MDLformer has the optimal substructure, that is: 1) the subformula of the target formula has a lower MDL than other formulas and 2) the MDL monotonically decreases along the construction route of the target formula $f$.
As shown in Figure \thefigure, we consider the Feynman I.18.4 equation, where the target formula can be obtained from five steps of transformations $T_{0:4}^{*}$. Specifically, starting from $d_{0}\equiv x$, we iteratively operate the transformation $T^{*}_{i}$ that eventually maps $d_{0}$ to $d_{5}\equiv y$. For each $d_{i}$, we estimate its MDL concerning $y$ with the MDLformer and plot the result in the red line, finding the estimated MDL does monotonically decrease as the formula form gets closer to the target formula.
For each $d_{i}$, we also draw the estimated MDL of $d^{\prime}=T^{\prime}(d_{i})$ for all possible symbolic functions $T^{\prime}$ as the blue sectors, finding that nearly few of $d^{\prime}$ has a lower MDL than the correct transformation result of $d_{i+1}^{*}=T_{i}^{*}(d_{i})$. indicating the correct search direction is consistent with the direction in which MDL decreases the fastest.
Ablation study on training strategy.
Figure \thefigurea shows the ablation experiment on the training strategy. We considered three strategies to train the MDLformer with the alignment objective $\mathcal{L}_{\mathrm{align}}$ and the prediction objective $\mathcal{L}_{\mathrm{pred}}$: 1) sequentially training for alignment and then prediction (i.e., the training scheme described in Sec LABEL:sec:pretrain), 2) training for alignment and prediction concurrently, and 3) direct training for prediction without alignment. A total of 1000 rounds of training were performed for each of the three wheres, where for the first method, the first 500 rounds are for alignment and the last 500 rounds are for prediction.
Among them, the first two strategies have lower RMSE than the last one, demonstrating that aligning numerical and symbolic spaces improves cross-model prediction, which is consistent with the observation of previous work \citepmeidani2023snip. The Sequential strategy has a lower RMSE than the Concurrent strategy, which may be because it is more difficult to use both objectives at the same time.
Figure \thefigureb shows the relationship between the prediction error and the number of input points $N$, demonstrating that more data can help MDLformer predict the minimum description length more accurately. However, a larger $N$ can lead to an increase in inference time, thus we choose $N=200$ to balance the accuracy and efficiency.
Consistent predictive capability across task difficulty.
In Figure \thefigured,e,f we measure the predictive performance of MDLformer on formulas of different difficulty, indicated by 1) the number of variables, 2) the number of unary operators, and 3) the number of binary operators. Although RMSE, consistent with intuition, increases with the formula difficulty. But considering that more difficult formulas can have longer lengths, we additionally plot the ratio of $RMSE$ to the average formula length, $\bar{L}$, in the graph. It can be seen that as the formula difficulty increases, the normalized RMSE remains basically unchanged, indicating that our MDLformer scales well with the formula difficulty.
Robustness against noise.
In Figure \thefigurec we add feature noise to the data of independent variables: $x\leftarrow x+n$, where $n\sim\mathcal{N}(0,\eta\sigma_{x})$ is additive noise with intensity proportional to the standard deviation of $x$, $\sigma_{x}$. We find that although the RMSE increases with the noise intensity, the ranking metric, AUC, basically remains unchanged as noise increases, suggesting that our method can identify the relative magnitude of MDL even under noisy conditions. Considering that the search process relies solely on the relative magnitude of estimated MDL, this explains the reason for the robustness of our method to noise in Section LABEL:sec:groundTruth.
\includegraphics
[width=]./figs/ablationStudy.pdf
Figure \thefigure:
Ablation Study.
The prediction performance of MDLformer with respect to
a: trained with three alignment strategies,
b: number of input pairs $N$,
c: feature noise $\eta$,
d: number of variables $D$,
e: number of unary operators,
and f: number of binary operators.
In d,e,f we also plot the RMSE normalized by the average formula length $\bar{L}$.

## \thesubsection MDLformer Performance

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. In Table 1, the second-best methods are DSR (Petersen et al., 2021) and AIFeynman2 (Udrescu et al., 2020). These methods from 2020 and 2021 not only outperform those from 2022, 2023, and 2024 significantly but also achieve results up to four times greater. Could this discrepancy be due to variations in experimental settings?
2. The proposed method is trained on an extensive dataset (1.3B), while the other methods were trained on considerably smaller datasets. Could an ablation study be conducted, where all methods are trained on the same dataset to enable a more direct performance comparison?
soundness: 2
strengths: 1. This paper is well-written, with the authors presenting the algorithm process and their perspectives clearly and comprehensively.
2. Figures 1 and 2 effectively illustrate the authors' viewpoints in a clear and intuitive way.
3. The proposed method demonstrates efficiency and achieves state-of-the-art performance compared to baseline methods.
summary: This paper proposes a search objective based on the principle of minimum description length, which aims to streamline and enhance symbolic regression tasks. The authors generate a targeted training dataset and employ neural network techniques to develop a symbolic regression function. By using neural networks in this way, the approach is intended to improve both the efficiency and effectiveness of modeling complex data relationships through symbolic regression.
weaknesses: 1. This paper demonstrates limited innovation. The proposed method comprises three main parts: the first part provides a conventional description of neural network structure; the second generates a dataset, but the symbolic formula generation method follows that of Kamienny et al. (2022). The third part introduces two loss functions in the training process, with the first being the standard mean square error. Overall, the paper offers little originality.
2. Could larger datasets be used for experimentation? The datasets in this study are relatively small, such as Strogatz (14 problems) and Feynman (119 problems).
3. The proposed method relies on training with a substantial dataset (1.3 billion), while other methods have not been trained on datasets of this scale. This raises the question of whether the method’s effectiveness is largely attributable to the extensive volume of training data.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: You say you sample D in line 215, which makes sense, since you need D to create the formula. However, you again sample D in line 221. However, here, shouldn’t D be the dimensionality of f?

I assume that the auxiliary loss on line 252 is computed per-batch? If so, this should be noted. If not, I would like more details on how this is done.
soundness: 3
strengths: This paper has a very elegant approach to the problem of symbolic regression, taking a principled approach towards the search process. Despite the theoretically intractable nature of the objective function selected, in practice it seems that a transformer is able to learn it well enough to make this search strategy better than existing strategies relying on end-to-end behavior. The resulting framework is more robust to noise than existing frameworks and more generalizable to a variety of domains. The results seem quite strong, with the only unfavorable result being underperformance relative to AIFeynman2 on the Feynman dataset in the absence of noise, which seems like a fairly narrow and understandable failure case.
summary: Existing symbolic regression frameworks operate by searching through the space of functions as vectors, minimizing a norm on the input-output behavior of the function. This paper instead approximates a search on the syntactic space of functions by computing a proxy metric for the minimum description length of the function necessary to take a given set of subcomponents and compute the full function. To do this, a synthetic dataset of functions is created and used to train a model that predicts a matching between functions and I/O behavior. The same dataset is then used to finetune this model to predict minimum description length. Overall, the model generally outperforms existing baselines, with particularly good relative performance in the case of noise.
weaknesses: Firstly, the datasets being evaluated on seem relatively small and thus potentially prone to being covered by the dataset. However, this seems to be a relatively standard convention that the related work follows, so I am not particularly concerned about this.

Secondly, the example in Figure 6 seems to suggest that there are very few alternate formulas that could be selected, and yet the recovery rate of this algorithm on the Feynman dataset is below 50%. Is this example atypical or is the search tree large even when heavily pruned? An explanation either way would be helpful (e.g., raw fractions for what the 4%, 0.2%, etc., are might clarify this if e.g., 4% is still 100 possibilities).

MInor:

Figure 6 and description: the blue sector description should probably say “all T that are lower according to the model than T^*” and emphasize that these are incorrect search paths -- it is a bit confusing to read otherwise. The caption does this better than the label on the  graph itself or the paragraph describing the figure.
471-472: “finding that nearly few” I think you mean “very few” or “nearly none”.
482: “for each of the three wheres” I think you mean “for each of the three strategies”
Figure 7: there are no axis labels for the right axis for d e and f.

Extremely minor nit: for figure 7 when you have two axes you color the left axis labels black and the right axis green, while the lines are blue and green. The axis labels should either both be black or blue and green.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: - The data contamination problem should be further discussed. The authors generate 131 million data points, which poses a potential risk of overlap between training data and testing data. Does the generated data introduce contamination problems, and how can this problem be avoided in the data generation process?
- Some related studies should be discussed. Many recent studies [1] focus on adopting neural networks for symbolic reasoning. The authors should provide a brief discussion about the differences and advantages of the proposed method.

[1] A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference. NeurIPS 2023.
soundness: 3
strengths: - The overall idea of this paper is intuitive and reasonable. The traditional search objective, i.e., prediction error, cannot effectively capture the distance between the target and current formulas.
- The experimental results are promising. The proposed method significantly outperforms existing methods, demonstrating that a more sophisticated objective can help improve the recovery rate.
summary: This paper addresses a fundamental challenge in symbolic regression: the traditional search objective, namely prediction error, is non-monotonic, which limits the effectiveness of the search process. The authors propose a novel approach by training a neural network called MDLformer to tackle this. This model introduces a new objective function to efficiently guide the formula search. The experimental results demonstrate that the proposed method significantly outperforms existing approaches.
weaknesses: - The evaluation dataset is limited. Unlike existing studies, this paper aims to introduce a neural network to guide the search process. As a result, it is crucial to comprehensively assess whether this model can generalize well on other tasks. However, the two datasets used in this study are relatively small. For instance, the Strogatz dataset only includes 14 problems, which is insufficient to effectively capture the performance of each method. Therefore, incorporating additional datasets [1] is necessary to thoroughly evaluate the proposed approach.
- The proposed MDLformer model requires an in-depth discussion. Firstly, the method generates synthetic data to train the model. How do the authors ensure that this synthetic data generalizes effectively across various downstream tasks? Secondly, with 131 million data points generated, how does the model’s performance change as the data scale increases, and does it eventually reach performance convergence?
- The technical section should be clear and self-contained. Although the concept of Minimum Description Length (MDL) originates from existing studies, further clarity is needed on its technical details, such as how it is computed in the proposed method. At present, the technical content is somewhat difficult to follow.

[1] A Comparison of Recent Algorithms for Symbolic Regression to Genetic Programming. Preprint.

Meta-review: This paper proposes a novel method for symbolic regression, namely discovering the symbolic formula fitting data. Unlike existing methods where the difference between the symbolic function and the actual data is minimized during the search steps, this paper proposed to minimize the minimum description length, a more appropriate metric for this task. Calculating the minimum description length is nontrivial, and the authors trained a transformer to do this calculation. The experiments show promising results on a few standard evaluation benchmarks in this field. 

While two reviewers recognized the importance and novelty of this work, reviewer LjPc questioned the contribution of this work and the fairness of comparison against prior work. The AC has also carefully read the paper and the reviews, and believes that the review from LjPc was indeed mostly due to misunderstandings of its setting. In this symbolic regression setting, the final goal is to recover the original symbolic expressions with high accuracy, and many baselines used self-generated training examples to fit their own pipeline, so the training examples are incomparable. A better metric the authors should actually compare is the amount of compute used for building this pipeline, compared to prior work. Despite some concerns on evaluation and some improvements on writing should be done to avoid confusion (like those from reviewer LjPc), the AC believes the methodology proposed in this work is insightful and may inspire future research in this field, so we recommend the acceptance of this paper.

Decision: Accept (Poster)