Deep Symbolic Superoptimization Without Human Knowledge
Authors: Hui Shi
Yang Zhang
Xinyun Chen
Yuandong Tian
Jishen Zhao
Venue:  (2020)

Abstract: Deep  symbolic superoptimization refers to the task of applying deep learning methods to simplify symbolic expressions.   Existing approaches either perform supervised training on human-constructed datasets that defines equivalent expression pairs, or apply reinforcement learning with human-defined equivalent trans-formation actions.  In short,  almost all existing methods rely on human knowledge to define equivalence, which suffers from large labeling cost and learning bias, because it is almost impossible to define and comprehensive equivalent set. We thus propose HISS, a reinforcement learning framework for symbolic super-optimization that keeps human outside the loop.  HISS introduces a tree-LSTM encoder-decoder network with attention to ensure tractable learning.   Our experiments show that HISS can discover more simplification rules than existing human-dependent methods, and can learn meaningful embeddings for symbolic expressions, which are indicative of equivalence.

Published as a conference paper at ICLR 2020
DEEP SYMBOLIC SUPEROPTIMIZATIOON WITHOUT HUMAN KNOWLEDGE
Hui Shi'; Yang Zhang?: Xinyun Chen
Yuandong Tian', Jishen Zhao'
UC San Diego', MIT-IBM Watson AI Lab?. UC Berkeley", Facebook AI Research {hshi, johao) @ ucsd.edu. yang.zhang2 @ ibm..cm, xinyun.chenen berkeley.edu. yuandong fbccom
ABSTRACT
Deep symbolic superoptimization refers to the task of applying deep learning methods simplify symbolic expressions. Existing approaches either perform supervised training on sion pairs, or apply reinforcement learning with human-defined equivalent trans- formation actions. In short, almost all existing methods rely on human knowl- edge define equivalence, which suffers from large labeling cost and learning bias. We thus propose HISS, reinforcement learning framework for symbolic superoptimization that keeps humans outside the loop. HISS introduces a tree- LSTM encoder-decoder network with attention ensure tractable learning. Our experiments show that HIss can discover more simplification rules than existing human-dependent methods, and can learn meaningful embeddings for symbolic expressions, which are indicative of equivalence
datasets that define equivalent expres-
INTRODUCTION
Superoptimization refers to the task of simplifying and optimizing over set of machine instruc- tions, or code (Massalin 1987 Schkufza et al., (203)), which a fundamental problem in computer science. As important direction in superoptimization, symbolic expression simplification, or symbolic superoptimization, aims at transforming symbolic expression to a simpler form in an ef- fective way, so as avoid unnecessary computations. Symbolic superoptimization is an important component in compilers, e.c. LLVM and Halide, and it also has a wide application in mathematical engines including Wolfram Matlab, and Sympy.
Over recent years, applying deep learning methods to address symbolic superoptimization has at- tracted great attention. Despite their variety, existing algorithms can be roughly divided into two categories. The first category is supervised learning, i.e. to learn mapping between the input expressions and the output simplified expressions from large number of human-constructed ex- pression pairs (Arabshahi al. 2018 Zaremba & Sutskever 2014). Such methods rely heavily on a numaanconstructed dataset, which is time- and labor-consuming, What worse, such systems are highly susceptible to bias, because it is generally very hard to define minimum and comprehensive axiom set for training. It is highly possible that some forms of equivalence are not covered in the training set, and fail to be recognized by the model. In order to remove the dependence on human annotations, the second category of methods leverages reinforcement learning to autonomously dis- cover simplifying equivalence (Chen et al., 2018). However, make the action space tractable, such systems still rely on a set of equivalent transformation actions defined by human beings, which again suffers from the labeling cost and learning bias.
In short, the existing neural symbolic superoptimization algorithms all require human input to define equivalences. would have benefited from improved efficiency and better simplification if there were algorithms independent of human knowledge. In fact, symbolic superoptimization should have been a task that naturally keeps human outside the loop, because directly operates on machine code, whose consumers and evaluators are machines, not humans.
"Authors contributed equally to this paper.
I 'The code is available at https: tttbb wtt.tttww..ooooeoeeoooooooottttt shi hui 2010 /// sttp//ymmllll/////////// ic_si ic_simpp mmpp1 fier https: wwwp//wwwwaao/ wol framal pha.pcc..o....oo.

---

Published as a conference paper at ICLR 2020
Therefore, we propose Human- Independent Symbolic Superoptimization (HISS), reinforcement learning framework for symbolic superoptimization that completely independent of human knowl- edge. Instead of using deffnnd equivalence, HISs adopts a set of unsupervised techniques to maintain the tractability of action space. First, HISS introduces a tree-I.ST'M encoder-decoder ar- chitecture with attention ensure that its exploration is confined within the set syntactically correct expressions. Second, the process of generating a simplified expression is broken into two stages. The first stage selects sub-expression that can be simplified and the second stage simplifies the sub-expression. We performed a set of evaluations on artificially generated expressions as well as a publicly available code dataset, called the Halide dataset (Chen & Tian (018), and show that HISS can achieve competitive performance. We also find out that HISS can automatically discover simplification rules that are not included the human predefined rules the Halide dataset.
RELATED WORK
Superoptimization origins from 1987 with the first design of Massalin (1987). With the probabilistic testing to reduce the testing cost, the brute force searching is aided with pruning strategy to avoid searching sub-spaces that contains pieces of code that have known shorter alternatives. Due to the explosive searching space for exhaustive searching, the capability of the first superoptimizer limited to only very short programs. More than a decades later, Joshi et al. (2002) presented Denali, which splits the superoptimization problem into two phases to expand the capability to optimize longer programs. STOKE (Schkufza et al. 2013) follows the two phases but sacrifices the completeness for efficiency in the second phase.
Recent attempts to improve superoptimization are categorized into two fields: exploring transforma- tion rules and accelcrating trajectory searching. Searching the rules are similar to the problem of su- peroptimization on limited size program, but targeting more on the comprehensiveness of the rules. Buchwald (2015) exhaustively enumerates all possible expressions given the syntax and checks the cquivalence of pairs of expressions by SMT solver. A similar method with an adaption of the SMT solver reuse the previous result is proposed by Jangda & Yorsh| (2017). On the other hand, deep neural networks are trained to guide the trajectory searching (Cai et al. 2018 Chen & Tian 2018).
Considering transformation rule discovery a limited space superoptimization, the large action space and sparse reward are the main challenges for using neural networks. Special neural generator structures are proposed for decoding valid symbolic programs, which leverage the syntax constraints to reduce the searching space as well as learn the reasoning of operations, and are gaining popularity in program synthesis (Parisotto et al.) |016 Zhong al., 2017 Bunel et al., (018), program trans- lation (Chen et al.] 2018 Drissi et al. 2018), and other code generation tasks (Ling et al.) 2016]] Alvarez-Melis & Jaakkola, 2016). Among the symbolic expression decoders, the family of tree structure RNNs (Parisotto et al. [016 Drissi et al., 2018] Aivarez-Melis & Jaakkola, 2016 Chen ct al. 2018) are more flexible than template-bar predictors (Ling et al. 2016 Zhong ct al. 2017).
3
THE HISS ARCHITECTURE
In this section, we will detail our proposed Hiss architecture. We will first introduce a few notations. T denotes tree; a denotes vector, and A denotes matrix. We introduce an LSTM(.) function that summarizes standard one-step LSTM operation as
[h,, c.] = LLS,M(E,,h
(1)
where he, e₁ and denote the output, cell and input at time t of a standard LSTM respectively.
3.1 FRAMEWORK OVERVIEW
Our problem can be formulated as follows. Given a symbolic expression T,, represented in the expression tree form, our goal is to find simplified expression To, such that 1) the two expressions are equivalent, and 2) To contains a smaller number of nodes than T7.
It is important write the symbolic expressions in their expression tree form, rather than strings be- cause HIss will be operating on tree structures. An expression tree assigns a node for each operation or variable. Each non-terminal node represents an operation, and each terminal node, leaf node,
2

