Title: COMBINING SYMBOLIC EXPRESSIONS AND BLACK-BOX FUNCTION EVALUATIONS IN NEURAL PROGRAMS

Abstract: Neural programming involves training neural networks to learn programs, mathematics, or logic from data. Previous works have failed to achieve good generalization performance, especially on problems and programs with high complexity or on large domains. This is because they mostly rely either on black-box function evaluations that do not capture the structure of the program, or on detailed execution traces that are expensive to obtain, and hence the training data has poor coverage of the domain under consideration. We present a novel framework that utilizes black-box function evaluations, in conjunction with symbolic expressions that define relationships between the given functions. We employ tree LSTMs to incorporate the structure of the symbolic expression trees. We use tree encoding for numbers present in function evaluation data, based on their decimal representation. We present an evaluation benchmark for this task to demonstrate our proposed model combines symbolic reasoning and function evaluation in a fruitful manner, obtaining high accuracies in our experiments. Our framework generalizes significantly better to expressions of higher depth and is able to fill partial equations with valid completions.

1. INTRODUCTION:

Human beings possess impressive abilities for abstract mathematical and logical thinking. It has long been the dream of computer scientists to design machines with such capabilities: machines that can automatically learn and reason, thereby removing the need to manually program them. Neural programming, where neural networks are used to learn programs, mathematics, or logic, has recently shown promise towards this goal. Examples of neural programming include neural theorem provers, neural Turing machines, and neural program inducers, e.g. Loos et al. (2017) ; Graves et al. (2014) ; Neelakantan et al. (2015) ; Bošnjak et al. (2017) ; Allamanis et al. (2017) . They aim to solve tasks such as learning functions in logic, mathematics, or computer programs (e.g. logical or, addition, and sorting), prove theorems and synthesize programs.

Most works on neural programming either rely only on black-box function evaluations (Graves et al., 2014; Balog et al., 2017) or on the availability of detailed program execution traces, where entire program runs are recorded under different input conditions (Reed & De Freitas, 2016; Cai et al., 2017) . Black-box function evaluations are easy to obtain since we only need to generate inputs and outputs to various functions in the domain. However, by themselves, they do not result in powerful generalizable models, since they do not have sufficient information about the underlying structure of the domain. On the other hand, execution traces capture the underlying structure, but, are generally harder to obtain under many different input conditions; even if they are available, the computational complexity of incorporating them is significant. Due to the lack of good coverage, these approaches fail to generalize to programs of higher complexity and to domains with a large number of functions. Moreover, the performance of these frameworks is severely dependent on the nature of execution traces: more efficient programs lead to a drastic improvement in performance (Cai et al., 2017) , but such programs may not be readily available.

In many problem domains, in addition to function evaluations, one typically has access to more information such as symbolic representations that encode the relationships between the given variables and functions in a succinct manner. For instance, in physical systems such as fluid dynamics or robotics, the physical model of the world imposes constraints on the values that different variables can take. Mathematics and logic are other domains in which expressions are inherently symbolic. In the domain of programming languages, declarative languages explicitly declare variables in the program. For instance, database query languages (e.g., SQL), regular expressions, and functional programming. Declarative programs greatly simplify parallel programs through the generation of symbolic computation graphs, and have thus been used in modern deep learning packages, such as Theano, TensorFlow, and MxNet. Therefore, rich symbolic expression data is available for many domains. We will show in this paper, that incorporating this type of information, as well as black-box function evaluations, will result in models that are more generalizable.

Summary of Results::

We introduce a flexible and a scalable neural programming framework that combines the knowledge of symbolic expressions with black-box function evaluations. To our knowledge, we are the first to consider such a combined framework. We demonstrate that this approach outperforms existing methods by a significant margin, using only a small amount of training data. The paper has three main contributions. (1) We design a neural architecture to incorporate both symbolic expressions and black-box function evaluation data. (2) We evaluate it on tasks such as equation verification and completion in the domain of mathematical equation modeling.

(3) We propose a data generation strategy for both symbolic expressions and black-box function evaluations that results in good balance and coverage.

We consider learning mathematical equations and functions as a case study, since it has been used extensively in previous neural programming works, e.g. Zaremba et al. (2014) ; Allamanis et al. (2017) ; Loos et al. (2017) . We employ tree LSTMs to incorporate the symbolic expression tree, with one LSTM cell for each mathematical function. The parameters of the LSTM cells are shared across different expressions, wherever the same function is used. This weight sharing allows us to learn a large number of mathematical functions simultaneously, whereas most previous works aim at learning only one or few mathematical functions. We then extend tree LSTMs to not only accept symbolic expression input, but also numerical data from black-box function evaluations. We employ tree encoding for numbers that appear in function evaluations, based on their decimal representation (see Fig. 1c ). This allows our model to generalize to unseen numbers, which has been a struggle for neural programing researchers so far. We show that such a recursive neural architecture is able to generalize to unseen numbers as well as to unseen symbolic expressions.

