Neural-Guided Symbolic Regression with Asymptotic Constraints
Authors: Li Li
Minjie Fan
Rishabh Singh
Patrick Riley
Venue:  (2020)
Keywords: symbolic regression
program synthesis
monte carlo tree search

Abstract: Symbolic regression is a type of discrete optimization problem that involves searching expressions that fit given data points. In many cases, other mathematical constraints about the unknown expression not only provide more information beyond just values at some inputs, but also effectively constrain the search space. We identify the asymptotic constraints of leading polynomial powers as the function approaches 0 and infinity as useful constraints and create a system to use them for symbolic regression. The first part of the system is a conditional expression generating neural network which preferentially generates expressions with the desired leading powers, producing novel expressions outside the training domain. The second part, which we call Neural-Guided Monte Carlo Tree Search, uses the network during a search to find an expression that conforms to a set of data points and desired leading powers. Lastly, we provide an extensive experimental validation on thousands of target expressions showing the efficacy of our system compared to exiting methods for finding unknown functions outside of the training set.

Under review as a conference paper at ICLR 2020
NEURAL-GUIDED SYMBOLIC REGRESSION ASYMPTOTIC CONSTRAINTS
WITH
Anonymous authors Paper under double-blind review
ABSTRACT
Symbolic regression is type of discrete optimization problem that involves search- ing expressions that fit given data points. In many cases, other mathematical constraints about the unknown expression not only provide more information be- yond just values at some inputs, but also effectively constrain the search space. We identify the asymptotic constraints of leading polynomial powers the func- tion approaches 0 and oo as useful constraints and create system to use them for symbolic regression. The first part of the system conditional production rule generating neural network which preferentially generates production rules to construct expressions with the desired leading powers, producing novel expressions outside the training domain. The second part, which we call Neural-Guider Monte Carlo Tree Search, uses the network during a search to find an expression that conforms to set of data points and desired leading powers. Lastly, provide extensive experimental validation on thousands of target expressions showing the efficacy of our system compared to exiting methods for finding unknown functions outside the training set.
INTRODUCTION
The long standing problem of symbolic regression tries to search expressions in large space that fit given data points (Koza & Kozal 1992, (Schmidt & Lipson 2009). These mathematical expressions are much more like discovered mathematical laws that have been an essential part of the natural sciences for centuries. Since the size of the search space increases exponentially with the length of expressions, current search methods can only scale to find expressions limited length. Moreover, current symbolic regression techniques fail to exploit a key value of mathematical expressions that has traditionally been well used by natural scientists. Symbolically derivable properties such as bounds, limits, and derivatives provide significant guidance finding an appropriate expression.
In this work, we consider one such property corresponding to the behavior of the unknown function as it approaches 0 and co. Many expressions have defined leading polynomial power in these limits. For examples when x - co, 2x + 5x has a leading power of 2 (because the expression behaves like x and 1 1/x² + 1/x has leading power of 11 We call these properties "asymptotic constraints" because this kind of property is known priori for some physical systems before the detailed law is derived. For example, most materials have heat capacity proportional 7 at low temperatures T and the gravitational field of planets (at distance r) should behave as 1/r as r + co.
Asymptotic constraints not only provide more information about the expression, leading to better extrapolation, but also constrain the search in the desired semantic subspace, making the search more tractable in much larger space. These constraints can not be simply incorporated using syntactic restrictions over the grammar of expressions. We present a system to effectively use asymptotic constraints for symbolic regression, which has two main parts. The first is conditional production rule generating neural network (NN) of the desired polynomial leading powers that generates production rules to construct novel expressions (both syntactically and semantically) and, more surprisingly, generalize leading powers not in the training set. The second part is Neural- Guided Monte Carlo Tree Search (NG-MCTS) that uses this NN to probabilistically guide the search at every step to find expressions that fit set of data points.
Finally, we provide an extensive empirical evaluation of the system compared to several strong baseline techniques. We examine both the NG-MCTS and conditional production rule generating NN

---

Under review as a conference paper at ICLR 2020
alone. In sharp contrast to almost all previous symbolic regression work, evaluate technique thousands of target expressions and show that NG-MCTS can successfully find the target expressions in much larger fracctinn of cases (71%) than other methods (23%) with search space sizes of more than 1050 expressions.
In summary, this paper makes the following key contributions: 1) We identify asymptotic constraints as important additional information for symbolic regression tasks. 2) We develop a conditional production rule generating NN to learn distribution over (syntactically--aiid) production rules conditioned on the asymptotic constraints. 3) We develop the NG-MCTS algorithm that uses the conditional production rule generating NN efficiently guide the MCTS large space. 4) We extensively evaluate our production rule generating NN to demonstrate generalization for leading powers, and show that the NG-MCTS algorithm significantly outperforms previous techniques on thousands of tasks.
2 PROBLEM DEFINITION
In order to demonstrate how prior knowledge can be incorporated into symbolic regression, construct a symbolic space using a context-free grammar G:
- $ + S'+'T S' 1 S S T '('S')' 'x' '1'
(1)
This expression space covers rich family of rational expressions, and the size of the space can be further parameterized by a bound on the maximum sequence length. For an expression [(x), the leading power at zo is defined as Pa-xo [f] p s.t. lim f(z)/2² /2" non-zero constant. this paper, we consider the leading powers at To E {0, oo as additional specification.
Let S(G, k)) denote the space of all expressions in the Grammar G with a maximum sequence length k. Conventional symbolic regression searches for a desired expression f(x) in the space of expressions S(G, k) that conforms g(x) S(G, k)) ((g(z), Drrain). where ó denotes the acceptance criterion, usually root mean square error (RMSE). With the additional specification of leading powers e( and c(00) at 0 and co, the problem becomes: find g(x) E S(G, k) ((g(z), A (P2--olg = (P2->oolll = c(oo)).
set of data points {ax, f=)) x E Dirsiu), i.e. find
3 CONDITIONAL PRODUCTION RULE GENERATING NEURAL NETWORK
is difficult to directly incorporate the asymptotic constraints as syntactic restrictions over the grammar. We, therefore, develop neural architecture that learns generate production rule in the grammar conditioned on the given asymptotic constraints.
expression
S
Selection
Expansion
4x) = 1
S
leading
(t))
TT
S+T+T
x--00
foo
Evaluation
Backpropagation
S4T4T
looding power 0
Heading pouse 6--20
Figure I: Overview. (a) Exemplary expression. (b) Leading powers of 1/(z æ + 1) and cc. (c) Parse tree of 1/(x +1)++ 1). (d) Production rule sequence, the preorder traversal of production rules the parse tree. (e) Architecture of the model predict the next production rule from the partial sequence conditioned on desired leading powers. (f) Using (e) to guide MCTS.
2

---

Under review as a conference paper at ICLR 2020
Figure [ and (c) show example of how an expression is parsed parse tree by the grammar defined in Eq. [ The parse tree in Figure T()) can be serialized into a production rule sequence Pi.....77 by preorder traversal (Figure (T), where L denotes the length of the production rule sequence. Figure shows the leading powers of the exemplary expression in Figure Ta). The sequential model
conditional distribution of expression is parameterized
L-1 II
Po([lc cloo)
po (ni.
- co)) c.oo)..
We build a NN (as shown in Figure Te)) to predict the next production rule r++1 from partial sequence "i,....?? and conditions " c(oo) During training, each expression in the training set first parsed as a production rule sequence. Then partial sequence of length t E (L...., L 1} is sampled randomly as the input and the (t + 1--th production rule is selected as the output (see blue and orange text in Figure [d)). Each production rule of the partial sequence is represented as embedding vector of size 10. The conditions are concatenated with each embedding vector. This sequence of embedding vectors are fed into a bidirectional Gated Recurrent Units (GRU) (Cho et al. 2014) with 1000 units. A softmax layer is applied to the final output of GRU to obtain the raw probability distribution over the next production rules in Eq. D.
Note that not all the production rules grammatically valid as the next production rule for given partial sequence. The partial sequence is equivalent to a partial parse tree. The next production rule expands the leftmost non-terminal symbol in the partial parse tree. For the partial sequence colored in blue in Figure [d), the next production rule expands non-terminal symbol T, which constrains the next production rule to only those with left-hand-side symbol T. We use stack to keep track of non-terminal symbols in a partial sequence as described in GVAE (Kusner et al. 2017). A mask of valid production rules is computed from the input partial sequence. This mask applied to the raw probability distribution and the result is normalized to as the output probability distribution. The training loss is calculated as the cross entropy between the output probability distribution and the next target production rule. It is trained from partial sequences sampled from expressions in the training set using validation loss for early stopping !
NEURAL-GUIDER MONTE CARLO TREE SEARCH
We now briefly describe the NG-MCTS algorithm that uses the conditional production rule generating NN to guide the symbolic regression search. The discrepancy between the best found expression g(x) and the desired (x) is evaluated on data points and leading powers. The error on data points is measured by RMSE A9(-) = v ExeED, (f(x)) - /(x)))/\(({)) on training points D
(1.2, 1.6, 2.0, 2.4, 2.8}, points in interpolation region D Dinterpolation {1.4. 1.8, 2.2, 2.6) and points in extrapolation region D Dextrapolation
(5, 6, 7,8, 9}. The error on leading powers measured by sum of absolute errors at 0 and oo, AP(o] [P==o[f] Pa_o[9]] + PPa--oo [f] [.]+ The default choice of objective function for symbolic regression algorithms is Agtrain alone. With additional leading powers constraint, the objective function be defined Agtrain + + P(g], which minimizes both the RMSE on the training points and the absolute difference of the leading powers.
Most symbolic regression algorithms are based on EA (Schmidt & Lipson| 2009), where it is nontrivial to incorporate our conditional production rule generating NN to guide the generation strategy in step-by-step manner, as the mutation and cross-over operators perform transformations on fully completed expressions. However, it is possible to incorporate a probability distribution over expressions in many heuristic search algorithms such as Monte Carlo Tree Search (MCTS). MCTS is a heuristic search algorithm that has been shown to perform exceedingly well in problems with large combinatorial space, such as mastering the game of Go (Silver al. (016) and planning chemical syntheses (Segler et al. 2018). In MCTS for symbolic regression, a partial parse tree sequence ri...... rt can be defined as state 8, and the next production rule is a set of actions (a). In the selection step, we use variant of the PUCT algorithm (Silver et al. 2016 Rosin 2011) 1) for exploration. For MCTS, the prior probability distribution p(a,) st) is uniform among all valid actions.
We develop NG-MCTS by incorporating the conditional production rule generating NN into MCTS for symbolic regression. Figure presents a visual overview of NG-MCTS. In particular, the prior
Model implemented in TensorFlow Ahadi et al. 2016) and available in submitted materials.
3