---

Published as a conference paper at ICLR 2020
Prob. of choosing sub-tree
Softmax
LP
Alt
Softmax
Linear Protection (oonsan)))
Altentio Nodule (Bq (6))
Sigmoid
LP
Ousput
Precteus Dutputt
LSTM
N
Alt
Mi-out
Input
50 Gall
LSTM
LSTM
Ax
x
62
The encoder (green) and subtree selector (orange).
(b) The tree decoder.
Figure 1:
The HIss architecture, illustrated on a three-node binary subtree, where is the parent of k, and p is the parent of i.
represents a variable or constant. The arguments of operation are represented as the descendant subtrees of the corresponding node. Compared string representation, tree representation natu- rally ensures any randomly generated expression in its form is syntactically correct. It also makes working with subexpressions easier: simply by working with subtrees.
HISS approaches the problem using the reinforcement learning framework, where the action of generating simplified expressions are divided into two consecutive actions. The first action is to pick subexpression (or subtree) that can be simplified, and the second action generates the simplified expression for the selected subexpression.
Accordingly, HISS contains three modules. The first module is tree encoder, which computes an embedding for each subtree (including the entire tree) of the input expression. The embeddings are useful for picking subtree for simplification well as simplifying subtree. The second module is a subtree selector, which selects a subtree for simplification. The third module is tree decoder with attention mechanism, which generates simplified expression based the input subtree embedding. The subsequent subsections will introduce each module respectively.
3.2 THE TREE ENCODER
The tree encoder generates embedding for every subtree of the input expression. We apply the N-ary Tree LSTM as proposed in Tai et al. (2015), where N represents the maximum number of arguments that an operation has. It important to note that although different operations have different number of arguments, for structural uniformity, we assume that all operations have N arguments, with the excessive arguments being a NULL symbol.
The tree encoder consists of two layers. The first layer is called the embedding layer, which is fully- connected layer that converts the one-hot representation of each input symbol to an embedding. The second layer is the tree LSTM layer, which is almost the same the regular LSTM, except that the cell information now flows from the children nodes to their parent node. Formally, denote c, h; and æ; the cell, output and input of node i respectively. Then the tree LSTM encoder performs the following information
hh, c.j = LSTM
Zi:
U SER(E)
hj
Cj
JED(S)
where ID()) denotes the of children of node i. Fig. encoder (in green). Since each node fuses the information from its children, which again fuse the information from their own children, easy to see that the output h, summarizes the information of the entire subtree led by node i, and thus can be regarded an embedding for this subtree.
plots the architecture of the tree LSTM
3.3 THE SUBTREE SELECTOR
The subtree selector performs the first action to select a subtree for simplification. takes the output of the tree encoder, (h:). its input, and produces the probability with which each subtree is
3

---

Published as a conference paper at ICLR 2020
selected. It consists of two feed-forward layers followed by softmax layer across all the nodes in the input tree. Figure Ta) shows the architecture of the subtree selector (in orange).
3.4 THE TREE DECODER
Once a subtree has been selected, and suppose the root node of the selected subtree is node the output of the encoder at node i, h;, is then fed into the tree decoder, which generates a simplified version of the subtree. The tree decoder can be regarded the inverse process of the tree encoder: the latter fuses information from the children to the parents, whereas the former unrolls the infor- mation from parents down to the entire -aary tree. When the parent node outputs a non-operation symbol, the expansion of this branch terminates and no child is further decoded.
The tree decoder adopts a novel LSTM architecture with attention, which, compared with the at- tention LSTM proposed by Chen et al. (2018), is more parameter- and computationally-effoe. consists of two layers. The first layer is tree LSTM layer, and the second layer is the symbol generation layer with attention. Figure[[] (b) illustrates the decoder structure. The decoder shares the same vocabulary with the encoder, and the embedding layer of the decoder shares the parameters with the embedding layer in the encoder.
Tree LSTM Layer. The tree LSTM in the decoder needs to accomplish two tasks. First, it needs to extract the information for generating the output for the current node. Second, it needs to split and pass on the information to its children. To better control the information flow, we introduce two tracks of LSTMs for the two different tasks. Formally, denote [h,, cj as the output and cell of node i, and assume [J,, .JN] are children nodes of i. Also denote yp as the decoder output for node p. which is the parent node of node i (If node is already the root node of the selected subtree, then yp becomes a special start token). Then the first LSTM track extracts the information that generates the current output:
[hi cou LSTMour hí, cf).
(3)
The second LSTM track splits and passes on the information to the children, i.e. Vn E (1, .
[hi d- LSTMM hi, ci).
(4)
Notice that we have appended subscript to the LSTM(-) to emphasize that LSTM functions with different subscripts do not share parameters. Finally, the LSTM information for specific children is derived by linearly projecting the output track and that specific children track:
h' Whihhoouut h( bb, c¹. = WW c(+ja.1 b
(5)
We find that this linear projection is useful for adding additional dependencies between the parent output and the descendants, so that the generated expression is more coherent.
Symbol Generation Layer with Attention. The symbol generation layer takes the output track produced by the previous tree LSTM layer, hi as input, and outputs the probability distribu- tion of generating different output symbols for the current node. It adopts an attention mechanism (Bahdanau al., 2014) to attend to the relevant part in the encoder, so that the input and output expressions have better correspondence. Formally, when generating the output for decoder node i, the attention weight on encoder node is computed from ho and h2 as follows:
e(()) 8" tanh Wahl W.h, + b.), [o.( (J)] softmax((es(1))........ ..())))))...).......
(6)
where J is the total number of input nodes at the encoder. Finally, the probability of symbol gen- eration at node i, denoted as pt. is computed by passing into a linear projection layer h and an attention context vector C, which is a linear combination of the encoder embeddings with the attention weights, i.e.
P W. Wo cil bo. where e; = Σ ai))))
j=1
4 LEARNING WITH HISS
In this section, we will elaborate on the training and inference schemes of HIss. In particular, we will introduce several mechanisms to improve the exploration efficiency of HIss.
4