We evaluate our framework on two tasks: equation verification and completion. Under equation verification, we further consider two sub-categories: verifying the correctness of a given symbolic identity as a whole, or verifying evaluations of symbolic expressions under given numerical inputs. Equation completion involves predicting the missing entry in a mathematical equation. This is employed in applications such as mathematical question answering (QA). We establish that our framework outperforms existing approaches on these tasks by a significant margin, especially in terms of generalization to equations of higher depth and on domains with a large number of functions.

We propose a novel dataset generation strategy to obtain a balanced dataset of correct and incorrect symbolic mathematical expressions and their numerical function evaluations. Previous methods do an exhaustive search of all possible parse trees and are therefore, limited to symbolic trees of small depth (Allamanis et al., 2017) . Our dataset generation strategy relies on dictionary look-up and sub-tree matching and can be applied to any domain by providing a basic set of axioms as inputs. Our generated dataset has good coverage of the domain and is key to obtaining superior generalization performance. We are also able to scale up our coverage to include about 3.5× mathematical functions compared to the previous works (Allamanis et al., 2017; Zaremba et al., 2014) .

Related work: Early work on automated programming used first order logic in computer algebra systems such as Wolfram Mathematica and Sympy. However, these rule-based systems required extensive manual input and could not be generalized to new programs. Graves et al. (2014) introduced using memory in neural networks for learning functions such as grade-school addition and sorting. Since then, many works have extended it to tasks such as program synthesis, program induction and automatic differentiation (Bošnjak et al., 2017; Tran et al., 2017; Balog et al., 2017; Parisotto et al., 2017; Reed & De Freitas, 2016; Mudigonda et al., 2017; Sajovic & Vuk, 2016; Piech et al., 2015) .

Based on the type of data that is used to train the models, frameworks in neural programming are categorized under 4 different classes. (1) Models that use black-box function evaluation data (Graves et al., 2014; Balog et al., 2017; Parisotto et al., 2017; Zaremba et al., 2014) , (2) models that use program execution traces (Reed & De Freitas, 2016; Cai et al., 2017) . (3) models that use a combination of black-box input-output data and weak supervision from program sketches (Bošnjak et al., 2017; Neelakantan et al., 2015) and finally (4) models that use symbolic data (Allamanis et al., 2017; Loos et al., 2017) . Our work is an extension of models of category 3 which uses symbolic data instead of weak supervision. As stated in Section 1, an example of symbolic data is the computation graph of a program which is different from program execution traces used in models of category 2 such as (Reed & De Freitas, 2016) . These high-level symbolic expressions summarize the behavior of the functions in the domain and apply to many groundings of different inputs as opposed to the Neural Programmer-Interpreter (Reed & De Freitas, 2016) . Therefore, we can obtain generalizable models that are capable of function evaluation. Moreover, this combination allows us to scale up the domain and model more functions as well as learn more complex structures.

One of the extensively studied applications of neural programming is reasoning with mathematical equations. These works include automated theorem provers (Loos et al., 2017; Rocktäschel & Riedel, 2016; Yuan; Alemi et al., 2016; law Chojecki, 2017; Kaliszyk et al., 2017) or computer algebra-like systems (Allamanis et al., 2017; Zaremba et al., 2014) . Our work is closer to the latter, under this categorization, however, the problem that we solve is in nature different. Allamanis et al. (2017) and Zaremba et al. (2014) aim at simplifying mathematical equations by defining equivalence classes of symbolic expressions that can be used in a symbolic solver. Our problem, on the other hand, is mathematical equation verification and completion which has broader applicability, e.g. our proposed model can be used in mathematical question answering systems.

Recent advances in symbolic reasoning and natural language processing have indicated the significance of applying domain structure to the models to capture compositionality and semantics. Socher et al. (2011; 2012) proposed tree-structured neural networks for natural language parsing and neural image parsing. Cai et al. (2017) proposed using recursion for capturing the compositionality of computer programs. Both Zaremba et al. (2014) and Allamanis et al. (2017) used tree-structured neural networks for modeling mathematical equations. Tai et al. ( 2015) introduced tree-structured LSTM for semantic relatedness in natural language processing. We will show that this powerful model outperforms other tree-structured neural networks for validating mathematical equations.

2. MATHEMATIC EQUATION MODELING:

We now address the problem of modeling mathematical equations. Our goal is to verify the correctness of a mathematical equation. This then enables us to perform equation completion. We limit ourselves to the domain of trigonometry and elementary algebra in this paper.

In this section, we first discuss our grammar that explains the domain under our study. we later describe how we generate a dataset of correct and incorrect symbolic equations within our grammar. We talk about how we combine this data with a few input-output examples to enable function evaluation. This dataset allows us to learn representations for the functions that capture their semantic properties, i.e. how they relate to each other, and how they transform the input when applied. We interchangeably use the word identity for referring to mathematical equations and input-output data to refer to function evaluations.

