Beyond Sentential Semantic Parsing: Tackling the Math SAT with a Cascade of Tree Transducers

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 795–804 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Beyond Sentential Semantic Parsing: Tackling the Math SAT with a Cascade of Tree Transducers Mark Hopkins, Cristian Petrescu-Prahova, Roie Levin, Ronan Le Bras, Alvaro Herrasti, and Vidur Joshi Allen Institute for Artificial Intelligence Seattle, WA {markh,cristipp,roiel,rlebras,alvaroh,vidurj}@allenai.org Abstract We present an approach for answering questions that span multiple sentences and exhibit sophisticated cross-sentence anaphoric phenomena, evaluating on a rich source of such questions – the math por- tion of the Scholastic Aptitude Test (SAT). By using a tree transducer cascade as its basic architecture, our system (called EU- CLID) propagates uncertainty from multi- ple sources (e.g. coreference resolution or verb interpretation) until it can be con- fidently resolved. Experiments show the first-ever results (43% recall and 91% pre- cision) on SAT algebra word problems. We also apply EUCLID to the public Dol- phin algebra question set, and improve the state-of-the-art F1-score from 73.9% to 77.0%. 1 Introduction Math word problems pose questions that are chal- lenging for current question answering (QA) sys- tems to solve. Consider the following question originating from a study guide for the Math SAT1: Example 1: Suppose 3x + y = 15, where x is a positive integer. What is the difference between the largest possi- ble value of y and the smallest possible value of x, assuming that y is also a pos- itive integer? The correct response is 11; however its relation- ship with the other numbers in the question (3 and 15) is oblique and not easily mapped to an opera- tor tree or equation template. This encourages us to build a semantic parser that produces an explicit 1The Math SAT is a standardized exam administered to college-bound high school students in the United States. representation of what the question is asking, if we want to make quantitative progress on the question set. However, while it is not hard to formalize the semantics: X × Y = {(x, y) | 3x + y = 15, x, y ∈ Z+} X = {x | (x, y) ∈ X × Y } Y = {y | (x, y) ∈ X × Y } solve: max Y − min X it is not clear how to devise a compositional trans- formation from the original question to the formal semantics, since the meaning is dispersed through- out the discourse, such that neither the maximiza- tion nor the minimization can be locally derived from some subtree of the syntactic structure. Moreover, SAT questions quickly reach the lim- its of preprocessing tools like anaphora resolution: Example 2: ⟨r, s, t⟩ In the sequence above, if each term after the first is x more than the previous term, what is the average of r, s, and t in terms of r and x? Understanding this question requires a nuanced resolution of each term after the first to the subse- quence ⟨s, t⟩, a coreference resolution beyond the …

Content truncated to 500 words