---

Under review as a conference paper at ICLR 2020
Table 1: Results of symbolic regression methods. Search expressions in holdout sets M [f]] - M[f] = 5 and M[f] = 6 with data points on Dtrain and or leading powers P== and P. Pa-xx [f]. The options are marked by on (v), off (x) and not available (-). If the RMSEs of the best found expression g(x) in interpolation and extrapolation are both smaller than 10 and AP[s] = 0, it is
solved. g(x)) is non-terminal or oc, it is invalid. Hard includes expressions in the holdout set which are not solved by any of the six methods. The medians of Attaain Afnt. Aexxt. and the median absolute errors of leading powers [ for hard expressions are reported.
M Method
Nearal
Objective Function
Solived
Invalid Percent
Hard
Guided
Denus
Pa-ause [
Percent
Afkrats
Aghut.
Aftect.
AP(a)
MCTS MCTS (PW-coly) MCTS PW NG-MCTS
X
0.545
2,93%%
0.728
0.598
0.723
3
0.24%
0.00%
2.069
2.823
1
44
EA
V
71.22%
12.834
0.20%
0.00%
0.39%
3,32%
23.66%
0.967
0:225
0.186
0.836
0.162
0.358
0.541
2
3
EA + PW
23.37%
0.44%
0.376
0.322
0.152
0
GVAR!
10.00%
0.00%
90.00%
0.217
0.159
0.599
2
GVAE PW1
10.00%
0.00%
90.00%
0.386
0.324
0.056
0
MCTS MCTS (PW-only) MCTS + PW NG-MCTS
3.90%
0.857
0.00%
0.00%
1,890
1/027
3
0.10%
3.50%
58.00%
L,105
0
0.600
4
5
32.10%
2,00%
0.00%
4
0.247
0.227
0.239
0,020
0
EA PW
9.20%
2.30%
0,366
0.365
0.109
0
GVAE
0.00%
0.00%
100,00%
0.233
0,259
0.164
4
GVAE PWT
3.33%
0.00%
96.67%
0.649
0.565
0.383
MCTS MCTS (ayyy
0.00%
6.33%
1.027
0.811
0.852
6
0.00%
0.00%
2.233
7,145
MCTS
NG-MCTS
V
17.33%
0.08%
0.17%
7,33%
71.25%
0.236
1.228
0.209
0.008
=6
EA
1.25%
5.08%
0,219
0.191
0.084
5
EA PW
4.92%
6.92%
0.329
0.285
0.047
GVAE!
0.00%E
0.00%
100.00%
0.260
0.206
0.037
5
GWAE
PWI
0.00%
0.008
100,00%
0.595
0.136
0,087
Evaluated on the subset of holdout sets. Hard are unsolved expressions in the subset (Appendix
probability distribution p(u.|st,c(0) c(0)) ((0)) is computed by our conditional production rule generating NN on the partial sequence and the desired conditions. We run MCTS for 500 simulations for each desired expression fz) The exploration strength is set to 50 and the production rule sequence length limit is set to 100. The total number of expressions this combinatorial space is 3 x 1093, We run evolutionary algorithm (EA) (Appendix G and grammar variational autoencoder (GVAE) (Kusner with comparable computational setup for comparison.
ct al. 2017) (Appendix H
5 EVALUATION
Dataset and Search Space: We denote the leading power constraint as a pair of integers
(Pa->o[J), [/-) and define the complexity of a condition by M[]]= [P]- + PP PP- []]. Obviously, expressions with M[J] = are more complicated to construct than those with M[ [[[]=0] =.
We create dataset balanced on each condition, as described in Appendix A The conditional produc- tion rule generating NN is trained on 28837 expressions and validated on 4095 expressions, both with M[f] < 4. The training expressions are sampled sparsely, which are only 10 23 of the expressions within 31 production rules. Symbolic regression tasks are evaluated on 4250 expressions
holdout
sets with M[f] < 4,
6. The challenges are: 1) conditions M[f] 5, 6 do not exist in training set: 2) the search spaces of M[]] = 5,6 6 are 10" and 10tal times larger than the training set.
5.1 EVALUATION OF SYMBOLIC REGRESSION TASKS
We now present the evaluation of our NG-MCTS method, where each step in the search is guided by the conditional production rule generating NN. Recent developments symbolic regression methods (Kusner et al. 2017 Sahoo et al. 2018) compare methods on only few expressions, which may cause the performance to depend on random seed for initialization and delicate tuning. To mitigate this, we apply different symbolic regression methods to search for expressions in holdout sets with thousands expressions and compare their results in Table [ Additional comparison on a subset of holdout sets is reported in Appendix H
4

---

Under review as a conference paper at ICLR 2020
Unsolved
150
Targel
NG-MCTS
100
GVAE
53 PW MCTS PM
Unsolved
GVAE + PW
EA
50
EA PW
Unsolved
-10
-50
-15
-10
2
10
NG MCTM
Figure 2: Extrapolation errors of symbolic re-
Figure 3: Plot of force field expressions found by each method. Grey area is the region compute interpolation error Agint. and light blue area the region to compute extrapolation error Agext..
gression methods in holdout set M[f] = Each expression is point, where 1o Agext. obtained by NG-MCTS is on x-axis and those obtained by other three methods
the y-axis.
We first discuss the results for holdout set M[ S 4. Conventional symbolic regression only fits on the data points Durain EA solves 12. 12.83% expressions, while MCTS only solves 0.54% expressions. This suggests that compared to EA, MCTS is not efficient in searching a large space with limited number of simulations. The median errors A are both 3 for hard expressions (expressions unsolved by all methods), which are large as maximum M[f] for this set is 4.
In order examine the effect of leading powers, use leading powers alone in MCTS (PW-ONLY). The median [Pgg] for hard expressions is reduced to but the medians Aint. and gext. significantly higher. We then add leading powers the objective function together with data points. MCTS PW does not have a notable difference to MCTS. However, EA + PW improves solved expressions 23.37% and A of hard expressions O. This indicates adding leading power constraints in the objective function is helpful for symbolic regression. Most importantly, we observe step-wise guidance of NN conditioned on leading powers can lead even more significant improvements compared to adding them in the objective function. NG-MCTS solves 71.22% expressions the holdout set, three times over the best EA PW. Note that both MCTS PW and EA PW have access to the same input information. Although EA has the lowest medians of AStrain and Agint., NG-MCTS is only slightly worse. On the other hand, NG-MCTS outperforms on Sgext. and AP[g). which indicates that step-wise guidance of leading powers helps to generalize better in extrapolation than all other methods.
We also apply the aforementioned methods to search expressions in holdout sets M[ 5 and M[f] 6. The percentage of solved expressions decreases as M increases as larger [[] requires learning expressions with
complex syntactic structure. The median of [ also increases with larger M for the other methods, but the value for NG-MCTS is always zero. This demonstrates that our NN model is able to successfully guide the NG-MCTS even for leading powers appearing in the training set. Due to the restriction on the computational time of Bayesian optimization for GVAE, we evaluate GVAE + PW on subset of holdout sets (Appendix H.. GVAE+ PW fails in holdout sets M [f] 5, 6. Overall, NG-MCTS still significantly outperforms other methods in solved percentage and extrapolation. Figure 2 compares Agxxt for each expression among different methods in holdout set [ = 5. The upper right cluster in each plot represents expressions unsolved by both methods. Most the plotted points are above the line (dashed), which shows that NG-MCTS outperforms the others for most unsolved expressions in extrapolation. Examples of expressions solved by NG-MCTS but unsolved by EA PW and vice versa are presented in Appendix P We also perform similar experiments with Gaussian noise on Derain and NG-MCTS still outperforms all other methods Appendix K)
Diguprree
5.2
CASE STUDY: FORCE FIELD POTENTIAL
Molecular dynamics simulations (Alder & Wainwright 1959) study the dynamic evolution of physical systems, with extensive applications in physics, quantum chemistry, biology and material science. The interaction of atoms coarse- coarse-grained particles (Kmiecik et al., 2016) is described by potential energy function called force field, which is derived from experiments or computations of quantum mechanics algorithms. Typically, researchers know the interactions in short and long ranges, which are examples
5

---

Under review as a conference paper at ICLR 2020
Table 2: Results of force field expressions found by each method.
Merhod
Expression Found
Agumi
Aguu..
Agist.
NG-MCTS
(1)z))
0.00
0.00
0.00
GVAE
(1/a)/la xa/a
0.47
0.29
34,9
+PW
(1/a)- -=+==++a---- x)a
EA
0.52
0.46
34.8
EA + PW
(1/s)+ (xx))))
1,15
1.10
6.16
0
of asymptotic constraints. We propose a force field potential U(x) = 1/x + x (x 1) with Coulomb interaction, uniform electric field and harmonic interaction. Assuming the true potential is unknown, the goal is to discover this expression. As a physical potential, besides values at Dtrain: : f1.2, 1.6, 2.0, 2.4, 2.8), researchers also know the short (r - 0) and long range (x - 20) behaviors as leading powers. Table Sable[]show, shows the expressions found by NG-MCTS, GVAE, GVAE = PW, EA and EA + PW, which are plotted in Figure 3 NG-MCTS can find the desired expression. The second best method is GVAE + PW, differing by a constant of 1 from the true expression.
5.3 EVALUATION OF CONDITIONAL PRODUCTION RULE GENERATING NN
NG-MCTS significantly outperforms other methods on searching expressions large space. To better understand the effective guidance from NN, we demonstrate its ability to generate syntactically and semantically novel expressions given desired conditions. In order to examine the NN alone, we directly sample from the model by Eq. instead of using MCTS. The model predicts the probability distribution over the next production rules from the starting rule 71 O - S and desired condition ((o)),
(c (()))), The next production rule is sampled from distribution po(r2 |ri, c00), c(oo)) and then appended to r1. Then 13 sampled from (o(ra)r r2, (0)), c(ee)) and appended to [ri, This procedure is repeated until [r....., TL] form parse tree where all the leaf nodes are terminal, the
length of generated sequence reaches the prespecified limit, which is set to 100 for our experiments.
Baseline Models We compare NN with number of baseline models that provide probability distribution over the next production rules. All these distributions are masked by the valid production rules computed from the partial sequence before sampling. For each desired condition within [Pa-o[[]] < 9 and |Pa-so [f] < 9, k 100 expressions are generated.
We consider the following baseline models: i) Neural Network No Condition (NNNC): same setup as NN except no conditioning on leading powers, ii) Random: uniform distribution over valid next production rules, iii) Full History (PH): using full partial sequence and conditions sample next production rule from its empirical distribution, iv) Full History No Condition (FHNC), v) Limited History (LH) (U: sampling next production rule from its empirical distribution given only the last I rules in the partial sequence, and vi) Limited History No Condition (LHNC) (l). Note that the aforementioned empirical distributions are derived from the training set {f). For limited history models, if exceeds the length of the partial sequence, we instead take the full partial sequence. More details about the baseline models can be found Appendix B
Metries We propose four metrics evaluate the performance. For each condition (c("), cloe)), expressions {g:} } are generated from model pa (f(((())) c(oe)). i) Success Rate: proportion of generated expressions with leading powers (Pz+o(gi)) (g.) (g:]) that match the desired condition, ii) Mean Li-distance: the mean Li-distance between (P2-oo[g)) (a.=ocl9.)) and (c("), c( iii) Syntactic Novelty Rate: proportion of generated expressions that satisfy the condition and are syntactically novel (no syntactic duplicate of generated expression in the training set), and iv) Semantic Novelty Rate: proportion of expressions satisfying the condition and are semantically novel (the expression obtained after normalizing the generated expression does not exist in the training set). For example, expressions x + 1 and (1) + x are syntactically different, but semantically duplicate. We use simplify function in SymPy (Meurer et al.) (017)) to normalize expressions. To avoid inflating the rates of syntactic and semantic novelty, we only count the number of unique syntactic and semantic novelties in terms of their expressions and simplified expressions, respectively.
Quantitative Evaluation Table compares the model performance of baseline and NN models
measured by different metries. We define M[f] < 4 as in-sample condition region and Mff > 4 as out-of sample condition region. In both regions, the generalization ability of the model is reflected by the number of syntactic and semantic novelties it generates, not just the number of successes. For