---

Published as a conference paper at ICLR 2020
4.1 TRAINING
We apply the standard REINFORCE framework function is given by
(Williams 1992) for training, where the reward
R( To) iT = To.
-By -By (o) otherwise,
(8)
where '=' denotes that the two expressions equivalent; card(.) denotes the number of nodes in the tree expression, or the length of the expression. not producing equivalent expression. This reward prioritizes equivalence, and given equivalence, favors shorter expressions. We applied a probabilistic testing scheme to determine equivalence as proposed in Massalin (1877). For each input, multiple outputs decoded via beam search, on each of which reward is evaluated. We introduce the following mechanisms to maintain the efficiency and stability of training.
a hyperparameter that depicts the penalty of
Curriculum Learning, Since generating the simplified expression is divided into two actions, sub- tree selection and subtree simplification, directly learning both can lead to very inefficient explo- ration. Instead, we introduce two-stage curriculum. The first stage trains only the encoder and decoder on very short expressions (maximum depth less than four). The subtree selector is not trained. Instead, we always feed the entire tree to the decoder for simplification. The second stage trains all the modules on longer expressions.
Subtree Embedding Similarity. In order to guide the encoder to learning meaning embeddings, we introduce an additional & loss to enforce that the equivalent expressions have similar encoder em- beddings, i.e. similar h&s Specifically, for each input expressions Tr. we decode set of generated expressions = {To} with beam search, and obtain their embeddings {h(To)) by feeding them back into the encoder (here add argument h emphasize that the embedding function of input expression). Then the lg loss expressed as follows
Σ [Ib(To) h (-1)>[//7To), (-n)) TOES
(9)
where [|-] denotes the indicator function, which equals one the statement its argument true, and zero otherwise. Note that this & applies to the encoder only, and can be optimized by regular gradient descent methods. REINFORCE, is not needed.
4.2 INFERENCE
Similar training, the inference performed by decoding multiple outputs via beam search and finding the best result as the final output. In order to accelerate the inference process, we introduce an offline procedure. During the first stage of the curriculum training. i.e. training on very short expressions, all the simplified equivalence rules discovered are logged. During inference, if the subtree to be fed into the decoder has an exact match the log, we will apply the logged simplified equivalence directly, rather than redoing the entire decoding process.
5 EXPERIMENTS
We performed two experiments. The first experiment compares HISS with human-independdent naive search algorithms. The second experiment compares HISS with existing human-dependent state-of-the-art systems on benchmark datasets. Throughout all the experiments, we use the same hyperparameter setting. Additional details on the hyperparameters and how the hyperparameters are determined can be found in appendix AA.3] Besides the experiments discussed in this section, some additional experiment results are reported in appendix B and set of ablation studies are introduced in appendix
5.1 COMPARING WITH HUMAN-INDEPENDENT METHODS
Since there are no existing human-inden indeeendddeen methods specifically for symbolic superoptimiza- tion. compare several search algorithms. Due to the search complexity, the evaluation camnot be performed on very long expressions. Therefore, this experiment is performed on the traverse equivalence dataset.
5

---

Published as conference paper at ICLR 2020
Expression Len gth Reduction
2.5
1.0
Hit Rate
0.8
0.25
0.20
0.15
MCTS KCMC
0.5
MCMC
0.2
HI5S
HISS
0.00
15 Sampling param
15
20
10
20
Sampling param
Sampling param
Figure 2: Comparison with human- iimmanniddeeeneent methods in terms of hit rate (left), expression length reduction (middle), tree size reduction (right), on Traverse Equivalence dataset.
Traverse Equivalence Dataset As complement the Halide dataset, build a dataset by travers- ing all the possible expressions with maximum depth four that consist of operations and symbols drawn from the Halide vocabulary method (Jia et al., 2019) to test if they can be simplified, and discard those that cannot. From the remaining expressions, we sample 900 expressions as the training set, 300 as the validation set and 300 the test set. The advantage of this dataset is that it is not built from Ience relation. However, the disadvantage of this dataset is that it does not contain expressions with maximum depth greater than four, limited by the complexity of the FingerPrint method. Additional details of our Traverse Equivalence dataset can be found in appendix A.
table 3 Among these expressions, we use the FingerPrint
equiva-
Training Since HISS does not operate very long expressions, it is only trained with stage-one in curriculum learning (the one with no subtree selection). Additional details regarding training can be found in appendix A.4
Baselines Two baseline searching methods are compared: Monte Carlo Tree Search (MCTS) (Bert- sekas (995) and Markov Chain Monte Carlo (MCMC) (Schkufza et 2013). MCTS decides the expression tree from root to leaves, choosing one symbol from Halide vocabulary for each node, and adopts Upper Confidence Bound (Kocsis Szepesvári 2006) for balancing exploration and exploitation. Similar to Schkuuza et al. (2013), MCMC takes one of four transformations: 1) replace an operator by another random operator, and generate discard operands if two operator takes different number of operands. 2) replace a variable/constant with another random variable/constant. 3) replace subexpression with a random single variable/constant. 4) replace variable/constant with random expression. The probability distribution of taking the transformation is defined the same as Schkufza al. (2013).
Three metrics are introduced: 1) hit rate, defined percentage of expressions that the model successfully found an equivalence given the computation budget parameter; 2) expression length reduction, defined as reduction in the total number of tokens; and 3) tree size reduction, defined as reduction the number of nodes in the expression tree.
Metrics.
The performance comparison of three models is shown in figure The sampling parameter in the horizontal axis refers to the beam size for HISS, the max trials budget for MCTS for each token decoded, and the sampling budget for MCMC. These quantities equivalently define the number of
Results.
Expression Length Reduction
Z3
39.9
Z3
11.4
Halide 36.1
Halide HISS
Tree Size Reduction
7.4
22
20.
17.7
to.
Figure 3: Comparison with human-dependent methods in terms of expression length reduction (left), and tree size reduction (right), on the Halide dataset.

---

