Elamur Research⌕
☰
home / papers / 2015 / Solving Geometry Problems: Combining Text and Diagram Interpretation

Solving Geometry Problems: Combining Text and Diagram Interpretation

Paper · 2015 · Minjoon Seo, Hannaneh Hajishirzi, Ali Farhadi et al.

Summary

The paper presents GeoS, described as the first automated system that solves unmodified SAT plane-geometry multiple-choice questions. Each question combines a natural-language text with a raster diagram. GeoS turns both into a formal description in Ω, a typed subset of first-order logic with constants, variables, predicates and functions. It works in three steps:

  • The text parser deliberately over-generates candidate literals and scores each one with a log-linear model.
  • A diagram parser grounds those literals in the image and scores them.
  • A subset of literals is chosen by maximizing an objective that rewards affinity with text and diagram and penalizes redundancy (coherence). Because this objective is submodular, a greedy algorithm gives a near-optimal selection.

An algebraic solver then checks which answer choice is consistent with the chosen literals. GeoS scores 49% on official SAT questions and 61% on practice questions. The authors note that roughly half of a typical SAT math score is the median. Using the diagram also makes text interpretation and dependency parsing more accurate. This matters because it shows multimodal grounding can compensate for very small training sets, and the data and code are public.

Key points

  • End-to-end scores: 49% on official and 61% on practice SAT questions. Using only diagram parsing gives about 5–10%, and using only text parsing gives about 10%. With both parsers replaced by oracles, scores rise to 84% (official) and 88% (practice).
  • Text interpretation (official set, F1):
    • Rule-based baseline: 0.37 (P 0.99, R 0.23).
    • GeoS without the diagram: 0.67.
    • Full GeoS: 0.83.
    • A fully supervised generic semantic parser (Berant et al., 2013): about 33%.
  • Dependency parsing: GeoS reranks the top-50 trees from the Stanford parser (Chen and Manning, 2014) by its text score. This improves results by 16% over Stanford combined with an equation-separating preprocessor.
  • Error analysis: about 38% of errors come from text parsing and about 46% from diagram parsing, with about 15% failing in both. The remaining errors involve missing coreference or reasoning beyond the system's scope.
  • Availability: the dataset, annotations and source code are released at geometry.allenai.org.

Interesting ideas

  • I1. Over-generate, then select. Rather than committing to one parse, GeoS proposes many scored candidate relations and picks a consistent subset. This could suit any low-resource semantic parsing task, where a single fragile parse is risky.
  • I2. Submodular objective for interpretation. Combining an affinity term with a coverage/anti-redundancy term makes a greedy, near-optimal search possible. The same framing could apply to grounded tasks such as navigation instructions or extracting facts from tables.
  • I3. Cross-modal rescoring. Literals proposed from the text are checked against a second source of evidence, the diagram. The authors show this extra evidence substantially boosts precision. It is a cheap way to clean noisy NLP output wherever an aligned modality or structured resource exists.
  • I4. Reranking a generic parser's n-best list with downstream task scores. GeoS fixes errors in an off-the-shelf dependency parser without retraining it. This could help adapt UD-style parsers to domains with formulas or other special notation.
  • I5. Oracle-component ablations. Swapping individual modules for gold annotations shows where the error budget lies, which helps decide which component to improve first in a pipeline.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of WashingtonSeattle · United States263 works · 180,581 citations🔬Allen Institute for Artificial IntelligenceSeattle · United States219 works · 89,712 citations

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputer Vision and Pattern Recognition · 1,282 works

Cite

Cite as Minjoon Seo, Hannaneh Hajishirzi, Ali Farhadi, Oren Etzioni and Clint Malcolm. 2015. Solving Geometry Problems: Combining Text and Diagram Interpretation. Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d15-1171

