A review of methods for automatic understanding of natural language mathematical problems

Anirban Mukherjee1, Utpal Garain2
1Department of IT, RCC Institute of Information Technology, Kolkata, India
2Computer Vision and Pattern Recognition Unit, Indian Statistical Institute, Kolkata, India

Tóm tắt

This article addresses the problem of understanding mathematics described in natural language. Research in this area dates back to early 1960s. Several systems have so far been proposed to involve machines to solve mathematical problems of various domains like algebra, geometry, physics, mechanics, etc. This correspondence provides a state of the art technical review of these systems and approaches proposed by different research groups. A unified architecture that has been used in most of these approaches is identified and differences among the systems are highlighted. Significant achievements of each method are pointed out. Major strengths and weaknesses of the approaches are also discussed. Finally, present efforts and future trends in this research area are presented.

Từ khóa


Tài liệu tham khảo

Bakman Y (2007) Robust understanding of word problems with extraneous information. http://aps.arxiv.org/abs/math.GM/070139.. Accessed 31 Mar 2008

Ballard BW, Biermann AW (1979) Programming in natural language: NLC as prototype. In: Proceedings of the 1979 ACM national conference, pp 228–237

Beckwith R, Miller GA, Tengi R (1993) Design and implementation of the WordNet lexical database and searching software. Working Paper, Princeton University

Benzmüller C, Horacek H, Kruijff-Korbayova I, Pinkal M, Siekmann J, Wolska M (2007) Natural language dialog with a tutor system for mathematical proofs. In: Lu R, Siekmann J, Ullrich C (eds) Cognitive systems, LNAI 4429:1–14

Biermann AW, Ballard BW (1980) Towards natural language computation. Am J Comput Linguist 6(2): 71–86

Biermann A, Rodman R, Ballard B, Betancourt T, Bilbro G, Deas H, Fineman L, Fink P, Gilbert K, Gregory D, Heidlage F (1982) Interactive natural language problem solving: a pragmatic approach. In: Proceedings of the first conference on applied natural language processing. Santa Monica, California, pp 180–191

Bobrow DG (1964a) Natural language input for a computer problem solving system. Report MAC-TR-1, Project MAC, MIT, Cambridge, June

Bobrow DG (1964b) Natural language input for a computer problem solving system. Ph.D. Thesis, Department of Mathematics, MIT, Cambridge

Briars DL, Larkin JH (1984) An integrated model of skill in solving elementary word problems. Cogn Instr 1: 245–296

Buckley M, Dietrich D (2007a) Integrating task information into the dialogue context for natural language mathematics tutoring. In: Medlock B and Séaghdha Dó (eds) Proceedings of the 10th annual CLUK research colloquium. Cambridge

Buckley M, Dietrich D (2007b) Verification of proof steps for tutoring mathematical proofs. In: Luckin R, Koedinger KR, Greer J (eds) Proceedings of the 13th international conference on artificial intelligence in education. Los Angeles, pp 560–562

Bundy A (1988) The use of explicit plans to guide inductive proofs. In: Proceedings of 9th international conference on automated deduction, pp 111–120

Bundy A (1990) A science of reasoning: extended abstract. In: Proceedings of 10th international conference on automated deduction. Springer, pp 633–640

Bundy A, Byrd L, Luger G, Mellish C, Palmer M (1979a) Solving mechanics problems using meta-level inference. In: Proceedings of IJCAI-79. Tokyo, pp 1017–1027

Bundy A, Byrd L, Luger G, Mellish C, Milne R, Palmer M (1979b) Mecho: a program to solve mechanics problems. Working paper no. 50. Department of Artificial Intelligence, Edinburgh

Chang KE, So YT, Lin HF (2005) Computer-assisted learning for mathematical problem solving. Comput Educ (in press)

Chang K-E, Sung Y-T, Lin S-F (2006) Computer-assisted learning for mathematical problem solving. Comput Educ. 46(2): 140–151

Charniak E (1968) CARPS, a program which solves calculus word problems. Report MAC-TR-51, Project MAC, MIT, Cambridge, July

Charniak E (1969) Computer solution of calculus word problems. In: Proceedings of international joint conference on artificial intelligence. Washington, DC, pp 303–316

Chester D (1976) The translation of formal proofs into English. Artif Intell 7: 178–216

Davis R, Buchanan BG (1977) Meta-level knowledge: overview and applications. IJCAI’77, pp 920–927

De Kleer J (1975a) Multiples representation of knowledge in a mechanics problem-solver. In: Proceedings of IJCAI-77. Cambridge, Massachusetts, pp 299–304

De Kleer J (1975b) Qualitative and quantitative knowledge in classical mechanics. Artificial Intelligence Laboratory TR-’352, MIT, Cambridge