---

Under review as a conference paper at ICLR 2020
Table 3: Metries for conditional production rule generating NN and baseline models.
Mff. S 4
MJJ 4
MIA
$
5
=7
Model
Total
Expressions Syn
Num Conditions with Suc
Syn (%)
Sem (%t)
Mean I.I-Dis
Suc
Sem
NN
35,0
2.7
1465
1416
1084
115
0.8
1,4
4.3
NNNC
1.8
0.2
7
7
4.0
5.6
6.5
7.5
Random
0.7
0.0
0
0
0
10.9
11.7
12.4
12.6
FH
0.0
0.0
0
0
0
0.0
18.0
18.0
18.0
FHNC
0.0
4.2
7.5
LH (2)
5.0
L.I
0
0
0
3.1
18.0
18.0
18.0
LH
2.1
2.5
18.0
18.0
LH (8)
14.6
2.4
0
0
0
1.8
18.0
18.0
18.0
LH
0.1
0.1
LHNC (2)
1.4
0.3
7
7
6
4.2
5.6
6.9
7,5
LHNN
3.9
7.3
LHNC (8)
1.5
0.3
8
6
4.2
5.9
6.7
7.6
LHNC (16)
0.1
4.3
7,5
example, FH behaves as a look-up table based method (i.c., sampling from the training set) so has 100% success rate in in-sample condition region. However, it is not able to generate any novel expressions. NN has the best performance on the syntactic and semantic novelty rates in both the in- sample (35% and 2.7%) and out-of-sample (1416 and 1084) condition regions by a significant margin. This indicates the generalization ability of the model to generate unseen expressions matching a desired condition. is worth pointing out that NNNC performs much worse than NN, which indicates that NN is not only learning the distribution of expressions in the dataset, but instead is also learning a conditional distribution to map leading powers to the corresponding expression distributions.
Furthermore, the L1 -i-isttaece measures the deviation from the desired condition when not matching exactly. NN has the least mean Li-distance the out-of-sample condition region. This suggests that for the unmatched expressions, NN prefers expressions with leading powers closer to the desired condition than all other models. NN outperforms the other models not only on the metries aggregated over all conditions, but also for individual conditions. Figure 4 shows the metrics for NN and LHNC (8) on each condition. NN performs better in the in sample region (inside the red boundary) and also generalizes to more conditions in the out-of -o---ple-pppe region (outside the red boundary).
NW:: Success rate (%)
Moan Lidd stance
Syriactic novelty rata (%) Semantic novelly rate (%)
loading
2007 123756788
04766-5510133350
power
LINNC (0I: Success rete (S)
Mean stance
Syntectic novelty rate (5)
Sementic novely by nate (%)
kcading
eading power
kading power x
leading po
leading power 2-0
Figure 4: Visualizing metrics for conditional production rule generating NN and LHNC (8) on each condition within [f- < 9 and PP-+solf]] < 9. Conditions with M[f] < 4 are inside the red boundary and points with 0 value are left blank.
Qualitative Evaluation To better comprehend the learned NN model and its generative behavior, we also perform a task of expression completion given a structure template of the form and variety of desired conditions in Table 4 For each condition, 1000 expressions
generated by NN and the probability of each syntactically unique expression is computed from its occurrence. We first start with c(0) = 0, c(oo) = 1. The completed expression g(x) ) is required to be a nonzero constant + co. The top three probabilities
as x - and g(x:) + easy complete. We then repeat the task (!0)) -1 (00) 1 and (0) -2,
close since this task is relatively
(00) (oo) 2, which
7

---

