Special Section on the Pacific-Rim Symposium on Image and Video Technology (PSIVT); Guest Editors: Xinguo Yu and Chao Sun (Central China Normal University)No Access

A Framework for Solving Explicit Arithmetic Word Problems and Proving Plane Geometry Theorems

Xinguo Yu

National Engineering Research Center for E-Learning, Central China Normal University, Wuhan 430079, P. R. China

E-mail Address: [email protected]

Search for more papers by this author

Mingshu Wang

National Engineering Research Center for E-Learning, Central China Normal University, Wuhan 430079, P. R. China

E-mail Address: [email protected]

Search for more papers by this author

Wenbin Gan

National Engineering Research Center for E-Learning, Central China Normal University, Wuhan 430079, P. R. China

E-mail Address: [email protected]

Search for more papers by this author

Bin He

http://orcid.org/0000-0003-2088-8193

National Engineering Research Center for E-Learning, Central China Normal University, Wuhan 430079, P. R. China

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

, and

Nan Ye

University of Queensland, Brisbane 4072, Australia

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0218001419400056Cited by:28 (Source: Crossref)

Abstract

This paper presents a framework for solving math problems stated in a natural language (NL) and applies the framework to develop algorithms for solving explicit arithmetic word problems and proving plane geometry theorems. We focus on problem understanding, that is, the transformation of a NL description of a math problem to a formal representation. We view this as a relation extraction problem, and adopt a greedy algorithm to extract the mathematical relations using a syntax-semantics model, which is a set of patterns describing how a syntactic pattern is mapped to its formal semantics. Our method yields a human readable solution that shows how the mathematical relations are extracted one at a time. We apply our framework to solve arithmetic word problems and prove plane geometry theorems. For arithmetic word problems, the extracted relations are transformed into a system of equations, and the equations are then solved to produce the solution. For plane geometry theorems, these extracted relations are input to an inference system to generate the proof. We evaluate our approach on a set of arithmetic word problems stated in Chinese, and two sets of plane geometry theorems stated in Chinese and English. Our algorithms achieve high accuracies on these datasets and they also show some desirable properties such as brevity of algorithm description and legibility of algorithm actions.

Keywords:

References

