Elamur Research
☰
home / papers / 2021 / Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning

Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning

Written for the Research library (claude-opus-5-5) from the paper text. Original — arxiv.org/pdf/2105.04165v3

Summary

Solving high-school geometry problems automatically means reading both the text and the diagram, then reasoning step by step with theorems. Earlier systems needed diagram symbols labelled by hand and gave no readable solution trace. They were also tested on datasets that were small or not public. The authors tackle these problems in two ways. First, they release Geometry3K, a benchmark of 3,002 multiple-choice problems taken from two textbooks for grades 6–12. Every problem's text and diagram is annotated in a shared formal language built from 91 predicates. Second, they propose Inter-GPS. It turns the question text into formal literals using template rules and uses a neural object detector to get literals from the diagram. A symbolic solver then applies theorems written as conditional rules. A theorem predictor suggests which theorems to try first, which shortens the search. With fully automatic parsing, Inter-GPS reaches 57.5% accuracy on Geometry3K. That is far above neural baselines and, by the authors' report, above human performance. It also sets a new best result on GEOS. Because every reasoning step is explicit, the solution can be inspected, which matters for education tools and neuro-symbolic research.

Key points

  • Geometry3K: 3,002 SAT-style problems from the McGraw-Hill and Geometryonline digital libraries. It covers 6 shape types and 4 goal types and includes trigonometric operators. GEOS has only 186 problems, and the larger GEOS++ (1,406) and GEOS-OS (2,235) were never released.
  • Parsing: the rule-based text parser is 97% accurate, compared with 67% for a semantic parser. Giving Inter-GPS ground-truth diagram literals raises accuracy by 17.5 points, so the diagram parser is the main bottleneck.
  • Accuracy: 57.5% with automatically generated literals and 78.3% with fully annotated formal language, a gain of 20.8 points.
  • Search strategy: running predicted theorems first and then lower-order ones ("Predict+Low-first") gives the best accuracy, 78.3%. It needs about 7.1 search steps on average, compared with 13.2 for random ordering. About 66% of solved problems need two steps or fewer.
  • Neural baselines: a neural Q+I baseline gains 9.2 points when its inputs are replaced with formal annotations. Remaining failures come from ambiguous diagrams, nested text expressions, and problems with combined shapes or shaded areas.

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

Fields: Mathematics & statistics

Cited by

120 papers of our library cite it (of the 140673 whose bibliographies we read); 20 of them have a page here, 100 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2105.04165 · arXiv 2105.04165

@misc{lu2021inter,
  title = {{Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning}},
  author = {Lu, Pan and Gong, Ran and Jiang, Shibiao and Qiu, Liang and Huang, Siyuan and Liang, Xiaodan and Zhu, Song-Chun},
  year = {2021},
  doi = {10.48550/arxiv.2105.04165},
  eprint = {2105.04165},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2105.04165}
}

References

