An Expression Tree Decoding Strategy for Mathematical Equation Generation (2023)

Abstract: Generating mathematical equations from natural language requires an accurate understanding of the relations among math expressions. Existing approaches can be broadly categorized into token-level and expression-level generation. The former treats equations as a mathematical language, sequentially generating math tokens. Expression-level methods generate each expression one by one. However, each expression represents a solving step, and there naturally exist parallel or dependent relations between these steps, which are ignored by current sequential methods. Therefore, we integrate tree structure into the expression-level generation and advocate an expression tree decoding strategy. To generate a tree with expression as its node, we employ a layer-wise parallel decoding strategy: we decode multiple independent expressions (leaf nodes) in parallel at each layer and repeat parallel decoding layer by layer to sequentially generate these parent node expressions that depend on others. Besides, a bipartite matching algorithm is adopted to align multiple predictions with annotations for each layer. Experiments show our method outperforms other baselines, especially for these equations with complex structures.

## introduction generating corresponding mathematical equations and solutions from text is important for a range of tasks, such as dialogues, question answering, math word problem (mwp), etc. it necessitates an accurate comprehension of semantics and the complex relations between mathematical symbols. we investigate the existing approaches from two perspectives: the generation is at the token-level or expression-level, and the order is based on sequence or tree structure. firstly, sequence-tosequence methods (seq2seq in figure 1 ) (wang et al., 2017, 2018; chiang and chen, 2019; li et al., † corresponding author. question: two cars are traveling from two places 10 km apart, the speed of the first car is 50km/h, the speed of the second car is 60km/h, the first car drives for 5 hours, the second car drives for 4 hours, finally how far apart are the two cars? generates mathematical tokens one by one at the tokenlevel; seq2tree generates tokens using prefix order. in contrast, seq2exp generates expressions one by one at expression-level. our expression tree decoding strategy predicts multiple math expressions in parallel and forms a tree, with the minimum decoding steps. recently, some researchers have explored expression-level approaches for mathematical equation generation, including @xcite @xcite @xcite . these approaches mostly place emphasis on generating a mathematical expression step by step (seq2exp), rather than a token. these seq2exp methods belong to a sequen-tial generation at expression-level. however, it is imperative to recognize that each mathematical expression represents a problemsolving step, and there inherently exists a parallel or dependent relation among these steps. the existing seq2exp approach may struggle to capture these relations since they only produce expressions in sequence. therefore, there is a pressing need for a versatile decoding strategy capable of simultaneously generating independent expressions in parallel at one step, while sequentially producing expressions that depend on others step by step. based on this belief, we propose an expression tree decoding strategy by combining the seq2exp with a tree structure at the expression level. differing from the prior seq2tree, each node in this tree represents an expression, rather than a token. to construct an expression-level tree, we generate multiple expressions in parallel at each step. these expressions are independent to each other and act as the leaf node in the expression tree. those expressions depend on others, they act as parent nodes and are sequentially generated based on their child nodes. as shown in figure 1 , the two expressions (50 × 5, 60 × 4) are completely independent and generated in parallel at step 1. the third expression depends on the first two, forming an expression tree. it not only empowers the model to exploit the inherent structure of the equation but also shortens its decoding path (the minimum steps in figure 1 ). to achieve this, we design a layer-wise parallel decoding strategy. at each decoder's layer, it can generate multiple independent expressions in parallel and then proceeds to the next layer, and repeat parallel prediction layer by layer. this layerwise parallel decoding process ensures that these independent expressions are produced in parallel, while these expressions depending on others are sequentially generated layer by layer, eventually constructing the entire expression tree. besides, to decode multiple expressions in parallel, we take inspiration from query-based object detection @xcite @xcite . similar to detecting multiple visual objects by queries, we also utilize queries to identify multiple mathematical relations for expression generation in parallel. lastly, we adopt a bipartite matching algorithm for loss calculation between multiple predicted expressions and the label. @xcite shares some similarities with us but the challenges and approaches are different. @xcite perform a bottom-up structure to extract multiple equations (e.g., x+@xmath0, y-2=4), whereas our method considers how to predict multiple expressions in parallel for a complex equation at each step (e.g., output 50 × 5, 60 × 4 simultaneously for 50 × 5 + 60 × 4). besides, @xcite enumerates all possible expression combinations but we first introduce bipartite matching to achieve parallel prediction. our contributions are threefold: by aligning the decoding process with the inherent structure of the equation, our approach paves the way for more intuitive, efficient equation generation. moreover, it provides insights that could be applicable to many other structured tasks. ## related work in advancing toward general-purpose ai, dependable reasoning remains imperative. the quest for human-equivalent reasoning has been rigorously explored in domains including nlp @xcite , rl @xcite , and robotics @xcite . recently, leveraging the planning and reasoning capabilities of llms paves the way for the development of numerous intelligent applications @xcite @xcite . accurate generation of mathematical equations is an important manifestation of reasoning abilities, which has been extensively investigated in a plethora of nlp tasks, e.g., math word problems @xcite @xcite , question answering @xcite , dialogue @xcite @xcite , etc. these tasks necessitate an accurate understanding of the semantics within the text as well as mathematical symbols. token-level generation mathematical equation was treated as a translation task from human language into the mathematical token (symbol) @xcite . many seq2seq-based methods were proposed with an encoder-decoder framework. @xcite introduced a group attention to enhance seq2seq performance. @xcite utilized a transformer model for equation generation. except for seq2seq methods, some researchers @xcite @xcite studied the decoding structures and proposed a treebased decoder using prefix sequence. @xcite al. (2020a, 2021 ## experiments math word problem task we first evaluate our expression tree decoding strategy on the math word problem task (mwp). mwp represents a challenging mathematical reasoning task where the model is required to comprehend the semantics of a given problem and generate a complete equation and the solution. encompassing a spectrum of topics, including engineering, arithmetic, geometry, and commerce, mwp effectively evaluates the model's prowess in semantic understanding as well as mathematical symbol generation. we use three standard mwp datasets foot_0 across two languages: mathqa @xcite , math23k @xcite , and mawps @xcite . we follow @xcite to preprocess datasets. the statistics of datasets are reported in appendix a.3. baselines we compare our method with three types of baselines: (1) seq2seq/tree: plm-gen @xcite , rank @xcite , symbol-dec @xcite , h-reasoner @xcite , logic-dec @xcite , prototype @xcite , t-dis @xcite , textual-cl @xcite , ana-cl @xcite and several representative methods. (2) seq2exp: e-pointer @xcite , dag @xcite , re-ext @xcite , m-view @xcite , elastic @xcite , m-tree @xcite and mwp-nas @xcite . besides, we also compare with gpt-3.5-turbo (openai, 2022) and self-consistency @xcite prompted by one demonstration through the openai api. more details are listed in appendix a.1. training details following most previous works @xcite standard deviation for math23k and mathqa, and 5-fold cross-validation for math23k and mawps. the test-set accuracy is chosen by the best dev-set accuracy step. since most of the math problems only require two or three mathematical expressions to be generated in parallel for each step, we set the number of queries k to be 6, which is sufficient to cover all cases. except for using a standard decoder for layer-wise decoding (our), we also explore an alternate variant (our layer-shared), in which parallel decoding is performed at every n transformer layer, but each decoding step shares the parameter of these n layers. this model is efficient with fewer parameters. model details are reported in figure a1 . ## conclusion we devise an expression tree decoding strategy for generating mathematical equations layer by layer. each layer produces multiple mathematical expressions in parallel which are non-dependent and order-free, achieving flexible decoding. during the training, we employ a bipartite matching algorithm to align the multiple generated expressions with the golden labels and compute the parallel prediction loss under the optimal matching scheme. extensive experiments demonstrate that our expression tree decoding strategy can effectively absorb the structural features of equations and enhance the capacity for generating complex equations for math reasoning.