The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Template Based Methods <s> Setting of the learning problem consistency of learning processes bounds on the rate of convergence of learning processes controlling the generalization ability of learning processes constructing learning algorithms what is important in learning theory?. <s> BIB001 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Template Based Methods <s> Most tasks require a person or an automated system to reasonto reach conclusions based on available information. The framework of probabilistic graphical models, presented in this book, provides a general approach for this task. The approach is model-based, allowing interpretable models to be constructed and then manipulated by reasoning algorithms. These models can also be learned automatically from data, allowing the approach to be used in cases where manually constructing a model is difficult or even impossible. Because uncertainty is an inescapable aspect of most real-world applications, the book focuses on probabilistic models, which make the uncertainty explicit and provide models that are more faithful to reality. Probabilistic Graphical Models discusses a variety of models, spanning Bayesian networks, undirected Markov networks, discrete and continuous models, and extensions to deal with dynamical systems and relational data. For each class of models, the text describes the three fundamental cornerstones: representation, inference, and learning, presenting both basic concepts and advanced techniques. Finally, the book considers the use of the proposed framework for causal reasoning and decision making under uncertainty. The main text in each chapter provides the detailed technical development of the key ideas. Most chapters also include boxes with additional material: skill boxes, which describe techniques; case study boxes, which discuss empirical cases related to the approach described in the text, including applications in computer vision, robotics, natural language understanding, and computational biology; and concept boxes, which present significant concepts drawn from the material in the chapter. Instructors (and readers) can group chapters in various combinations, from core topics to more technically advanced material, to suit their particular needs. Adaptive Computation and Machine Learning series <s> BIB002 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Template Based Methods <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> BIB003 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Template Based Methods <s> This paper presents a new algorithm to automatically solve algebra word problems. Our algorithm solves a word problem via analyzing a hypothesis space containing all possible equation systems generated by assigning the numbers in the word problem into a set of equation system templates extracted from the training data. To obtain a robust decision surface, we train a log-linear model to make the margin between the correct assignments and the false ones as large as possible. This results in a quadratic programming (QP) problem which can be efficiently solved. Experimental results show that our algorithm achieves 79.7% accuracy, about 10% higher than the state-of-the-art baseline (Kushman et al., 2014). <s> BIB004 </s> The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers <s> Template 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> BIB005
There are two methods BIB003 , BIB004 that pre-define a collection of equation set templates. Each template contains a set of number slots and unknown slots. The number slots are filled by the numbers extracted from the text and the unknown slots are aligned to the nouns. An example of template may look like where n i is a number slot and u i represents an unknown variable. To solve an equation set problem, these approaches first identify a candidate template from the corpus of pre-defined templates. The next task is to fill the number slots and unknown slots with the information extracted from the text. Finally, the instance with the highest probability is returned. This step often involves a scoring function or a rank-aware classifier such as RankSVM  . A widely-adopted practice is to define the probability of each instance of derivation y based on the feature representation x for a text problem and a parameter vector θ, as in BIB005 , BIB003 , BIB004 : With the optimal derivation instance y opt , we can obtain the final solution. In BIB003 , the objective is to maximize the total probabilities of y that leads to the correct answer. The latent variables θ are learned by directly optimizing the marginal data log-likelihood. More specifically, L-BFGS  is used to optimize the parameters. The search space is exponential to the number of slots because each number in the text can be mapped to any number slot and the nouns are also candidates for the unknown slots. In practice, the search space is too huge to find the optimal θ and beam search inference procedure is adopted to prevent enumerating all the possible y leading to the correct answer. For the completion of each template, the next slot to be considered is selected according to a pre-defined canonicalized ordering and only top-k partial derivations are maintained. In BIB004 , Zhou et al. proposed an enhanced algorithm for the template-based learning framework. First, they only consider assigning the number slots with numbers extracted from the text. The underlying logic is that when the number slots have been processed, it would be an easy task to fill the unknown slots. In this way, the hypothesis space can be significantly reduced. Second, the authors argue that the beam search used in BIB003 does not exploit all the training samples, and its resulting model may be sub-optimal. To resolve the issue, the max-margin objective BIB001 is used to train the log-linear model. The training process is turned into a QP problem that can be efficiently solved with the constraint generation algorithm BIB002 . Since the annotation of equation templates is expensive, a key challenge to KAZB and ZDC is the lack of sufficient annotated data. To resolve the issue, in  , Upadhyay et al. attempted to exploit the large number of algebra word problems that have been posted and discussed in online forums. These data are not explicitly annotated with equation templates but their numeric answers are extracted with little or no manual effort. The goal of  is to improve a strong solver trained by fully annotated data with a large number of math problems with noisy and implicit supervision signals. The proposed MixedSP algorithm makes use of both explicit and implicit supervised examples mixed at the training stage and learns the parameters jointly. With the learned model to formulate the mapping between an algebra word problem and an equation template, the math problem solving strategy is similar to KAZB and ZDC. All the templates in the training set have to be exploited to find the best alignment strategy. The aforementioned template-based methods suffer from two drawbacks  . First, the math concept is expressed as an entire template and may fail to work well when the training instances are sparse. Second, the learning process relies on lexical and syntactic features such as the dependency path between two slots in a template. Such a huge and sparse feature space may play a negative impact on effective feature learning. Based on these two arguments, FG-Expression  parses an equation template into fine-grained units, called template fragment. Each template is represented in a tree structure as in Figure 3 and each fragment represents a sub-tree rooted at an internal node. The main objective and challenge in  are learning an accurate mapping between textual information and template fragments. For instance, a text piece "20% discount" can be mapped to a template fragment 1 − n 1 with n 1 = 0.2. Such mappings are extracted in a semi-supervised way from training datasets and stored as part of the sketch for templates. The proposed solution to a math problem consists of two stages. First, RankSVM model  is trained to select top-k templates. The features used for the training incorporate textual features, quantity features and solution features. It is worth noting that the proposed template fragment is applied in the feature selection for the classifier. The textual features preserve one dimension to indicate whether the problem text contains textual expressions in each template fragment. In the second stage, the alignment is conducted for the k templates and the one with the highest probability is used to solve the problem. The features and rank-based classifier used to select the best alignment are similar to those used in the first stage. Compared to the previous template-based methods, FG-Expression also significantly reduces the search space because only top-k templates are examined whereas previous methods align numbers for all the templates in the training dataset.