The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> This paper formalizes the problem of solving multi-sentence algebraic word problems as that of generating and scoring equation trees. We use integer linear programming to generate equation trees and score their likelihood by learning local and global discriminative models. These models are trained on a small set of word problems and their answers, without any manual annotation, in order to choose the equation that best matches the problem text. We refer to the overall system as ALGES. We compare ALGES with previous work and show that it covers the full gamut of arithmetic operations whereas Hosseini et al. (2014) only handle addition and subtraction. In addition, ALGES overcomes the brittleness of the Kushman et al. (2014) approach on single-equation problems, yielding a 15% to 50% reduction in error. <s> BIB001 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> In this paper, we consider the task of learning control policies for text-based games. In these games, all interactions in the virtual world are through text and the underlying state is not observed. The resulting language barrier makes such environments challenging for automatic game players. We employ a deep reinforcement learning framework to jointly learn state representations and action policies using game rewards as feedback. This framework enables us to map text descriptions into vector representations that capture the semantics of the game states. We evaluate our approach on two game worlds, comparing against baselines using bag-ofwords and bag-of-bigrams for state representations. Our algorithm outperforms the baselines on both worlds demonstrating the importance of learning expressive representations. 1 <s> BIB002 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> We introduce a novel schema for sequence to sequence learning with a Deep Q-Network (DQN), which decodes the output sequence iteratively. The aim here is to enable the decoder to first tackle easier portions of the sequences, and then turn to cope with difficult parts. Specifically, in each iteration, an encoder-decoder Long Short-Term Memory (LSTM) network is employed to, from the input sequence, automatically create features to represent the internal states of and formulate a list of potential actions for the DQN. Take rephrasing a natural sentence as an example. This list can contain ranked potential words. Next, the DQN learns to make decision on which action (e.g., word) will be selected from the list to modify the current decoded sequence. The newly modified output sequence is subsequently used as the input to the DQN for the next decoding iteration. In each iteration, we also bias the reinforcement learning's attention to explore sequence portions which are previously difficult to be decoded. For evaluation, the proposed strategy was trained to decode ten thousands natural sentences. Our experiments indicate that, when compared to a left-to-right greedy beam search LSTM decoder, the proposed method performed competitively well when decoding sentences from the training set, but significantly outperformed the baseline when decoding unseen sentences, in terms of BLEU score obtained. <s> BIB003 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> We present an active detection model for localizing objects in scenes. The model is class-specific and allows an agent to focus attention on candidate regions for identifying the correct location of a target object. This agent learns to deform a bounding box using simple transformation actions, with the goal of determining the most specific location of target objects following top-down reasoning. The proposed localization agent is trained using deep reinforcement learning, and evaluated on the Pascal VOC 2007 dataset. We show that agents guided by the proposed model are able to localize a single instance of an object after analyzing only between 11 and 25 regions in an image, and obtain the best detection results among systems that do not use object proposals for object localization. <s> BIB004 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> This paper presents a novel approach to automatically solving arithmetic word problems. This is the first algorithmic approach that can handle arithmetic problems with multiple steps and operations, without depending on additional annotations or predefined templates. We develop a theory for expression trees that can be used to represent and evaluate the target arithmetic expressions; we use it to uniquely decompose the target arithmetic problem to multiple classification problems; we then compose an expression tree, combining these with world knowledge through a constrained inference framework. Our classifiers gain from the use of quantity schemas that supports better extraction of features. Experimental results show that our method outperforms existing systems, achieving state of the art performance on benchmark datasets of arithmetic word problems. <s> BIB005 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> Math word problems provide a natural abstraction to a range of natural language understanding problems that involve reasoning about quantities, such as interpreting election results, news about casualties, and the financial section of a newspaper. Units associated with the quantities often provide information that is essential to support this reasoning. This paper proposes a principled way to capture and reason about units and shows how it can benefit an arithmetic word problem solver. This paper presents the concept of Unit Dependency Graphs (UDGs), which provides a compact representation of the dependencies between units of numbers mentioned in a given problem. Inducing the UDG alleviates the brittleness of the unit extraction system and allows for a natural way to leverage domain knowledge about unit compatibility, for word problem solving. We introduce a decomposed model for inducing UDGs with minimal additional annotations, and use it to augment the expressions used in the arithmetic word problem solver of (Roy and Roth 2015) via a constrained inference framework. We show that introduction of UDGs reduces the error of the solver by over 10 %, surpassing all existing systems for solving arithmetic word problems. In addition, it also makes the system more robust to adaptation to new vocabulary and equation forms . <s> BIB006 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> There has been a recent interest in understanding text to perform mathematical reasoning. In particular, most of these efforts have focussed on automatically solving school level math word problems. In order to make advancements in this area accessible to people, as well as to facilitate this line of research, we release the ILLINOIS MATH SOLVER, a web based tool that supports performing mathematical reasoning. ILLINOIS MATH SOLVER can answer a wide range of mathematics questions, ranging from compositional operation questions like “What is the result when 6 is divided by the sum of 7 and 5 ?” to elementary school level math word problems, like “I bought 6 apples. I ate 3 of them. How many do I have left ?”. The web based demo can be used as a tutoring tool for elementary school students, since it not only outputs the final result, but also the mathematical expression to compute it. The tool will allow researchers to understand the capabilities and limitations of a state of the art arithmetic problem solver, and also enable crowd based data acquisition for mathematical reasoning. The system is currently online at https://cogcomp.cs.illinois. edu/page/demo_view/Math. <s> BIB007 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> Identifying mathematical relations expressed in text is essential to understanding a broad range of natural language text from election reports, to financial news, to sport commentaries to mathematical word problems. This paper focuses on identifying and understanding mathematical relations described within a single sentence. We introduce the problem of Equation Parsing -- given a sentence, identify noun phrases which represent variables, and generate the mathematical equation expressing the relation described in the sentence. We introduce the notion of projective equation parsing and provide an efficient algorithm to parse text to projective equations. Our system makes use of a high precision lexicon of mathematical expressions and a pipeline of structured predictors, and generates correct equations in $70\%$ of the cases. In $60\%$ of the time, it also identifies the correct noun phrase $\rightarrow$ variables mapping, significantly outperforming baselines. We also release a new annotated dataset for task evaluation. <s> BIB008 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Tree-Based Methods <s> Most successful information extraction systems operate with access to a large collection of documents. In this work, we explore the task of acquiring and incorporating external evidence to improve extraction accuracy in domains where the amount of training data is scarce. This process entails issuing search queries, extraction from new sources and reconciliation of extracted values, which are repeated until sufficient evidence is collected. We approach the problem using a reinforcement learning framework where our model learns to select optimal actions based on contextual information. We employ a deep Q-network, trained to optimize a reward function that reflects extraction accuracy while penalizing extra effort. Our experiments on two databases -- of shooting incidents, and food adulteration cases -- demonstrate that our system significantly outperforms traditional extractors and a competitive meta-classifier baseline. <s> BIB009
The arithmetic expression can be naturally represented as a binary tree structure such that the operators with higher priority are placed in the lower level and the root of the tree contains the operator with the lowest priority. The idea of tree-based approaches BIB005 , BIB001 , BIB006 ,  is to transform the derivation of the arithmetic expression to constructing an equivalent tree structure step by step in a bottom-up manner. One of the advantages is that there is no need for additional annotations such as equation template, tags or logic forms. Figure 3 shows two tree examples derived from the math word problem in Figure 2 . One is called expression tree that is used in BIB005 , BIB006 ,  and the other is called equation tree in BIB001 . These two types of trees are essentially equivalent and result in the same solution, except that equation tree contains a node for the unknown variable x. The overall algorithmic framework among the tree-based approaches consists of two processing stages. In the first stage, the quantities are extracted from the text and form the bottom level of the tree. The candidate trees that are syntactically valid, but with different structures and internal nodes, are enumerated. In the second stage, a scoring function is defined to pick the best matching candidate tree, which will be used to derive the final solution. A common strategy among these algorithms is to build a local classifier to determine the likelihood of an operator being selected as the internal node. Such local likelihood is taken into account in the global scoring function to determine the likelihood of the entire tree. Roy et al. BIB005 proposed the first algorithmic approach that leverages the concept of expression tree to solve arithmetic word problems. Its first strategy to reduce the search space is training a binary classifier to determine whether an extracted quantity is relevant or not. Only the relevant ones are used for tree construction and placed in the bottom level. The irrelevant quantities are discarded. The tree construction procedure is mapped to a collection of simple prediction problems, each determining the lowest common ancestor operation between a pair of quantities mentioned in the problem. The global scoring function for an enumerated tree takes into account two terms. The first one, denoted by φ(q), is the likelihood of quantity q being irrelevant, i.e., q is not used in creating the expression tree. In the ideal case, all the irrelevant quantities are correctly predicted with high confidence, resulting in a large value for the sum of φ(q). The other term, denoted by φ(op), is the likelihood of selecting op as the operator for an internal tree node. With these two factors, Score(E) is formally defined as where I (E) is the group of irrelevant quantities that are not included in expression E, and N refers to the set of internal tree nodes. To further reduce the tree enumeration space, beam search is applied in BIB005 . To generate the next state T ′ from the current partial tree, the algorithm avoids choosing all the possible pairs of terms and determining their operator. Instead, only top-k candidates with the highest partial scores are retained. Experimental results with k = 200 show that the strategy achieves a good balance between accuracy and running time. In BIB007 , the authors publish the service as a web tool and it can respond promptly to a math word problem. The solution in BIB001 , named ALGES, differs from BIB005 in two major ways. First, it adopts a more brutal-force manner to exploit all the possible equation trees. More specifically, ALGES does not discard irrevalent quantities, but enumerates all the syntactically valid trees. Integer Linear Programming (ILP) is applied as it can help enforce the constraints such as syntactic validity, type consistence and domain specific simplicity considerations. Consequently, its computation cost is dozens of times higher than that in BIB001 , according to an efficiency evaluation in  . Second, its scoring function is different from Equation 1. There is no need for the term φ(q) because ALGES does not build a classifier to check the quantity relevance. Besides the monotonic aggregation of the likelihood from local operator classifiers, the scoring function incorporates a new term φ(P) = θ T f p to assign a coherence score for the tree instance. Here, f P is the global feature extracted from a problem text P, and θ refers to the parameter vector. The goal of BIB008 is also to build an equation tree by parsing the problem text. It makes two assumptions that can simplify the tree construction, but also limit its applicability. First, the final output equation form is restricted to have at most two variables. Second, each quantity mentioned in the sentence can be used at most once in the final equation. The tree construction procedure consists of a pipeline of predictors that identify irrelevant quantities, recognize grounded variables, and generate the final equation tree. With customized feature selection and SVM based classifier, the relevant quantities and variables are extracted and used as the leaf nodes of the equation tree. The tree is built in a bottom-up manner. It is worth noting that to reduce the search space and simplify the tree construction, only adjacent nodes are combined to generate their parent node. UnitDep BIB006 can be viewed as an extension work of BIB005 by the same authors. An important concept, named Unit Dependency Graph (UDG), is proposed to enhance the scoring function. The vertices in UDG consist of the extracted quantities. If the quantity correspond to a rate (e.g., 8 dollars per hour), the vertex is marked as RATE. There are six types of edge relations to be considered, such as whether two quantities are associated with the same unit. Building the UDG requires additional annotation overhead as we need to train two classifiers for the nodes and edges. The node classifier determines whether a node is associated with a rate. The edge classifier predicts the type of relationship between any pair of quantity nodes. Given a valid unit dependency graph G generated by the classifiers, its likelihood is defined as In other words, we sum up the prediction probability for the RATE nodes and all the edges. The new scoring function for an expression tree extends Equation 1 by incorporating φ(G). Rules are defined to enforce the rate consistence between an expression tree T and a candidate graph G. For example, if v i is the only node in the tree that is labeled RATE and it appears in the question, there should not exist a path from the leaf node to the root which only contains operators of addition and subtraction. Finally, the candidate graph G with the highest likelihood and rate-consistent with T is used to calculate the total score of T . In  , Wang et al. made the first attempt of applying deep reinforcement learning to solve arithmetic word problems. The motivation is that deep Q-network has witnessed success in solving various problems with big search space such as playing text-based games BIB002 , information extraction BIB009 , text generation BIB003 and object detection in images BIB004 . To fit the math problem scenario, they formulate the expression tree construction as a Markov Decision Process and propose the MathDQN that is customized from the general deep reinforcement learning framework. Technically, they tailor the definitions of states, actions, and reward functions which are key components in the reinforcement learning framework. By using a two-layer feedforward neural network as the deep Q-network to approximate the Q-value function, the framework learns model parameters from the reward feedback of the environment. Compared to the aforementioned approaches, MathDQN iteratively picks the best operator for two selected quantities. This procedure can be viewed as beam search with k = 1 when exploiting candidate expression trees. Its deep Q-network acts as the operator classifier and guides the model to select the most promising operator for tree construction.