Dellarosa D (1986) A computer simulation of children’s arithmetic word problem solving. Behav Res Methods Instrum Comput 18: 147–154

Edgar A, Pelletier FJ (1993) Natural language explanation of natural deduction proofs. In: Proceedings of the first conference of the pacific association for computational linguistics. Centre for Systems Science, Simon Fraser University

Fellbaum C (1990) English verbs as a semantic net. Inter J Lexicogr 3(4): 278–301

Fellbaum C, Gross D, Miller K (1990) Adjectives in WordNet. Inter J Lexicogr 3: 265–277

Fletcher CR (1985) Understanding and solving arithmetic word problems: a computer simulation. Behav Res Methods Instrum Comput 17: 565–571

Gelb JP (1971a) Experiments with a natural language problem solving system. In: Proceedings of IJCAI-71. London, England, pp 455–462

Gelb JP (1971b) The computer solution of English probability problems. Ph.D. Thesis, Computer Science Program, RPI, Troy, New York

Huang X (1996) Human oriented proof presentation: a reconstructive approach. Infix St. Augustin, Germany

Huang X, Kerber M, Kohlhase M, Melis E, Nesmith D, Richts J, Siekmann J (1992) Ω-MKRP—a proof development environment. SEKI Report SR-92-22, Fachbereich Informatik, Universitat des Saarlandes Saarbrucken, Germany, 1992. A shorter version presented at the Workshop on automated theorem proving, IJCAI-93, Chambery, France

Hsu WL, Wu SH, Chen YS (2001) Event identification based on the information map—INFOMAP. In: Proceedings of the 2001 IEEE systems, man, and cybernetics conference. Tuscon, Arizona, pp 1661–1672

Kintsch W, Greeno JG (1985) Understanding and solving word arithmetic problems. Psychol Rev 92: 109–129

Koedinger KR, Sueker ELF (1996) PAT goes to college: evaluating a cognitive tutor for developmental mathematics. In: Proceedings of the second international conference on the learning sciences, pp 180–187

Koedinger KR, Anderson JR, Hadley WH, Mark MA (1997) Intelligent tutoring goes to school in the big city. Inter J Artif Intell Educ 8: 30–43

Lambiris MAK, Oberem GE (1993) Natural language techniques in computer-assisted legal instruction: a comparison of alternative approaches. J Legal Educ 43(1): 60–78

Lindsay RK (1963) Inferential memory as the basis of machines which understand natural language. Computers and thought. McCraw-Hill, New York

Lingenfelder C (1989) Structuring computer generated proofs. In: Sridharan NS (ed) Proceedings of the 11th IJCAI. Detroit, Michigan, pp 378–383

Lingenfelder C (1990) Transformation and structuring of computer generated proofs. Ph.D. Thesis, Fachbereich Informatik, UniversitatKaiserslautern, Kaiserslautern, Germany

Lingenfelder C, Pracklein A (1991) Proof transformation with built-in equality predicate. In: Proceedings of the 12th IJCAI. Sydney, pp 165–170

Littlefield J, Rieser J (1993) Semantic features of similarity and children’s strategies for identifying relevant information in mathematical story problems. Cogn Instr 11(2): 133–188

Looi CK, Tan BT (1998) A cognitive-apprenticeship-based environment for learning word problem solving. J Res Math Educ 17(4): 339–354

Luger G (1981) Mathematical model building in the solution of mechanics problems: human protocols and the mecho trace. Cogn Sci 5(1): 55–77

Mann WC, Thompson SA (1987) Rhetorical structure theory: a theory of text organization. Technical Report ISI/RS-87-190, USC Information Sciences Institute

Marples D (1974) Argument and technique in the solution of problems in mechanics and electricity. Technical Report CUED/C-Educ/TRI, Department of Engineering, Cambridge, England.

Marshall SP (1995) Schemas in problem solving. Cambridge University Press, Cambridge

Mathlab Group (1974) MACSYMA reference manual. MIT, Cambridge

McDermott D, Sussman GJ (1974) The conniver reference manual, artificial intelligence laboratory. A1M-259a. MIT, Cambridge

McDonald D (1983) Natural language generation as a computational problem: an introduction. In: Brady M, Berwick RC(eds) Computational models of discourse. MIT Press, Cambridge, pp 209–266

Melis E, Andres E, Goguadse G, Libbrecht P, Pollet M, Ullrich C (2001a) Activemath: system description. In: Proceedings of the international conference on artificial intelligence in education, http://citeseer.ist.psu.edu/article/melis01activemath.html

Melis E, Andres E, Budenbender J, Frischauf A, Goguadse G, Libbrecht P, Pollet M, (2001b) Activemath: a generic and adaptive web-based learning environment. Int J Artif Intell Educ 12(4): 385–407

