Reinforcement Symbolic Regression Machine

Q2. The functionality of the interpolation method and its relation to data pre-processing.

Reply: Thanks for your comment. We employ an interpolation method to generate $f(-x)$ and directly compare it with $f(x)$ for each data point, establishing the presence of odd, even, or neither symmetry within the function. The determination of parity remains consistent throughout and precedes the search step, remaining unchanged thereafter. Hence, this meticulous procedure is a fundamental component of our pre-processing stage.

Q3. The meaning of “performing well” and details about the selection of expression forms.

Reply: Thank for your suggestion. Firstly, performing well means greater reward.

Next, we give details of selecting expression forms: (1) In the form of multiplication ($\mathcal A \times f(x)$) or exponentiation ($\mathcal A^{f(x)}$), we select the best expression as the chosen form. (2) In the case of addition ($\mathcal A + f(x)$), we opt for expressions with a reward greater than $k_p \times \max\{\text{reward}\}$.Then those expressions are split and count each part. Additionally, we select components whose occurrences satisfy $o > k_s \times \max\{o\}$. The values of $k_s$ and $k_p$ are provided in Appendix A.1. For instance, if $x^5$ occurs 50 times, $-x^4$ occurs 4 times, and $x^3$ occurs 11 times, we finds the form as $x^5 - x^3 + f(x)$. These thresholds remain consistent across all datasets.

Q4. The unclear part of the form-discovery algorithm.

Reply: Thank for your notice. Please see our explanation as follows.

"This approach effectively reduces the difficulty associated with specific equations." This statement is not clear.

For example, obtaining an expression like $x^4 - x^3 - 0.5y^2 + x$ directly can be challenging. However, by identifying its components such as $x^4$ and $-x^3$, we construct the form $x^4 - x^3 + x + f(x)$ to alleviate the difficulty of searching for the term $-0.5y^2$.

The concept of "search form" and the use of "..in this search form" is not clear. Is search form a synonym of "search space"? Please clarify.

The term “search form” denotes the continuous exploration based on a predefined expression structure. For instance, in the form $e^x + f(x)$, we regard $e^x$ as an integral part of the overall expression. Therefore, if the outcome of the MCTS is $x + x^2$, the resultant expression would be $e^x + x + x^2$. Our calculations for RMSE and reward are based on this resultant expression.

The form ($\mathcal A + f(x)$) considers that the entire expression is constructed by the concatenation of terms through sign addition ($+$) or subtraction ($-$). Consequently, if expressions such as $e^x - x$ and $e^x + x$ yield favorable results, it suggests that the overall expression may be of the form $e^x + f(x)$.

Similarly, when the form($\mathcal A \times f(x)$) involves concatenation through multiplication ($\times$) or division ($\div$), the evaluation of expressions like $1.57e^x$ and $1.56e^x + x$ helps identify that the expression could be of the form $e^x \times f(x)$.

Q5. Number of expressions evaluated.

Reply: This is an excellent comment. In fact, there is a tradeoff between the recovery rate (accuracy) and the computational complexity of the model. We have performed a trade-off experiment in the manuscript illustrating the recovery rate in terms of the number of evaluations. Please see Appendix Section C.7 and Fig. S2. Here is the table of this experiment result for your reference.

Table. Trade-off experiment: Average Number of Evaluations / Average Recovery Rate (%) of the Nyugen Benchmark over 100 parallel runs.

Please do not hesitate to let us know if you have any further questions. Thank you very much.

We sincerely thank the reviewer for the constructive comments and suggestions, which are very helpful for improving our paper. The revisions have been incorporated in the revised manuscript marked in red.

Q1. Clarity and presentation of the paper.

Reply: Thank you for this comment. We have followed the reviewer’s suggestion and thoroughly revised the manuscript. Here are some examples of revision (more details are found in the revised manuscript):

To better illustrate the novelty of our proposed model, an additional paragraph highlighting the motivation and novelty of the Modulated Sub-tree Discovery (MSDB) has been included.