40 references, 8 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 Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). find
  2. Chris Alvin, Sumit Gulwani, Rupak Majumdar, and Supratik Mukhopadhyay. 2017. Synthesis of solutions for shaded area geometry problems. In The Thirtieth International Flairs Conference. find
  3. Aida Amini, Saadia Gabriel, Peter Lin, Rik Koncel-Kedziorski, Yejin Choi, and Hannaneh Hajishirzi. 2019. Mathqa: Towards interpretable math word problem solving with operation-based formalisms. In Proceedings of Annual Conference of the North American Chapter of the Association for Computational Lin… find our card
  4. Feng Han and Song-Chun Zhu. 2005. Bottom-up/top-down image parsing by attribute graph grammar. In Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1, volume 2, pages 1778– 1785. IEEE. find
  5. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778. find
  6. Yining Hong, Qing Li, Daniel Ciao, Siyuan Huang, and Song-Chun Zhu. 2021. Learning by fixing: Solving math word problems with weak supervision. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI-21. find
  7. Mislav Balunovic, Pavol Bielik, and Martin T Vechev. 2018. Learning to solve smt formulas. In Advances in Neural Information Processing Systems (NeurIPS), pages 10338–10349. find
  8. Mark Hopkins, Ronan Le Bras, Cristian Petrescu-Prahova, Gabriel Stanovsky, Hannaneh Hajishirzi, and Rik Koncel-Kedziorski. 2019. Semeval-2019 task 10: Math question answering. In Proceedings of the 13th International Workshop on Semantic Evaluation, pages 893–899. find
  9. Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2014. Tailoring continuous word representations for dependency parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 809–815. find our card
  10. Danqing Huang, Shuming Shi, Chin-Yew Lin, and Jian Yin. 2017. Learning fine-grained expressions to solve math word problems. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP), pages 805–814. find
  11. Trapit Bansal, Arvind Neelakantan, and Andrew Mc-Callum. 2017. Relnet: End-to-end modeling of entities & relations. arXiv preprint arXiv:1706.07179. — [arXiv:1706.07179](https://arxiv.org/abs/1706.07179) find
  12. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 595–603. find our card
  13. Mohan Chinnappan. 1998. Schemas and mental models in geometry problem solving. Educational Studies in Mathematics, 36(3):201–217. find
  14. Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv:1409.1259. find our card
  15. Shang-Ching Chou, Xiao-Shan Gao, and Jing-Zhong Zhang. 1996. Automated generation of readable proofs with geometric invariants. Journal of Automated Reasoning, 17(3):325–347. find
  16. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT (NAACL). find
  17. Wenbin Gan and Xinguo Yu. 2018. Automatic understanding and formalization of natural language geometry problems using syntax-semantics models. International Journal of Innovative Computing, Information and Control, pages 83–98. find
  18. Wenbin Gan, Xinguo Yu, Ting Zhang, and Mingshu Wang. 2019. Automatically proving plane geometry theorems stated by text and diagram. International Journal of Pattern Recognition and Artificial Intelligence, 33(07):1940003. find
  19. Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020. Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. In Proceedings of the 58th Annual Meeting of the… find our card
  20. Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. 2017. Focal loss for dense object detection. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 2980–2988. find our card
  21. Sarah Loos, Geoffrey Irving, Christian Szegedy, and Cezary Kaliszyk. 2017. Deep network guided proof search. arXiv preprint arXiv:1701.06972. find
  22. Takuya Matsuzaki, Takumi Ito, Hidenao Iwane, Hirokazu Anai, and Noriko H Arai. 2017. Semantic parsing of pre-university math problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL), pages 2131–2141. find
  23. Andi Saparuddin Nur and Evy Nurvitasari. 2017. Geometry skill analysis in problem solving reviewed from the difference of cognitive style students junior high school. Journal of Educational Science and Technology (EST), 3(3):204–210. find
  24. Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville. 2018. Film: Visual reasoning with a general conditioning layer. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 32. find our card
  25. Jinghui Qin, Lihui Lin, Xiaodan Liang, Rumin Zhang, and Liang Lin. 2020. Semantically-aligned universal tree-structured solver for math word problems. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 3780–3789. find
  26. Subhro Roy and Dan Roth. 2018. Mapping to declarative knowledge for word problem solving. Transactions of the Association for Computational Linguistics (TACL), 6:159–172. find our card
  27. Mrinmaya Sachan, Avinava Dubey, Eduard H Hovy, Tom M Mitchell, Dan Roth, and Eric P Xing. 2020. Discourse in multimedia: A case study in extracting geometry knowledge from textbooks. Computational Linguistics, 45(4):627–665. find
  28. Mrinmaya Sachan, Kumar Dubey, and Eric Xing. 2017. From textbooks to knowledge: A case study in harvesting axiomatic knowledge from textbooks to solve geometry problems. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP), pages 773–784. find
  29. Mrinmaya Sachan and Eric Xing. 2017. Learning to solve geometry problems from natural language demonstrations in textbooks. In Proceedings of the 6th Joint Conference on Lexical and Computational Semantics, pages 251–261. find
  30. Min Joon Seo, Hannaneh Hajishirzi, Ali Farhadi, and Oren Etzioni. 2014. Diagram understanding in geometry questions. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). find
  31. Minjoon Seo, Hannaneh Hajishirzi, Ali Farhadi, Oren Etzioni, and Clint Malcolm. 2015. Solving geometry problems: Combining text and diagram interpretation. In Proceedings of Empirical Methods in Natural Language Processing (EMNLP), pages 1466– 1476. find
  32. Linda G Shapiro and George C Stockman. 2001. Computer vision. Prentice Hall. find
  33. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural networks. arXiv preprint arXiv:1409.3215. find
  34. Kewei Tu, Meng Meng, Mun Wai Lee, Tae Eun Choe, and Song-Chun Zhu. 2014. Joint video and text parsing for understanding events and answering queries. IEEE MultiMedia, 21(2):42–70. find
  35. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in Neural Information Processing Systems (NeurIPS), 30:5998–6008. find
  36. Lei Wang, Yan Wang, Deng Cai, Dongxiang Zhang, and Xiaojiang Liu. 2018. Translating a math word problem to an expression tree. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP). find
  37. Lei Wang, Dongxiang Zhang, Jipeng Zhang, Xing Xu, Lianli Gao, Bing Tian Dai, and Heng Tao Shen. 2019. Template-based math word problem solvers with recursive neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 33, pages 7144–7151. find
  38. Wu Wen-Tsun. 1986. Basic principles of mechanical theorem proving in elementary geometries. Journal of Automated Reasoning, 2(3):221–252. find
  39. Xinguo Yu, Mingshu Wang, Wenbin Gan, Bin He, and Nan Ye. 2019. A framework for solving explicit arithmetic word problems and proving plane geometry theorems. International Journal of Pattern Recognition and Artificial Intelligence, 33(07):1940005. find
  40. Song-Chun Zhu and David Mumford. 2006. A stochastic grammar of images. Foundations and Trends in Computer Graphics and Vision, 2(4):259–362. find