Miller GA (1990) Nouns in WordNet: a lexical inheritance system. Inter J Lexicogr 3(4): 245–264

Miller GA, Beckwith R, Fellbaum C, Gross D, Miller K (1990) Introduction to WordNet: an on-line lexical database. Inter J Lexicogr 3(4): 235–244

Minsky M (1973) A framework for representation of knowledge artificial intelligence laboratory AIM-306. MIT, Cambridge

Mukherjee A, Garain U, Nasipuri M (2007) On construction of a GeometryNet. In: Proceedings of IASTED international conference on artificial intelligence and applications (AIA 2007). Innsbruck, Austria, pp 530–536

Mukherjee A, Garain U (2009) Understanding of natural language text for diagram drawing. In: Proceedings of 13th international conference on artificial intelligence and soft computing

Muth D (1992) Extraneous information and extra steps in arithmetic word problems. Contemp Educ Psychol 17: 278–285

Newell A, Shaw JC, Simon HA (1959) Report on a general problem-solving program. In: Proceedings of the international conference on information processing, pp 256–264

Novak GS (1976) Computer understanding of physics problems stated in natural language. The University of Texas at Austin, Ph.D. Thesis, arch 61

Novak GS, Bulko WC (1993) Diagrams and text as computer input. J Vis Lang Comput 4(2): 161–175

Oberem GE (1987) ALBERT: a physics problem solving monitor and coach. In: Proceedings of the first international conference on computer assisted learning (ICCAL’87). Calgary Alberta, Canada, pp 179–184

Oberem GE (1994) Transfer of a natural language system for problem-solving in physics to other domains. In: Proceedings of ED-MEDIA 94—World conference on educational multimedia and hypermedia. Vancouver, British Columbia, pp 424–431

Oberem GE, Mayer O, Makedon F (1992) ILONA: an advanced CAI tutorial system for the fundamentals of logic. Educ Comput 8(3): 245–254

Oberem GE, Shaffer PS, McDermott LC (1993) Using a computer to investigate and address student difficulties in drawing free-body diagrams. A paper presented at the summer meeting of the American association of physics teachers, Boise, ID

Parsaye K, Chignell M (1988) Expert systems for experts. Wiley, London

Pinkal M, Siekmann J, Benzmüller C, Kruijff-Korbayova I (2008) DIALOG: natural language-based interaction with a mathematics assistance system. Project report in the Collaborative Research Centre SFB 378 on resource-adaptive cognitive processes

Ramani S (1969) Language based problem-solving. Ph.D. Thesis, Computer Group, Tata Institute of Fundamental Research

Ramani S (1979) A language based problem solver. In: Proceedings of IJCAI-71. London, pp 463–473

Siekmann J et al (2002) Proof development with Ω MEGA. In: Proceedings of the 18th conference on automated deduction, LNAI 2392. Springer, Copenhagen

Simmons RF (1970) Natural language question-answering systems: 1969. Commun ACM 13(1): 15–30

Simmons RF (1973) Semantic networks: their computation and use for understanding english sentences. In: Schank RC, Colby KM (eds) Computer models of thought and language. Freeman and Co., pp 63–113

Slagle JR (1965) Experiments with a deductive question-answering program. J-CACM 8(12): 792–798

Steele M, Steele J (1999) DISCOVER: an intelligent tutoring system for teaching students with learning difficulties to solve word problems. J Comput Math Sci Teach 18(4): 351–359

Sterling L, Bundy A, Byrd L, O’Keefe RA, Silver B (1982) Solving symbolic equations with PRESS. In: Proceedings of the European conference on computer algebra, LNCS, pp 109–116

Wheeler JL, Regian JW (1999) The use of a cognitive tutoring system in the improvement of the abstract reasoning component of word problem solving. Comput Human Behav 15: 243–254

Winograd T (1972) Understanding natural language. Academic Press, New York

Wong WK, Hsu Sheng-Cheng, Wu Shih-Hung, Lee Cheng-Wei, Hsu Wen-Lian (2007) LIM-G: learner-initiating instruction model based on cognitive knowledge for geometry word problem comprehension. Comput Educ (Elsevier) 48((4): 582–601

Woods WA (1970) Transition network grammars for natural language analysis. Commun ACM 13(10): 591–606

WordNet: A lexical database for the english language. Cognitive Science Laboratory, Princeton University, Princeton http://wordnet.princeton.edu/

Zinn C (1998) Verifying textbook proofs. Technical Report, Technical University of Vienna

Zinn C (2003) A computational framework for understanding mathematical discourse. Log J IGPL 11(4): 457–484

Zinn C, Moore JD, Core MG (2002) A 3-tier planning architecture for managing tutorial dialogue. In: Proceedings of intelligent tutoring systems, 6th international conference, vol 2363 of LNCS. Springer, Biarritz, pp 574–584