While it has become common to perform automated translations on natural language, performing translations between different representations of mathematical formulae has thus far not been possible. We implemented the first translator for mathematical formulae based on recursive neural networks. We chose recursive neural networks because mathematical formulae inherently include a structural encoding. In our implementation, we developed new techniques and topologies for recursive tree-to-tree neural networks based on multi-variate multi-valued Long Short-Term Memory cells. We propose a novel approach for minibatch training that utilizes clustering and tree traversal. We evaluate our translator and analyze the behavior of our proposed topologies and techniques based on a translation from generic LATEX to the semantic LATEX notation. We use the semantic LATEX notation from the Digital Library for Mathematical Formulae and the Digital Repository for Mathematical Formulae at the National Institute for Standards and Technology. We find that a simple heuristics-based clustering algorithm outperforms the conventional clustering algorithms on the task of clustering binary trees of mathematical formulae with respect to their topology. Furthermore, we find a mask for the loss function, which can prevent the neural network from finding a local minimum of the loss function. Given our preliminary results, a complete translation from formula to formula is not yet possible. However, we achieved a prediction accuracy of 47.05% for predicting symbols at the correct position and an accuracy of 92.3% when ignoring the predicted position. Concluding, our work advances the field of recursive neural networks by improving the training speed and quality of training. In the future, we will work towards a complete translation allowing a machine-interpretation of LATEX formulae.
Most mathematical formulae are denoted in presentation language (PL) [
The National Institute for Standards and Technology (NIST), the Digital Library for Mathematical Formulae
(DLMF), and the Digital Repository for Mathematical Formulae (DRMF) developed a set of LATEX macros that
allow an unambiguous mathematical notation within LATEX [
Thus, we experimented with a standalone neural disambiguation that classifies which semantic LATEX macro is most likely to be correct. To use this approach, we would require a rule-based translator that utilizes the neural network only in ambiguous cases.
Rule-based translators are not readily transferable to other mathematical languages. Furthermore, they require a very complex program that depends on the input and output language and are also hard to maintain if the languages are extended or a new language should be added.
Therefore, we use machine learning methods to build a full translator as announced in [
Recently, recurrent neural networks with sequence-to-sequence models yielded state-of-the-art results on natural
language translation tasks [
As sequential recurrent neural networks don’t utilize the tree-like structure of input and output, they lack precision in the domain of structure.
An alternative to recurrent neural networks is recursive neural networks, which are not linear but have a tree-like structure.
By building a recursive neural network, the neural network explicitly receives information on the location of the respective words and symbols. As soon as this information is relevant for the translation, a recursive neural network can yield better results than a recurrent neural network. Further, recursive neural networks have a lower depth than recurrent neural networks. Thus, the problem of exploding or vanishing gradients is reduced.
In most cases, no structural information about natural language is given. Therefore, it is required to deduce a structure for these sentences. Finding such a structure is ambiguous and error-prone. Mathematical formulae often allow a straightforward derivation of the semantic structure or are already given in a structured format. Thus, we believe that utilizing recursive neural networks is a promising approach for the automatic translation of mathematical formulae.
In summary, our research contributes towards: • the disambiguation of mathematical formulae, and • the neural machine translation of mathematical formulae. • faster training by using a semi-batched computation, and • a local minima avoiding loss function for decoders.
Furthermore, our research yields the following contributions for recursive neural networks: The contributions for recursive neural networks may also be applicable to other machine-learning tasks, including sentiment analysis.
We structure the presentation of our contributions as follows. Section 2 presents an overview of prior research. Section 3 states the problem of translation and presents our neural network approach. Section 4 presents the applied preprocessing steps for the formulae. Section 5 presents our evaluation techniques and current results. Section 6 discusses our results and conclusions. Finally, avenues for future work are presented in section 7. 2
To the best of our knowledge, no research towards machine learning translation for mathematical formulae between different representations has been performed thus far. Our research towards machine translation of mathematical formulae will enable future work on various topics from automated checking of mathematical formulae to plagiarism detection.
There have already been rule-based attempts to translate between mathematical languages. There exists
a rule-based translator from semantic LATEX to CASs (e.g., Maple) [
State-of-the-art for language translation uses recurrent neural networks employing, e.g., Long Short-Term
Memory (LSTM) cells in sequence-to-sequence networks [
In recent time, also recursive neural networks have been used for the translation of structured data in tree-to-tree
networks. Chen et al. used tree-to-tree networks for program translation [
Tai et al. [
This means that we use a neural network whose encoder and decoder have the same topology as the binary
parse tree of the input formula respectively output formula. Therefore, the structure of the input defines the
topology of the neural network. Thus, in general, for the training of recursive neural networks, a batched
computation is not directly possible. A reason for that is that trees with different topologies usually cannot
share one neural network [
In this section, we will present the problem of translation of trees and give an overview of our approach. Further, we will present our method for a standalone disambiguation and comment on our implementation.
DLMF/DRMF train. set formulae (generic + semantic LATEX pairs) val. set
mentation
generic semantic Let x ∈ X be the binary parse tree of a generic LATEX formula. Further, let y ∈ Y be the respective binary parse tree of the semantic LATEX translation of x. In these binary trees, only the leaves are labeled with positive integers corresponding to the words and symbols of the formula, all other nodes are labeled as zero.
Further, let xa for a, being a binary tree with a ⊃ x, be a tree with the topology of a and the values of x padded with the tag yend with respect to the topology of a. Here, “a ⊃ b” means that for each node in b there is a node in a at the same position in the tree. The padding is performed such that a position is tagged with yend iff there is no node at the respective position in x.
We want to find a mapping f : X → Y, x 7→ y.
This mapping has to be derivable with respect to the tree topologies, the definition of our recursive neural network, and the trained weight and bias matrices.
Therefore, we create a neural network and generate a loss as a distance measure between the ground truth and the prediction. By minimizing the loss, we get an improved mapping. 3.2
Since we apply an additional tree traversal on the binary trees for the purpose of obtaining a better clustering, we need to consider this traversal inside the neural network. Each time we take or obtain two children, we lookup the stored traversal information T where T = 0 if the children were not exchanged and T = 1 if the children were exchanged in the preprocessing step. Then, we compute
(1 − T ) · (ULhkL + URhkR ) + T · (URhkL + ULhkR ) instead of
ULhkL + URhkR for the left and right children’s weight matrices UL, UR and the left and right children’s hidden states hkL , hkR . By this replacement, the neural network obtains the correct trees, while the topology of the neural network is independent of a clustering improving traversal.
We use this structure per layer, while the hidden state of a previous layer
is the input of the next layer. The input of the first layer of the encoder is
the embedding of the respective value in the input tree. The output of the
highest layer is used for the prediction. The prediction is computed by the
application of two embeddings on the output of a respective LSTM. We
initialize the weight matrices using the Xavier initializer [
In this section, we describe how we trained the aforementioned recursive neural network. We use the clusters of trees as mini-batches. As loss function, we use softmax cross-entropy.
Since the actual formula is only a subtree of the input for the neural networks with sizes of roughly about 30 − 60%, most nodes are padded with zeros and yends. This causes the primary influence on the loss to be the prediction of the padding zeros and yends. Thus, the neural network learns the local minimum of only predicting these recurrent values quickly.
Furthermore, the high occurrence frequency of tokens such as, “^” in mathematical formulae yields a strong bias towards predicting these tokens.
Therefore, we mask the loss function to lower the influence of commonly occurring symbols, such as parentheses, on the learning process. We achieve this by element-wise multiplication of the losses with the mask mi := (
β ||{yj|yi=yj}||α if yˆi = yi
1
||{yj|yi=yj}||α if yˆi 6= yi
where yˆ is the prediction and y is the correct translation. Here, α, β ∈ [
Because the speed of learning should be independent of the size of the input tree’s size and the local mini-batch size, we use reduce_sum instead of reduce_mean in order to weight every node equally and independent of the mini-batch in which it is included. The advantages of the common reduce_mean, easier search for a learning rate and better numeric stability, are outweighed in this case.
For training, we use the RMSProp optimizer [
As an alternative to directly feeding the encoder with the input formula and the decoder with the output formula, we can use two auto-encoders, one for the input formula and another one for the output formula. This means that the encoder, as well as the decoder, is fed with the same values. Thus, the auto-encoders are trained to simulate the identity function. Because the information has to be compressed to be preserved while being propagated through the neural network as a state of lower size, a fitting representation is learned. Subsequently, we can combine the auto-encoder of the input formula as the encoder and the auto-encoder of the output formula as the decoder to a new neural network. By having translators from an input tree to a vector and from another vector to an output tree, we can easily train a mapping between these representations. At firsts, we implemented a single-layer version of the neural network in TensorFlow. We found that in our case plain Python resulted in a speed increase of about 10 to 50 times compared to TensorFlow. TensorFlow was so slow because the recurrent changing of the neural network topology takes a long time in TensorFlow. Thus, a majority of the training time has been used by the creation of the neural network because we needed to recreate the neural network for each mini-batch. Further, TensorFlow is optimized for GPUs, yet we used CPUs because of a high memory demand. Therefore, we rewrote our TensorFlow code in plain Python utilizing numpy and autograd. While the TensorFlow implementation consumed up to 500GB of RAM for a single layer, our numpy implementation uses only up to 12GB of RAM with three layers. 4
This section describes the preprocessing steps from formula strings to clusters of formula trees.
For training and evaluation, we used 13 939 generic / semantic LATEX formula pairs from the DLMF/DRMF, NIST. As shown in Figure 1, we first apply data augmentation on the training set. Then, we parse the formulae to trees and cluster these trees with respect to their topology. 4.1
To achieve a robust neural network, we extended our dataset using the following mechanism. For this, we split our dataset on comparators1 since the subexpressions obtained by these splits are still valid mathematical expressions. We then take the single terms, every two and three adjacent terms, including one or two comparators, and the whole formula (less if less is given). The following example shows these steps. As a result of this data augmentation, we received a data set containing 51 217 mathematical terms.
→ 1. 2. 3. 4. 5.
− 2 3 π − δ 3 π + δ ≤ ph((λ2 − λ1)z) ≤ 2 3 π + δ − 2
3 π + δ ≤ ph((λ2 − λ1)z) − 2 ph((λ2 − λ1)z)
3 π − δ ph((λ2 − λ1)z) ≤ 2 3 π − δ 2 4.2
In the following, we will describe our heuristics based formula parser for transforming the formulae into only-leaflabeled binary parse trees.
Our parser first tokenizes the formula string. It then recursively transforms the token stream into a non-full n-ary tree. Structure-only generating braces and brackets are omitted, since the structure of the tree represents them. The following heuristics can either be activated or deactivated; due to lack of time, we have not yet 1We use =, \gt, \lt, \equiv, \asympeq, \sim, \[Rr]ightarrow, and \to thoroughly evaluated, how well these heuristics perform. In future work, we will carry out this evaluation. To achieve the results reported on in this paper, we have activated the first two heuristics.
• If a node forms a command, <COMMAND_END> is added as an additional terminating leaf. • If a node forms a concatenation on the same level (e.g., a + b), <CONCAT_END> is added as an additional terminating leaf. • Leaves that are infix operators are moved to the left, such that they are present in prefix notation.
After applying this tree traversal, we transform the n-ary tree into an adaptation of left-child right-sibling binary trees. I.e., we adapt left-child right-sibling binary trees to leaf-only valued trees. Here, the left child is the first child, and the right child is the same node excluding the first child.
The following example input illustrates the parsing and traversal process: \frac{2a}{n+\sqrt{2}}+\sqrt{3} n+2a√2 + √3
\frac { 2 a } { n + \sqrt { 2 } } + \sqrt { 3 } As shown in Figure 3, we generate an n-ary tree from this token stream. Next, we can (optionally) add the <COMMAND_END> and <CONCAT_END> tokens as shown in Figure 4. Additionally, we can (optionally) traverse the tree from infix to prefix notation as shown in Figure 5.
\frac 2 a n + \sqrt 2 + \sqrt 3 \frac 2 a n + \sqrt 2 + \sqrt 3 \frac 2 a <2> n + \sqrt 2 <1> <2> <1> + \sqrt 3 <1> \frac 2 a <2> n + \sqrt 2 <1> <2> <1> + \sqrt 3 <1> + \frac 2 a + n \sqrt 2 \sqrt 3 + \frac 2 a + n \sqrt 2 \sqrt 3
Now, we can perform a traversal to gain the right-child-biggest property. For this, we recursively exchange the children of a tree if the size of the left child is greater than that of the right child. For a reconstruction within the neural network, we store the information on which children of a tree we performed the exchange. Thus, we obtain trees that are more similar, which improves the clustering (i.e., increases the speed of training).
After the subsequent clustering, these binary trees serve as input for the neural network. Because the topology of the neural network depends on the input, we would have to generate a new neural network for each formula. Therefore, we apply a padding to the binary trees. To do this, we create a binary tree a with a topology greater or equal to every tree x ∈ X and compute xa, the padded version of x.
Generating the neural network for a for all trees, would result in having ∼ 80 000 nodes which would require approximately tens of Terabytes of RAM, which is impractical. Therefore, we cluster the pairs of binary trees (x, y) according to their topology.
We implemented numerous standard clustering algorithms, including k-means, DBSCAN, and linkagealgorithms. The results of these algorithms were insufficient. Therefore, we implemented Algorithm 1. For this algorithm, the choice of min-elems-list and max-size-list is crucial. The following choices yielded the best results: (1) (2) (3) (min-elems)i := $
2% · #trees to cluster ||min-elems||−p12% · #trees to cluster i−1
% (max-size)i := 5 ·
||max-size||−√1104 i−1
Result: clustering 1 clustering ← empty clustering 2 min-elems-list ← descending list (e.g., 20 exponential steps ⊂ [b2% · #trees to clusterc, 1]) 3 max-size-list ← ascending list (e.g., 20 exponential steps ⊂ [5, 5 · 104]) 4 for min-elems, max-size in min-elems-list, max-size-list do 5 clustering ← FindClusters (clustering, masks, minelems, maxsize) 6 end 6 7 8 9 10 end end end if number of elements in cluster < min-elems then
resolve cluster Algorithm 2: Find clusters
Data: clustering, masks, min-elems, max-size
Result: clustering 1 for mask in non-clustered masks do 2 initialize new cluster 3 while min{ kak | ∀e ∈ cluster : e ⊂ a} ≤ max-size do 4 Add all elements to cluster that do not increase kak 5 Add the element to cluster which has the least increment to kak if min{ kak | ∀e ∈ cluster : e ⊂ a} ≤ max-size still holds
Compared to the other tested clustering algorithms, this algorithm led to the best results on the given task of finding clusters with a small hull tree and finding as many elements as possible per cluster in a short time. The table in Figure 6 shows selected results of the clustering algorithms. Experiments showed that the training time is roughly proportional to #clusters · Px∈X || ax‘s cluster || α where α ∈ [1, 1.02] and where ax‘s cluster is the minimal tree, such that a ⊃ b holds for each b in x’s cluster. Thus, we want to minimize this product to achieve a shorter training duration. In general, it is more important to reduce the number of clusters than the size of the paddings because this enables a better parallelization and because less native Python code is executed. By combining this clustering algorithm and the previously presented tree traversal, semi-batched computation and training is made possible. aLess important quality measure: Lower is better bMore important quality measure: Lower is better cAccording to equation 3 with α = 1 and multiplied with 10−6 dCPU-time of clustering including preprocessing and evaluation on SCCKN at ∼ 2.5GHz eAs in equations 1 and 2 fDBSCAN was very weak because either a lot of elements were not related to a cluster or the clusters were too huge. 5
We evaluated our recursive neural network using 10-fold cross validation. As the accuracy measure, we computed full accuracy pf and masked accuracy pm.
pf := ||{ i | yˆi = yi }|| ||{ i | yi ∈ y }|| pm := ||{ i | yˆi = yi, yi 6= 0, yi 6= yend }|| ||{ i | yi 6= 0, yi 6= yend }|| The accuracies ignore that a prediction may be almost correct if the result is, for example, shifted by one node. Therefore, if an error occurs near the root, a proper subtree at the wrong position is interpreted as wrong, too. For this reason, we additionally implemented a bag-of-words accuracy pb := 1 − nX−1 max #iy − #iyˆ , 0 i=0 kyk where n is the number of possible values, and #iy is the number of occurrences of i in y. The bag-of-words accuracy thus measures whether the prediction consists of the same unsorted values and frequencies as the ground truth but ignores their structure. This makes the measure robust against shifts of nodes. Since the training is in no way biased towards the direction of this measure, it is very likely that most of the errors which cause a reduction in the full accuracy, but are correct with respect to the bag-of-words accuracy, are only a slight displacement within the tree.
If the full accuracy is higher than the masked accuracy, the prediction of the topology of the tree (equal to the prediction of zeros) is better than the prediction of the values. This can indicate a bias towards predicting zeros. While this almost always occurs, our loss function avoids falling into a local minimum.
Until now, we mainly trained on a subset of only 15 240 mathematical terms for performance reasons. Further, we used relatively high learning rates.
Currently, we achieved a masked validation accuracy of pm = 47.05%. Further, we repeatedly obtained full validation accuracies of up to pf = 80%. Our experiment with the best masked validation reached a bag-of-words accuracy of pb = 92.3%.
The results show that the single-layer approach outperforms the multi-layer approaches. An LSTM state size of 256 produced the best results.
By traversing and clustering the trees, we could achieve a speed increase of roughly factor ten. 5.1
The standalone disambiguation of mathematical formulae, which chooses which mathematical interpretation (i.e., semantic LATEX macro) to use, yielded excellent results. Without training (i.e., random prediction), we achieved an accuracy of 50 − 60%. This is because some generic LATEX symbols are restricted to a single semantic LATEX macro. Using our bag-of-words approach and neural networks, we obtained an accuracy of about 97% per choice of a semantic LATEX macro.
Since we would need a rule-based translator which only utilizes the neural network in ambiguous cases, our standalone disambiguation approach is currently not applicable. Our results show that neural networks are adequate for this disambiguation task. Thus, if a rule-based translator with ambiguities will be implemented, this would be a good solution. 6
The current results cannot yet be applied to a complete translation but are promising considering that we did not yet use an attention mechanism, and that we did not yet use the entire data set for training. Further, a shortage of time did not allow a full training.
One major drawback of recursive neural networks is their performance, because, batched training is generally not possible. We achieved a speed increase of roughly factor ten. How well our technique can be combined with other speed-optimizing approaches remains to be determined.
A drawback of clustering the training data is that the order of occurring formulae is biased, because formulae with a similar topology are used together for training. Experiments with a different neural network on the same bias showed that this bias can be neglected if the learning rate is low enough.
We think that the single-layer network outperforms the multi-layer network since pre-trained embeddings are not available, and since we didn’t perform layer-wise training, yet. 7
In future research, we will improve our implementation to enable a complete formula translation. For that, we will implement a novel attention mechanism for recursive neural networks. Additionally, we will extend our auto-encoder approaches and will apply layer-wise training.
For the parsing and tree traversal, we will implement an improved traversal approach based on post-fix notation to enhance the tree structure.
In the future, this work may allow the DLMF/DRMF to extend their repository of semantic LATEX formulae more easily. Other applied use cases for this translator are mathematical spell-checkers, validation of mathematical books, easier interfaces for CASs, and the automated pre-correction of students’ math problem sets.
The standalone disambiguation could also be implemented using a recurrent or recursive neural network instead of a bag-of-words based approach. This would most likely yield better results, because the order of the formulae, or respectively, the structure of the formulae can be considered using this approach.
We would like to thank Howard Cohl et al. [