2.1. GRAMMAR:

Let us start by defining our domain of the mathematical identities using the context-free grammar notation. Identities (I), by definition, consist of two expressions that we are trying to verify (Eq. ( 1)). A mathematical expression, represented by E in Eq. ( 2), is composed either of a terminal (T ), such as a constant or a variable, a unary function applied to any expression (F 1 ), or a binary function applied to two expression arguments (F 2 ). Without loss of generality, functions that take more than two arguments, i.e. n-ary functions with n > 2, are omitted from our task description, since n-ary functions like addition can be represented as the composition of multiple binary addition functions. Therefore, this grammar covers the entire space of trigonometric and elementary algebraic identities. The trigonometry grammar rules are thus as follows:

I → = (E, E), =(E, E) (1) E → T, F 1 (E), F 2 (E, E) (2) sin cos = ^1 ✓ 2 ✓ ^2 + (a) sin 2 (θ) + cos 2 (θ) = 1 sin ⇥ 1 = 2.5 ⇥ 1 0.6 (b) sin(-2.5) = -0.6 = + ⇥ 10 0 10 1 ⇥ 2.5 2 5

(c) decimal tree for 2.5 

+ × ∧ F 1 → sin, cos, tan, . . . (3) F 2 → +, ∧, ×, . . .

(4) T → -1, 0, 1, 2, π, x, y, . . . , any number of precision 2 in [-3.14,+3.14] (5)

Table 1 presents the complete list of functions and symbols as well as examples of the terminals of the grammar. Note that we exclude subtraction and division because they can be represented with addition, multiplication and power, respectively. Furthermore, the equations can have as many variables as needed.

The above formulation provides a parse tree for any symbolic and function evaluation expression, a crucial component for representing the equations in a model. Figure 1 illustrates 3 examples of an identity in our grammar in terms of its expression tree. It is worth noting that there is an implicit notion of depth of an identity in the expression tree. Since deeper equations are compositions of multiple simpler equations, validating higher-depth identities requires reasoning beyond what is required for identities with lower depths, and thus depth of an equation is somewhat indicative of the complexity of the mathematical expression. However, depth is not sufficient; some higher depth identities such as 1 + 1 + 1 + 1 = 4 may be much easier to verify than tan 2 θ + 1 = acos 2 θ. Symbolic and function evaluation expressions are differentiated by the type of their terminals. Symbolic expressions have terminals of type constant or variable, whereas function evaluation expressions have constants and numbers as terminals. We will come back to this distinction in section 3 where we define our model. As shown in Table 1 , our domain includes 28 functions. This scales up the domain in comparison to the state-of-the-art methods that use up to 8 mathematical functions (Allamanis et al., 2017; Zaremba et al., 2014) . We will also show that our expressions are of higher complexity as we consider equalities of depth up to 4, resulting in trees of size at most 31. Compared to the state-of-the-art methods that use trees of size at most 13 (Allamanis et al., 2017) .

Axioms: We refer to a small set of basic trigonometric and algebraic identities as axioms. These axioms are gathered from the Wikipedia page on trigonometric identities 1 as well as manually specified ones covering elementary algebra. This set consists of about 140 identities varying in depth from 1 to 7. Some examples of our axioms are (in ascending order of depth), x = x, x + y = y + x, x × (y × z) = (x × y) × z, sin 2 (θ) + cos 2 (θ) = 1 and sin(3θ) = -4 sin 3 (θ) + 3 sin(θ). These axioms represent the basic properties of the mathematical functions in trigonometry and algebra, but do not directly specify their input/output behavior. The axioms, consisting of only positive (or correct) identities, serve as a starting set for generating a dataset of mathematical identities.

2.2. DATASET OF MATHEMATICAL EQUATIONS:

In order to provide a challenging and accurate benchmark for our task, we need to create a large, varied collection of correct and incorrect identities, in a manner that can be extended to other domains in mathematics easily. Our approach is based on generating new mathematical identities by performing local random changes to known identities, starting with 140 axioms described above. These changes result in identities of similar or higher complexity (equal or larger depth), which may be correct or incorrect, that are valid expressions within the grammar.

Generating Possible Identities: To generate a new identity, we select an equation at random from the set of known equations, and make local changes to it. In order to do this, we first randomly select a node in the expression tree, followed by randomly selecting one of the following actions to make the local change to the equation at the selected node:

• ShrinkNode: Replace the node, if it's not a leaf, with one of its children, chosen randomly.

• ReplaceNode: Replace the symbol at the node (i.e. the terminal or the function) with another compatible one, chosen randomly. • GrowNode: Provide the node as input to another randomly drawn function f , which then replaces the node. If f takes two inputs, the second input will be generated randomly from the set of terminals. • GrowSides: If the selected node is an equality, either add or multiply both sides with a randomly drawn number, or take both sides to the power of a randomly drawn number.