• We introduced a new modulated sub-tree discovery (MSDB) block, the critical component of the proposed RSRM model, to heuristically learn and define new math operators to improve the representation ability of underlying math expression trees. Here, we would like to emphasize that MSDB addresses a crucial observation that models often struggle to generate complete expressions but excel in capturing certain components. For instance, NGGP may discover an expression like $x^4-x^3+\cos(y)+x-1$, while the ground truth is $x^4-x^3-0.5y^2+x$. Notably, it successfully recovers the simplified expression $x-0.5y^2$ with the same distribution. To this end, MSDB offers a new alternative to simplify expressions by subtracting specific components in the context of a sub-tree, as exemplified by the subtraction of $x^4-x^3$ in the aforementioned case.

Given the brevity of the description of the workflow in the previous version, we have revised the caption of Figure 1.

• RSRM comprises several steps. First, the data is input into the data pre-processing module to determine the parity. Each epoch, the process initiates with the utilization of the MCTS module to generate expressions (Step ①). Subsequently, these expressions undergo the addition of forms and reward calculation (Step ②). The expressions are then refined through GP (Step ③), leading to more accurate expressions (Step ④). Following this, the equation forms are integrated and rewards are calculated (Step ⑤). This iterative cycle, involving MCTS and GP, continues for several rounds, ultimately resulting in the renewal of forms based on the most proficient expressions (Step ⑥).

In the absence of a comprehensive description of the design of the three sub-tree expression forms, an additional paragraph has been added to explicate the genesis of these forms.

• In fact, the three forms (namely, ${\mathcal{A} + f(x)}$, $\mathcal{A}\times f(x)$, $\mathcal{A}^{f(x)}$) are general and applicable to express sub-tree structures of any generic formula. Our approach involves the establishment of these forms based on the initial token of the expression tree, because the root of an expression tree serves as a focal point, indicating the primary operation or function in the expression. Thus, we can separate the sub-tree forms based on it. Specifically, if the first token corresponds to addition ($+$) or subtraction ($-$), the method proceeds to learn the generation of the left and right sides of the respective operators. Similarly, for tokens such as multiplication ($\times$), division ($\div$), or exponentiation (^{}), a similar procedure is followed. In the case of unary expressions, such as trigonometric functions ($\sin$ and $\cos$), the MCTS and GP models effortlessly derive the complete expression. Therefore, while our method involves a degree of empirical design in identifying the sub-tree expression forms, it possesses a universal nature.

In addition, here are some examples of the revision of uncleared sentences:

• Symbolic Regression (SR) can be defined as the task of automatically distilling equations from limited data.

• However, there still exist bottlenecks that current methods struggle to break when the expression we need to explore tends toward infinity and especially when the underlying math formula is intricate.

• In the early years, polynomial analysis was commonly used to fit expressions.

• By incorporating double Q-learning into MCTS, we effectively balance exploration and exploitation of SR tasks

• The objective of SR can be transformed into the generation of an optimal expression tree.

We believe these revisions significantly enhance the clarity of our manuscript, making it easier to follow. We would like to take this opportunity to thank the reviewer for the careful reading and putting forward these detailed and constructive comments.

Table 1. Average Recovery Rate of the Const Optimization Benchmark over 100 parallel runs

Table 2. Percentage of expressions under a certain recovery rate about the Const Optimization Benchmark over each initializing method

We sincerely thank the reviewer for the constructive comments and suggestions, which are very helpful for improving our paper. The revisions have been incorporated in the revised manuscript marked in red.

Q1. Theoretical Analysis.

Reply: Thanks for this comment. Since primary part of the search method we employed in our proposed RL model is the UCT-based MCTS, the theoretical analysis (e.g., convergence, guarantees) of this algorithm can be found in literature such as Shah et al. (2019). We have clarified this in our revised manuscript.

Q2. Definition of $c$ in the UCT algorithm.

Reply: Thanks for the reviewer’s comment. $c$ typically represents the exploration-exploitation tradeoff parameter. The exploration-exploitation tradeoff is a fundamental challenge in decision-making under uncertainty. In the context of UCT, it refers to the balance between exploring new possibilities (potentially discovering a better move or solution) and exploiting known information (favoring moves or solutions that seem promising based on existing knowledge).

Choosing an appropriate value for $c$ is crucial, as it influences the algorithm's behavior. A higher $c$ encourages more exploration, while a lower $c$ emphasizes exploitation. The optimal value for $c$ often depends on the specific problem or environment being addressed. It may need to be tuned through experimentation for different scenarios. In this paper , we take $c = \sqrt{2}$.

Q3. Experiment on initial value of constant optimization.