1. F. Botana, M. Hohenwarter, P. Janicic and S. Weitzhofer, Automated theorem proving in GeoGebra: Current achievements, J. Automated Reason. 55(1) (2015) 39–59. Crossref, Web of Science, Google Scholar
2. X. S. Gao, D. K. Wang, Z. Qiu and H. Yang, Equation Solving and Machine Proving-Problem Solving with Mmp (Science Press, 2006). Google Scholar
3. M. J. Hosseini, H. Hajishirzi, O. Etzioni and N. Kushman, Learning to solve arithmetic word problems with verb categorization, in Conf. Empirical Methods in Natural Language Processing (Doha, Qatar, 2014), pp. 523–533. Crossref, Google Scholar
4. C. T. Huang, Y. C. Lin and K. Y. Su, Explanation generation for a math word problem solver, Int. J. Comput. Linguist. Chinese Lang. Process. 20 (2015), pp. 64–70. Google Scholar
5. D. Huang, S. Shi, C. Y. Lin and J. Yin, Learning fine-grained expressions to solve math word problems, Conf. Empirical Methods in Natural Language Processing (Copenhagen, Denmark, 2017), pp. 805–814. Crossref, Google Scholar
6. D. Huang, S. Shi, C. Y. Lin, J. Yin and W. Y. Ma, How well do computers solve math word problems? Large-scale dataset construction and evaluation, in Meeting of the Association for Computational Linguistics (Berlin, Germany, 2016), pp. 887–896. Crossref, Google Scholar
7. ICTCLAS (Institute of Computing Technology, Chinese Lexical Analysis System) http://ictclas.nlpir.org/. Google Scholar
8. J. Jiang and J. Zhang, A review and prospect of readable machine proofs for geometry theorems, J. Syst. Sci. Complex. 25(4) (2012) 802–820. Crossref, Web of Science, Google Scholar
9. A. M. Johnson, K. R. Butcher, G. Ozogul and M. Reisslein, Introductory circuit analysis learning from abstract and contextualized circuit representations: Effects of diagram labels, IEEE Trans. Edu. 57 (2014) 160–168. Crossref, Web of Science, Google Scholar
10. W. Kintsch and J. G. Greeno, Understanding and solving word arithmetic problems, Psycholo. Rev. 92(1) (1985) 109–29. Crossref, Web of Science, Google Scholar
11. R. Koncel-Kedziorski, S. Roy, A. Amini, N. Kushman and H. Hajishirzi, MAWPS: A math word problem repository, in Conf. North American Chapter of the Association for Computational Linguistics: Human Language Technologies (San Diego, California, USA, 2016), pp. 1152–1157. Crossref, Google Scholar
12. R. Koncel-Kedziorski, H. Hajishirzi, A. Sabharwal, O. Etzioni and S. D. Ang, Parsing algebraic word problems into equations, J. Comput. Biol. 7(1–2) (1999) 293–302. Google Scholar
13. N. Kushman, L. Zettlemoyer, R. Barzilay, Y. Artzi, N. Kushman, L. Zettlemoyer, R. Barzilay and Y. Artzi, Learning to automatically solve algebra word problems, in Annual Meeting of the Association for Computational Linguistics (Baltimore, Maryland, USA, 2014), pp. 271–281. Crossref, Google Scholar
14. C. Liguda and T. Pfeiffer, Modeling math word problems with augmented semantic networks, Int. Conf. Application of Natural Language to Information Systems (Springer, Berlin, Heidelberg, 2012), pp. 247–252. Crossref, Google Scholar
15. Y. C. Lin, C. C. Liang, K. Y. Hsu, C. T. Huang, S. Y. Miao, W. Y. Ma, L. W. Ku, C. J. Liau and K. Y. Su, Designing a tag-based statistical math word problem solver with reasoning and explanation, Int. J. Comput. Linguist. Chin. Lang. Process. 20 (2015) 58–63. Google Scholar
16. Q. T. Liu, H. Huang and L. J. Wu, Using restricted natural language for geometric construction, Appl. Mech. Mater. 145 (2012) 465–469. Crossref, Google Scholar
17. Y. Ma, Y. Zhou, G. Cui, Y. Ren and R. Huang, Frame-based calculus of solving arithmetic multi-step addition and subtraction word problems, Second Int. Workshop Education Technology and Computer Science (Wuhan, China, 2010), pp. 476–479. Google Scholar
18. T. Matsuzaki, H. Iwane, H. Anai and N. H. Arai, The most uncreative examinee: A first step toward wide coverage natural language math problem solving, Conf. Conf. American Association for Artificial Intelligence (Quebec, Canada, 2014), pp. 1098–1104. Crossref, Google Scholar
19. A. Mukherjee and U. Garain, A review of methods for automatic understanding of natural language mathematical problems, Artif. Intell. Rev. 29(2) (2008) 93–122. Crossref, Web of Science, Google Scholar
20. L. S. Myneni, N. H. Narayanan, S. Rebello, A. Rouinfar and S. Pumtambekar, An interactive and intelligent learning system for physics education, IEEE Trans. Learn. Technol. 6 (2013) 228–239. Crossref, Web of Science, Google Scholar
21. S. Roy and R. Dan, Unit dependency graph and its application to arithmetic word problem solving, Conf. American Association for Artificial Intelligence (San Francisco, California, 2017), pp. 3082–3088. Crossref, Google Scholar
22. S. Roy and D. Roth, Solving general arithmetic word problems, Conf. Empirical Methods in Natural Language Processing (Lisbon, Portugal, 2015), pp. 1743–1752. Crossref, Google Scholar
23. M. Seo, H. Hajishirzi, A. Farhadi, O. Etzioni and C. Malcolm, Solving geometry problems: Combining text and diagram interpretation, Conf. on Empirical Methods in Natural Language Processing (Lisbon, Portugal, 2015), pp. 1466–1476. Crossref, Google Scholar
24. S. Shi, Y. Wang, C. Y. Lin, X. Liu and Y. Rui, Automatically solving number word problems by semantic parsing and reasoning, Conf. Empirical Methods in Natural Language Processing (Lisbon, Portugal, 2015), pp. 1132–1142. Crossref, Google Scholar
25. Y. Wang, X. Liu and S. Shi, Deep neural solver for math word problems, in Conf. Empirical Methods in Natural Language Processing (Taipei, Taiwan, 2017), pp. 845–854. Crossref, Google Scholar
26. L. Wang, D. Zhang, L. Gao, J. Song, L. Guo and H. Shen, MathDQN: Solving arithmetic word problems via deep reinforcement learning, Conf. American Association for Artificial Intelligence (New Orleans, Louisiana, 2018) (under publication). Crossref, Google Scholar
27. W. T. Wu, Basic principles of mechanical theorem proving in elementary geometries, J. Autom. Reason. 2(3) (1986) 221–252. Crossref, Google Scholar
28. Z. Ye, S. C. Chou and X. S. Gao, An introduction to java geometry expert, in International Workshop on Automated Deduction in Geometry (Springer, Berlin Heidelberg, 2008), pp. 189–195. Google Scholar
29. Z. Ye, S. C. Chou and X. S. Gao, Visually dynamic presentation of proofs in plane geometry, J. Autom. Reason. 45(3) (2010) 213–241. Crossref, Web of Science, Google Scholar
30. X. Yu, P. Jian, M. Wang and S. Wu, Extraction of implicit quantity relations for arithmetic word problems in Chinese, Int. Conf. Educational Innovation Through Technology (Tainan, Taiwan, 2017), pp. 242–245. Google Scholar
31. J. Z. Zhang, L. Yang and X. R. Hou, The WE complete method of theorem-proving in geometry, J. Syst. Sci. Math. Sci. 15(3) (1995) 200–207. Google Scholar
32. L. Zhou, S. Dai and L. Chen, Learn to solve algebra word problems using quadratic programming, Conf. Empirical Methods in Natural Language Processing (Lisbon, Portugal, 2015), pp. 817–822. Crossref, Google Scholar