At the end of this procedure we use a symbolic solver, sympy (Meurer et al., 2017) , to separate correct equations from incorrect ones. Since we are performing the above changes randomly, the number of generated incorrect equations are overwhelmingly larger than the number of correct identities. This makes the training data highly unbalanced and is not desired. Therefore, we propose a method based on sub-tree matching to generate new correct identities.

Generating Additional Correct Identities: In order to generate only correct identities, we follow the same intuition as above, but only replace structure with others that are equal. In particular, we maintain a dictionary of valid statements (mathDictionary) that maps a mathematical statement to another. For example, the dictionary key x + y has value y + x. We use this dictionary in our correct equation generation process where we look up patterns from the dictionary. More specifically, we look for keys that match a subtree of the equation then replace that subtree with the pattern of the value of the key. E.g. given input equation sin 2 (θ) + cos 2 (θ) = 1, this subtree matching might produce equality cos 2 θ + sin 2 (θ) = 1 by finding key-value pair x + y : y + x.

The initial mathDictionaty is constructed from the input list of axioms. At each step of the equation generation, we choose one equation at random from the list of correct equations so far, and choose a random node n of this equation tree for changing. We look for a subtree rooted at n that matches one or several dictionary keys. We randomly choose one of the matches and replace the subtree with the value of the key by looking up the mathDictionary.

We generate all possible equations at a particular depth before proceeding to a higher depth. In order to ensure this, we limit the depth of the final equation and only increase this limit if no new equations are added to the correct equations for a number of repeats. Some examples of correct and incorrect identities generated by out dataset generation method is given in Table 2 .

Generating Function Evaluation data: We generate a few input-output examples from a specific range of numbers for the functions in our domain. For unary functions, we randomly draw floating point numbers of fixed precision in the range and evaluate the functions for the randomly drawn number. For binary functions we repeat the same with two randomly generated numbers. Note that function evaluation results in identities of depths 2 and 3.

Generating Numerical Expression Trees::

It is important for our dataset to also have a generalizable representation of the numbers. We represent the floating point numbers with their decimal expansion which is representable in our grammar. In order to make this clear, consider number 2.5. In order to represent this number, we expand it into its decimal representation 2.5 = 2 × 10 0 + 5 × 10 -1 and feed this as one of the function evaluation expressions for training (Figure 1c ). Therefore, we can represent floating point numbers of finite precision using integers in the range [-1,10].

1 2 = x -1×0 0.5 x+2 = sin(0.5) x+2 (arctan 10) 2 2 = (arctan 10) 3+1 π × csc(x) = -csc(x) x × (-1 + x) = x × (x -1) -4 = -4 x x 1 = x + 0 √ 2 2 × √ x = √ x ✓ 2 1 W symb W symb W symb W sin W cos W + W ✓ 2 W symb W symb W ^one-

3. TREE LSTM ARCHITECTURE FOR MODELING EQUATIONS:

Analogous to how humans learn trigonometry and elementary algebra, we propose using basic axioms to learn about the properties of mathematical functions. Moreover, we leverage the underlying structure of each mathematical identity to make predictions about their validity. Both Zaremba et al. (2014) and Allamanis et al. (2017) validate the effectiveness of using tree-structured neural networks for modeling equations. Tai et al. (2015) show that Tree LSTMs are powerful models for capturing the semantics of the data. Therefore, We use the Tree LSTM model to capture the compositionality of the equation and show that it improves the performance over simpler tree-structured, a.k.a recursive, neural networks. We describe the details of the model and training setup in this section.

Tree LSTM Model for Symbolic Expressions and Function Evaluations:

The structure of Tree LSTM mirrors the parse-tree of each input equation. As shown in Figure 1 , the input equation's parse tree is inherent in each equation. As described in section 2.1 an equation consists of terminals and binary and unary functions. Terminals are input to Tree LSTM through the leaves that embeds their representation using vectors. Each function is associated with an LSTM block with its own weights, with the weights shared among all appearances of the function in different equations. we predict the validity of each equation at the root of the tree.

The architecture of the neural network is slightly different for symbolic expressions compared to function evaluation expressions. Recall from section 2.1, that the two are distinguished by their terminal types. This directly reflects to the structure of the network used in the leaves for embedding. Moreover, we use different loss functions for each type of expression as described below.

• Symbolic expressions These expressions consist of constants and symbols. These terminals are represented with their one-hot encoding and are passed through symbol, a single layer neural network block. The validity of a symbolic expression is verified by computing the dot product of the left-hand-side and right-hand-side vector embeddings and applying the logistic function. • function evaluation expressions In order to encode the terminals of function evaluation expressions we train an autoencoder. The encoder side embeds the floating point numbers into a high-dimensional vector space. We call this a number block. The decoder of this auto-encoder is trained for predicting the floating point number given an input embedding.