Published as a conference paper at ICLR 2020
Table I: Example simplification rules learned by HISs (left) and their corresponding rules listed in Halide (right). If the learned rule has no corresponding preset rule Halide, the row is left blank.
HiSs
Halide
Input
Output
Input
Output
(c0+v0) -(V0+c0) (c0/v0)*v0 c0-c0
c0
(y*x)/x
0
X-x
0
c0 S c0 c0== min(c0, v0) - v0
true
x<x
falsse
true
x ==x
true
true
x < min(x, y)
false
min(c0 + v0, cl) vc) min(cO, (m)) +c
true
true
vc0+vO)-cl
vO
(x + y) - max(x, x)
y
max(c0, c0)
c0
X
min(cO, v0+ cl) < (cl v0)
true
c0 S max(vO, c0)
true 1 true
max(y, x) <x x/x
false
c0/c0
1
min(c0 vO, cl) S (c0 v0) c0 + +v0 (v0-vll) c0)
v0
xy y
min(min(cO, v0). cl - c2) < vo
true
min(min(cO, v0). vl) S v0
search attempts per token. As can be seen, HISS is significantly more powerful in finding the simpler equivalent than MCTS and MCMC. MCMC performs almost equally well as HISS in terms of Hit Rate, and both of them far outperform MCTS. However, both MCTS and HISs adopt top-down decoding in the huge decoding space, while MCMC starts with the imput expression and applies local transformations, which makes it much easier to find an equivalence. Also, MCMC achieves much worse average length reduction and average tree size reduction than Hiss.
5.2 COMPARING WITH
METHODS
In this section, we compare HIss with existing human-dependent state-of-the-art methods on the Halide dataset.
Halide Dataset The Halide dataset (Chen & Tian 2018) is the benchmark dataset for symbolic expression simplification. It consists of equivalent expression pairs constructed from human pre- defined rules. Since HISS is an unsupervised method, we only use the longer expression from each pair for training. Additional details of the Halide dataset can be found in appendix A.2
Training & Inference In this experiment, HISS is trained with both stages of curriculum learning- The first stage is trained on the moderately short expressions from the Traverse Equivalence dataset, whose configuration follows that in section 5.1 The second stage is trained on the Halide training set in an unsupervised manner. More details can be found in appendix A.4
Since HISS only simplifies one subtree time, while the actual simplification usually requires sequentially simplifying multiple subtrees, we iteratively invoke the HIss procedure for both train- ing and inference, in Chen Tian (2018). Table shows an example of the iterative process. The iterations terminate when 1) the number of iterations reaches 20; 2) the simplification output becomes a single node; or 3) the subtree selector assigns small scores (below 0.05) to all subtrees.
shows
Two baselines are included: 1) Halide (Ragan -aagan-Kelley et al.) 2013), which applies Halide predefined rules; 2) Z3, the simplification function in Z3, a high-performance theorem prover devel- oped by De Moura & Bjørner (2008), to perform transformations using the Halide predefined rules. is worth mentioning that both baselines have access to the Halide predefined rules that are used to construct the dataset, which gives them an advantage over HISs.
Baselines
Metries Expression length reduction and tree size reduction are applied as the metrics.
Results Figure 3 shows the performance of HISS compared with the baselines. As can be seen, HISs outperforms both Halide and Z3 in both metrics. This result is quite non-trivial because the Halide dataset is built exclusively from the Halide's ruleset, to which both baseline algorithms have access. Therefore, this result implies that even for expressions that are specifically designed to be simplified by set of predefined rules, they can still be further simplified by rules that are outside of the set.
7

---

