The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> This paper describes a system for extracting typed dependency parses of English sentences from phrase structure parses. In order to capture inherent relations occurring in corpus texts that can be critical in real-world applications, many NP relations are included in the set of grammatical relations used. We provide a comparison of our system with Minipar and the Link parser. The typed dependency extraction facility described here is integrated in the Stanford Parser, available for download. <s> BIB001 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> We present a novel deterministic dependency parsing algorithm that attempts to create the easiest arcs in the dependency structure first in a non-directional manner. Traditional deterministic parsing algorithms are based on a shift-reduce framework: they traverse the sentence from left-to-right and, at each step, perform one of a possible set of actions, until a complete tree is built. A drawback of this approach is that it is extremely local: while decisions can be based on complex structures on the left, they can look only at a few words to the right. In contrast, our algorithm builds a dependency tree by iteratively selecting the best pair of neighbours to connect at each parsing step. This allows incorporation of features from already built structures both to the left and to the right of the attachment point. The parser learns both the attachment preferences and the order in which they should be performed. The result is a deterministic, best-first, O(nlogn) parser, which is significantly more accurate than best-first transition based parsers, and nears the performance of globally optimized parsing models. <s> BIB002 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> Natural language parsing has typically been done with small sets of discrete categories such as NP and VP, but this representation does not capture the full syntactic nor semantic richness of linguistic phrases, and attempts to improve on this by lexicalizing phrases or splitting categories only partly address the problem at the cost of huge feature spaces and sparseness. Instead, we introduce a Compositional Vector Grammar (CVG), which combines PCFGs with a syntactically untied recursive neural network that learns syntactico-semantic, compositional vector representations. The CVG improves the PCFG of the Stanford Parser by 3.8% to obtain an F1 score of 90.4%. It is fast to train and implemented approximately as an efficient reranker it is about 20% faster than the current Stanford factored parser. The CVG learns a soft notion of head words and improves performance on the types of ambiguities that require semantic information such as PP attachments. <s> BIB003 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> Almost all current dependency parsers classify based on millions of sparse indicator features. Not only do these features generalize poorly, but the cost of feature computation restricts parsing speed significantly. In this work, we propose a novel way of learning a neural network classifier for use in a greedy, transition-based dependency parser. Because this classifier learns and uses just a small number of dense features, it can work very fast, while achieving an about 2% improvement in unlabeled and labeled attachment scores on both English and Chinese datasets. Concretely, our parser is able to parse more than 1000 sentences per second at 92.2% unlabeled attachment score on the English Penn Treebank. <s> BIB004 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> This paper presents a novel approach to learning to solve simple arithmetic word problems. Our system, ARIS, analyzes each of the sentences in the problem statement to identify the relevant variables and their values. ARIS then maps this information into an equation that represents the problem, and enables its (trivial) solution as shown in Figure 1. The paper analyzes the arithmetic-word problems “genre”, identifying seven categories of verbs used in such problems. ARIS learns to categorize verbs with 81.2% accuracy, and is able to solve 77.7% of the problems in a corpus of standard primary school test questions. We report the first learning results on this task without reliance on predefined templates and make our data publicly available. 1 <s> BIB005 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> We present an approach for automatically learning to solve algebra word problems. Our algorithm reasons across sentence boundaries to construct and solve a system of linear equations, while simultaneously recovering an alignment of the variables and numbers in these equations to the problem text. The learning algorithm uses varied supervision, including either full equations or just the final answers. We evaluate performance on a newly gathered corpus of algebra word problems, demonstrating that the system can correctly answer almost 70% of the questions in the dataset. This is, to our knowledge, the first learning result for this task. <s> BIB006 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <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> BIB007 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <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> BIB008 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> Solving simple arithmetic word problems is one of the challenges in Natural Language Understanding. This paper presents a novel method to learn to use formulas to solve simple arithmetic word problems. Our system, analyzes each of the sentences to identify the variables and their attributes; and automatically maps this information into a higher level representation. It then uses that representation to recognize the presence of a formula along with its associated variables. An equation is then generated from the formal description of the formula. In the training phase, it learns to score the pair from the systematically generated higher level representation. It is able to solve 86.07% of the problems in a corpus of standard primary school test questions and beats the state-of-the-art by <s> BIB009 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <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> BIB010 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Preprocessing <s> Math word problems form a natural abstraction to a range of quantitative reasoning problems, such as understanding financial news, sports results, and casualties of war. Solving such problems requires the understanding of several mathematical concepts such as dimensional analysis, subset relationships, etc. In this paper, we develop declarative rules which govern the translation of natural language description of these concepts to math expressions. We then present a framework for incorporating such declarative knowledge into word problem solving. Our method learns to map arithmetic word problem text to math expressions, by learning to select the relevant declarative knowledge for each operation of the solution expression. This provides a way to handle multiple concepts in the same problem while, at the same time, support interpretability of the answer expression. Our method models the mapping to declarative knowledge as a latent variable, thus removing the need for expensive annotations. Experimental evaluation suggests that our domain knowledge based solver outperforms all other systems, and that it generalizes better in the realistic case where the training data it is exposed to is biased in a different way than the test data. <s> BIB011
Before we review the feature space defined in various MWP solvers, we first present the preliminary background on the preprocessing steps that have been commonly adopted to facilitate the subsequent feature extraction. Syntactic parsing focuses on organizing the lexical units and their semantic dependency in a tree structure, which serves as a useful resource for effective feature selection. Sorts of parsers have been developed, among which the Stanford parser works as the most comprehensive and widely-adopted one. It is a package consisting of different probabilistic natural language parsers. To be more specific, its neural-network parser BIB004 is a transition-based dependency parser that uses high-order features to achieve high speed and good accuracy; the Compositional Vector Grammar parser BIB003 can be seen as factoring discrete and continuous parsing in one model; and the (English) Stanford Dependencies representation BIB001 is an automatic system to extract typed dependency parses from phrase structure parses, where a dependency parse represents dependencies between individual words and a phrase structure parse represents nesting of multi-word constituents. Besides Stanford parser, there exist other effective dependency parsers with their own traits. For example, BIB002 presents an easy-fist parsing algorithm that iteratively selects the best pair of neighbors in the tree structure to connect at each parsing step. Those parsers account in WMP solvers. For instance, the neural-network parser BIB004 is adopted in BIB011 for coreference resolution, which is another pre-processing step for MWP solvers. UnitDep BIB008 automatically generates features from a given math problem by analyzing its derived parser tree using the Compositional Vector Grammar parser BIB003 . Additionally, the Stanford Dependencies representation BIB001 has been applied in multitple solvers. We observed its occurrence in Formula BIB009 and ARIS BIB005 to extract attributes of entities (the subject, verb, object, preposition and temporal information), in KAZB BIB006 to generate part-of-speech tags, lematizations, and dependency parses to compute features, and in ALGES BIB007 to obtain syntactic information used for grounding and feature computation. ExpressionTree BIB010 is an exceptional case without using Stanford Parser. Instead, it uses the easy-fist parsing algorithm BIB002 to detect the verb associated with each quantity.