Parsing Algebraic Word Problems into Equations

Parsing Algebraic Word Problems into Equations Rik Koncel-Kedziorski, Hannaneh Hajishirzi, Ashish Sabharwal†, Oren Etzioni†, and Siena Dumas Ang University of Washington, †Allen Institute for AI {kedzior,hannaneh,sienaang}@uw.edu, {ashishs,orene}@allenai.org Abstract This paper formalizes the problem of solv- ing multi-sentence algebraic word problems as that of generating and scoring equation trees. We use integer linear programming to gener- ate equation trees and score their likelihood by learning local and global discriminative mod- els. 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 Kush- man et al. (2014) approach on single-equation problems, yielding a 15% to 50% reduction in error. 1 Introduction Grade-school algebra word problems are brief nar- ratives (see Figure 1). A typical problem first de- scribes a partial world state consisting of characters, entities, and quantities. Next it updates the condition of an entity or explicates the relationship between entities. Finally, it poses a question about a quantity in the narrative. An ordinary child has to learn the required alge- bra, but will easily grasp the narrative utilizing ex- tensive world knowledge, large vocabulary, word- sense disambiguation, coreference resolution, mas- tery of syntax, and the ability to combine individual Oceanside Bike Rental Shop charges 17 dollars plus 7 dollars an hour for renting a bike. Tom paid 80 dollars to rent a bike. How many hours did he pay to have the bike checked out? = +$ 17$ ∗$ 7$ xh 80$ solution : 9 17 + (7 ∗ x) = 80 Figure 1: Example problem and solution sentences into a coherent mental model. In contrast, the challenge for an NLP system is to “make sense” of the narrative, which may refer to arbitrary activ- ities like renting bikes, collecting coins, or eating cookies. Previous work coped with the open-domain as- pect of algebraic word problems by relying on deter- ministic state transitions based on verb categoriza- tion (Hosseini et al., 2014) or by learning templates that cover equations of particular forms (Kushman et al., 2014). We have discovered, however, that both approaches are brittle, particularly as training data is scarce in this domain, and the space of equations grows exponentially with the number of quantities mentioned in the math problem. We introduce ALGES,1 which maps an unseen multi-sentence algebraic word problem into a set of possible equation trees. Figure 1 shows an equation tree alongside the word problem it represents. ALGES generates the space of trees via Integer Linear Programming (ILP), which allows it to con- 1The code and data is publicly available at https:// gitlab.cs.washington.edu/ALGES/TACL2015 . 585 Transactions of the Association for Computational Linguistics, vol. 3, pp. 585–597, 2015. Action Editor: Regina Barzilay. Submission batch: …

Content truncated to 500 words