Published as a conference paper at ICLR 2020
Table 2: Simplification process of HIss (upper) and Halide (lower) Eq. (T)). The subtrees
selected for simplification in the next iteration are marked with box unless the entire tree is selected.
Step
Hiss
0
(1(1444(60072))))22)++++ - (1500- (v077)))0)))
1
(M00)44+(0072))))2)))++++ S. (v000)))))2))
2
((114- (v0*7))) S (150- (v0*72))
3
(144-(v007)) S (146- (v0+72))
4
(((v0*72) -(V0-22) $
5
0 2
6
True
Step
Halide
0
((((()44 -1:444-00000 (v+-2))222))) + 4) Σ ((150 (v0*72))4)*4)
1
((((2- (v0*36))*2++ & ((1150 (v007(2)))))))
2
((((72 (v0*36))*2) + 4) v ((37.5 (8))*))
3
1((37.5 (=0+18)))4) < ((((72 (e0*36))*2) +
5.3 SIMPLIFICATION PROCESS ANALYSIS
In this subsection, we will provide in-depth analysis of the simplification process of HIss and Halide, which can explain why numan-predefined rules can be insufficient, and how HIss can exceed the limit of purde-eded rules.
Example Simplification Rules To start with, table T lists some example simplification rules learned by Hiss For each example rule, the corresponding numan-predeffiee rule in Halide is also listed if available. There are two observations. First, HISS is able to learn the most fundamental axiomatic identities such as the inverse relationship between plus and minus, and between multiplication and division, most of which can be matched with the numan--redeffing importantly, HIss can also uncover some more complicated rules that have no matches in Halide, nor could be equivalently derived from any composition of the rules in Halide. A close inspection into these rules reveals that these rules, despite their complexity, are still very fundamental, and therefore the failure to include these rules is expected to impact the simplification performance. In addition to these fundamental rules, HISS is also able to find some involved but interesting rules, which are listed in table 4 and discussed in appendix (.2 B.2
rules in Halide. Second and more
Example Simplification Traces. To illustrate how the completeness of the rules can impact on the simplification performance, table compares the simplification traces of Halide and HIss for the following expression
(((((144- (v0*72))/) + ((150- (v0+72))44*4)
(10)
For Halide, each step represents the process of applying Halide predefined rule to simplify the expression. For HIss, each step represents one simplification iteration. As each step, the subtree that is chosen for simplification for the next step is marked with box, unless the entire expression is chosen. As can be seen, HISS follows some reasonable steps to trim the constants and eliminates vO, but Halide gets stuck after some trivial constant reduction. The reason for this failure is there no such rules as (((cD - (r0 cl2)) c2 + c0 - (r0 x cl) ) or z + + y + or (z y) * in the Halide ruleset. Of course, one can fix this problem one time by appending the aforementioned rules to the ruleset, but this does not fundamentally solve the problem because one would never be able to exhaustively list all the possible rules needed for simplification in the ruleset.
x y*
Why Subtree Selector Matters. Table also illustrates why the subtree selector is an integral part of HIss. In many reduction steps, only subexpression is simplified (as boxed). Without the subtree selector, the decoder of HISS would have to process the entire expression only to simplify the subexpression, which makes it hard to effectively learn via reinforcement learning. For more analysis on the effect of the subtree selector, please refer to appendix C
6 CONCLUSIONS
We presented HISS as a symbolic expression simplification algorithm that is independent human knowledge. We demonstrated that removing the dependence humans is advantageous for this task
8

---

Published as a conference paper at ICLR 2020
because machines can autonomously figure out rewrite rules that humans fail to discover, and thus achieve comparably well simplification results. We also showed that we are one step closer to find- ing serivaleecc-prsserving embedding for symbolic expressions. Although HISs has achieved promising results, there still much room for improvement. Although HISs has adopted several techniques reduce the complexity of the search space, learning simplification rules very long expressions is still challenging, which calls for the exploration of more efficient reinforcement learn- ing algorithms as a future research direction.
ACKNOWLEDGEMENT
We thank the anonymous reviewers for their valuable feedback. This paper is supported by NSF grant 1829525.

---

Published as a conference paper at ICLR 2020
REFERENCES
David Alvarez-Melis and Tommi S Jaakkola. Tree-structured decoding with doubly-recurrent neural networks. 2016.
Forough Arabshahi, Sameer Singh, and Animashree Anandkumar. Combining symbolic expressions and black-box function evaluations in neural programs. arXiv preprint arXiv:1801. 04342, 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv preprint arXiv: (0ti::/4000047555 2014.
Dimitri P Bertsekas. Dynamic programming and optimal control, volume Athena scientific Belmont, MA, 1995.
Sebastian Buchwald. Optgen: generator for local optimizations. International Conference on Compiler Construction, pp. 171-189. Springer, 2015.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. arXiv preprint 1:X55:800.042111 2018.
Cheng-Hao Cai, Yanyan Xu, Dengfeng Ke, and Kaile Su. Learning of human-lite algebraic reason- ing using deep feedforward neural networks. Biologically inspired cognitive architectures, 25: 43-50, 2018.
Xinyun Chen and Yuandong Tian. Learning to progressively plan. arXiv preprint arXiv:1810.00337, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Tree-to-tree neural networks for program translation. In Advances in Neural Information Processing Systems, pp. 2547-2557, 2018.
Leonardo De Moura and Nikolaj Bjømer. Z3: An efficient sunt solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 337-340. Springer, 2008
Mehdi Drissi, Olivia Watkins, Aditya Khant, Vivaswat Ojha, Pedro Sandoval, Rakia Segev, Eric Weiner, and Robert Keller. Program language translation using grammar-drive tree-to-tree model. arXiv preprint arviv: / 1807.0/744 2018.
Abhinav Jangda and Greta Yorsh. Unbounded superoptinization. In Proceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Program- ming and Software, pp. 78 88. ACM, 2017.
Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex Aiken. Taso: optimizing deep learning computation with automatic generation of graph substitutions. In Pro- ceedings of the 27th ACM Symposium on Operating Systems Principles, pp. 47-62. ACM, 2019.
Rajeev Joshi, Greg Nelson, and Keith Randall. Denali: goal-directed superoptimizer, volume 37. ACM, 2002.
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning. pp. 282-293. Springer, 2006.
Wang Ling, Edward Grefenstette, Karl Moritz Hermann, Tomá Kočiský, Andrew Senior, Fumin Wang, and Phil Blunsom. Latent predictor networks for code generation. arXiv preprint arXiv:1603.06744, 2016.
Hongbin Liu and Ickjai Lee. End-to-end trajectory transportation mode classification using bi- Istm recurrent neural network. In 2017 12th International Conference on Intelligent Systems and Knowledge Engineering (ISKE), pp. 1-5. IEEE, 2017.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 2579 2008
10

---

Published as a conference paper at ICLR 2020
Henry Massalin. Superoptimizer a look at the smallest program. In ACM SIGARCH Computer Architecture News, volume 15, pp. 122-126. IEEE Computer Society Press, 1987.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. arXiv preprint 1rXiv:161..0185.. 2016.
Jonathan Began-Kellly,, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Amarasinghe. Halide: language and compiler for optimizing parallelism, locality, and recom- putation in image processing pipelines. Acm Sigplan Notices, (8(6))511--330 2013.
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. ACM SIGPLAN Notices, volume 48, pp. 305-316. ACM, 2013.
Kai Sheng Tai, Richard Socher, and Christopher D) Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:7503.00075, 2015.
Ronald J Williams. Simple statistical gralient-follownng algorithms for connectionist reinforccmettt learning. Machine learning, 8(3-4):229-255 1992.
Wojciech Zaremba and Ilya Sutskever. Learning to execute. arXiv preprint arXiv: 2014.
Victor Zhong, Caiming Xiong, and Richard Socher. Seq2sql: Generating structured queries from natural language using reinforcement learning. arXiv preprint arXiv:1709.001003 2017.

---

Published as a conference paper at ICLR 2020
A EXPERIMENT SETUP
A.1 TRAVERSE EQUIVALENCE DATASET
Table 3 shows the vocabulary of Halide syntax, which is used to construct the traverse equivalence dataset. As there are 14 binary operators, unary operator, and ternary operator, the total number of different expressions of depth two would be over 50k, and the number of different expressions of depth three is over 1.25e+14 14. However, the rule of thumb is that the simplification is most possible when there
some variables repeatedly appear in the expression, for example, (x + 3) r y while (I + =) + could not be simplified. Therefore, we constraint the enumeration of expression to only 16 operators, constants, and the first three variables (vO, vl, v2). As a result, roughly billion expressions are enumerated.
To check whether an expression could be simplified in this plethora of possible candidates, we adopted the FingerPrint method (Jia et al., 2019). The idea is that equivalent expressions should produce the same output under the same set of input. Initially, n sets of random value assignment to all variables are generated, and the fingerprint of an expression is defined as the tuple of the cor- responding n output given the assignment. According to the fingerprint, expressions with exactly (n = 4 in our case) same results are grouped into a shard. It can be implied that any equíva- lent expressions must be in the same shard. Thus, the shards could be processed in parallel. It is highly possible that the initial assignment would lead an extremely large shard. Therefore, when processing each shard, we repetitively compute new fingerprints until the shard breaks into small shards containing fewer than 5,000 expressions. Then, expressions from the same shard to determine whether the expression pair is equivalent. For each expression pair that is equivalent, the longer expression is labeled as reducible. After all the pairs are tested, all the expressions that are labeled as reducible are retained, and the rest are removed.
probabilistic testing each pair of
Further, it is obvious that if an expression could be simplified, the longer expression containing it could also be simplified. So if an expression contains a subexpression that could be simplified, then this expression does not represent the minimal sequence of this simplification and is removed from the dataset as well. After the FingerPrint method and the minimality checking, we obtain approximately 20,000 equivalent expression pairs, from which 1,500 samples are randomly sampled and further split into training, testing, and validation set with a ratio of 6:2:2.
A.2 HALIDE DATASET
The Halide dataset (Chen & Tian 2018) contains around 10,000 training sequences, 1,000 testing sequences, and 1,000 validation sequences, generated and split randomly. The number of words for cach sequence ranges from 6 to 100, averaged at 58. The expressions generated contain many constants beyond {0, I, 2. True, False). and the constant is renamed to constant symbols shown in table and the same constant value is renamed to the same constant symbol. There are at most 14 constant symbols and at most 15 variables in a single expression.
A.3 HYPERPARAMETER SETTING AND DETERMINATION
The input to the network is one-hot encoded sequences where the vocabulary size is 50, then the input is encoded by single fully connected layer with output size 32. The hidden units of LSTM are set to 64 for both encoder and decoder, as a common setting adopted in many previous works (Liu & Lee 2017), and the number of layers is 1. The output size of the encoder is 64, and the output size of the decoder is equal to the vocabulary size (50). The subtree selector consists of two ceed-forward layers with output sizes of 128 and respectively. The model is trained with the ADAM optimizer with learning rate of le-3. Rather than tuned on the validation set, this hyperparameter setting is determined by following the common setting in previous works (QLiu & Lee 2017) as well as referencing to the Halide vocabulary size. The same hyperparameter setting has been applied throughout this research project. Finetuning the hyperparameters is expected to have minor effect on the performance as compared to refining our major algorithm design, egg. introducing subtree selector and &g embedding regularizer, which will be discussed in further details in the ablation studies in appendix C
12

---

Published as a conference paper at ICLR 2020
Table The vocabulary of the symbols and operators that are used construct the traverse equiva- lence dataset.
Type
Symbols
Operators Constants Variables
min, max, 2, S, <, F, select, + ", &&
0, 1, 2. True, False
v0, vl, v14
Constant symbols
c0, cl, ... c13
The penalty of not getting an equivalent expression, 3 (as in Eq. (8) is set to 0. This is motivated by our observation that in the Monte Carlo sampling results the ratio of equivalent expressions over nonequivalent expressions is roughly 10:1 on a randomly initialized model. Therefore, by matching this ratio can balance the reward and penalty and achieve average reward of around zero, at least for the initial iterations, which is shown to contribute to a more stable REINFORCE training. However, please be reminded that not a crucial parameter because the baseline removal process in REINFORCE would automatically balance the reward and penalty. A good choice of & would mostly only benefit the onset of the training when the baseline estimation not yet accurate. The weight to embedding similarity loss term is set to 0.1.
A.4 TRAINING AND INFERENCE
As mentioned, the training for section whereas the training for section 5.2 involves both stages in the curriculum learning. Below the details regarding the training and inference schemes.
5.1 involves only the first stage in the curriculum learning,
Training Iterations For the stage-one training in both experiments, we apply identical setting, where the encoder-decoder model is trained for 10 epochs (90,000 steps). The model with the highest hit rate on the validation set is selected for evaluation in section 5.1 as well for the stage- two training of the curriculum. The stage-two training takes two weeks to train the HIss for full simplification pipeline on RTX 2080 for 40 epochs (400k steps).
Beam Search The beam search algorithm is performed as follows. In the beginning, the top choices of the root node with the highest probability are decoded. Then for each choice of root node value, the next step would be to decode the top k choices of each child node of the root node. Since decoding processes of different child nodes of the same parent node are independent, we then perform the Cartesian product of all the & choices for each node at the current step, and preserve the top combinations with the highest probability. Repeating this way, at step 4, beam search decodes k highest probability tree up to depth t. Finally, top (s k) expressions are backtracked and used to estimate the expected reward of the model. The probability of beam search decoded expression re-normalized according to Bunel et al. (2018). In all the experiments, we set beam size k 20 and 20.
Constant Folding Since the Halide dataset contains large number of constant values, apply technique called constant folding to both stage-two training and inference of HISS as well as to all other baselines. Specifically, once the expression is rewritten by the neural network in the symbolic domain, it will be checked if all the leaf nodes in the subtree are constant. If so, the expression is executed and replaced by new single node with the execution result. Constant folding is applied in both training and inference.
B ADDITIONAL EXPERIMENT RESULTS
B. ATTENTION VISUALIZATION
To understand the attention mechanism, we visualize the attention to the input sequence shown in figure 4 We find that when decoding operator, the attention tends to be flat (with a few exceptions in the right two figures), because it needs to understand the overall logic. This is different from machine translation summarization, where the output attention of single word is usually focused on several input tokens. On the other hand, when decoding a variable, the model attends sharply to the corresponding variable in the input.
13

---

Published as a conference paper at ICLR 2020
0.30 11
021
0.16
0.18
3.14
1y-
0.12
002
0.12
0.19
tru)
0.09
0.08
(eax
2.08
0.04
D00 y0
Figure 4: Attention weights on the imput sequences for each token decoded. The x-axis shows the output sequence, and the y-axis shows the input sequence. The input sequence is encoded from leaves to root and the output sequence is decoded from root to leaves. Tokens are re-arranged in the natural order for better visualization.
Table 4: Involved simplification rules discovered by HISs.
Input
Output
(Itrue) < (1) 11-11
(tree 2 y)
(y truc) [ 2 true)
true
max(z, 1) 2 [falsel| (x))
true
(1-z) 2 min(x, true) (t(e))&((222)))
2 z
x&
1- < x)
2 x
select(2: 2, 2, true) == select(2, false, true) (x &true
y&&x
(y + 1) (yl&22
0
Table 5: Mean and standard deviation of the performance metrics among random initialization. The experiment setting is the same as in section 5.1
Sampling Parameter
10
Hit Rate
0.391 + 0.013
0.391 + 0.009
0.406 - 0.014
0,406 + 0.014
Expression Length Reduction
2.250 + 0.172
2.250 = 0.140
2.578 + 0.242
2.578 = 0.242
Tree Size Reduction
1.078 1 0.077
1.078 1 0.069
1.219 1 0.114
1.2191 0.114
B.2 EXAMPLES INVOLVED SIMPLIRICATION RULES
In order to further appreciate the ability of HISs in finding equivalence, in addition to the rules listed table we list some simplification rules discovered by HISs on randomly generated expressions that are more involved in table In fact, it takes the authors quite while to figure alence. These rules are hardly useful in practice because no humans will code in this way, but vivid illustration of the advantage of HIss in finding powerful simplifications beyond human knowledge.
the equiv-
B.3 ROBUSTNESS AGAINST RANDOM INITIALIZATION
To assess the performance of HISS is robust to random model initialization, we perform the same experiment in section 5. times with different random initialization and compute the mean and standard deviation of the three metrics, which are shown in table Compared to the absolute value of the mean, the standard deviation is very small, which shows that the random initialization has minor influence on the performance of HISs.
C ABLATION STUDIES
In this section, we introduce a set of ablation studies that investigate the significance of the major components of HIss in terms of contribution to performance. The major components of interest the subtree embedding similarity loss as in Eq. (9). the subtree selector as introduced section 3.3
and the tree-LSTM encoder-decoder architecture in sections 3.2 and B.4
As an overview, figure 5 compares the performance between Hiss and the following variants of HIss the Halide dataset.
14

---

Published as a conference paper at ICLR 2020
LiniarLLTTM Stlector
39,9
Linear- LSTM
114
Expression Length Reduction
No
25
Tree Size Reduction
24.8
7.2
5.1
Figure 5: Performance of different variants HISs on the Halide dataset.
No-Embed-Loss: The original HIss trained without the subtree embedding similarity loss.
No-Selector: The original HISS without the subtree selector.
Linear-LS7M: The Tree-LSTM structure removed and a simple linear-LSTM used instead. The embedding loss as well as the subtree selector are no longer applicable and therefore also moved.
Other than the variations aforementioned, all the experiment settings are identical to the experiment in section 5.2 As can be seen in figure [5] without training with the embedding similarity loss or the subtree selector, the performance is significantly compromised. Furthermore, removing the tree- LSTM structure leads to almost a complete failure. The subsequent subsections further investigate why each of these modules has such significant impact the performance respectively.
C.I SUBTREE EMBEDDING SIMILARITY
We would like to investigate the specific effects that introducing the embedding similarity loss brings.
The direct goal of the embedding similarity loss is to better cluster the embeddings whose cor- responding expressions are equivalent. Therefore, would like first check if this direct goal is achieved. To evaluate this, in the experiment described in section [..] we select the six most- populated subsets of equivalent expressions in the test set and evaluate the similarity of the em- beddings computed by HISS in two ways. First, the embeddings are further projected to two- dimensional space using t-SNE (Maaten Hinton] 2008), which forms a scatter plot as Fig- ure 16]a-1). The points corresponding to equivalent expressions are shown in the same color. As can seen, the embeddings equivalent expressions are highly clustered. Notice that this result is on the low-dimensional projection of the embedding. To better evaluate their similarity in the original space, we compare their inter- and intra-subset distances. The interriinra-subse distance of subset is defined as the Euclidean distance between the centroid of the subset and the samples outside/within the subset. Figure 6(a-2) illustrates the box plot of these distances. As shown, there significant difference between intra- and inter-subset distances. Except for the first subset, the quartile intervals are well separated.
Figure b]b-)) and (b-2) show the same plots on the No-Embed-Loss model, i.e. the HIss variant that is trained without the embedding similarity loss. As can be seen, the scatter points are apparently less well-clustered, and the difference between inter- and intra-subset distances, although still exists, is smaller. Therefore, we can draw two conclusions. First, even without the embedding similarity loss. HIss is still able learn embeddings that are somewhat clustered according to equivalence, which shows the goal of finding equivalent expressions roughly aligns with the need to cluster the embedding based on the expression equivalence. Second, the embedding similarity loss can improve embedding clustering.
However, what we are more interested in is why an improved clustering of the embeddings would lead to significant performance gain. To answer this question, f the average reward as a function of training epoch of Hiss and its variant without the embedding similarity loss, which gives
very interesting insights. Notice that despite their initial difference, which is due to the random initialization, both reward curves reach the same plateau at around epoch seven, where they both become stagnant for while. However, with the help of embedding similarity loss, HISS
15

---

Published as a conference paper at ICLR 2020
3.5
Intra-
3.0
Inter
2.5
Compuntt
distance
2.0
1.5
1.0
0.5
cluster
(a-1)
(a-2)
Intra-
inter-
26-
Componant
distance
1.0
-20-
0.5
0.0
cluster
(b-1)
(b-2)
Figure 6: Evaluation similarity of the embeddings of equivalent expressions. The upper plots ((a-1) and (a-2)) are evaluated on the original HISS model. The lower plots ((b-1) and (b-2)) are evaluated on the No-Embed-Loss model. Left plots ((a-1) and (b-l)) are scatter plots of embeddings projected onto two-dimes -vo-dimensional space using t-SNE. Points corresponding to equivalent expressions are shown in the same color. Right plots (a-2) and (b-2)) are box plots of intra- (blue) and inter- subset (orange) distances of the embeddings trained with & loss. The bars in the box represent 25% 50% and 75% quartile values. The line intervals denote the 1.5 interquartile range (IQR) beyond the quartile values. The dots represent the extreme values.
-3
-4
-5
Reward(10-3)
-7-
-8
-9-
HISS
No Do-Embed-Loss
-10
10
15
20
25
Epoch
Figure 7: Expected reward of HISS with the embedding similarity loss (HISS) and without the embedding similarity loss NNo-Embed-Lost
16

---

Published as a conference paper at ICLR 2020
Table 6: Simplification traces of HIss with and without the subtree selector on Eq. (I). The subexpressions selected by the subtree selector are boxed, unless the entire expression is chosen.
Step
Hiss with the Subtree Selector
(v1++v)-7){((((
((mxx((1_00)118887))) ((V+)))))27
2
Step
Hiss without the Seltroe Selector
0
Table Output sequences Linear-LSTM trained on Traverse Equivalence dataset
Linear-LSTM with only equivalence reward
Input
2. Output
max(vl + vO, +2+ vO)
min(min(y2, v0 + vl), v0 v3)
"9''" '',
c9 "9', "0', c9' c9
'c9'l
(v0 v
c9', 'c9',
'c9',
'2
Linear-LSTMe frained with equivalence and valid expression reward
Input
Output ['vl]
min(v2, v0 vi)-vi
vl =[v00[[l))
['c0]]
min(v2, v0 v1)
['2". '2', 'vO']
is finally able to escape from the plateau and reach higher reward level, whereas the one without the embedding similarity loss gets trapped in the plateau. This result suggests that the embedding similarity loss provides extra training signal to address the convergence issue of REINFORCE.
C.2 SUBTREE SELECTOR
We have already demonstrated the wnrkr-workings of the subtree selector in section 5.3 and shown in figure that subtree selector is indispensable for the good performance of Hiss. Here we would
like intuitively explain why this is the case. Table 6 compares the simplification traces of Hiss with and without the subtree selector on the following expression
(1I)
As can be seen, HISS with the subtree selector can first offset the **8" and '/8' terms in the subex- pression ((max(y1,)) 18))8)
before it applies the cancellation rule to merge the constants '-7'
and '-27'. On the other hand, HISS without the subtree selector unable identify the reducible subexpression, and so it only applies the cancellation rule. This result shows that the reason why the subtree selector helps is that can thoroughly check on each subexpression, and therefore con- tributes to a better simplification. Without the subtree selector, the algorithm is prone to overlook some small subexpressions that are reducible.
C.3 TREE LSTM V.S. LINEAR LSTM
We can see the conspicuous disadvantage the Linear-LSTM model from figure 5 To illustrate the fundamental issue with the Linear-LSTM model, we sampled some output of the model trained on the Traverse Equivalence dataset, listed in table The model was trained with REINFORCE for 200k steps, with two different reward settings: 1) the equivalence reward in Eq. 8 2) the equiv- alence reward plus a valid expression reward, which is an additional reward of 0. if the decoded sequence is syntactically correct.
As can be seen in table 7 when trained with only the equivalence reward, the linear decoder is un- valid expression, not mention generating equivalent expression to the input. So the linear decoder could hardly converge and learn useful information from reward, which was almost always a negative constant. As remedy, we can add valid expression reward to guide
able to decode
17

---

Published as a conference paper at ICLR 2020
the linear LSTM to generate valid expressions. However, can be observed in table under this additional reward, the model would overfit this reward by only generating short valid expressions, which are not equivalent to the input. This is because short expressions contain only one variable or constant have a higher generation probability than longer valid expressions. During the training, whenever the model happens generate single expression, it was rewarded positive valid pression reward. So the behavior of generating only a single constant or variable is strengthened. Still, the probability that random variable equivalent the input expression, small, and therefore the model can hardly be guided by equivalence reward, but focuses only on generating short but valid expressions.
This experiment demonstrates the advantage of using the tree LSTM, which is guaranteed to gener- ate syntactically correct, and which has much higher probability of hitting an equivalent expres- sion. Therefore, the tree LSTM can be much better guided by the equivalence reward.
18


Reviews:
[{"review_id": "Skl0FlWAtS", "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": "The authors present a framework for symbolic superoptimization using methods from deep learning. A deep learning approach operating on the expression tree structures is proposed based on a combination of subtree embeddings, LSTM RNN structures, and an attention mechanism. \n\nThe approach avoids the exploitation of human-generated equivalence pairs thus avoiding human interaction and corresponding bias. Instead, the approach is trained using random generated data. It remains somewhat unclear how the corresponding random data generation influences general applicability w.r.t. other tasks, as the authors apply constraints on the generation process for complexity reasons. A corresponding discussion would be valuable here.\n\nIn Secs. 3 & 4, the authors present their specific modeling and learning approach. However, they do not report on modeling or learning alternatives. It would be interesting for the audience to understand, how the authors reached these specific choices, and how (some of) these choice influence performance and learning stability. For example, in Sec. 4.1, an additional loss term is introduced to further support the learning of embeddings. However, it might interesting to see comparative results quantitatively investigating the effect of this additional loss term. Also, as far as I can see, no information on the choice of hyperparameters (e.g. LSTM dimensions) are provided or analyzed w.r.t. their effect on the performance of the proposed approach.", "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": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklviNintr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 provides a novel approach to the problem of simplifying symbolic expressions without relying on human input and information. To achieve this, they apply a REINFORCE framework with a reward function involving the number of symbols in the final output together with a probabilistic testing scheme to determine equivalence. The model itself consists of a tree-LSTM-based encoder-decoder module with attention, together with a sub tree selector. Their main contribution is that this framework works entirely independent of human-labelled data. In their experiments, they show that this deep learning approach outperforms their provided human-independent baselines, while sharing similar performance with human-dependent ones.\nOverall, the work in this paper has the potential to be a contribution to ICLR but lacks completeness and clarity. A number of experimental details are missing, making it difficult to understand the setup under which results were obtained. Moreover, the paper does not seem to have been revised with many grammatical issues that make it hard to read.\nThe following are major issues within the paper and should be addressed:\n•\tThe paper does not mention the amount of compute given to their model, nor the amount of time taken to train. As the REINFORCE framework is generally quite computation-heavy, these are significant details. Without assessing the amount of compute and time allotted for training HISS, the comparisons to previous baselines lose a fair amount of meaning. The paper alludes to processes being ‘extremely time consuming’, but then does not provide any numbers.\n•\tThey do not mention the data used to train the model weights. In the comparisons sections, some details on datasets are given, but these seem to refer to data for inference.\n•\tThere are many grammatical errors that likely could have been detected with \t revision. A handful of such errors would not affect the score, but they are so numerous as to make the paper much more difficult to understand.\nAdditionally, these are comments that slightly detract from the quality of the paper:\n•\tIt’s unclear what to glean from Section 5.1, as the dataset and baselines seem to be fairly trivial. If their claim is to have the first nontrivial human-independent approach to simplifying symbolic expressions, there is no need to compare to baselines that can only handle small expressions.\n•\tSections 5.3 and 5.4 contribute little to the paper. For 5.3, the model was trained to embed equivalent expressions close together, using L2 regularization. It is therefore unsurprising that equivalent expressions are then closer together than non-equivalent ones. The paper also does not provide a comparison to the method without this regularization, and so it’s unclear if this embedding similarity helps in any way.  For 5.4, the section is extremely short and contains very little content. Moreover, just as many of the variables in their provided examples oppose their conjectures as support them.\n•\tThe most interesting figure provided is the rewrite rules discovered by the model. It would be even better if an additional column containing the rules discovered by Halide (the main baseline) were provided.\nOverall, in my understanding, the primary point in favor of the paper is in being the first nontrivial human-independent approach to simplifying symbolic expression. That said, this is not my area of expertise, so I cannot judge novelty or importance as well as other reviewers.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlylMRX5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 presents a method for symbolic superoptimization — the task of simplifying equations into equivalent expressions. The main goal is to design a method that does not rely on human input in defining equivalence classes, which should improve scalability of the simplification method to a larger set of expressions. The solution uses a reinforcement learning method for training a neural model that transforms an equation tree into a simpler but equivalent one. The model consists of (i) a tree encoder, a recursive LSTM that operates over the input equation tree, (ii) a sub-tree selector, a probability distribution over the nodes in the input equation tree, and (iii) a tree decoder, a two layer LSTM that includes a tree layer and a symbol generation layer. The RL reward uses an existing method for determining soft equivalence between the output tree and the input tree along with a positive score for compressing. \n\nThe main strengths of the paper are that (i) it targets the scalability problem in simplifying arithmetic expressions by reducing the amount of human effort involved in the process, (ii) it provides some evaluation comparing against methods that use pre-defined rules for transforming equations, (iii) it provides a baseline method against which future scalable models can be compared against.\n\nThe following are the main concerns I have with the paper\n\n1) The model description should include more details about the design choices. \nFor instance, the specific reward function, the central component of the model, is left rather under-discussed. The function form is sensible but why does the negative case use -0.1 as the reward scaling constant? Why not some other number? How is this tuned? \n\n2) As far as I can see there is no real ablation analysis that shows which of the components are actually useful. Is the sub-tree selector necessary? Is the curriculum training necessary? How much does the sub-tree embedding similarity loss contribute to the results? Even if each of these actually add value it will be useful to know how much. What about other design choices? If we trained a direct seq2seq model with linearized expressions instead of the tree structured inputs, would it work just as well? These are empirical questions that need to be answered to justify that the proposed model indeed is useful. \n\n3) The experimental details are sparse. In particular, there is no mention of how hyper-parameters of the proposed method are tuned. Are the performance numbers averages over a set of random seeds or is it simply the best performing number that has been reported? This is especially troublesome for a RL based model. \t\n\nOverall the paper presents a particular model and strategy for training but lacks appropriate experimentation to establish their utility. \n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work introduces a neural architecture and corresponding method for simplifying symbolic equations, which can be trained without requiring human input. This is an area somewhat outside most of our expertise, but the general consensus is that the paper is interesting and is an advance. The reviewer's concerns have been mostly resolved by the rebuttal, so I am recommending an accept. 
Decision: Accept (Poster)