We call this the decoder block. We pass the output vector embedding of the left-hand-side and right-hand-side to the decoder block. The validity of a function evaluation is then computed by minimizing the MSE loss of the decoder outputs of each side.

Figure 2 illustrates our tree LSTM structure constructed from the parse-tree of the equations in Figures 1a and 1b .2 

Baseline Models We compare our proposed model with chain-structured neural networks, such as sequential Recurrent Neural Networks (RNN), LSTMS's as well as tree-structured neural networks (TreeNN's) consisting of fully connected layers (Socher et al., 2011; Zaremba et al., 2014) . It should be noted that both these papers discover equivalence classes in a dataset, and since our data consists of many equivalence classes especially for the function evaluation data, we do not use the EqNet model proposed in (Allamanis et al., 2017) as a baseline. Another baseline we have used is Sympy.

Given each equality, Sympy either returns True, or False, or returns the input equality in its original form (indicating that sympy is incapable of deciding whether the equality holds or not). Let's call this the Unsure class. In the reported Sympy accuracies we have treated the Unsure class as a miss-classification. It should be noted, however, that Since Sympy is used at time of data generation to verify the correctness of the generated equations, its accuracy for predicting correct equations in our dataset is always 100%. Therefore, the degradation in Sympy's performance in Table 3 is only due to incorrect equations. It is interesting to see Sympy's performance when another oracle is used for validating correct equalities.

As we will show in the experiments, the structure of the network is crucial for equation verification and equation completion. Moreover, by adding function evaluation data to the tree-structured models we show that using this type of data not only broadens the applicability of the model to enable function evaluation, but it also enhances the final accuracy of the symbolic expressions compared to when no function evaluation data is used.

We demonstrate that Tree LSTMs outperform Tree NN's by a large margin with or without function evaluation data in all the experiments. We attribute this to the fact that LSTM cells ameliorate vanishing and exploding gradients along paths in the tree compared to fully-connected blocks used in Tree NNs. This enables the model to be capable of reasoning in equations of higher depth where reasoning is a more difficult task compared to an equation of lower depth. Therefore, it is important to use both a tree and a cell with memory, such as an LSTM cell for modeling the properties of mathematical functions.

Implementation Details Our neural networks are developed using MxNet (Chen et al., 2015) . All the experiments and models are tuned over the same search space and the reported results are the best achievable prediction accuracy for each method. We use L2-regularization as well as dropout to avoid overfitting, and train all the models for 100 epochs. We have tuned for the hidden dimension {10,20,50}, the optimizers {SGD, NAG (Nesterov accelerated SGD), RMSProp, Adam, AdaGrad, AdaDelta, DCASGD, SGLD (Stochastic Gradient Riemannian Langevin Dynamics)}, dropout rate {0.2,0.3}, learning rate {10 -3 , 10 -5 }, regularization ratio {10 -4 , 10 -5 } and momentum {0.2,0.7}. Most of the networks achieved their best performance using Adam optimizer Kingma & Ba (2014) with a learning rate of 0.001 and a regularization ratio of 10 -5 . Hidden dimension and dropout varies under each of the scenarios.

4. EXPERIMENTS AND RESULTS:

We indicate the complexity of an identity by its depth. We setup the following experiments to evaluate the performance and the generalization capability of our proposed framework. We investigate the behavior of the learned model on two different tasks of equation verification and equation completion.

Under both tasks, We assess the results of the method on symbolic as well as function evaluation expressions. We compare each of the models with sequential Recurrent Neural Networks (RNN), LSTMs and recursive tree neural networks also knows as Tree NN's. Moreover, we show the effect of adding function evaluation data to the final accuracy on symbolic expressions. All the models train on the same dataset of symbolic expressions. Models, Tree LSTM + data and Tree NN + data use function evaluation data on top of the symbolic data.

Our dataset consists of 17632 symbolic equations, 8902 of which are correct. This data includes 39 equations of depth 1, 2547 equations of depth 2, 12217 equations of depth 3 and 2836 equations of depth 4. It should be noted that the equations of depth 1 and 2 have been maxed out in the data generation. We also add 2000 function evaluation equations and decimal expansion trees for numbers that includes 1029 correct samples. We have 2 equations of depth 1, 831 equations of depth 2 and 1128 equations of depth 3 in this function evaluation dataset. Our numerical data includes 30% of numbers of precision 2 in the range [-3.14, 3.14] chosen at random.

Equation Verification -Generalization to Unseen Identities: In this experiment we randomly split all of the generated data that includes equations of depths 1 to 4 into train and test partitions with an 80%/20% split ratio. We evaluate the accuracy of the predictions on the held-out data. The results of this experiment are presented in Table 3 . As it can be seen, tree structured networks are able to make better predictions compared to chain-structured or flat networks. Therefore, we are leveraging the structure of the identities to capture information about their validity. Moreover, the superiority of Tree LSTM to Tree NN shows that it is important to incorporate cells that have memory. The detailed prediction accuracy broken in terms of depth and also in terms of symbolic and function evaluation expressions is also given in Table 3 .

