Non-Autoregressive Math Word Problem Solver with Unified Tree Structure (2023)

Abstract: Existing MWP solvers employ sequence or binary tree to present the solution expression and decode it from given problem description. However, such structures fail to handle the variants that can be derived via mathematical manipulation, e.g., (a_1+a_2)*a_3 and a_1 * a_3+a_2 * a_3 can both be possible valid solutions for a same problem but formulated as different expression sequences or trees. The multiple solution variants depicting different possible solving procedures for the same input problem would raise two issues: 1) making it hard for the model to learn the mapping function between the input and output spaces effectively, and 2) wrongly indicating wrong when evaluating a valid expression variant. To address these issues, we introduce a unified tree structure to present a solution expression, where the elements are permutable and identical for all the expression variants. We propose a novel non-autoregressive solver, named MWP-NAS , to parse the problem and deduce the solution expression based on the unified tree. For evaluating the possible expression variants, we design a path-based metric to evaluate the partial accuracy of expressions of a unified tree. The results from extensive experiments conducted on Math23K and MAWPS demonstrate the effectiveness of our proposed MWP-NAS. The codes and checkpoints are available at: https://github.com/mengqunhan/MWP-NAS .

## introduction automatically solving math word problems (mwp) is an important and fundamental task in artificial intelligence that has attracted a great deal of research attention throughout the years @xcite @xcite . figure 1 illustrates an mwp example and its solutions. given an input word problem description, the mwp solver needs to understand the problem in natural language, figure out the mathematical logic underlying the problem, then formulate the corresponding solution expression by employing suitable mathematical operation symbols (e.g., +, -, ×, /) to link the relevant numbers in the problem. due to the complex reasoning in text and expression, automatically solving math word problems has always been considered as one of the key testbeds for evaluating the intelligence level of an ai agent @xcite . the approaches for automatically solving mwp proposed by various researchers over the years can be categorized into three stages: manual features and rule-based at early stage, followed by facilitating quantitative reasoning with semantic parsing, and the use of deep learning in recent years @xcite . methods from the first two stages did not work well as they were limited in their capacity for feature representation and language understanding. with the success of deep learning in natural language understanding, a series of neu-ral solvers for mwp have been proposed recently and achieved superior performance. inspired by the sequence to sequence modeling in machine translation, several works @xcite @xcite considered mwp as a sequence to sequence mapping problem, from natural language to mathematical expression, and sequentially generate the numbers and operators of the expression. however, such sequential representation ignored the arithmetic properties of the expression. as such, the binary tree was introduced to present the expression and achieved tremendous progress with seq2tree models @xcite @xcite and graph2tree models @xcite . more recently, the application of pre-trained language models to mwp solving @xcite have led to new state-of-the-arts due to the superior capacity and performance in language modelling. most existing approaches learn to match exactly the target expression and ignore the alternative ones that can be derived by the arithmetic laws, e.g., commutative law, associative law, and distributive law. as the example shown in figure 1 , we can calculate the answer following either the rules of incomeexpense or saturday + sunday resulting in different expressions and binary trees. however, translating the same problem description to different expression variants is inconsistent with the function mapping, which introduces output indeterminacy and makes the model difficult to optimize. furthermore, the issue of variant expressions may lead to problems in expression evaluation due to possible false negatives and thus underestimation of the performance of the methods. to address the above issues, we propose to learn the mwp solver based on a unified form of expression. specifically, we eliminate the diversity of expression variants and unify them to an identical format with mtree structure @xcite . unlike having only two branches in binary tree, mtree may contain multiple branches for each node, as shown in figure 1 . since the expression diversity is mainly introduced by the computational priority, mtree removes the / andoperators, and introduces ×-and +/ to make all the operators are with the same superiority and the child nodes of the same parent are permutable. based on such mtree, @xcite design mtree codes to represent and learn the mapping between prob-lem and expression. however, such codes break the mathematical relations between numbers @xcite and may lead to inferior performance. furthermore, the code dictionary has to be predefined which limits the flexibility and may incur the issue of out-of-vocabulary (oov) during inference. motivated by the intuition of goal-driven strategy for tree-structure decoding, we propose a non-autoregressive mwp solver, mwp-nas for short, to integrate with goal-driven decoding based on mtree. specifically, our mwp-nas first obtains the semantic representation of problem text via a neural language model, and uses it as the initial goal for mtree decoding. as there exist multiple unordered child nodes for each parent, we employ a non-autoregressive transformer to explore the comprehensive interactions among the nodes and predict them in parallel. for each sub-goal, we recursively implement such non-autoregressive decoding until all the child nodes are numbers. a cross-goal attention strategy is devised to enable the interactions between goals and make the decomposed sub-goals more accurate. in mtree, as each number could be applied in one of four forms: {n, -n, 1 n , -1 n }, we design a simple classification module to learn the form, which is jointly trained with the non-autoregressive decoder. we also observe that under the current evaluation approaches, the variants of the same expression would be reported as wrong by expression evaluation, a.k.a false negative, which may underestimate the ability of the methods. furthermore, we want to be able to evaluate the ability of a solver not only from the final expression, but also considering the partial correctness of the sub-expressions. towards this end, we propose two mtree based evaluation metrics: 1) mtree acc measuring the exact matching accuracy of unified mtree, and 2) mtree iou calculating the intersection over union of mtree paths between predicted and ground-truth expressions. in summary, the main contributions of this paper are as follows: ## methodology to handle multiple branches in mtree, we propose a non-autoregressive solver, termed as mwp-nas, for the child nodes generation. as depicted on the left of figure 2 , our mwp-nas mainly consists of a problem encoder and a goal-driven mtree generator to understand the problem and reason the mtree structure of solution expression, which is used to compute the final answer. to handle multibranch decoding in mtree generator, we devise a novel non-autoregressive goal decomposer, shown on the right side in figure 2 . all the details will be introduced in the subsequent parts. ## evaluation most existing works employ expression accuracy and value accuracy to evaluate and compare the performance of mwp methods @xcite @xcite . value accuracy measures the accuracy of the final answer, but fails to evaluate the validity of the solving procedure. expression accuracy tries to address this issue and measure the exact matching accuracy between predicted and ground-truth expression, and results in much lower performance due to the diverse variants of the same solution expression. obviously, the expression accuracy should be the same as value accuracy in theory, or slightly lower for some exception cases. the ideal metric to evaluate the expression should be capable of handling the reasonable variants of solution expressions. in other words, all the variants derived from the gold expression with arithmetic rules would lead to the gold answer, and should be considered as true. however, it is hard to include all the variants and conduct an exhaustive evaluation. based on the uniqueness of mtree in expression variants, we propose mtree accuracy and mtree iou to evaluate the expression accuracy more accurately. specifically, following existing expression accuracy to verify the exact matching accuracy on the whole tree, mtree accuracy measures the matching accuracy between predicted and gold unified mtrees. while such evaluation on the whole expression tree fails to measure the partial correctness of expressions, which is also an important way to evaluate the ability of solvers, as well as humans. for example, given the example in figure 1 , 13 × (10 + 3) + 40 and (13 × 10 + 3 -40) are two false expressions, and the former one only uses the wrong operation "+" for the expense, but all the items are correct. while the latter applies incorrect calculation of income on sunday, which should obtain a lower score. to this end, we propose mtree iou to calculate the accuracy of paths connecting root and leaves to measure the partial correctness of expressions. mtree iou first transforms the predicted and ground-truth expressions to mtrees, then constructs root-leaf path sets p p and p g for them, respectively. inspired by the evaluation in object detection @xcite , we calculate the intersection over union (iou) as: ## conclusion we presented a novel non-autoregressive mwp solver (mwp-nas) based on the unified mtree structure. our proposed mwp-nas implements a goal-driven manner for multi-branch decomposition to generate the mtree of expressions. we devised a cross-goal attention strategy to pass information between goals during goal decomposing. we have also designed two metrics based on mtree for better expression evaluation. experiments conducted on math23k and mawps demonstrated the effectiveness of our approach and metrics.