Solving math word problems is a challenging task that requires accurate natural language understanding to bridge natural language texts and math expressions. Motivated by the intuition about how human generates the equations given the problem texts, this paper presents a neural approach to automatically solve math word problems by operating symbols according to their semantic meanings in texts. This paper views the process of generating equations as a bridge between the semantic world and the symbolic world, where the proposed neural math solver is based on an encoder-decoder framework. In the proposed model, the encoder is designed to understand the semantics of problems, and the decoder focuses on tracking semantic meanings of the generated symbols and then deciding which symbol to generate next. The preliminary experiments are conducted in a benchmark dataset Math23K, and our model significantly outperforms both the state-of-the-art single model and the best non-retrieval-based model over about 10% accuracy, demonstrating the effectiveness of bridging the symbolic and semantic worlds from math word problems. 1 1 Introduction Automatically solving math word problems has been an interesting research topic and also been viewed as a way of evaluating machines' ability (Mandal and Naskar, 2019). For human, writing down an equation that solves a math word problem requires the ability of reading comprehension, reasoning, and sometimes real world understanding. Specifically, to solve a math word problem, we first need to know the goal of the given problem, then understand the semantic 1 The source code is available at https://github. meaning of each numerical number in the problem, perform reasoning based on the comprehension in the previous step, and finally decide what to write in the equation. Most prior work about solving math word problems relied on hand-crafted features, which required more human knowledge. Because those features are often in the lexical level, it is not clear whether machines really understand the math problems. Also, most prior work evaluated their approaches on relatively small datasets, and the capability of generalization is concerned. This paper considers the reasoning procedure when writing down the associated equation given a problem. Figure 1 illustrates the problem solving process. The illustration shows that human actually assigns the semantic meaning to each number when manipulating symbols, including operands (numbers) and operators ( +   ). Also, we believe that the semantic meaning of operands can help us decide which operator to use. For example, the summation of  price of one pen  and  number of pens Tom bought  is meaningless; therefore the addition would not be chosen. Following the observation above, this paper proposes a novel encoder decoder model, where the encoder extracts semantic meanings of numbers in the problem, and the decoder is equipped with a stack that facilitates tracking the semantic meanings of operands. The contributions of this paper are 4-fold:  This paper is the first work that models semantic meanings of operands and operators for math word problems. This paper proposes an end-to-end neural math solver with a novel decoding process that utilizes the stack to generate associated equations. This paper achieves the state-of-the-art performance on the large benchmark dataset Math23K. This paper is capable of providing interpretation and reasoning for the math word problem solving procedure. There is a lot of prior work that utilized handcrafted features, such as POS tags, paths in the dependency trees, keywords, etc., to allow the model to focus on the quantities in the problems (Kush-man et al., 2014; Hosseini et al., 2014; Roy et al., 2015; Roy and Roth, 2015; Koncel-Kedziorski et al., 2015; Roy et al., 2016; Upadhyay et al., 2016; Upadhyay and Chang, 2017; Roy and Roth, 2018; Wang et al., 2018). Recently, Mehta et al.; Wang et al.; Ling et al. attempted at learning models without predefined features. Following the recent trend, the proposed end-to-end model in this paper does not need any hand-crafted features. Kushman et al. first extracted templates about math expressions from the training answers, and then trained models to select templates and map quantities in the problem to the slots in the template. Such two-stage approach has been tried and achieved good results (Upadhyay and Chang, 2017). The prior work highly relied on human knowledge, where they parsed problems into equations by choosing the expression tree with the highest score calculated by an operator classifier, working on a hand-crafted trigger list containing quantities and noun phrases in the problem, or utilizing features extracted from text spans (Roy et al., 2015, 2016; Koncel-Kedziorski et al., 2015). Shi et al. defined a Dolphin language to connect math word problems and logical forms, and generated rules to parse math word problems. Upadhyay et al. parsed math word problems without explicit equation annotations. Roy and Roth clas-sified math word problems into 4 types and used rules to decide the operators accordingly. Wang et al. trained the parser using reinforcement learning with hand-crafted features. Hosseini et al. modeled the problem text as transition of world states, and the equation is generated as the world states changing. Our work uses a similar intuition, but hand-crafted features are not required and our model can be trained in an end-to-end manner. Some end-to-end approaches have been proposed, such as generating equations directly via a seq2seq model (Wang et al., 2017). Ling et al. tried to generate solutions along with its rationals with a seq2seq-like model for better interpretability. This paper belongs to the end-to-end category, but different from the previous work; we are the first approach that generates equations with stack actions, which facilitate us to simulate the way how human solves problems. Furthermore, the proposed approach is the first model that is more interpretable and provides reasoning steps without the need of rational annotations. Our approach composes of two parts, an encoder and a decoder, where the process of solving math word problems is viewed as transforming multiple text spans from the problems into the target information the problems ask for. In the example shown in Figure 1, all numbers in the problem are attached with the associated semantics. Motivated by the observation, we design an encoder to extract the semantic representation of each number in the problem text. Considering that human usually manipulates those numbers and operators (such as addition, subtraction, etc.) based on their semantics for problem solving, a decoder is designed to construct the equation, where the semantics is aligned with the representations extracted by the encoder. The idea of the proposed model Tom has $ 10 5 pens ? is to imitate the human reasoning process for solving math word problems. The model architecture is illustrated in Figure 2. The encoder aims to extract the semantic representation of each constant needed for solving problems. However, the needed constants may come from either the given problem texts or domain knowledge, so we detail these two procedures as follows. For each math word problem, we are given a passage consisting of words { w Pt } mt =1 , whose word embeddings are { e Pt } mt =1 . The problem text includes some numbers, which we refer as constants. The positions of constants in the problem text are denoted as { p i } ni =1 . In order to capture the semantic representation of each constant by considering its contexts, a bidirectional long short-term mem-ory (BLSTM) is adopted as the encoder (Hochre-iter and Schmidhuber, 1997): h E t , c E t = BLSTM( h E t  1 , c E t  1 , e P t ) , (1) and then for the i -th constant in the problem, its semantic representation e ci is modeled by the corresponding BLSTM output vector: e ci = h Ep i . (2) 3.1.2 External Constant Leveraging External constants, including 1 and  , are leveraged, because they are required to solve a math word problem, but not mentioned in the problem text. Due to their absence from the problem text, we cannot extract their semantic meanings by BLSTM in (2). Instead, we model their semantic representation e  , e 1 as parts of the model parameters. They are randomly initialized and are learned during model training. The decoder aims at constructing the equation that can solve the given problem. We generate the equation by applying stack actions on a stack to mimic the way how human understands an equation. Human knows the semantic meaning of each term in the equation, even compositing of operands and operators like the term  (10  1  5)  in Figure 1. Then what operator to apply on a pair operands can be chosen based on their semantic meanings accordingly. Hence we design our model to generate the equation in a postfix manner: a operator is chosen base on the semantic representations of two operands the operator is going to apply to. Note that the operands a operator can apply to can be any results generated previously. That is the reason why we use stack as our data structure in order to keep track of the operands a operator is going to apply to. The stack contains both symbolic and semantic representations of operands, denoted as S = [( v Sl t , e Sl t ) , ( v Sl t  1 , e Sl t  1 ) ,    , ( v S 1 , e S 1 )] , (3) where v S of each pair is the symbolic part, such as x + 1 , while e S is the semantic representation, which is a vector. The components in the decoder are shown in the right part of Figure 2, each of which is detailed below. At each decoding step, decisions are made based on features of the current state. At each step, fea-1015 0.5   10  1  5 0.5  10  1  5  10 1  5  10 5 1  10 5  10  Apply  Push 0.5 Apply  Apply  Push 1 Push 5 Push 10 Push  Apply =  0.5 1 10 5 Encoder & Generated Var. tures r sa and r opd are extracted to select a stack action (section 3.3.2) and an operand to push (sec-tion 3.3.3). Specifically, the features are the gated concatenation of following vectors:  h D t is the output of an LSTM, which encodes the history of applied actions: h Dt , c Dt = LSTM( h Dt  1 , c Dt  1 , res t  1 ) , (4) where res t  1 is the result from the previous stack action similar to the seq2seq model (Sutskever et al., 2014). For example, if the previous stack action o t  1 is push, then res t  1 is the semantic representation pushed into the stack. If the previous stack action o t  1 is to apply an operator (cid:5) , then res t  1 is the semantic representation generated by f (cid:5) . s t is the stack status. It is crucial because some operators are only applicable to certain combinations of operand semantics, which is similar to the type system in programming languages. For example, operating multiplication is applicable to the combination of  quantity of an item  and  price of an item , while operating addition is not. Considering that all math operators supported here ( + ,  ,  ,  ) are binary operators, the semantic representations of the stack's top 2 elements at the time t  1 are considered: s t = [ e Sl t ; e Sl t ] . (5)  q t incorporates problem information in the decision. It is believed that the attention mechanism (Luong et al., 2015) can effectively capture dependency for longer distance. Thus, the attention mechanism over the encoding problem h E 1 , h E 2 ,    is adopted: q t = Attention( h Dt , { h Ei } mi =1 ) , (6) where the attention function in this paper is defined as a function with learnable parameters w, W, b : Attention( u, { v i } mi =1 ) = m (cid:88) i =1  i h i , (7)  i = exp( s i ) (cid:80) ml =1 exp( s i ) , (8) s i = w T tanh( WT [ u ; v i ] + b ) . (9) In order to model the dynamic features for different decoding steps, features in r sat is gated as follows: r sat = [ g sat, 1  h Dt ; g sat, 2  s t ; g sat, 3  q t ] , (10) g sat =  ( W sa  [ h Dt ; s t ; q t ]) , (11) where  is a sigmoid function and W sa is a learned gating parameter. r opdt is defined similarly, but with a different learned gating parameter W opd . The stack action selector is to select an stack action at each decoding step (section 3.3.2) until the unknowns are solved. The probability of choosing action a at the decoding step t is calculated with a network NN constituted of one hidden layer and ReLU as the activation function: P ( Y t |{ y i } t  1 i =1 , { w i } mi =1 ) (12) = StackActionSelector( r sat ) = softmax(NN( r sat )) , where r sat is decoding state features as defined in section 3.3. 3.3.2 Stack Actions The available stack actions are listed below:  Variable generation : The semantic representation of an unknown variable x is generated dynamically as the first action in the decoding process. The decoder module can decide how many unknown variables are required to solve the problem, and the semantic representation of the unknown variable is generated with an attention mechanism: e x = Attention( h Dt , { h Ei } mi =1 ) . (13)  Push : This stack action pushes the operand chosen by the operand selector (section 3.3.3). Both the symbolic representation v  and semantic representation e  of the chosen operand would be pushed to the stack S in (3). Then the stack state becomes S = [( v S  , e S  ) , ( v Sl t , e Sl t ) ,    , ( v S 1 , e S 1 )] . (14)  Operator (cid:5) application ( (cid:5)  { + ,  ,  , } ) : One stack action pops two elements from the top of the stack, which contains two pairs, ( v i , e i ) and ( v j , e j ) , and then the associated symbolic operator, v k = v i (cid:5) v j , is recorded. Therefore, after an operator is applied to the stack specified in (3), the stack state becomes S =[( v Sl t (cid:5) v Sl t  1 , f (cid:5) ( e Sl t , e Sl t  1 )) , (15) ( v Sl t  2 , e Sl t  2 ) ,    , ( v S 1 , e S 1 )] . Note that this procedure provides the flexibility of solving problems with more than one unknown variables. Also, a semantic transformation function f (cid:5) for that operator is invoked, which generates the semantic representation of v k by transforming semantic representations of v i and v j to e k = f (cid:5) ( e i , e j ) . Equal application : When the equal application is chosen, it implies that an equation is completed. This stack action pops 2 tuples from the stack, ( v i , e i ) , ( v j , e j ) , and then v i = v j is recorded. If one of them is an unknown variable, the problem is solved. Therefore, after an OP is applied to the stack specified in (3), the stack state becomes S = [( v Sl t  2 , e Sl t  2 ) ,    , ( v S 1 , e S 1 )] . When the stack action selector has decided to push an operand, the operand selector aims at choosing which operand to push. The operand candidates e include constants provided in the problem text whose semantic representations are e c 1 , e c 2 ,    , e cn , unknown variable whose semantic representation is e x , and two external constants 1 and  whose semantic representations are e 1 , e  : e = [ e c 1 , e c 2 ,    , e cn , e 1 , e  , e x ] . An operand has both symbolic and semantic representations, but the selection focuses on its semantic meaning; this procedure is the same as what human does when solving math word problems. Inspired by addressing mechanisms of neural Turing machine (NTM) (Graves et al., 2014), the probability of choosing the i -th operand candidate is the attention weights of r t over the semantic representations of the operand candidates as in (8): P ( Z t | { y i } t  1 i =1 , { w i } mi =1 ) (18) = OperandSelector( r opdt ) = AttentionWeight( r opdt , { e i } mi =1  { e 1 , e  , e x } ) , and r opdt is defined in section 3.3. A semantic transformer is proposed to generate the semantic representation of a new symbol resulted from applying an operator, which provides the capability of interpretation and reasoning for the target task. The semantic transformer for an operator (cid:5)  { + ,  ,  , } transforms semantic representations of two operands e 1 , e 2 into f (cid:5) ( e 1 , e 2 ) = tanh( U (cid:5) ReLU( W (cid:5) [ e 1 ; e 2 ]+ b (cid:5) )+ c (cid:5) ) , (19) where W (cid:5) , U (cid:5) , b (cid:5) , c (cid:5) are model parameters. Semantic transformers for different operators have different parameters in order to model different transformations. Both stack action selection and operand selection can be trained in a fully supervised way by giving problems and associated ground truth equations. Because our model generates the equation with stack actions, the equation is first transformed into its postfix representation. Let the postfix representation of the target equation be y 1 ,    y t ,    , y T , where y t can be either an operator ( + ,  ,  ,  , = ) or a target operand. Then for each time step t , the loss can be computed as L ( y t ) = (cid:40) L 1 (push op) + L 2 ( y t ) y t is an operand L 1 ( y t ) otherwise , where L 1 is the stack action selection loss and L 2 is the operand selection loss defined as L 1 ( y t ) =  log P ( Y t = y t | { o i } t  1 i =1 , { w i } mi =1 ) , L 2 ( y t ) =  log P ( Z t = y t | r t ) . The objective of our training process is to minimize the total loss for the whole equation, (cid:80) Tt =1 L ( y t ) . When performing inference, at each time step t , the stack action with the highest probability P ( Y t |{  y i } t  1 i =1 , { w i } mi =1 ) is chosen. If the chosen stack action is  push , the operand with the highest probability P ( Z t |{  Y i } t  1 i =1 , { w i } mi =1 ) is chosen. When the stack has less than 2 elements, the probability of applying operator + ,  ,  ,  , = would be masked out to prevent illegal stack actions, so all generated equations must be legal math expressions. The decoder decodes until the unknown variable can be solved. After the equations are generated, a Python package SymPy (Meurer et al., 2017) is used to solve the unknown variable. The inference procedure example is illustrated in Figure 3. The detailed algorithm can be found in Algorithm 1. To evaluate the performance of the proposed model, we conduct the experiments on the benchmark dataset and analyze the learned semantics. The experiments are benchmarked on the dataset Math23k (Wang et al., 2017), which contains 23,162 math problems with annotated equations. Each problem can be solved by a single-unknown-variable equation and only uses operators + ,  ,  ,  . Also, except  and 1 , quantities in the equation can be found in the problem text. There are also other large scale datasets like Dolphin18K (Shi et al., 2015) and AQuA (Ling et al., 2017), containing 18,460 and 100,000 math word Algorithm 1 Training and Inference function SOLVEPROBLEM (problem text) v  ExtractConstants(problem text) (cid:46) v is a list of constants in the problem. problems respectively. The reasons about not evaluating on these two datasets are 1) Dolphin18k contains some unlabeled math word problems and some incorrect labels, and 2) AQuA contains rational for solving the problems, but the equations in the rational are not formal (e.g. mixed with texts, using x to represent  , etc.) and inconsistent. Therefore, the following experiments are performed and analyzed using Math23K, the only large scaled, good-quality dataset. The results are shown in Table 1. The retrieval-based methods compare problems in test data with problems in training data, and choose the most Model Accuracy Retrieval Jaccard 47.2% Cosine 23.8% Classification BLSTM 57.9% Self-Attention 56.8% Generation Seq2Seq w/ SNI 58.1% Proposed Word-Based 65.3% Proposed Char-Based 65.8% Hybrid Retrieval + Seq2Seq 64.7% Table 1: 5-fold cross validation results on Math23K. similar one's template to solve the problem (Kush-man et al., 2014; Upadhyay and Chang, 2017). The classification-based models choose equation templates by a classifier trained on the training data. Their performance are reported in Robaidek et al.. The seq2seq and hybrid models are from Wang et al., where the former directly maps natural language into symbols in equations, and the latter one ensembles prediction from a seq2seq model and a retrieval-based model. The ensemble is the previous state-of-the-art results of Math23K. Our proposed end-to-end model belongs to the generation category, and the single model performance achieved by our proposed model is new state-of-the-art ( > 65%) and even better than the hybrid model result (64.7%). In addition, we are the first to report character-based performance on this dataset, and the character-based results are slightly better than the word-based ones. Among the single model performance, our models obtain about more than 7% accuracy improvement compared to the previous best one (Wang et al., 2017). The performance of our character-based model also shows that our model is capable of learning the relatively accurate semantic representations without word boundaries and achieves better performance. To better understand the performance contributed by each proposed component, we perform a series of ablation tests by removing components one by one and then checking the performance by 5-fold cross validation. Table 2 shows the ablation results. Char-Based v.s. Word-Based As reported above, using word-based model instead of character-based model only causes 0.5% performance drop. To fairly compare with prior word-Model Accuracy Char-Based 65.8% Word-Based 65.3% Word-Based Gate 64.1% Word-Based Gate Attention 62.5% Word-Based Gate Attention Stack 60.1% Word-Based Semantic Transformer 64.1% Word-Based Semantic Representation 61.7% Table 2: 5-fold cross validation results of ablation tests. Word-Based Gate It uses r t instead of r sat and r oprt as the input of both StackActionSelector and OperandSelector . Word-Based Gate Attention Considering that the prior generation-based model (seq2seq) did not use any attention mechanism, we compare the models with and without the attention mechanism. Removing attention means excluding q t  1 in (11), so the input of both operator and operand selector becomes r t = [ h Dt ; s t ] . The result implies that our model is not better than previous models solely because of the attention. Word-Based Gate Attention Stack To check the effectiveness of the stack status ( s t in (11)), the experiments of removing the stack status from the input of both operator and operand selectors ( r t = h Dt ) are conducted. The results well justify our idea of choosing operators based on semantic meanings of operands. Word-Based Semantic Transformer To validate the effectiveness of the idea that views an operator as a semantic transformer, we modify the semantic transformer function of the operator (cid:5) into f (cid:5) ( e 1 , e 2 ) = e (cid:5) , where e (cid:5) is a learnable parameter and is different for different operators. Therefore, e (cid:5) acts like the embedding of the operator (cid:5) , and the decoding process is more similar to a general seq2seq model. The results show that the semantic transformer in the original model encodes not only the last operator applied on the operands but other information that helps the selectors. Word-Based Semantic Representation To explicitly evaluate the effectiveness of operands' semantic representations, we rewrite semantic representation of the i -th operand in the problem texts .00 .00 .00 .00 .00 .00 .00 .00 .00 .01 .01 .00 .00 .00 .00 .08 .65 .21 .01 .01 .01 .00 .00 .01 .00 .00 .00 .01 .09 .42 .21 .02 .05 .13 .00 .00 .00 .00 .00 .01 .01 .02 .00 .01 .00 .00 .02 .15 .02 .03 .26 .14 .01 .02 .00 .02 .31 .00 .00 .00 .00 .00 .01 .00 .01 .00 .00 .00 .00 5 8 . from (2) to e ci = b ci , where b ci is a parameter. Thus for every problem, the representation of the i -th operand is identical, even though their meanings in different problems may be different. This modification assumes that no semantic information is captured by b ci , which can merely represent a symbolic placeholder in an equation. Because the semantic transformer is to transform the semantic representations, applying this component is meaningless. Here the semantic transformer is also replaced with f (cid:5) ( e 1 , e 2 ) = e (cid:5) as the setting of the previous ablation test. The results show that the model without using semantic representations of operands causes a significant accuracy drop of 3.5%. The main contribution of this paper about modeling semantic meanings of symbols is validated and well demonstrated here. To further analyze whether the proposed model can provide interpretation and reasoning, we visualize the learned semantic representations of constants to check where the important cues are, To better understand the information encoded in the semantic representations of constants in the problem, a self-attention is performed when their semantic representations are extracted by the encoder. Namely, we rewrite (2) as e ci = Attention( h Ep i , { h Et } mt =1 . Then we check the trained self-attention map (  in the attention function) on the validation dataset. For some problems, the self-attention that generates semantic representations of constants in the problem concentrates on the number's quantifier or unit, and sometimes it also focuses on informative verbs, such as  gain ,  get ,  fill , etc., in the sentence. For example, Figure 4 shows the attention weights for an example math word problem, where lighter colors indicate higher weights. The numbers  58  and  6  focus more on the quantifier-related words (e.g.  every  and  how many ), while  9  pays higher attention to the verb  fill . The results are consistent with those handcraft features for solving math word problems proposed by the prior research (Hosseini et al., 2014; Roy and Roth, 2015; Roy et al., 2015). Hence, we demonstrate that the automatically learned semantic representations indeed capture critical information that facilitates solving math word problems without providing human-crafted knowledge. We visualize the attention map ( q t in (6)) to see how the attention helps the decoding process. An example is shown in the top of Figure 5, where most attention focuses on the end of the sentence. Unlike the machine translation task, the attention shows the word-level alignment between source and target languages, solving math word problems requires high-level understanding due to the task complexity. To further analyze the effectiveness of the proposed gating mechanisms for stack action and operand selection, the activation of gates g sa , g opd at each step of the decoding process is shown in the bottom of Figure 5. It shows that most of time, the gate activation is high, demonstrating that the proposed gating mechanisms play an important role during decoding. We also observe a common phenomenon that the activation g sa 2 , which controls how much attention the stack action selector puts on the stack state when deciding an stack action, is usually low until the last opera-tor application stack action. For example, in the example of Figure 5, g sa 2 is less than 0 . 20 till the last argument selection stack action, and activates when deciding the division operator application (  ) and the equal application ( = ). It may result from the higher-level semantics of the operand (6 . 75  2 . 75) on the stack when selecting the stack action division operator application (  ). In terms Problem & Results    60         1/6 We randomly sample some results predicted incorrectly by our model shown in Table 3. In the first example, the error is due to the language ambiguity, and such ambiguity cannot be resolved without considering the exact value of the number. From the second example, although our model identi-fies the problem as a comparison problem successfully, it handles the order of the operands incorrectly. For the third problem, it cannot be solved by using only the surface meaning but requires some common sense. Therefore, above phenomena show the difficulty of solving math word problems and the large room for improvement. We propose an end-to-end neural math solver using an encoder-decoder framework that incorporates semantic representations of numbers in order to generate mathematical symbols for solving math word problems. The experiments show that the proposed model achieves the state-of-the-art performance on the benchmark dataset, and empirically demonstrate the effectiveness of each component in the model. In sum, the proposed neural math solver is designed based on how human performs reasoning when writing equations, providing better interpretation without the need of labeled rationals.
abstain objective objective abstain objective abstain abstain other abstain abstain abstain abstain method abstain abstain method abstain objective objective objective result objective other abstain abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain other abstain method abstain abstain abstain method abstain abstain method abstain method other abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain method other abstain abstain other abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain other abstain other abstain other abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain result abstain result abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective abstain abstain