Reply: This is an excellent remark. We conducted an experiment considering different initialization approaches for constant optimization. Specifically, we explored seven methods shown as follows (Case 1 – Case 7).

Case 1: Initializing constants with a vector of ones (the initialization method in former models). Case 2: Initializing constants with a vector of random uniform values between 0 and 1. Case 3: Initializing constants with a vector of random uniform values between 0.5 and 1.5. Case 4: Initializing constants with a vector of random Gaussian values with a mean of 0 and standard deviation of 1. Case 5: Initializing constants with a vector of random Gaussian values with a mean of 1 and standard deviation of 1. Case 6: Initializing constants with a vector of random Gaussian values with a mean of 1 and standard deviation of 0.5. Case 7: Initializing constants with a vector of random Gaussian values with a mean of 0 and standard deviation of $\frac{1}{3}$.

We evaluated the recovery rate of each expression using different constant initialization methods across diverse benchmarks, employing ranges of input values such as [0,1], [-1,1], [0,10], [-10,10], [0,50], [-50,50], and data sizes of 20 or 500. Notably, Table 1 demonstrates that the average recovery rates across all initializing methods are remarkably close.

However, examining the distribution of expression recovery rates below 50%, 10%, and 0%, it becomes apparent that the method employing a vector of ones exhibits the highest percentage from Table 2. This observation indicates that the Case 1 initialization method (with the vector of all ones) has the highest number of expressions unable to converge once across 100 parallel runs.

We have added a section in the Appendix to discuss this (see Appendix Section C.6).

Q4. The AIFeynman Benchmark results.

Reply: Thanks for your question. The selection of 12 AI Feynman equations was based on a stratified representation of difficulty levels for symbolic regression. The chosen expressions include easy ones, such as $x_1x_2$ and $\frac{3}{2}x_1x_2$; medium complex expressions like $x_1x_2x_3\sin(x_4)$ and $x_1x_2+x_3x_4+x_5x_6$; medium-hard expressions such as $\frac12x_1(x_2^2+x_3^2+x_4^2)$ and $x_1x_2x_3(\frac{1}{x_4}-\frac{1}{x_5})$; and hard expressions like $\frac{x_1x_2x_3}{(x_4-x_5)^2+(x_6-x_7)^2+(x_8-x_9)^2}$ and $1+\frac{x_1x_2}{1-x_1x_2/3}$. This selection for illustration provides a comprehensive coverage of the AIFeynman benchmark.

Despite we only show the detailed results for the above 12 selection equations, the complete recovery results of the AIFeynman benchmark are summarized in Figure 3b. Notably, our model achieves a SOTA 80% average recovery rate, outperforming other existing representative baseline models and indicating its proficiency in capturing the underlying mathematical structures across a diverse range of expressions.

Q5. No error bars on the main results.

Reply: Thanks for your suggestion. In fact, since the recovery rates of individual equations within the same benchmark dataset do not follow the Gaussian distribution, the application of an error bar denoting the confidence range may not be suitable in this context. This is generally admitted in the symbolic regression community. However, we provide a table (see Table 3 below) outlining the 95% confidence range for each method within each benchmark for your reference.

Table 3. 95% confidence range of recovery rate (%) for each method within each benchmark

Please do not hesitate to let us know if you have any further questions. Thank you very much.

Dear Reviewer AFH1,

We extend our sincere gratitude for dedicating your valuable time to thoroughly review our paper and provide insightful comments. With only two days remaining in the Author-Review Discussion period, we want to ensure that we've satisfactorily addressed all your concerns. If there are any remaining questions or unresolved matters, please don't hesitate to reach out. We are glad to provide further clarification or make necessary revisions.

Best regards,

The Authors

We sincerely thank the reviewer for the constructive comments and suggestions, which are very helpful for improving our paper. The revisions have been incorporated in the revised manuscript marked in red.

Q1. Expression forms that may restrict the applicability of the method to other domains.