Under review as a conference paper at ICLR 2020
still in the in sa-sam condition region and the model can still complete expressions that match the
desired conditions. We also show examples of c(0) = -3, c = 2. which is in the out-of-sample condition region. Note that to match condition c = -3, more complicated completion such as 1/(r * (z x)) has to be constructed by the model. Even in this challenging case, the model can still generate some expressions that match the desired condition. We also show examples of the syntactic
novelties learned by model in Appendix L
6 RELATED WORK
Schmidt & Lipson (0099) present a symbolic regression technique to learn natural laws from experimental data. The symbolic space is defined by operators + - *, /, sin, cos, constants, and variables. An expression is repre- sented as a graph, where intermediate nodes rep- resent operators and leaves represent coefficients and variables. The EA varies the structures to search new expressions using score that accounts for both accuracy and the complexity of the ex- pression. This approach has been further used to get empirical expressions in electronic engineer- ing (Ceperic et al. 2014), water resources (Klotz et al. (017). and social science (Truscott & Korns 2014). GVAE (Kusner et al., 2017) was recently proposed to learn generative model of structured arithmetic expressions and molecules, where the latent representation captures the underlying structure. This model was further shown to improve Bayesian optimization based method for symbolic regression.
Symbolic Regression:
Table 4: Examples of top-3 probable expression completions for different desired conditions.
Misi
Expression
Probability
1/
13
7.8%
7.7%
7.0%
17.43
V
6.8%
V
[2
48.5%
12.5%
1
7.4%%
1/ (1)
20.5%
1/ [2+2]
10.3%
x
1/ ((+())))))
12.9%
Similar to these approaches, most other approaches search for expressions from scratch using only data points (Schmidt & Lipson 2009 Ramachandran et al. [2017] Ouyang et al. (018)) without other symbolic constraints about the desired expression. AAbu-Mostafa (1994) suggests incorporating prior
knowledge of a similar form to our property constraints, but actually implements those priors by adding additional data points and terms in the loss function.
Neural Program Synthesis: Program synthesis the task of learning programs in a domain-specific language (DSL) that satisfy given specification (Gulwani al.] 2017). It is closely related to symbolic regression, where the DSL can be considered as grammar defining the space of expressions. Some recent works use neural networks for learning programs (Devlin et al. 2017 Balog et al.) 20166) Parisotto et al. 2017; Vijayakumar et al. 2018). RobustFill (Devlin et al. 2017 trains an encoder- decoder model that learns decode programs as sequence of tokens given set of ouputt examples. For more complex DSL. grammars such as Karel that consists of nested control-flow, an additional grammar mask used to ensure syntactic validity of the decoded programs (Bunel et al., 2018). However, these approaches only use examples as specification. Our technique can be useful to guide search for programs where the program space is defined using grammars such as SyGuS with additional semantic constraints other than only examples (Alur et al. 2013 Si et al. 2018).
7 CONCLUSION
We present a two-step framework of first learning neural network of the relation between syntactic structure and leading powers and then using that to guide MCTS for efficient search. This framework evaluated in the context of symbolic regression and focused on the leading power properties on thousands of desired expressions, much larger evaluation set than benchmarks considered in existing literature. We plan to further extend the applicability of this framework to cover other symbolically derivable properties of expressions. Similar modeling ideas could be equally useful in general program synthesis settings, where other properties such as the desired time complexity or maximum control flow nesting could be used constraints.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: system for large-scale machine learning. In 12th USENIX Symposium Operating Systems Design and Implementa- lion (OSDI 16), pp. 265 2016.
org/ system/ files/
Con.ereence/ssdiin osdi 16 abadi. pdf
Yaser S Abu-Mostafa. Learning from hints. J. Complex. 10:165-178, 1994.
Berni J Alder and Thomas Everett Wainwright. Studies in molecular dynamics. i. general method.
The Journal of Chemical Physics, 31(2):4594466 1959.
Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax- guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR, USA, October 20-23, 2013, pp. 1-8, 2013. URL http:://teexxpooeeeeee wew.ppp.....eeee..o.......... org/
(occuent/6679330
Matej Balog Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning write programs. CoRR, abs/1611.01989, 2016. http:////arxy
org abs//ba/// 16661.166 01989
Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. Scheduled sampling for sequence prediction with recurrent neural networks. Advances in Neural Information Processing Systems, pp. 1171-1179, 2015.
Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. CoRR, abs/1 805.04276, 2018.
Vladimir Ceperic, Niko Bako, and Adrijan Baric. A symbolic regression-based modelling strategy of ac/dc rectifiers for rfid applications. Expert Systems with Applications, 41((1):7061-7067 2014.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint 140iv:1406.100 2014.
Oscar Claveria, Enric Monte, and Salvador Torra. Quantification of survey expectations by means of symbolic regression via genetic programming to estimate economic growth in central and eastern european economies. Kastern European Economics, 54(2):171-18, 2016.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Australia, 6-1 August 2017, pp. 998, 2017. http: htttt::/prroeeeee ngs ml press/v70// deniiiiiiiill.. html
Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. DEAP: Evolutionary algorithms made easy. Journal of Machine Learning Research, 13:2171-2175, jul 2012.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends in Programming Languages, 4(1-2):1-119 2017. doi: 10.1561/2500000000. URL https
//doi. aawii.org/ii. 15110000000000000000000000
Klotz, M Hermegger, and K Schulz. Symbolic regression for the estimation of transfer functions of hydrological models. Water Resources Research, 53(1 1)94022-9423, 2017.
Sebastian Kmiecik, Dominik Gront, Michal Kolinski, Lukasz Wieteska, Aleksandra Elzbieta Dawid, and Andrzej Kolinski. Coarse- -raiied protein models and their applications. Chemical reviews, 116( (18114))78877999 2016.

---

Under review as a conference paper at ICLR 2020
John R Koza and John R Koza. Genetic programming: the programming of computers by means of natural selection, volume 1. 1992.
Matt J Kusner, Brooks Paige, and José Miguel Hermández-Lobato. Grammar variational autoencoder.
arXiv preprini
2017.
Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondřej Čertik, Sergey B. Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rathnayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pedregosa, Matthew J. Curry, Andy R. Terrel, Stěpán Roučka, Ashutosh Saboo, Isuru Fernando, Sumith Kulal, Robert Cimrman, and Anthony Scopatz. Sympy: symbolic computing in python. PeerJ Computer Science, 3:3103, January 2017. ISSN 2376-5992, doi: 10.7717/peerj-cs.100 URL httttttt///....ooo wtg. 10. 7717/peer] cs. 103
Runhai Ouyang, Stefano Curtarolo, Emre Ahmetcik, Matthias Scheffler, and Luca M Ghiringhelli. Sisso: compressed-sensingg method for identifying the best low-dimensional descriptor in an immensity of offered candidates. Physical Review Materials, 2(8):083802, 2018.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. ICLR, 2017. URL httt:://arxiv.org/
1611.01851
Markus Quade, Markus Abel, Kamran Shafi, Robert K Niven, and Bernd R Noack. Prediction of dynamical systems by symbolic regression. Physical Review E, 94(1):012214, 2016.
Prajit Ramachandran, Barret Zoph, and Quoe Le. Searching for activation functions. CoRR, abs/1710.05941, 2017. URLphtt:://arxtiti www.ooogggg/baaaooeo abs/1710. 05941
Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):203-22 2200000-2222222200 2011.
Subham S Sahoo, Christoph H Lampert, and Georg Martius. Learning equations for extrapolation and control. arXiv preprint arXiv:1806.07255 2018
Michael Schmidt and Hod Lipson. Distilling free-form natural laws from experimental data, science, 324(5923):81-88) 2009.
Marwin HS Segler, Mike Preuss, and Mark P Waller. Planning chemical syntheses with deep neural networks and symbolic ai. Nature, 555(7698):604, 2018.
Xujie Si, Yuan Yang, Hanjun Dai, Mayur Naik, and Le Song. Learning a meta-solver for syntax- guided program synthesis. ICLR, 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484, 2016.
Philip Truscott and Michael F Korns. Explaining unemployment rates with symbolic regression. In Genetic Programming Theory and Practice XI, pp. 119-135. Springer, 2014.
Ashwin J. Vijayakumar, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guide deductive search for real-time program synthesis from examples. CoRR, abs/1804, 118880401181 2018
10

---

Under review as a conference paper at ICLR 2020
A DATASET
To create an initial dataset, we first enumerate all possible parse trees from
0 S S - S'TT 5' - S S |
T '(S'' '1'''''
within ten production rules. Then we repeat the following downsampling and augmentation operations for four times to expand the dataset for longer expressions and diverse conditions.
Downsampling Expressions are grouped by their simplified expressions computed by SymPy (Meurer et al. (017). We select 20 shortest expressions terms of string length from each group. These expressions are kept to ensure syntactical diversity and avoid having too long expressions.
Augmentation For each kept expression, five new expressions are created by randomly replacing one of the or x symbols by (1/z), (z/(1 x)), (x/(1 x)). (1/(1+ + z)), (1/(1 - z)), (1 x). (1 + +)) (x * x), (x * (1+ z)). (x * (1 z)). These five newly created expressions are added back to the pool of kept expressions to form an expanded set of expressions.
After repeating the above operations for four times, we apply the downsampling step again in the end. To make the dataset balanced on each condition, we keep 1000 shortest expressions in terms of string length for each condition. this way, we efficiently create an expanded dataset which is not only balanced on each condition but also contains large variety of expressions with much longer length than the initial dataset. Compared to enumerating all possible expressions given the maximum length, the created dataset is much sparser and smaller.
For each pair of integer leading powers satisfying M[f] S 1000 shortest expressions are selected to obtain 41000 expressions in total. They are randomly split into three sets. The first two are training (28837) and validation (4095) sets. For the remaining expressions, 50 expressions with unique simplified expressions are sampled from each condition for M[]] S 4, to form holdout set with 2050 expressions. In the same way, we also create a holdout set of 1000 expressions for M [f] = and 1200 expressions for [ 6. These conditions do not exist in training and validation sets.
Table A.I: Minimum, median and maximum of the lengths of the production rule sequence. Space size is the number of possible expressions within the maximum length of the production rule sequence.
Length
Name
Number of Expressions
Space Size
Min
Median
Max
training [[ < 4
19
31
28837
2.2 x 1027
holdout M[ S 4
19
2050
2.2 x 1027
holdout M[ 5
15
27
39
1000
8.9 x 1034
holdout M[f] = 6
11
31
43
1200
5.8 x 1038
Figure A. shows the histogram of lengths of the production rule sequence for expressions in the training set and holdout sets. Table A. shows the minimum, median and maximum of the lengths of the production rule sequence. The last column, space size, shows the number of possible expressions within the maximum length of the production rule sequence (including those non- terminal expressions). It is computed recursively as follows. Let N., denote the number of possible expressions with length Σ i and whose production rule sequences start with symbol *, where * can be O, S and T. Then we have
Ns.1
Σ (Ns.p Nr,i-1-p) + Nr.-11; p=0
Nr, Ns..1
and the initial condition is Ng.0 Nr = 1. We can obtain Ns., using the recursive formula. The quantity of interest No,; N given that the first production rule is pre-defined O - S. Holdout sets [f] = 5, 6 not only contain expressions of higher leading powers but also of longer length, which is challenging for generalization both semantically and syntactically.

---

Under review as a conference paper at ICLR 2020
training set S4
8000
6000
4000
2000
0
800
holdout set M <4
400
0
400
holdout set M
300
200
100
400
holdout set M
300
200
100
0
length of the production rule sequence
Figure A.1: Histograms of lengths of the production rule sequence.
B DETAILS OF THE BASELINE MODELS
We provide more details of the baseline models we proposed be compared with our NN model. Using the same notation as in Eq. ④ the conditional distribution of the next production rule given the partial sequence and the desired condition is denoted by
p(ret1/ri...... (0)) c(0))).
The baseline models essentially different ways to approximate the conditional distribution using empirical distributions.
Limited History (LH) (I) The conditional distribution is approximated by the empirical conditional distribution given at most the last / production rules of the partial sequence and the desired condition. We derive the empirical conditional distribution from the training by first finding all the partial sequences therein that match the given partial sequence and desired condition. Then we compute the proportion of each production rule that appears as the next production rule of the found partial sequences. The proportional is therefore the empirical conditional distribution. To avoid introducing an invalid next production rule, the empirical conditional distribution is multiplied by the production rule mask of valid next production rules, and renormalized.
PLH(() = p(r (0) c(oo)).
Full History (FH) The conditional distribution approximated by the empirical conditional distribution given the full partial sequence and the desired condition. The empirical conditional distribution is derived from the training set similarly as the LH model.
PFH = ((r++1 (f,...., Pt, (0) cloo)).
Limited History No Condition (LHNCC) ( The conditional distribution approximated by the empirical conditional distribution given at most the last I production rules of the partial sequence only, where the desired condition is ignored. The empirical conditional distribution is derived from the training set similarly as the LH model.
PlHNO()
12

---

Under review as a conference paper at ICLR 2020
Full History No Condition (FHNC) The conditional distribution is approximated by the empirical conditional distribution given the full partial sequence only, where the desired condition is ignored. The empirical conditional distribution is derived from the training set similarly as the LH model.
РFHNс = p(retalr
C DETAILS OF AGGREGATING METRICS ON DIFFERENT LEVELS
The metrics are aggregated on different levels. We compute the average of success rates, syntactic novelty rates and semantic novelty rates over all the conditions in the in-sample condition region. The out-of-sample condition region is not bounded, and hence we consider the region within [/]] < and [2-+=>]]] I 9. Since the average can arbitrarily small the boundary is arbitrarily large, instead we compute the total number of success, syntactic novelty and semantic novelty expressions over all the conditions in the -aatpll-ampee region.
The LI-distance is not well defined for expression which is non-terminal or oc. For both cases, we specify the L1 distance as 18, which is the Li-distance between conditions (0, 0) and (9,9).
D DIVERSITY OF GENERATED EXPRESSIONS
Condition
Condition
Condition (-2,
Unique expression
350
Unique simplified expcission
200
300
Count
250
150
200
150
100
5
50
50
00
200
400
600
800
1000
0
200
4000 600
800
1000
0
200
4000
600
800
1000
Number of generated expressions
Number of generated expressions
Number of generated expressions
Figure D.I: Cumulative counts of unique expressions and unique simplified expressions that satisly the desired condition among expressions generated by the NN model on various desired conditions. Left: desired condition (c(0) c(oo)) (0, Middle: desired condition (c(0) cloo)
(5, 5). Right: desired condition (c(0) c(())) (-).-3).
model that generates expressions with a high success rate (i.e., satisfying the desired condition most of the times) but lacking of diversity is problematic. To demonstrate the diversity of ex- pressions generated by our NN model, we generate 1000 expressions on each desired condition, and compute the cumulative counts of unique expressions and unique simplified expressions that satisfy the desired condition among the first number of expressions of the 1000 generated expres- sions, respectively. Figure D.I shows the cumulative counts on three typical desired conditions (c("), c((=)) (0, 0), (5, 5), (-2,- -3). We can observe that the counts steadily increase as the ber of generated expressions under consideration increases. Even with 1000 expressions, the counts have not been saturated.
E ADDITIONAL. PLOTS OF METRICS FOR PRODUCTION RULE GENERATING NN AND BASELINE MODELS
Due to the space limit of the paper, Figure in the main text only contains the plots of metrics each condition for LHNC (8) and NN. Additional plots of all the baseline models in Table are presented in this section. Figure E. contains NN, NNNC and Random. Figure E.2 contains FH and FHNC. Figure E. contains LH (2), LH (4), LH (8) and LH (16). Figure E.4 contains LHNC (2), LHNC (4), LHNC (8) and LHNC (16).
13

---

Under review as a conference paper at ICLR 2020
NN: Success rate (%)
Mean Li-distance
Syntactic novelty rate (96)
Semantic novelty rate (%)
POBB
leading power
BBR
BB
BB
B BO SE COUR
BB0
48.76543210 2244222112456777
98.765533 003432201235500
9876543210123455777
leading
leading
leading power
leading
Success rate 1%6
1-distance MInn
Syntactic nevelty rate 1%)
Semantic novelty (%6)
leading power
10000000
00000
0000000
00000000000000000000000000000000
44176543210333433
448-----5--2---1-
035443211133360 leading power 2 -
941-445443321123444 leading power 2 0
leading power -
leading power 0
Random: Success rate (%)
Mean L1-dit 11-distance
Syntactic nevelty rate 1%)
Semantic novelty rate (%)
leading power
44.7445-::32----- 1 889
448-7----4-32--10 14563345777 4
2487456-321117336 221-232522133347788 08745443101234550
leading
leading
leading
leading =
Figure E.1: Metrics for NN, NNNC and Random models each condition within P and Pa-+iu [f]] S 9. Each column corresponds to a metric: success rate, mean Ll-distance, syntactic novelty and semantic novelty rate, respectively. Conditions with M[f] S 4 are inside the red boundary. Conditions with zero success rate, syntactic novelty rate or semantic novelty rate are left blank the corresponding plots.
F SELECTION STEP IN MONTE CARLO TREE SEARCH
In the selection step, we use variant of the PUCT algorithm Silver et al. 2016 Rosin 201 for exploration,
V Es (s,,
U(s a) Cpuct P(st, a) 1 ()),,
(3)
where N(st, a) is the number of visits to the current node, Σs N( is the number of visits to the parent of the current node, Cpuct controls the strength of exploration and P(*e, a) is the prior probability of action a. This strategy initially prefers action with high prior probability and low visits for similar tree node quality Q(s,,a). a).
G EVOLUTIONARY ALGORITHM
We implemented the conventional symbolic regression approach with EA using DEAP (Fortin et al. 2012). a popular package for symbolic regression research (Quade et al., 2016 Claveria et al. 2016). We define of required primitives:
-, *, and 1. An expression represented where all the primitives are nodes. We start with a population of 10 individual trees with the maximum tree height set 50. The probability of mating two individuals is 0.1, and of mutating individual
tree
14

---

Under review as a conference paper at ICLR 2020
FH: Success rate 1%)
Mean Li-distance
Syntactic novelty rate 196
Semantic novelty rate (%)
leading power to
98.765432202 23466789
98745432101234500
48775443210123455777
leading power
leading power
leading power
leading power
FHNC: Success rate (%)
1-distance
Syntactic nevelty rate 1%)
Semantic nevelty rate (%)
leading power
448-7---5543----1 0260244577
441745433101234300 leading power 2 -
leading power 0
leading power 2 0
leading power 2-00
Figure E.2: Metrics for FH and FHNC models on each condition within PP < and [Pa-iin [5] 9. Each column corresponds metrie: success rate, mean L. L.1-distacce syntactic novelty rate and semantic novelty rate, respectively. Conditions with M[ʃ] S 4 are inside the red boundary. Conditions with zero success rate, syntactic novelty rate or semantic novelty rate are left blank in the corresponding plots.
is 0.5 (chosen based hyperparameter search, see Appendix D.. The limit of number of evaluations for a new offspring is set to 500 so that it is comparable to the number of simulations in MCTS.
H GRAMMAR VARIATIONAL. AUTOENCODER
We would like to point out that the dataset this paper is more challenging for GVAE than the dataset used in Grammar Variational Autoencoder (GVAR) paper (Kusner et al. 2017), although it is constructed with fewer production rules. First, the maximum length production rule sequences in GVAE paper is 15, while the maximum length is 31 in our training set and 43 in holdout set. The RNN decoder usually has difficulties in learning longer sequence due to e.g. exposure bias (Bengio maximum length is more than doubled, training set only contains 28837 expressions compared to 100000 in GVAE paper. Samples in our training set are sparser in the syntactic space than those of the GVAE paper.
al. 2015). Second, while
We trained a GVAE using the the open-sourced code with the following modifications: 1) using context-free grammar in our paper 2) setting the length to 100 it is comparable with MCTS and EA experiments in our paper. The GVAE paper reported reconstruction accuracy 0.537. On our validation set, the reconstruction accuracy is 0.1
During each iteration in Bayesian optimization, 500 data in the training set are randomly selected to model the posterior distribution and the model will suggest 50 new expressions. These 50 new expressions will be evaluated and concatenated into the training set. For each symbolic regression task, we ran iterations. The only difference from the setting in Kusner et al. (017)) that instead of averaging over 10 repetitions, we average over 2 repetitions so the total number of evaluation is 2 x 50- = 500 for searching each expression, which is comparable to the setting of MCTS and EA.
Due to the restriction on the computational time of Bayesian optimization for GVAE, we evaluate GVAE a subset of holdout sets. 30 expressions randomly selected from each of the holdout
15

---

Under review as a conference paper at ICLR 2020
LH (2): Success rate (%)
Mean Li-distance
Syntactic novelty rate (9%
Semantic novelty rate (%)
leading power
1000000
98.75443220
4877543210122444
48876543210123455
leading power
leading power
leading power
leading power
(4): Success rate (%)
L1-distance Baodena
Syntactic nevelty rate 1%)
Semantic nevelty rate (%)
leading power 30
44776543200134553
448------54----11
44--655-321133 0233222133336780 leading power 2 0
24174454-321112344333 leading power 2 0
leading power 0
leading power 0
LH (8): Success rate (%)
Mean L1 Li-distance
Syntactic nevelty rate 1%)
Semantic novelty rate (%)
leading power de
448-74-5---22-101 3445666
leading power 0
leading 2-0
leading power
leading =
Success rate (%)
L1-distance
Syntactic novelty rate (%6
Semantic novelty (3)
leading power
387755322011
9-8-765--2210 73466769 98.76.53222
323466789
leading power 0
leading power 2
leading power -
leading power 2+0
Figure E.3: Metrics for LH models with different history length on each condition within IP- < 9 and [P]- < 9. Each column corresponds to metrie: success rate, mean LI-distance, syntactic novelty rate and semantic novelty rate, respectively. Conditions with [ < 4 inside the red boundary. Conditions with zero success rate, syntactic novelty rate semantic novelty rate are left blank in the corresponding plots.
sets (M <= 4,= 6) in Section 5 and symbolic regression tasks are performed on these 120 expressions. We report the results of NG-MCTS, GVAE and GVAE+PW (including the error of leading powers to the score function in Bayesian optimization) evaluated on median extrapolation RMSE and absolute error of leading powers in Table H.1l GVAE + PW has better P comparing to GVAE. NG-MCTS significantly outperforms GVAE and GVAE + PW on solved percentage and extrapolation error Agext.
16

---

Under review as a conference paper at ICLR 2020
LHNC (2): Success rate
Mean Li-distance
Syntactic novelty rate 196)
Semantic novelty rate (%)
leading power
98.76543210222 03444330122447788
481865432101224558
leading power
leading
leading power
leading power
[4): Success (%)
1-distance
Syntactic nevelty rate (%)
Semantic novelty rate (%)
leading power
00000000
1000 6
48876543211133430
$4.-74----------1
248-7-65----23113 033433677334 leading power 2 -
94176554321112343000 leading power 2 -
leading power 0
leading power 0
LHNC (8): Success rate (%)
Mean L1-dit 1-distance
Syntactic nevelty rate 1%)
Semantic novelty rate (%)
leading power
00000000000 0000000
44--7-5--.33----- 1222--10333330 373467799
448-74:5-:322-101 2 3456734777 7
44--755--322111 173456788
leading
leading 2-0
leading
leading
(16):
L1-distance
Syntactic novelty rate (%)
Semantic novelty (%)
leading power
BOBOS
9.8.7-5-.333222 1 2 23456709 -98765533210 11143222012356770
leading power =+
leading power
leading power -
leading power 2-+0
Figure E.4: Metrics for LHNC models with different history length on each condition within IPa < 9 and [P]+ < 9. Each column corresponds to metrie: success rate, mean LI-distance, syntactic novelty rate and semantic novelty rate, respectively. Conditions with [ < inside the red boundary. Conditions with zero success rate, syntactic novelty rate semantic novelty rate are left blank the corresponding plots.
I CHOICE OF HYPERPARAMETERS
NN trained with batch size 256 for 107 steps. The initial learning rate is 0.001. It decays exponentially every 10s steps with base of 0.99.
The hyperparameters of MCTS (exploration strength = 50) and EA (the probability of mating two individuals 0.1, the probability of mutating individual 0.5) are selected by hyperparameter searching to maximize the solved percentage in holdout set M[] < 4 with both D Dirain and Px-so[f), Pr Pz-soo(] provided.
17

---

Under review as a conference paper at ICLR 2020
Table H.I: Comparison with GVAE on subset of holdout sets.
Method
Neural
Objective Function
Salved
Invalid
Unselved
Guided
Deram
Pa [
Pereent
Percent
Perecot
Aghrain
Aguer.
Agern.
NG-MCTS
83.33%
0.00%
16.67%
0.136
1.000
0.009
GVAE GVAE + PW
90.01%
0.217
0.159
0.599
V
10.00%
0.00%
90.00%
0.386
0.524
0.056
NG-MCTS
60.00%
0.00%
40.00%
0.088
0.086
0,011
V
0.233
GVAE PW
V
3.33%
0.00%
96.675
0.649
0.565
0.383
NG-MCTS
10.00%
0.00%
90.00%
0.306
0.266
0.009
GVAE
0.00%
0.00%
100.00%
0.260
0.206
0.037
GVAE PW
0.00%
0.00%
100.00%
0.595
0.436
0.087
J EXAMPLES SYMBOLIC REGRESSION RESULTS
In this section, we select expressions solved by NG-MCTS but unsolved by EA PW in Table examples symbolic regression results. Figure J.I FigureJ.2 and Tigure[.3 show eight expressions with M < 4, [ 5 and [ 6, respectively. The symbolic expressions, leading powers, interpolation errors and extrapolation errors of these 24 desired expressions f(x)), as well as their corresponding best expressions found by NG-MCTS, denoted by No NG-MTTS (x)), and by EA PW,
denoted by EA PW (I), are listed in Table J.1
We also select expressions solved by EA PW but unsolved by NG-MCTS in Table I as examples of symbolic regression results. Figure T.4, Figure J.5 and Figure J.6 show eight expressions with
M[f] - 4, Mff] 5 and M[f] 6, respectively. The symbolic expressions, leading powers, interpolation errors and extrapolation errors of these 24 desired expressions f(x), as well as their
corresponding best expressions found by NG-MCTS and EA PW are listed Table
Advi
Adha
Adh
Atle 0.16
Adai 0.12
Autos
0.32
0.03
0.49
0.06
68
0.08
-4
[a]
(b)
[c)
[d]
Adex
Aute 34.84
Attel 0.75
Agen
30.53,
100
50
[(2)
-50
-100
dostred
NG-MCTS
-150
(c]
(f)
(g)
[h]
-200
Figure J.1: Examples of expressions solved by NG-MCTS but unsolved by EA + PW with
M[fl < 4. Each subplot of (a)-(h) demonstrates expression solved by NG-MCTS but unsolved by EA + PW. Grey area is the region to compute interpolation error Agint. and light blue area is the region compute extrapolation error Agest.. The display range of y-axis is [-5, 5] for the four subplots in the first row and [-200, 200) for the four subplots in the second row to show the discrepancy of expressions on two different scales.
K SYMBOLIC REGRESSION WITH NOISE
In the main text, the training points Durain from the desired expression is noise-free. However, in realistic applications of symbolic regression, measurement noise usually exists. We add a random Gaussian noise with standard deviation 0.5 to expression evaluations Dursin and compute Agnat and Agext. using evaluations without noise. The results are summarized in Table K. The perfor- mance of all the methods is worse than that in the noise-free experiments, but the relative relationship
18

---

Under review as a conference paper at ICLR 2020
Adea 0.20
Adlus
Jyhn 0.03
Askus 0.01
Astal 0.10
Ada 0.54
Adia
Adiu
0.01
0.41
0.05
-2
[3]
(b)
[c]
[d]
26
3
3/h
A...
Adu. 0.20
Adt.: 30.51
Ag...
2.27
22.35
0.37
247.60 .9
12.20
340, 24
-100
destree IG-HICTS
-15
EA PW
(2)
(1)
-200
10.
10.0
10
10
Figure J.2: Examples of expressions solved by NG-MCTS but unsolved by EA + PW with
M = 5. Each subplot (a)-(h) demonstrates an expression solved by NG-MCTS but unsolved by EA + PW. Grey area is the region to compute interpolation error Agint and light blue area is the region to compute extrapolation error gext.. The display range of y-axis is [-5, 5] for the four subplots in the first and [-200, 200] for the four subplots in the second row show the discrepancy of expressions on two different scales.
Adea
Agua
J/h
Agu. 0.00
Adai 0.08
Adai 0.00
Adea
Ag..
2.67
0.00
0.03
0.01
0.00
-2
[a)
(b)
tct
200
150
0.65
262.11
2.01
Jutu
AA....
359.71
1.19
2145,62
Asu.
Artu 2.02
46,65
Aut...
-100
desired
IGG-CCTS
-150
E4 PV
(g)
2200
Figure J.3: Examples of expressions solved by NG-MCTS but unsolved by EA PW with
M[ = 6. Each subplot (a)-(h) demonstrates an expression solved by NG-MCTS but unsolved by EA PW. Grey area is the region compute interpolation error Agint. and light blue is the region to compute extrapolation еrror Agext.. The display range of y-axis is [-5, 5] for the four subplots in the first row and [-200, 200] for the four subplots in the second row show the discrepancy of expressions on two different scales.
still remains. NG-MCTS solves the most expressions than all the other methods. It has the lowest medians of Agext. and AP[g), suggesting good generalization in extrapolation even with noise on training points.
L SYNTACTIC NOVELTY EXAMPLES
For ease of presentation, we show syntactic novelties generated by NN that only have one semantically identical expression (i.e., the expression that shares the same simplified expression) in the training set. By comparing each syntactic novelty and its semantically identical expression the training set (shown in T.bleeL..))
observe that the model generates nontrivial syntactic novelties. For
19

---

Under review as a conference paper at ICLR 2020
Table J.1: Examples of expressions solved by NG-MCTS but unsolved by EA + PW. This table shows the desired expressions f(x) and their corresponding best expressions found by NG-MCTS g (GGMMTT5x)) (z) and by EA + PW g @ (z). The leading powers Pz-ol-), P2-+0 [. interpolation enror Affit. and extrapolation error Aext. are reported for each expression.
540
800
500
500
403
590
3059
500
0:0 810
590
1917
116
New
0.50
4:01
0.0
9.0
0.0
020
033
9:21
0.50
4403
9
3.91
4.23
035
9
0100
2
119
3
-1 100
the www.iiiiimmmmm.mmmm..... mon min te wite Deit 21 mith www.o0t-- 2loNhen D1 200000
1000 ntt Ouiree -1 200U to- Stealeetonn Te -1- II0 200 Ditatt 100 201
wwollttee 10000 So 400 5-200 (1 <if 11- wwweeetl)-))))
(1 2 H100O Iit DD alti wotteeteeeeiiie -a00 221 Ztaan
aiteetale moneeee ai deed Mirl (0000))
0005 10 -2---- Coltt 2iteeii 1n 2) 211 apghoo (e zinn (rOo
ii------------ 3ij can -it 000 SHUCE tee II Nell Imn
1t000ll--0000000000 40000 e-ll----0 200 11:30 De 1100
-1- 201 - 1II mi 220 aa e)) - zill to -1 www. (e milei
1 dee 1eat zin the www. nI a twvil
di0 -tt 6--0 d- dix wa) O 00000 -1 0l0
01- (1-44-1000 Mili 8- Ro0 Dr 40 HMC De 20 40
1000 thl milliee Di zite tie tie Djttleeee 01
ot 1--- b::00 MESOLUE
Wi (aliii 1 2e 1t State 1700
(1ithe 1e-3----- 000 m
650 RMMM -04 Will
031 2000 22100000
de-
11-10-00---0
(02 rdl 200000 te)
Wo AM AL Urer
rage 13 D030
-
(111 O0 01 2000
1000le
(MA -i 1880
Mell
0.12- ---1---------- 1-11--1----11-- 1--1--1--11-111---
(00 BOAIN
M1H 20
0-20-47-
y (1 COAA
ae sestti 01-2
(engjes
at ariii
ya mgl
mi
ye fin
wolle
N
13
humans to propose such syntactic novelties, they would need know and apply the corresponding nontrivial mathematical rules (shown in the first column of Table to derive the expressions from those already known in the training set. On the contrary, NN generates the syntactic novelties such as
20

---

Under review as a conference paper at ICLR 2020
Adea 0.03
Aylu
Juhn 0.09
Ad 0.60
Adia
Adia
0.05
0.11
0.09
0.50
0.95
-2
[3]
(b)
[cl
1d]
Adu
3/hu
Ad..
Ad...
Ad..
3....
5.55
3.90
0.45
5.20
0.93
40.74
0.93
34.72
EA
-100
115
(f)
-200
10.0
10.0
10
10
Figure J.4: Examples of expressions solved by EA PW but unsolved by NG-MCTS with M < 4. Each subplot of (a)-(h) demonstrates an expression solved by EA + PW but unsolved by NG-MCTS. Grey area the region to compute interpolation error Agntt and light blue area the region to compute extrapolation error Aexxt.. The display range y-axis is -5, 5] for the four subplots in the first and [-200, 200] for the four subplots in the second row show the discrepancy of expressions on two different scales.
Sdva
Jdwa
3dh 0.20
Adve
Adui 0.07
Sdvs
0.00
0.05
-2
-4
[a]
(b)
(c)
[d]
Adea
Arles
Juh
2.19
333.27
4.10
14.28
2.63
39.65
4.05
379.43
f(a)
NG-METS
cestred
-50
-100
-10
[e]
(f)
(g)
[h]
-200
10.00
10.00
30
10
Figure J.5: Examples of expressions solved by EA PW but unsolved by NG-MCTS with M[ = Each subplot of (a)-(h) demonstrates an expression solved by EA + PW but unsolved by NG-MCTS. Grey area is the region to compute interpolation error Agnat and light blue area the region to compute extrapolation error Agext. The display range y-axis is [-5, 5, for the four subplots in the first row and [-200, 200] for the four subplots in the second row to show the discrepancy of expressions on two different scales.
1/(A/B) B/A, BB C) A/B/C, etc, without being explicitly taught these mathematical rules.
21

---

Under review as a conference paper at ICLR 2020
Agu.. 0.00
4gw 5.20
Adwi
Án... 0.13
Agu.
0.01
0,42
0.18
0.01
0.00
-4
[a]
(b)
(c)
(d)
3daa
Adh.
3daa
Adua
4.57
1,20.90
2419.77
50
-50
-100
desired
-150
(e)
(f)
(g)
[h]
-200
10
10
Figure J.6: Examples of expressions solved by EA + PW but unsolved by NG-MCTS with M[S] = Each subplot of (a)-(h) demonstrates expression solved by EA PW but unsolved by NG-MCTS. Grey area the region to compute interpolation error Agint and light blue area the region to compute extrapolation error Agext. The display range y-axis is [-5, for the four subplots in the first row and [-200, 200] for the four subplots in the second row to show the discrepancy of expressions on two different scales.
22

---

Under review as a conference paper at ICLR 2020
Table J.2: Examples of expressions solved by EA + PW but unsolved by NG-MCTS. This table shows the desired expressions f(x) and their corresponding best expressions found by NG-MCTS g NNG-MCTS(>> (x)) and by EA + PW y BBA+PW (z). The leading powers P=- P2- [.) interpolation error Aint. and extrapolation error Agext. are reported for each expression.
Maa
1.80
330
5164
4634
13539
14.00
130 6R0
00.00
305777
100
Aga
5100
5.04
6100
6.94
600
6:00
1000
0.25
5,00
219
5.00
4000
5.00
4001
6-1
6/00
6000
2:82
8.00
Chec to Wi1- -------- Wiill ai- 2n2iile (D E- 2ilt la 28 20 a (3 2- (09 www.i (at0l
Bieg) (te 2000
ti Se 1000 Dxttt 221 elde (it-) m000
www. t cehiilr in Mee0 all 00 I 300 1e00
tte it Soeel Iife 0it TI ai0
20z00ont m00 -220 120001 221- m
Oit -i-------------- 101-1 (t diiiee de to Se il X00 de te 0--0- 100
Dillil 11 0- 100 1II-- ted0) tiee qUile 1302 (20 000
Onbile 1. 10- O2n) mn di 2ol 1 (ww.ei0000
2
<0-0W000 5) (it--llttt (ite 2040
d- 40
8. on (it 10 de- 2000
100 11-100 4 We t1 tl tt 1801 10 d tegg
nye oiten ai -e 1000
So 10 10 10 ei0em
COOANNN 2i 40 txx
X--4
Dove Seaa-- 2009 +-11
200 22 20-2 0022
2000-
4
6- 10 211l
Dr f1
6--3- -2)
(39 salle aer
(20 Hoteelll
(35446
23
101
-10
Hel
10 2
23

---

Under review as a conference paper at ICLR 2020
Table K.1: Results of symbolic regression methods with noise. Search expressions in holdout sets M[ < 4, M = and M with data points on Dtrain and or leading powers P and Pr- []]. The options are marked by on (v), off (x) and not available (-). If the RMSEs of the best found expression g(x) in interpolation and extrapolation are both smaller than 10-9 and A O, it is solved. If ((x) is non-terminal
it is invalid. Hard includes expressions in the holdout set which are not solved by any of the six methods. The medians of Atrain Aiint. Dext.
and the median absolute errors of leading powers A for hard expressions reported.
M[A]
Method
Neural
Objective Function
Solved
Invalid
Hard
Guided
Dirain
Pe-10,ou
Porcent
Percent
Porcent
Agtraia
Apja
Agus.
AP(a]
MCTS (PW-ynly)
0.34%
0.00%
1.003
0.865
44 MCTS | PW
NG-MCTS
24.29%
0.34%
0.05%
0.49%
71 41%%
0.432
0.887
0.449
0.643
0.256
0,825
0.399
EA PW
4.34%
0.39%
0.385
0.489
0.260
MCTS
0.00%
4,00%
0,931
0,399
0,972
IPW-only) MCTS + PW NG-MCTS
5
10,80%
0.00%
0.10%
3.00%
83 40%
0.558
0.911
0.430
0.817
0.103
0.727
0
EA
1.00%
3.10%
0.480
0.256
0.266
1.80%
MCTS
0.00%
9.75%
0,960
0.762
0.588
6
MCTS (PW-nnly)
0.00%
0.00%
1.024
0.861
NG-MCTS
10.33%
0.08%
0.126
0.205
0.009
EA EA PW
0.67%
4,58%
0.463
0.427
0.652
1.42%
6.50%
0,388
0.369
0.065
Table L.1: Examples of syntactic novelties to demonstrate what the NN model learned. Sem- identical expression refers the expression in the training that shares the same simplified expression as the corresponding syntactic novelty. The first column shows the mathematical rules human needs to know and apply derive each syntactic novelty from its semantically identical expression in the training set.
SYNTACTIC NOVELTY
MATHEMATICAL RULE
SEM-IDENTICAL EXPRESSION
1+1/01+ (x/(1(()/(+a)))) (1++))/(1+
1/(A/B) B/A
1-#/(1+2)+1+o)) 1-(0/1+0)/(+1)
A/(B B) A/B/2
A+B - B+B
</(=((/((+))+
(1 00-c</1=2))//00o
A/(B + C) A/B/C
(1 (=(4/(-=))//o+))
(2+))
A/C+ B/C - (A B)/C
((1 (1+=)/)/(=11--0x))
24


Reviews:
[{"review_id": "rkxD5oj2YH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a task of symbolic regression (SR) when additional information called 'asymptotic constraints' on the target expression is given. For example, when the groundtruth expression is 3 x^2 + 5 x, it behaves like x^2 in the limit x -> infinity, thus the power '2' is given as additional information 'asymptotic constraint'. In the paper's setting, for SR with univariate groundtruth functions f(x), 'asymptotic constraints' for x-> infinity and x -> 0 are given. For this situation, the paper proposes a method called NG-MCTS with an RNN-based generator and MCTS guided by it to consider asymptotic constraints. In SR, a learner is asked to acquire an explicit symbolic expression \\hat{f}(x) from a given set of datapoints {x_i, f(x_i)}, but unlike the parameter optimization aspect of a standard supervised ML setting, the problem is essentially combinatorial optimization over exponentially large space of symbolic expressions of a given context-free grammar (CFG). For a given symbolic space with a prespecified CFG, extensive experimental evaluations are performed and demonstrated significant performance gain over existing alternatives based on EA. Also, quantitative evaluations about extrapolative performance and detailed evaluation of the RNN generator are also reported.\n\nThough it includes a lot of quite interesting methods and results, the paper has two major issues: \n\n(1) the proposed method NG-MCTS explicitly uses the fact that the target expressions are generated from a CFG, but this assumption sounds unnatural if the target problem is SR (unlike the case of GVAE). Apparently, all results except a toy case study in 5.2 depend on artificial datasets from a CFG, and any practical advantages or impacts are still unclear because the experimental settings are very artificial. \n\n(2) the most important claim of this paper would be the proposal to use 'asymptotic constraints', but the availability of this information sounds too strong and again artificial in practical situations. A one-line motivation saying that 'this property is known a priori for some physical systems before the detailed law is derived' is not convincing enough.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SyeeGb2gcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper introduces the use of asymptotic constraints to find\nprune the search space of mathematical expressions for symbolic\nregression.  This is done by training a neural network to\ngenerate production rules conditioned on being given the\nasymptotic constraints and previously generated production\nrules. This neural network is then itself also used to guide a\nMCTS to generate mathematical expressions.\n\nThe algorithms is compared against a reasonable set of baselines\nand related algorithms.\n\nFeedback:\n\nThis is a very clear and well-written paper. It was\nstraightforward to understand and very easy to see how it fits in\nwith the broader literature. The insight about using asymptotic\nconstraints makes the result a bit limited to only generating\nmathematical expressions, and it would have been a bit nicer if\nthere was something more generically applicable to program\nsynthesis in general. It's not really clear to me how the\nexisting work extends to programs.\n\nThe evaluation was very thorough and the appropriate algorithms\nwere compared against the work. I came away with a good\nunderstanding of how well the model generalizes to larger\nexpressions compared to existing work.\n\nMinor notes:\n\nThe abstract is a bit inaccurate as the NN generates production rules\nand not expressions.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HklhRjcJcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors of this paper propose a novel approach for symbolic regression. The simulation results demonstrate that the proposed approach can find a better function g producing similar results as desired function f by providing the additional information – the leading power of function f.\n\nPaper strength:\n1.\tThe proposed NG-MCTS is elegant to solve the problem of symbolic regression.\n2.\tExperiment results illustrate the superiority of the proposed approach\n\nPaper weakness:\n\n1.\tI can follow most of the mathematics in the paper. But the most confusing part for me is why you feed the random partial sequence for training. Besides, how you do inference to generate a sequence of the production rules.\n2.\tWhat is the final objective function? If I do not misunderstand, it could be the cross-entropy loss between the output of GRU and the next target production rule, RMSE and the error on leading power. Then how you optimize it? Please describe more details about this.\n3.\tThe authors of this paper introduce more information – leading power of desired function for symbolic regression but they incorporate the additional information by introducing a simple loss function term. How about the performance of baseline approaches with those kinds of information?\n4.\tThe whole systems seem like very complicate and it would be more interesting if the authors provide sufficient ablations to decompose the complex algorithm.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes 1) using neural-guided Monte-Carlo Tree Search to search for expressions that match a dataset and 2) Augments the loss to match the asymptotics of the true function when these are given.

The use of MCTS sounds more sensible than standard evolutionary search.  The augmented loss could make sense but seems extremely niche, requiring specific side information about the problem being solved.

Overall, the task is so niche that I don't think it'll be of wide interest.  It's not clear that it's solving a real problem.
Decision: Reject