Equation Verification -Extrapolation to Unseen Depths: Here we evaluate the generalization of the learned model to equations of higher and lower complexity. Generalization to equations of higher depth indicates that the network has been able to learn the properties of each mathematical function and is able to use this in more complex equations to verify their correctness. Ability to generalize to lower complexity indicates whether the model can infer properties of simpler mathematical functions by observing their behavior in complex equations. For each setup, we hold out symbolic expressions of a certain depth and train on the remaining depths. Table 4 presents the results of both setups, which suggest that Tree LSTM trained on a combination of symbolic and function evaluation data, outperforms all other methods across all metrics. Comparing the symbolic accuracy of Tree models with and without the function evaluation data, we conclude that our models are able to utilize the patterns in the function evaluations to improve and better model the symbolic expressions as well.

Equation Completion: In this experiment, we evaluate the capability of the model in completing equations by filling in a blank in unseen identities. For this experiment, we use the same models as reported in table 3 . We take all the test equations and randomly choose a node of depth either 1 or 2 in each equation, and replace it with all possible configurations of depth 1 and 2 expressions from our grammar. We then give this set of equations to the models and look at the top-k predictions for the blank ranked by the model's confidence. We perform equation completion on both symbolic and function evaluation expressions.

Figure 3a shows the accuracy of the top-k predictions vs. k, for the symbolic expressions. We define the top-k accuracy as the percentage of samples for which there is at least one correct match for the blank in the top k predictions. This indicates that the hardest task is to have a high accuracy for k = 1. Therefore, as in Fig 3a , the differences at k = 1 for models that use function evaluation data vs. models that do not, indicates the importance of combining symbolic and function evaluation data for the task of equation completion. We can also see that tree-structured models are substantially better than sequential models, indicating that it is important to capture the compositionality of the data in the structure of the model. Finally, Tree LSTM shows superior performance compared to Tree NN under both scenarios.

Figure 3b evaluates equation completion on function evaluation expressions by measuring the top-k minimum MSE for different ks. We define the top-k minimum MSE as the MSE between the true value of the blank and the closest prediction to the true value among the top-k predictions. Similar to the top-k accuracy, the hardest task is to have a low MSE for k = 1 since it indicates that the correct prediction is the first model prediction. We would like to note that, for function evaluation expressions, there is only one correct prediction for a blank, whereas for symbolic expressions, there may be many correct candidates for a specific blank. This evaluation is performed only for models 4 tanh(0) = x pred prob -2 0 0.9999 1 0 0.9999 7 0 0.9999 -3 0 0.999 8 0 0.999 6 0 0.999 2.5 0 0.999 9 0 0.999 5 0 0.999 (a) Symbolic Equation cos(-) = -0.57 pred modelErr trueErr 3 1.8e-5 1.7e-1 2.17 1.9e-5 9.9e-5 2.16 2.6e-5 3.9e-4 2.18 1.9e-4 0 2.15 2.1e-4 3.9e-4 2.19 5.5e-4 1.0e-4 2.2 1.0e-3 4.0e-4 2.13 1.1e-3 1.6e-3 2.12 1.8e-3 2.5e-3

(b) Function Evaluation 4a and 4b show examples of equation completion from the test set where the predictions are ranked by model's confidence and the correct prediction is shown in boldface. Figure 4c depicts the predicted values of cos(x) with blue dots for x in [-3.14,3.14] in the test set that use function evaluation data. We can see from the figure, that Tree LSTM's MSE is better that that of Tree NN across all ks.

We present examples of equations and generated candidates in Figures 4a and 4b for the Tree LSTM + data model. Figure 4a presents the results on a symbolic equation for which the correct prediction value is 1. The Tree LSTM is able to generate many candidates with a high confidence, all of which are correct. Column prob in the figure is the output probability of softmax which indicates the model's confidence in its prediction. On the other hand, in Figure 4b , we show a function evaluation example, where the correct answer is 2.18 rounded to precision 2. The correct answer is among the top predictions as shown in Figure 4b . All the predicted values for the blank are listed in column pred ranked by the model's prediction confidence. Column modelErr shows the model's confidence of prediction, which is the squared error between the predicted value of cos(-pred) and -0.57. Column trueErr is the squared error between the true value of cos(-pred) rounded to precision 2 and -0.57.

As it is shown, the predicted candidates are close to the true value. It is worth noting that for the function evaluation task of Figure 4b , there is only 1 correct answer, whereas for the task in Figure 4a there can be many correct solutions. We also present example predictions of our model for function evaluations by plotting the top predicted values for cos on samples of test data in Figure 4c .

5. CONCLUSIONS AND FUTURE WORK:

In this paper we proposed combining black-box function evaluation data with symbolic expressions to improve the accuracy and broaden the applicability of previously proposed models in this domain.