@inproceedings{seo2015solving,
  title = {{Solving Geometry Problems: Combining Text and Diagram Interpretation}},
  author = {Minjoon Seo, Hannaneh Hajishirzi, Ali Farhadi, Oren Etzioni and Clint Malcolm},
  booktitle = {Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  doi = {10.18653/v1/d15-1171},
  url = {https://doi.org/10.18653/v1/d15-1171}
}

References

49 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Chris Alvin, Sumit Gulwani, Rupak Majumdar, and Supratik Mukhopadhyay. 2014. Synthesis of geometry proof problems. In AAAI. find
  2. Gabor Angeli and Christopher D. Manning. 2014. Naturalli: Natural logic inference for common sense reasoning. In EMNLP.
  3. Yoav Artzi and Luke Zettlemoyer. 2013. Weakly supervised learning of semantic parsers for mapping instructions to actions. TACL, 1.
  4. J. Berant and P. Liang. 2014. Semantic parsing via paraphrasing. In ACL.
  5. Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic parsing on freebase from question-answer pairs. In EMNLP.
  6. College Board. 2014. The college board. find
  7. Antoine Bordes, Nicolas Usunier, and Jason Weston. 2010. Label ranking under ambiguous supervision for learning semantic correspondences. In ICML. find
  8. SRK Branavan, Nate Kushman, Tao Lei, and Regina Barzilay. 2012. Learning high-level planning from text. In ACL. find
  9. William C. Bulko. 1988. Understanding text with an accompanying diagram. In IEA/AIE. find
  10. Danqi Chen and Christopher D Manning. 2014. A fast and accurate dependency parser using neural networks. In EMNLP.
  11. David Chen, Joohyun Kim, and Raymond Mooney. 2010. Training a multilingual sportscaster: Using perceptual context to learn language. JAIR, 37. find
  12. Jim Cowie and Wendy Lehnert. 1996. Information extraction. Communications of the ACM, 39(1). find
  13. Aron Culotta and Jeffrey Sorensen. 2004. Dependency tree kernels for relation extraction. In ACL.
  14. Jacob Eisenstein, James Clarke, Dan Goldwasser, and Dan Roth. 2009. Reading to learn: Constructing features from semantic abstracts. In EMNLP. find
  15. Thomas G Evans. 1964. A heuristic program to solve geometric-analogy problems. In Proceedings of the April 21-23, 1964, spring joint computer conference. find
  16. Hao Fang, Saurabh Gupta, Forrest Iandola, Rupesh Srivastava, Li Deng, Piotr Dollár, Jianfeng Gao, Xiaodong He, Margaret Mitchell, John Platt, et al. 2014. From captions to visual concepts and back. In CVPR. find
  17. Ali Farhadi, Mohsen Hejrati, Mohammad Amin Sadeghi, Peter Young, Cyrus Rashtchian, Julia Hockenmaier, and David Forsyth. 2010. Every picture tells a story: Generating sentences from images. In ECCV. find
  18. E.A. Feigenbaum and J. Feldman, editors. 1963. Computers and Thought. McGraw Hill, New York. find
  19. Jeffrey Flanigan, Sam Thomson, Jaime Carbonell, Chris Dyer, and Noah A. Smith. 2014. A discriminative graph-based parser for the abstract meaning representation. In ACL.
  20. Ruifang Ge and Raymond J. Mooney. 2006. Discriminative reranking for semantic parsing. In ACL. find
  21. Dan Goldwasser and Dan Roth. 2011. Learning from natural instructions. In IJCAI. find
  22. Yunchao Gong, Liwei Wang, Micah Hodosh, Julia Hockenmaier, and Svetlana Lazebnik. 2014. Improving image-sentence embeddings using large weakly annotated photo collections. In ECCV. find
  23. Sonal Gupta and Raymond J. Mooney. 2010. Using closed captions as supervision for video activity recognition. In AAAI. find
  24. Hannaneh Hajishirzi, Julia Hockenmaier, Erik T. Mueller, and Eyal Amir. 2011. Reasoning about robocup soccer narratives. In UAI. find
  25. Hannaneh Hajishirzi, Leila Zilles, Daniel S Weld, and Luke S Zettlemoyer. 2013. Joint coreference resolution and named-entity linking with multi-pass sieves. In EMNLP.
  26. Mary Hegarty and Marcel Adam Just. 1989. 10 understanding machines from text and diagrams. Knowledge acquisition from text and pictures. find
  27. Ben Hixon, Peter Clark, and Hannaneh Hajishirzi. 2015. Learning knowledge graphs for question answering through conversational dialog. In NAACL. find
  28. Mohammad Javad Hosseini, Hannaneh Hajishirzi, Oren Etzioni, and Nate Kushman. 2014. Learning to solve arithmetic word problems with verb categorization. In EMNLP.
  29. Rohit J. Kate and Raymond J. Mooney. 2007. Learning language semantics from ambiguous supervision. In AAAI. find
  30. Joohyun Kim and Raymond J. Mooney. 2013. Adapting discriminative reranking to grounded language learning. In ACL. find
  31. Dan Klein and Christopher D Manning. 2005. Parsing and hypergraphs. In New developments in parsing technology. Springer. find
  32. R Koncel-Kedziorski, Hannaneh Hajishirzi, and Ali Farhadi. 2014. Multi-resolution language grounding with weak supervision. In EMNLP. find
  33. Dieter et. al. Kraft. 1988. A software package for sequential quadratic programming. DFVLR Obers-faffeuhofen, Germany. find
  34. Girish Kulkarni, Visruth Premraj, Sagnik Dhar, Siming Li, Yejin Choi, Alexander C Berg, and Tamara L Berg. 2011. Baby talk: Understanding and generating image descriptions. In CVPR. find
  35. Nate Kushman, Yoav Artzi, Luke Zettlemoyer, and Regina Barzilay. 2014. Learning to automatically solve algebra word problems. In ACL. find
  36. T Kwiatkowski, E Choi, Y Artzi, and L Zettlemoyer. 2013. Scaling semantic parsers with on-the-fly ontology matching. In EMNLP.
  37. Percy Liang, Michael I. Jordan, and Dan Klein. 2009. Learning semantic correspondences with less supervision. In ACLAFNLP.
  38. Xinggang Lin, Shigeyoshi Shimotsuji, Michihiko Minoh, and Toshiyuki Sakai. 1985. Efficient diagram understanding with characteristic pattern detection. CVGIP, 30(1). find
  39. A. Lovett and K. Forbus. 2012. Modeling multiple strategies for solving geometric analogy problems. In CCS. find
  40. Gordon Novak. 1995. Diagrams for solving physical problems. Diagrammatic reasoning: Cognitive and computational perspectives. find
  41. Lawrence O’Gorman and Rangachar Kasturi. 1995. Document image analysis, volume 39. Citeseer. find
  42. Hoifung Poon and Pedro Domingos. 2009. Unsupervised semantic parsing. In EMNLP.
  43. Siva Reddy, Mirella Lapata, and Mark Steedman. 2014. Large-scale semantic parsing without question-answer pairs. TACL, 2(Oct). find
  44. S. Roy, T. Vieira, and D. Roth. 2015. Reasoning about quantities in natural language. find
  45. Min Joon Seo, Hannaneh Hajishirzi, Ali Farhadi, and Oren Etzioni. 2014. Diagram understanding in geometry questions. In AAAI. find
  46. Rohini K Srihari. 1994. Computational models for integrating linguistic and visual information: A survey. Artificial Intelligence Review, 8(5-6). find
  47. Adam Vogel and Daniel Jurafsky. 2010. Learning to follow navigational directions. In ACL. find
  48. David J Wales and Jonathan PK Doye. 1997. Global optimization by basin-hopping and the lowest energy structures of lennard-jones clusters containing up to 110 atoms. The Journal of Physical Chemistry A, 101(28). find
  49. Luke S. Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In UAI.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/seo-2015-solving-geometry-problems-combining-text/