Reply: Thanks for the reviewer’s excellent comment. In fact, the three forms (namely, ${\mathcal{A} + f(x)}$, $\mathcal{A}\times f(x)$, $\mathcal{A}^{f(x)}$) are general and applicable to express sub-tree structures of any generic formula. Our approach involves the establishment of these forms based on the initial token of the expression tree, because the root of an expression tree serves as a focal point, indicating the primary operation or function in the expression. Thus, we can separate the sub-tree forms based on it. Specifically, if the first token corresponds to addition ($+$) or subtraction ($-$), the method proceeds to learn the generation of the left and right sides of the respective operators. Similarly, for tokens such as multiplication ($\times$), division ($\div$), or exponentiation (^{}), a similar procedure is followed. In the case of unary expressions, such as trigonometric functions ($\sin$ and $\cos$), the MCTS and GP models effortlessly derive the complete expression. Therefore, while our method involves a degree of empirical design in identifying the sub-tree expression forms, it possesses a universal nature.

Q2. Application of SR in practical domains and its superiority over neural network regression.

Reply: Thanks for this question. Symbolic regression (SR) has found broad applications across diverse fields, including discovery of fundamental physical laws [1, 2] or governing equations [3-5], modeling material constitutive relations [6], and TCP congestion control [7], among many others. For example, in the case of TCP congestion control, SR can be used to learn the control policy with better interpretability and generalization ability, which also exhibit advantage of computational speed in comparison with neural network regression models. In addition, when the training data is very limited, the neural network model tends to have the over-fitting issue, whereas SR can still produce a model with good generalizability.

Q3. Elaboration on each step in figure 1.

Reply: Thanks for your suggestion. We have added more detailed description of each step about Figure 1 in its caption, e.g.,

“First, the data is input into the data pre-processing module to determine the parity. Each epoch, the process initiates with the utilization of the MCTS module to generate expressions (Step ①). Subsequently, these expressions undergo the addition of forms and reward calculation (Step ②). The expressions are then refined through GP (Step ③), leading to more accurate expressions (Step ④). Following this, the equation forms are integrated and rewards are calculated (Step ⑤). This iterative cycle, involving MCTS and GP, continues for several rounds, ultimately resulting in the renewal of forms based on the most proficient expressions (Step ⑥).”

Please do not hesitate to let us know if you have any further questions. Thank you very much.

References:

[1] Silviu-Marian Udrescu and Max Tegmark. AI Feynman: A physics-inspired method for symbolic regression. Science Advances, 6(16): eaay2631, 2020.

[2] Ziming Liu and Max Tegmark. Machine learning conservation laws from trajectories. Physical Review Letters, 126(18):180604, 2021.

[3] Michael Schmidt and Hod Lipson. Distilling free-form natural laws from experimental data. Science, 324(5923):81–85, 2009.

[4] Zhao Chen, Yang Liu, and Hao Sun. Physics-informed learning of governing equations from scarce data. Nature Communications, 12(1):6136, 2021.

[5] Fangzheng Sun, Yang Liu, Jian-Xun Wang, and Hao Sun. Symbolic physics learner: Discovering governing equations via Monte Carlo tree search. International Conference on Learning Representations, 2023.

[6] Yiqun Wang, Nicholas Wagner, and James M Rondinelli. Symbolic regression in materials science. MRS Communications, 9(3):793–805, 2019.

[7] SP Sharan, Wenqing Zheng, Kuo-Feng Hsu, Jiarong Xing, Ang Chen, and Zhangyang Wang. Symbolic distillation for learned TCP congestion control. Advances in Neural Information Processing Systems, 35:10684–10695, 2022.

We sincerely thank the reviewer for the constructive comments and suggestions, which are very helpful for improving our paper. The revisions have been incorporated in the revised manuscript marked in red.

Q1. Novelty, motivation and advantages of the model.

Reply: Thanks for this question. Firstly, we would like to mention that existing symbolic regression (SR) methods generally struggle with generating lengthy and complex equations, and are faced with issues related to overfitting, e.g., poor generalizability. We aimed to develop a new model (aka., RSRM) to overcome these critical challenges, which has shown SOTA performance as demonstrated over extensive examples on over 200 symbolic test formulas.

Secondly, we do not agree with the reviewer’s comment on “a simple combination of existing methods”. The coordination of different methods or blocks requires a rational design (see the workflow in Figure 1) which largely affects the balance between exploration and exploitation. A simple combination would not work. In addition, we introduced a new modulated sub-tree discovery (MSDB) block, the critical component of the proposed RSRM model, to heuristically learn and define new math operators to improve the representation ability of underlying math expression trees. Here, we would like to emphasize that MSDB addresses a crucial observation that models often struggle to generate complete expressions but excel in capturing certain components. For instance, NGGP may discover an expression like $x^4-x^3+\cos(y)+x-1$, while the ground truth is $x^4-x^3-0.5y^2+x$. Notably, it successfully recovers the simplified expression $x-0.5y^2$ with the same distribution. To this end, MSDB offers a new alternative to simplify expressions by subtracting specific components in the context of a sub-tree, as exemplified by the subtraction of $x^4-x^3$ in the aforementioned case.