We apply this to the novel task of validating and completing mathematical equations. We studied the space of trigonometry and elementary algebra as a case study to validate the proposed model. We also proposed a novel approach for generating a dataset of mathematical identities and generated identities in trigonometry and elementary algebra. As noted, our data generation technique is not limited to trigonometry and elementary algebra. We show that under various experimental setups, Tree LSTMs trained on a combination of symbolic expressions and black-box function evaluation achieves superior results compared to the state-of-the-art models.

In our future work we will expand our testbed to include other mathematical domains, inequalities, and systems of equations. What is interesting about multiple domains is to investigate if the learned representations for one domain can be transfered to the other domains, and whether the embedding of each domain are clustered close to each other similar to the way the word embedding vectors behave. We are also interested in exploring recent neural models with addressable differentiable memory, in order to evaluate whether they can handle equations of much higher complexity.

:

https://en.wikipedia.org/wiki/List_of_trigonometric_identities

Our dataset generation method, proposed model, and data is available here: https://github.com/ ForoughA/neuralMath

Figures and Tables:

Figure 1: Identities and their Expression Trees. with (a) a symbolic expression, (b) a function evaluation, and (c) a number represented as the decimal tree (also part of the function evaluation data)

Figure 2: Tree-structured recursive neural model, for the trees in Figure 1a (left) and 1b (right)

Figure 3: Evaluating Equation Completion, Figure 3a shows the top-k accuracy of the symbolic data for different methods, and Figure 3b illustrates the minimum MSE of the top-k predictions, for the function evaluation data.

Figure 4: Examples of Equation Completion of the Tree LSTM + data model. Figures4a and 4bshow examples of equation completion from the test set where the predictions are ranked by model's confidence and the correct prediction is shown in boldface. Figure4cdepicts the predicted values of cos(x) with blue dots for x in[-3.14,3.14]  in the test set

Symbols in our grammar, i.e. the functions, variables, and constants

Table content: <table><tr><td/><td colspan="3">Unary functions, F 1</td><td/><td colspan="2">Terminal, T</td><td>Binary, F 2</td></tr><tr><td>sin</td><td>cos</td><td>csc</td><td>sec</td><td>tan</td><td>0</td><td>1</td></tr><tr><td>cot</td><td colspan="4">arcsin arccos arccsc arcsec</td><td>2</td><td>3</td></tr><tr><td colspan="2">arctan arccot</td><td>sinh</td><td>cosh</td><td>csch</td><td>4</td><td>10</td></tr><tr><td colspan="5">sech arcsch arsech artanh arcoth tanh coth arsinh arcosh exp</td><td>0.5 0.4</td><td>-1 0.7</td></tr><tr><td/><td/><td/><td/><td/><td>π</td><td>x</td></tr></table>

Examples of generated equations

Table content: <table><tr><td>Examples of correct identities</td><td>Examples of incorrect identities</td></tr></table>

Generalization Results: the train and the test contain equations of the same depth[1,2,3,4]. Results are on unseen equations. Sym refers to accuracy of Symbolic expressions and F Eval refers to MSE of function evaluation expressions. The last four columns measure the accuracy of symbolic expressions of different depths.

Table content: <table><tr><td>Approach</td><td colspan="6">Sym F Eval depth 1 depth 2 depth 3 depth 4</td></tr><tr><td>Test set size</td><td>3527</td><td>401</td><td>7</td><td>542</td><td>2416</td><td>563</td></tr><tr><td>Majority Class</td><td>50.24</td><td>-</td><td>28.57</td><td>45.75</td><td>52.85</td><td>43.69</td></tr><tr><td>Sympy</td><td>81.74</td><td>-</td><td>85.71</td><td>89.11</td><td>82.98</td><td>69.44</td></tr><tr><td>RNN</td><td>66.37</td><td>-</td><td>57.14</td><td>62.93</td><td>65.13</td><td>72.32</td></tr><tr><td>LSTM</td><td>81.71</td><td>-</td><td>85.71</td><td>79.49</td><td>80.81</td><td>83.86</td></tr><tr><td>TreeNN</td><td>92.06</td><td>-</td><td>100.0</td><td>95.37</td><td>94.16</td><td>87.45</td></tr><tr><td>TreeLSTM</td><td>95.18</td><td>-</td><td>85.71</td><td>96.50</td><td>95.07</td><td>94.50</td></tr><tr><td>TreeNN + data</td><td colspan="2">93.60 0.191</td><td>100.0</td><td>94.1</td><td>93.13</td><td>95.11</td></tr><tr><td colspan="3">TreeLSTM + data 97.20 0.047</td><td>71.42</td><td>98.29</td><td>97.45</td><td>96.00</td></tr></table>

Extrapolation Evaluation to measure capability of the model to generalize to unseen depth on symbolic equations

