# Automatic Symbolic Equation Generator

*Developed by Forough Arabshahi*

This notebook presents the code for the automatic dataset generation scheme presented in [this](https://openreview.net/forum?id=Hksj2WWAW&noteId=Hksj2WWAW) paper.

This equation generation approach is based on generating new mathematical identities by performing local random changes to known identities, starting with a small number of axioms from the domain under study. 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 a grammar. The grammar and its rules are defined in detail in [section 2.1 of the paper](https://openreview.net/forum?id=Hksj2WWAW&noteId=Hksj2WWAW). In this notebook we choose elementary algebra and trigonometry as the domain under study.

### Generating Possible Equations
<a id="sec:posEq"></a>
In order to generate a new identity which may be correct or incorrect, we select an equation at random from the set of known equations, and make local changes to it. We 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.

This is implemented in a function called *genNegEquation*

### Generating Additional Correct Equations
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(\theta) + \cos^2(\theta) = 1$, this subtree matching might produce equality $\cos^2(\theta) + \sin^2(\theta) = 1$ by finding key-value pair $x + y : y + x$.

This is implemented in a function called *genPosEquation*

***

## Implementation Details

The dependency for this notebook if the [latex2sympy](https://github.com/augustt198/latex2sympy) package which converts a latex equation to sympy. Set the path to latex2sympy in file eqGen.py available in the root folder. Our equations are represented using the *EquationTree* object. The attributes of this object are: 
1. func: string that stores the function name
2. args: list of EquationTree objects that are the children of this node
3. varname: string that stores the variable name if the node is a leaf, otherwise this is ''
4. number: integer that indicates the node's unique number
4. depth: integer that indicates the depth of the subtree that is attached to the node.

below is an example of some equations

$\sin^2(\theta) + \cos^2(\theta) = 1$ | $\sin(-2.5) = -0.6$ | Decimal expression tree for $2.5$
- | - | -
  |  | 

### 1. Importing Modules
<a id="sec:import"></a>

Most of the functions are implemented in *eqGen.py*. *readJson* reads an input json in latex format and uses latex2sympy to convert it to a sympy equation. Finally, *buildEq* converts a sympy equation to an EquationTree object. *readAxioms* reads an input txt file and uses the compiler package to convert the equations to a compiler object. Function *parseEquation* then converts this to an EquationTree object. *writeJson* saves the generated EquationTree objects in a json file.


```python
!pip install -i https://pypi.anaconda.org/pypi/simple antlr4-python2-runtime
```

    Collecting antlr4-python2-runtime
      Downloading https://pypi.anaconda.org/pypi/simple/antlr4-python2-runtime/4.4.1/antlr4-python2-runtime-4.4.1.tar.gz (107kB)
    [K    100% |################################| 112kB 672kB/s ta 0:00:01
    [?25hBuilding wheels for collected packages: antlr4-python2-runtime
      Running setup.py bdist_wheel for antlr4-python2-runtime ... [?25ldone
    [?25h  Stored in directory: /home/nbuser/.cache/pip/wheels/0e/2a/00/359c1581cca44aca5faffb568a96adb6bf4a8508754188d365
    Successfully built antlr4-python2-runtime
    Installing collected packages: antlr4-python2-runtime
    Successfully installed antlr4-python2-runtime-4.4.1



```python
!git clone https://github.com/augustt198/latex2sympy
```

    Cloning into 'latex2sympy'...
    remote: Counting objects: 174, done.[K
    remote: Total 174 (delta 0), reused 0 (delta 0), pack-reused 174[K
    Receiving objects: 100% (174/174), 49.94 KiB | 0 bytes/s, done.
    Resolving deltas: 100% (104/104), done.
    Checking connectivity... done.



```python
!cd latex2sympy; antlr4 PS.g4 -o gen
```

    /bin/sh: antlr4: command not found



```python
!pip install mxnet
```

    Requirement already satisfied: mxnet in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages
    Requirement already satisfied: requests in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from mxnet)
    Requirement already satisfied: numpy in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from mxnet)
    Requirement already satisfied: graphviz in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from mxnet)
    Requirement already satisfied: chardet<3.1.0,>=3.0.2 in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from requests->mxnet)
    Requirement already satisfied: idna<2.7,>=2.5 in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from requests->mxnet)
    Requirement already satisfied: urllib3<1.23,>=1.21.1 in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from requests->mxnet)
    Requirement already satisfied: certifi>=2017.4.17 in /home/nbcommon/anaconda2_501/lib/python2.7/site-packages (from requests->mxnet)



```python
import json
from sympy import *
import pprint
import re
import copy
import random
import compiler
import mxnet as mx
import numpy as np
import sys
sys.path.append("./latex2sympy")
from eqGen import readJson, readAxioms, parseEquation, buildEq, buildAxiom, genPosEquation,\
                  genNegEquation, isCorrect, writeJson
from neuralAlgonometry import catJsons
```

### 2. Parsing input axioms
<a id="sec:axioms"></a>

In this section we a small set of input axioms from trigonometry and elementary algebra and convert them to EquationTree objects. trigonometry equations are in file *"axioms/trigonometryAxioms.json"* which are collected from the wikipedia [List of Trigonometric Identities](https://en.wikipedia.org/wiki/List_of_trigonometric_identities) page. Elementary algebra equations are in file *"axioms/algebraAxioms.txt"* and are hand generated.


```python
# path to trigonometry equations collected from wiki
inputPath = "axioms/trigonometryAxioms.json"
# path to some axioms from elementary algebra
axiomPath = "axioms/algebraAxioms.txt"
jsonAtts = ["equation", "range", "variables","labels"]

labels = []
inputRanges = []
inputEquations = [] 
eqVariables = []
parsedEquations = []
parsedRanges = []
ranges = []
inputAxioms = []
axiomVariables = []
axioms = []
axLabels = []

random.seed(1)
```

Function *readJson* parses latex equations. An example of the resulting output is given below


```python
# parses latex equations from file:
readJson(inputPath, inputEquations, inputRanges, jsonAtts)
inputEquations[1]
```




    '\\sin\\theta = \\frac{1}{\\csc\\theta}'



We use function *parseEquation* to convert these equations to a sympy equation using the latex2sympy package. An example of the output equation follows:


```python
# Converts latex equations to sympy equations using process_latex
parseEquation(inputEquations, parsedEquations, eqVariables)
parsedEquations[1]
```




    Eq(sin(theta), 1/csc(theta))



Function *buildEq* converts each sympy equation to an EquationTree object as shown below. The pre order traversal of the parsed equation is also shown as an example


```python
# converts equations from sympy format to EquationTree object
# equations pretty print as well as pre order traversal follows
equations = []
for i, eq in enumerate(parsedEquations):
    # building EquationTree object
    currEq = buildEq(eq, eqVariables[i])
    # assigning a unique number to each node in the tree as well as indicating subtree depth at each level
    currEq.enumerize_queue()
    equations.append(currEq)
    
    # creating training labels
    # the first equation in the input function is incorrect. It has been deliberately added
    # to include all possible functionalities in the functionDictionary. 
    # This is for compatibility with MxNet's bucketingModule.
    if i == 0:
        labels.append(mx.nd.array([0]))
    else:
        labels.append(mx.nd.array([1]))
    
print "currEq:", equations[1]
print "pre order traversal"
equations[1].preOrder()
```

    currEq: Eq(sin(var_0),Pow(csc(var_0),-1))
    pre order traversal
    functionality: Equality
    assigned node number: 0
    subtree depth: 3
    functionality: sin
    assigned node number: 1
    subtree depth: 2
    variable name: var_0
    functionality: Symbol
    assigned node number: 3
    subtree depth: 1
    functionality: Pow
    assigned node number: 2
    subtree depth: 2
    functionality: csc
    assigned node number: 4
    subtree depth: 1
    variable name: var_0
    functionality: Symbol
    assigned node number: 6
    subtree depth: 0
    variable name: -1
    functionality: NegativeOne
    assigned node number: 5
    subtree depth: 1


After parsing trigonometry axioms, we start parsing algebra axioms using python's built in compiler and function *readAxioms*. The parsed equation is shown below:


```python
# parses text equations using the compiler package and returns an equation in the compiler format
readAxioms(axiomPath, inputAxioms, axiomVariables)
inputAxioms[0]
```




    Compare(Add((Const(1), Const(1))), [('==', Const(2))])



Once we have the compiler object, we can convert it to an EquationTree object using function *buildAxiom*. An example parsed equation as well its pre order parse is given below.


```python
# converting compiler object axioms to EquationTree objects and creating training labels
for i, ax in enumerate(inputAxioms):
    currAxiom = buildAxiom(ax, axiomVariables[i])
    currAxiom.enumerize_queue()
    axioms.append(currAxiom)
    axLabels.append(mx.nd.array([1]))
    
print "an axiom:", axioms[0]
print "pre order traversal:"
axioms[0].preOrder()
```

    an axiom: Eq(Add(1,1),2)
    pre order traversal:
    functionality: Equality
    assigned node number: 0
    subtree depth: 2
    functionality: Add
    assigned node number: 1
    subtree depth: 1
    variable name: 1
    functionality: One
    assigned node number: 3
    subtree depth: 0
    variable name: 1
    functionality: One
    assigned node number: 4
    subtree depth: 0
    variable name: 2
    functionality: Integer
    assigned node number: 2
    subtree depth: 1



```python
# appending algebra axioms to trigonometry axioms
equations.extend(axioms)
eqVariables.extend(axiomVariables)
labels.extend(axLabels)
print len(equations)
print len(eqVariables)
print len(labels)
```

    148
    148
    148


The distribution of the depth of the equations, that contains all axioms from trigonometry and algebra, is shown below. The vector shows the number of equations of depth *i* at *i*th vector position.


```python
depthMat = [0 for _ in range(26)]
for eq in equations:
    depthMat[eq.depth] += 1
print "distribution of depth of equations"
print depthMat[:10]
```

    distribution of depth of equations
    [0, 10, 35, 39, 21, 29, 7, 6, 0, 0]


### 3. Contructing the mathDictionary
<a id="sec:dict"></a>

Here, we construct the *mathdictionary* which is used for generating additional correct identities. This dictionary contains (key, value) pairs that are mathematically equivalent. E.g. $(x+y : y+x)$ is a (key,value) pair in the mathDictionary


```python
# constructing the mathDictionary whose (key,value) pairs are valid math equalities
# e.g. (x+y : y+x) is a (key,value) pair in the mathDictionary
# the dictionary will be updated as more correct equations are generated
mathDictionary = {}
strMathDictionary = {}
for i, eq in enumerate(equations):
    if i!=0:
        eqCopy = copy.deepcopy(eq)
        if str(eqCopy) not in strMathDictionary:
            strMathDictionary[str(eqCopy)] = 1
            mathDictionary[eqCopy.args[0]] = eqCopy.args[1]
            mathDictionary[eqCopy.args[1]] = eqCopy.args[0]
        else:
            strMathDictionary[str(eqCopy)] += 1
# for k, v in strMathDictionary.iteritems():
#     print k, v
print len(strMathDictionary)
print len(mathDictionary)
```

    147
    294


### 4. Generating correct equations using mathDictionary lookup
<a id="sec:subtreeMatching"></a>

Function *genPosEquation* generates a candidate correct equation using subtree matching from a dictionary lookup. More specifically, it chooses a random node of the equation and looks for patterns in the dictionary key that match the subtree of the chosen node. The subtree is then replaced by the dictionary key's value. 

The code snippet below generates about 10 correct equations by making local changes to equations selected at random from the input axioms. If no duplicate equation is generated, this equation will be added to the list of equations. The depth of the generated equation is limited to 7 (*maxDepth*). parameter *maxDepthSoFar* along with *thrsh* control the generated number of equations of a certain depth before moving to the next depth. This is a good control for training since it ensures that a minimum number of equations of each depth are present in the final dataset. It shoul dbe noted that as depth increases, the space grows exponentially, and this does not aim to cover this exponential space. 

The distribution of the generated equations are shown below. 


```python
maxDepth = 7
numPosEq = 10
numNegEq = 10
numNegRepeats = 2
thrsh = 5

# set maxDepthSoFar to 0 to generate up to thrsh number of 
# repeated equations before moving to equations of higher depth
maxDepthSoFar = 7
totDisc = 0
for i in range(0, numPosEq):
    randInd = random.choice(range(1, len(equations)))
    while labels[randInd].asnumpy() == 0:
        randInd = random.choice(range(1, len(equations)))
    randEq = copy.deepcopy(equations[randInd])
    randEqVariable = copy.deepcopy(eqVariables[randInd])

    posEq = genPosEquation(randEq, mathDictionary, randEqVariable)
    posVars = posEq.extractVars()
    posEq.enumerize_queue()

    old = 0
    disc = 0
    tries = 0
    # this loop is to make sure there are no repeats and also that enough 
    # number of equations of a certain depth are generated
    while str(posEq) in strMathDictionary or posEq.depth > maxDepthSoFar:
        if str(posEq) in strMathDictionary:
            strMathDictionary[str(posEq)] += 1
            old += 1
            totDisc += 1
        elif posEq.depth > maxDepthSoFar:
            disc += 1
            totDisc += 1

        if old > thrsh:
            old = 0
            maxDepthSoFar += 1
            print "new max depth %d" %(maxDepthSoFar)
            if maxDepthSoFar > maxDepth:
                print "reached maximum depth"
                maxDepthSoFar = maxDepth
                break

        randInd = random.choice(range(1, len(equations)))
        randEq = equations[randInd]
        randEqVariable = copy.deepcopy(eqVariables[randInd])
        posEq = genPosEquation(randEq, mathDictionary, randEqVariable)
        posVars = posEq.extractVars()
        posEq.enumerize_queue()

    if posEq.depth <= maxDepth:
        posEqCopy = copy.deepcopy(posEq)

        if str(posEqCopy) not in strMathDictionary:
            strMathDictionary[str(posEqCopy)] = 1
            if posEqCopy.args[0] not in mathDictionary:
                mathDictionary[posEqCopy.args[0]] = posEqCopy.args[1]
            if posEqCopy.args[1] not in mathDictionary:
                mathDictionary[posEqCopy.args[1]] = posEqCopy.args[0]

            equations.append(posEq)
            eqVariables.append(posVars)
            labels.append(mx.nd.array([1]))
    else:
        totDisc += 1
        print "discarded pos equation of depth greater than %d: %s" %(maxDepth, str(posEq))

depthMat = [0 for _ in range(26)]
for eq in equations:
    depthMat[eq.depth] += 1
print "distribution of depth of equations"
print depthMat
```

    distribution of depth of equations
    [0, 10, 36, 41, 24, 29, 11, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]


### 5. Generating correct and incorrect equations using local changes
<a id="sec:valid"></a>

Function *genNegEquation* generated a candidate correct or incorrect mathematical equation. This function takes as input an EquationTree object. It selects a node chosen at random from that equations and performs one of the operations explained in [this section](#sec:posEq) to the node depending on the type of node. We check the correctness or incorrectness of this generated equation using function *isCorrect* that uses sympy. The depth of the final equations are shown below.


```python
# generating negative equations
negLabels= [[] for _ in range(numNegRepeats)]
negEquations = [[] for _ in range(numNegRepeats)]
negEqVariables = [[] for _ in range(numNegRepeats)]
negStrMathDictionary = {}
corrNegs = 0
totDiscNeg = 0
ii = len(equations)
for i in range(1, len(equations)): 
    for rep in range(numNegRepeats):
        randInd = i
        randEq = copy.deepcopy(equations[i])
        randEqVariable = copy.deepcopy(eqVariables[randInd])

        negEq = genNegEquation(randEq, randEqVariable)
        negVars = negEq.extractVars()
        negEq.enumerize_queue()
        disc = 0
        tries = 0
        old = 0
        while str(negEq) in negStrMathDictionary or negEq.depth > maxDepth:
            if str(negEq) in negStrMathDictionary:
                negStrMathDictionary[str(negEq)] += 1
                old += 1
                totDiscNeg += 1
                # print "repeated neg equation"
            elif negEq > maxDepth:
                # print "equation larger than depth"
                disc += 1
                totDiscNeg += 1

            if old > thrsh:
                old = 0
                break

            negEq = genNegEquation(randEq, randEqVariable)
            negVars = negEq.extractVars()
            negEq.enumerize_queue()

        if negEq.depth <= maxDepth:
            
            negEqCopy = copy.deepcopy(negEq)
            try:
                isCorrect(negEq)

                if isCorrect(negEq):
                    corrNegs += 1

                    print "correct negative Eq:", negEq

                    if str(negEq) not in strMathDictionary:

                        strMathDictionary[str(negEqCopy)] = 1
                        if negEqCopy.args[0] not in mathDictionary:
                            mathDictionary[negEqCopy.args[0]] = negEqCopy.args[1]
                        if negEqCopy.args[1] not in mathDictionary:
                            mathDictionary[negEqCopy.args[1]] = negEqCopy.args[0]

                        labels.append(mx.nd.array([1]))
                        equations.append(negEq)
                        eqVariables.append(negVars)

                elif str(negEqCopy) not in negStrMathDictionary:
                        negStrMathDictionary[str(negEqCopy)] = 1

                        negLabels[rep].append(mx.nd.array([0]))
                        negEquations[rep].append(negEq)
                        negEqVariables[rep].append(negVars)
                else:
                    totDiscNeg += 1

            except:

                if str(negEqCopy) not in negStrMathDictionary:
                    negStrMathDictionary[str(negEqCopy)] = 1

                    negLabels[rep].append(mx.nd.array([0]))
                    negEquations[rep].append(negEq)
                    negEqVariables[rep].append(negVars)
                else:
                    totDiscNeg += 1

        else:
            totDiscNeg += 1
            print "discarded neg equation of depth greater than %d: %s" %(maxDepth, str(negEq))

depthMat = [0 for _ in range(26)]
for eq in negEquations[0]:
    depthMat[eq.depth] += 1
print "distribution of depth of neg equations"
print depthMat
```

    correct negative Eq: Eq(sec(Mul(1,var_0)),sec(var_0))
    correct negative Eq: Eq(tan(Add(Mul(pi,Pow(2,-1)),Mul(-1,Mul(var_0,1)))),cot(var_0))
    correct negative Eq: Eq(cot(Add(var_0,Add(pi,pi))),cot(var_0))
    correct negative Eq: Eq(Mul(0,-1),0)
    correct negative Eq: Eq(Pow(0,2),0)
    correct negative Eq: Eq(Mul(0,2),Mul(0,2/5))
    correct negative Eq: Eq(Mul(0,3),Mul(0,pi))
    correct negative Eq: Eq(Mul(Mul(0,0),1),0)
    correct negative Eq: Eq(Mul(0.7,0),0)
    correct negative Eq: Eq(Pow(1,1/2),Add(1,0))
    correct negative Eq: Eq(Pow(1,Mul(1/2,var_0)),1)
    correct negative Eq: Eq(1,1)
    correct negative Eq: Eq(1,1)
    correct negative Eq: Eq(Pow(pi,0),1)
    correct negative Eq: Eq(Pow(4,tanh(0)),1)
    correct negative Eq: Eq(tan(Add(0,0)),0)
    correct negative Eq: Eq(0,0)
    correct negative Eq: Eq(Add(Mul(0,var_0),var_0),var_0)
    correct negative Eq: Eq(asin(Mul(0,var_0)),0)
    correct negative Eq: Eq(Mul(Mul(Pow(var_1,1),var_2),var_0),Mul(var_1,Mul(var_0,var_2)))
    correct negative Eq: Eq(Mul(Add(-1,var_0),0),0)
    correct negative Eq: Eq(0,0)
    correct negative Eq: Eq(Add(var_0,var_0),Add(var_0,var_0))
    distribution of depth of neg equations
    [0, 5, 20, 45, 25, 31, 12, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


### 6. Saving the generated dataset
<a id="sec:save"></a>

Finally, we would like to save the resulting dataset which will be used to train neural network models for mathematical equalities. Function *writeJson* writes this resulting dataset to a json. In order to save an EquationTree object, we use the pre-order traversal of each equation. E.g. In order to save equation $0=0$, we construct:

"equation": {
               * "vars": ",0,#,#,0,#,#", 
               * "numNodes": "3", 
               * "variables": {}, 
               * "depth": "1,0,#,#,0,#,#", 
               * "nodeNum": "0,1,#,#,2,#,#", 
               * "func": "Equality,Integer,#,#,Integer,#,#"
            },
            
Where # indicates a null pointer. It should be noted that the trees are binary. 

Finally function *catJsons* concatenates all the created jsons into a single file containing correct and incorrect equations that can be loaded for training.


```python
# writing equations to file
writeJson("data/data%d_pos.json"%(numPosEq), equations, ranges, eqVariables, labels, maxDepth)
for rep in range(numNegRepeats):
    writeJson("data/data%d_neg_rep%d.json"%(numNegEq,rep), negEquations[rep], ranges, negEqVariables[rep], negLabels[rep], maxDepth)
```

    data/data10_pos.json : [1, 10, 42, 49, 26, 30, 11, 6]
    data/data10_neg_rep0.json : [0, 5, 20, 45, 25, 31, 12, 8]
    data/data10_neg_rep1.json : [0, 6, 26, 40, 25, 30, 11, 7]



```python
catJsons(['data/data%d_pos.json'%(numPosEq), 'data/data%d_neg_rep%d.json'%(numNegEq,0), 'data/data%d_neg_rep%d.json'%(numNegEq,1)],
          'data/data%d_final.json'%(numPosEq), maxDepth=maxDepth)
```


```python

```

8608fd5e8743a831d13590838f9048a5f6fa8b2b
ipynb
Jupyter Notebook
mltrain-nips-2017/forough_arabshahi/notebooks/equationGenerator.ipynb
gopala-kr/ds-notebooks
bc35430ecdd851f2ceab8f2437eec4d77cb59423
MIT
2019-05-10T09:16:23.000Z
2019-05-10T09:16:23.000Z
mltrain-nips-2017/forough_arabshahi/notebooks/equationGenerator.ipynb
gopala-kr/ds-notebooks
bc35430ecdd851f2ceab8f2437eec4d77cb59423
MIT
mltrain-nips-2017/forough_arabshahi/notebooks/equationGenerator.ipynb
gopala-kr/ds-notebooks
bc35430ecdd851f2ceab8f2437eec4d77cb59423
MIT
2019-05-10T09:17:28.000Z
2019-05-10T09:17:28.000Z
Qwen/Qwen-72B
1. YES
2. YES