Learn to Solve Algebra Word Problems Using Quadratic Programming

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 817–822, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Learn to Solve Algebra Word Problems Using Quadratic Programming Lipu Zhou, Shuaixiang Dai, and Liwei Chen Baidu Inc., Beijing, China zhoulipu@outlook.com, {daishuaixiang, chenliwei}@baidu.com Abstract This paper presents a new algorithm to automatically solve algebra word prob- lems. Our algorithm solves a word prob- lem via analyzing a hypothesis space con- taining all possible equation systems gen- erated by assigning the numbers in the word problem into a set of equation sys- tem 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 base- line (Kushman et al., 2014). 1 Introduction An algebra word problem describes a mathemat- ical problem which can be typically modeled by an equation system, as demonstrated in Figure 1. Seeking to automatically solve word problems is a classical AI problem (Bobrow, 1964). The word problem solver is traditionally created by the rule- based approach (Lev et al., 2004; Mukherjee and Garain, 2008; Matsuzaki et al., 2013). Recently, using machine learning techniques to construct the solver has become a new trend (Kushman et al., 2014; Hosseini et al., 2014; Amnueypornsakul and Bhat, 2014; Roy et al., 2015). This is based on the fact that word problems derived from the same mathematical problem share some common semantic and syntactic features due to the same underlying logic. Our method follows this trend.1 To solve a word problem, our algorithm ana- lyzes all the possible ways to assign the numbers 1Our code is available at http://pan.baidu.com/ s/1dD336Sx Our method Kushman’s method Word problem An amusement park sells 2 kinds of tickets. Tickets for children cost $ 1.50. Adult tickets cost $ 4. On a certain day, 278 people entered the park. On that same day the admission fees collected totaled $ 792. How many children were admitted on that day? How many adults were admitted? Template 1 2 1 2 1 3 2 4 0 0 u u n n u n u n 1 1 1 2 1 2 2 2 1 3 2 4 0 0 u u n n u n u n Assignment 1 2 3 4 2,1.5, 4, 278, 792 , , , n n n n 1 1 2 2 1 2 3 4 1 2 1 2 2,1.5, 4, 278, 792, , , , , , , , nouns n n n n u u u u Possible Assignment 5 4 3 2 120 174 5 4 3 2 10022520 Figure 1: Comparison between our algorithm and (Kushman et al., 2014). Nouns are boldfaced. in the word problem to a set of equation system templates. Kushman et al. …

Content truncated to 500 words