Table content: <table><tr><td>Approach</td><td/><td colspan="6">Train depth:1,2,3; Test depth: 4 Train depth:1,3,4; Test depth: 2</td></tr><tr><td/><td/><td colspan="6">Accuracy Precision Recall Accuracy Precision Recall</td></tr><tr><td>Majority Class</td><td/><td>55.22</td><td>0</td><td/><td>0</td><td>56.21</td><td>0</td><td>0</td></tr><tr><td>RNN</td><td/><td>65.15</td><td colspan="2">68.61</td><td>75.51</td><td>71.27</td><td>82.98</td><td>43.27</td></tr><tr><td>LSTM</td><td/><td>76.40</td><td colspan="2">71.62</td><td>78.35</td><td>79.31</td><td>75.27</td><td>79.31</td></tr><tr><td>TreeNN</td><td/><td>88.36</td><td colspan="2">87.87</td><td>85.86</td><td>92.58</td><td>89.04</td><td>94.71</td></tr><tr><td>TreeLSTM</td><td/><td>93.27</td><td colspan="2">90.20</td><td>95.33</td><td>94.78</td><td>94.15</td><td>93.90</td></tr><tr><td>TreeNN + data</td><td/><td>93.34</td><td colspan="2">90.34</td><td>95.33</td><td>93.36</td><td>89.75</td><td>95.78</td></tr><tr><td>TreeLSTM + data</td><td/><td>96.17</td><td colspan="2">92.97</td><td>97.15</td><td>97.37</td><td>96.08</td><td>96.86</td></tr><tr><td>2</td><td>4</td><td>6</td><td>8</td><td>10</td><td/><td/></tr></table>

Peer review (iclr2018):
 SUMMARY The model evaluates symbolic algebraic/trigonometric equalities for validity, with an output unit for validity level at the root of a tree of LSTM nodes feeding up to the root; the structure of the tree matches the parse tree of the input equation and the type of LSTM cell at each node matches the symbol at that node in the equation: there is a different cell type for each symbol. It is these cell types that are learned. The training data includes labeled true and false algebraic/trigonometric identities (stated over symbols for variables) as well as function-evaluation equalities such as "tan(0.28) = 0.29" and decimal-expansion equations like "0.29 = 2*10^(-1) + 9*10^(-2)". I believe continuous values like "0.29" in the preceding expressions are encoded as the literal value of a single unit (feeding into an embedding unit of type W_{num}), whereas the symbols proper (including digit numerals) are encoded as 1-hot vectors (feeding into an embedding unit of type W_{symb}). Performance is at least 97% when testing on unseen expressions of the same depth (up to 4) as the training data. Performance when trained on 3 levels (among 1 - 4) and testing on generalization to the held-out level is at least 96% when level 2 is held out, at least 92% when level 4 is withheld. Performance degrades (even on symbolic identities) when the function-evaluation equalities are omitted, and degrades when LSTM cells are replaced by plain RNN cells. The largest degradation is when the tree structure is replaced (presumably) by a sequence structure. Performance was also tested on a fill-in-the-blank test, where a symbol from a correct equation was removed and all possible replacements for that symbol with expressions of depth up to 2 were tested, then ranked by the resulting validity score from the model. From the graph it looks like an accuracy of about 95% was achieved for the 1-best substituted expression (accuracy was about 32% for a sequential LSTM). WEAKNESSES * The title is misleading; "blackbox function evaluation" does not suggest what is intended, which is training on function-evaluation equations. The actual work is more interesting than what the title suggests. * The biggest performance boost (roughly 15%) arises from use of the tree structure, which is given by an oracle (implemented in a symbolic expression parser, presumably): the network does not design its own example-dependent structure. * What does the sympy baseline mean in Table 2? We are only told that sympy is a "symbolic solver". Yet the sympy performance scores are in the 70-80% range. If the solver’s performance is that weak, why is it used during generation of training data to determine the validity of possible equations? * Given that this is a conference on "learning representations" it would have been nice to see at least a *little* examination of the learned representations. It would be easy to do some interesting tests. How well does the vector embedding for "2*10^(-1) + 9*10^(-2)" match the vector for the real value 0.29? W_{num} embeds a continuum of real values in R^d: what is this 1-dimensional embedding manifold like? How do the embeddings of different integers provided by W_{sym} relate to one another? My rating would have been higher had there been some analysis of the learned representations. * We are told only that the "hidden dimension … varies"; it would be nice if the text or results tables gave at least some idea of what magnitude of embedding dimension we’re talking about. STRENGTHS The weaknesses above notwithstanding, this is a very interesting piece of work with impressive results. * The number of functions learned, 28, is a quantum jump from previous studies using 8 or fewer functions. * It is good to see the power of training the same system to learn the semantics of functions from the equations they satisfy AND from the values they produce. * The inclusion of decimal-expansion equations for relating numeral embeddings to number embeddings is clever. * The general method used for randomly generating a non-negligible proportion of true equations is useful. * The evaluation of the model is thorough and clear. * In fact the exposition in the paper as a whole is very clear.