Solving Geometry Problems: Combining Text and Diagram Interpretation

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1466–1476, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Solving Geometry Problems: Combining Text and Diagram Interpretation Minjoon Seo, Hannaneh Hajishirzi, Ali Farhadi, Oren Etzioni, Clint Malcolm University of Washington, Allen Institute for Artificial Intelligence {minjoon,hannaneh,clintm}@washington.edu,{alif,orene}@allenai.org Abstract This paper introduces GEOS, the first au- tomated system to solve unaltered SAT ge- ometry questions by combining text un- derstanding and diagram interpretation. We model the problem of understanding geometry questions as submodular opti- mization, and identify a formal problem description likely to be compatible with both the question text and diagram. GEOS then feeds the description to a geometric solver that attempts to determine the cor- rect answer. In our experiments, GEOS achieves a 49% score on official SAT ques- tions, and a score of 61% on practice ques- tions.1 Finally, we show that by integrat- ing textual and visual information, GEOS boosts the accuracy of dependency and se- mantic parsing of the question text. 1 Introduction This paper introduces the first fully-automated system for solving unaletered SAT-level geomet- ric word problems, each of which consists of text and the corresponding diagram (Figure 1). The ge- ometry domain has a long history in AI, but previ- ous work has focused on geometric theorem prov- ing (Feigenbaum and Feldman, 1963) or geomet- ric analogies (Evans, 1964). Arithmetic and alge- braic word problems have attracted several NLP researchers (Kushman et al., 2014; Hosseini et al., 2014; Roy et al., 2015), but geometric word prob- lems were first explored only last year by Seo et al. (2014). Still, this system merely aligned diagram elements with their textual mentions (e.g., “Circle O”)—it did not attempt to fully represent geome- try problems or solve them. Answering geometry questions requires a method that interpert question text and diagrams in concert. 1The source code, the dataset and the annotations are pub- licly available at geometry.allenai.org. In the diagram at the le., circle O has a radius of 5, and CE = 2. Diameter AC is perpendicular to chord BD. What is the length of BD? In isosceles triangle ABC at the le., lines AM and CM are the angle bisectors of angles BAC and BCA. What is the measure of angle AMC? In the figure at le., The bisector of angle BAC is perpendicular to BC at point D. If AB = 6 and BD = 3, what is the measure of angle BAC? Equals(RadiusOf(O), 5) IsCircle(O) Equals(LengthOf(CE), 2) IsDiameter(AC) IsChord(BD) Perpendicular(AC), BD) Equals(what, Length(BD)) IsIsoscelesTriangle(ABC) BisectsAngle(AM, BAC) IsLine(AM) CC(AM, CM) CC(BAC, BCA) IsAngle(BAC) IsAngle(AMC) Equals(what, MeasureOf(AMC)) a) 110 b) 115 c) 120 d) 125 e) 130 IsAngle(BAC) BisectsAngle(line, BAC) Perpendicular (line, BC) Equals(LengthOf(AB), 6) Equals(LengthOf(BD), 3) IsAngle(BAC) Equals(what, MeasureOf(BAC)) a) 15 b) 30 c) 45 d) 60 e) 75 correct correct correct (a) (b) (c) Ques*ons a) 12 b) 10 c) 8 d) 6 e) 4 Interpreta*ons Figure 1: Questions (left column) and interpretations (right column) derived by GEOS. The geometry genre …

Content truncated to 500 words