Therefore, the novelty of the proposed model is three-fold: (1) Using double Q-learning in junction with MCTS effectively reduces redundant search thus improving the exploration efficiency and efficacy. (2) The proposed MSDB block for discovering new sub-tree expression forms takes the divide-and-conquer concept and could significantly improve the overall search performance of the RSRM model. In particular, MSDB can handle equations with symmetry (reducing the complexity), and assist in dealing with long equations by identifying common patterns and defining new math operators on the fly. (3) The proposed RSRM model demonstrates clear superiority over many representative baseline models and yields the SOTA SR results, which offers a new approach to tackle very complex SR challenges.

Q2. Exploration efficiency of MCTS.

Reply: This is a good question. In fact, the UCT is employed during the MCTS simulation while the greedy selection of the maximum reward is only applied to choose the optimal expression tree (as shown in Algorithm 1). We have tested, when we designed the model, that greedy selection of the maximum reward performs better that the case of the highest UCT score in the context of SR tasks.

Note that the maximum UCT score-based greedy selection method often selects nodes with a lower possibility to generate non-meaningful equations. For instance, it may prefer selecting $\sin$ nodes across all instances range over $\log$ nodes, because the output of $\sin$ is within the [-1,1] range, and the latter might yield NaN for negative values. However, this preference doesn't align with our objective, as the $\log$ token could potentially be the optimal choice. Hence, we opt to only consider the best expression (with the maximum reward) to determine which node to use in the selection step.

Q3. Expression forms that may restrict the applicability of the method to real-world problems.

Reply: Thanks for the reviewer’s excellent comment. In fact, the three forms (namely, ${\mathcal{A} + f(x)}$, $\mathcal{A}\times f(x)$, $\mathcal{A}^{f(x)}$) are general and applicable to express sub-tree structures of any generic formula. Our approach involves the establishment of these forms based on the initial token of the expression tree, because the root of an expression tree serves as a focal point, indicating the primary operation or function in the expression. Thus, we can separate the sub-tree forms based on it. Specifically, if the first token corresponds to addition ($+$) or subtraction ($-$), the method proceeds to learn the generation of the left and right sides of the respective operators. Similarly, for tokens such as multiplication ($\times$), division ($\div$), or exponentiation (^{}), a similar procedure is followed. In the case of unary expressions, such as trigonometric functions ($\sin$ and $\cos$), the MCTS and GP models effortlessly derive the complete expression. Therefore, while our method involves a degree of empirical design in identifying the sub-tree expression forms, it possesses a universal nature.

Q4. The generalization experiment on more complex problems.

Reply: Thanks for your comment and suggestion. The reason why we tested our model by discovering a surrogate formula to approximate the cumulative density function (CDF) of a normal distribution is because this equation lacks an explicit elementary expression. Hence, it's impossible to obtain an exact solution through SR. Learning this function requires balancing between training error and generalization error, demanding a stronger ability to generalize. Moreover, only half of the curve data is provided, necessitating strong generalization skills from the model to extrapolate and accurately fit the missing portion of the curve. This calls for the proficiency of the model in capturing the distribution of the entire curve. In summary, this is in fact not a simple SR case, in which many existing SR methods fail.

Indeed, we acknowledge the importance of assessing the generalization ability of our model in more complex real-world scenarios. To address this, we conducted tests on the SRBench datasets, a benchmark comprising complex real-world problems with added noise. The results (see Figure 3b and Appendix Figure S3) demonstrate the superior performance of our model compared to other models, including UDSR, which has been recognized as the leading model in the preceding year.

Dear Reviewer d71r,

We extend our sincere gratitude for dedicating your valuable time to thoroughly review our paper and provide insightful comments. With only two days remaining in the Author-Review Discussion period, we want to ensure that we've satisfactorily addressed all your concerns. If there are any remaining questions or unresolved matters, please don't hesitate to reach out. We are glad to provide further clarification or make necessary revisions.

Best regards,

The Authors