Rule-based expert systems to support step-by-step guidance in algebraic problem solving: The case of the tutor PAT2Math Rule-based expert systems to support step-by-step guidance in algebraic problem solving: The case of the tutor PAT2Math Patricia A. Jaques a,⇑, Henrique Seffrin a, Geiseane Rubi a, Felipe de Morais a, Cássio Ghilardi a, Ig Ibert Bittencourt b, Seiji Isotani c a PIPCA – UNISINOS, Av. Unisinos, 950 Bairro Cristo Rei, CEP 93.022-000 São Leopoldo, Brazil b NEES – IC – UFAL, Campus A.C. Simões, BR 104, Norte, km 97, Cidade Universitária, CEP 57072-970 Maceio, AL, Brazil c ICMC – University of São Paulo, Avenida Trabalhador São-carlense, 400 Centro, CEP 13566-590 Sao Carlos, SP, Brazil a r t i c l e i n f o Keywords: Intelligent tutoring systems Expert systems Math learning Algebra Equations a b s t r a c t In order for an Intelligent Tutoring System (ITS) to correct students’ exercises, it must know how to solve the same type of problems that students do and the related knowledge components. It can, thereby, com- pare the desirable solution with the student’s answer. This task can be accomplished by an expert system. However, it has some drawbacks, such as an exponential complexity time, which impairs the desirable real-time response. In this paper we describe the expert system (ES) module of an Algebra ITS, called PAT2Math. The ES is responsible for correcting student steps and modeling student knowledge compo- nents during equations problem solving. Another important function of this module is to demonstrate to students how to solve a problem. In this paper, we focus mainly on the implementation of this module as a rule-based expert system. We also describe how we reduced the complexity of this module from O(nd) to O(d), where n is the number of rules in the knowledge base, by implementing some meta-rules that aim at inferring the operations students applied in order to produce a step. We evaluated our approach through a user study with forty-three seventh grade students. The students who interacted with our tool showed statistically higher scores on equation solving tests, after solving algebra exercises with PAT2Math during an approximately two-hour session, than students who solved the same exercises using only paper and pencil. � 2013 Elsevier Ltd. All rights reserved. 1. Introduction Intelligent Tutoring Systems (ITSs) have shown promising results when applied as a supplemental classroom learning tool (Koedinger, Anderson, Hadley, & Mark, 1997; Nicaud, Bittar, Chaachoua, Inam- dar, & Maffei, 2006; Nicaud, Bouhineau, & Huguet, 2002). Large- scale experiments in high-schools demonstrated that ITSs can im- prove students learning (Koedinger et al., 1997; Koedinger & Sueker, 1996). The success of this type of educational software is due to the fact that it can offer important features to personalize the learning processes such as one-on-one learning, immediate personal feed- back, demonstration of problem solving when students are having difficulty, and assessment of students’ skills. Vanlehn (2006) describes the tutor as having two loops. The outer loop is responsible for deciding the sequence of exercises or problems for students to work on. The inner loop provides step- by-step guidance during problem solving activity. In order to provide immediate feedback in the inner loop, an ITS’ architecture is generally composed of an expert system module (ES) that is able to solve the same type of exercises that students should do in multiple ways. Thus, for each step of the problem the system compares the answer provided by a student with the expert system’s solutions (an answer may have several correct solutions) and checks whether they are equivalent. If the ES can generate or test all possible solutions to a given prob- lem, then it can identify when a student has taken an incorrect path to solve the given problem and offer immediate feedback (generally colored labels are presented to indicate whether or not the student’s answer for a given step is correct) (Heffernan, Koedinger, & Razzaq, 2008). Some tutors provide additional re- sources (e.g. explanations or hints) when students are having difficulty or solving the problem or arriving at the correct answer. In fields such as math and physics, the knowledge is usually implemented as a rule in the form: ‘‘if hcondition is truei then hdo action Ai’’. Each rule represents an operation that can be applied in a step to solve a problem. The ES inference engine scans the base searching for rules to be triggered, i.e. rules whose conditions are satisfied by the current step of the solution. 0957-4174/$ - see front matter � 2013 Elsevier Ltd. All rights reserved. http://dx.doi.org/10.1016/j.eswa.2013.04.004 ⇑ Corresponding author. Tel.: +55 51 3591 1100x1626. E-mail addresses: pjaques@unisinos.br, patricia.jaques@gmail.com (P.A. Jaques), hseffrin@hotmail.com (H. Seffrin), geiserubi@gmail.com (G. Rubi), felipedemor- aisfm@hotmail.com (F. de Morais), cassioghilardi@hotmail.com (C. Ghilardi), ig.ibert@ic.ufal.br (I.I. Bittencourt), sisotani@icmc.usp.br (S. Isotani). Expert Systems with Applications 40 (2013) 5456–5465 Contents lists available at SciVerse ScienceDirect Expert Systems with Applications j o u r n a l h o m e p a g e : w w w . e l s e v i e r . c o m / l o c a t e / e s w a http://crossmark.dyndns.org/dialog/?doi=10.1016/j.eswa.2013.04.004&domain=pdf http://dx.doi.org/10.1016/j.eswa.2013.04.004 mailto:pjaques@unisinos.br mailto:patricia.jaques@gmail.com mailto:hseffrin@hotmail.com mailto:geiserubi@gmail.com mailto:felipedemoraisfm@hotmail.com mailto:felipedemoraisfm@hotmail.com mailto:cassioghilardi@hotmail.com mailto:ig.ibert@ic.ufal.br mailto:sisotani@icmc.usp.br http://dx.doi.org/10.1016/j.eswa.2013.04.004 http://www.sciencedirect.com/science/journal/09574174 http://www.elsevier.com/locate/eswa In addition to providing appropriate feedback to students, the rules also contain information about the related knowledge com- ponents. For example, a rule can represent the process (knowledge component or skill) of ‘‘subtracting an integer b on both sides of the equation’’. Thus, when the ES module corrects a student step solution, it is able to provide the student model with information about the skills necessary to solve that step. The student model uses this information to infer which skills students have mastered and which they need to practice more. This allows the tutor to cre- ate personalized hints in the inner loop and also to select more appropriate exercises for students to solve (outer loop). Although there are well known algebra tutors (Chaachoua, Ni- caud, Bronner, & Bouhineau, 2004; Cohen, Beal, & Adams, 2008; Koedinger & Sueker, 1996; Melis, Goguadze, Libbrecht, & Ullrich, 2009), few of them have an expert system module that is able to solve exercises and provide step-by-step guidance (Chaachoua et al., 2004; Koedinger & Sueker, 1996), an essential feature for a learning system to be classified as an ITS, according to (Vanlehn, 2006). Furthermore, previous work does not explore in detail how to implement an expert system module, which artificial intel- ligence knowledge representation format needs to be used, when an inference mechanism should be trigged and how to solve some inherent computational complexity problems. This paper presents the ES of the algebra tutor PAT2Math. PAT2- Math is an intelligent tutor system that teaches students how to solve linear and quadratic equations. It is a web system imple- mented in Java, which allows students to use it in any computer or platform with Internet access. PAT2Math is composed of an algebra editor (PATequation), which assists students in solving equations. The ES has an essential role in PATequation; it is responsible for providing immediate feedback to students at every step of their problem solving. Our main goal is to present this module knowl- edge and explain how to the ES implements problem solving and provides the student with step-by-step guidance. We describe how to reduce the complexity of this module from O(nd) to O(d), where n represents the number of rules in the knowledge base, by using meta-rules that guide the inference of the operations stu- dent applied to produce a step. We finish this paper by presenting the results of a user study we conducted with forty-three 7th grade students who interacted with PATequation for three classes. This paper is organized as follows. Section 2 describes problem solving under a pedagogical perspective. Section 3 presents the current state of the art in Algebra Intelligent Tutoring Systems. In Section 4, we explain the main artificial intelligence techniques used to develop ITS expert systems. In Section 5, we describe PAT2- Math, the Algebra Tutor that our research group is developing. PATequation, the problem solving editor of PAT2Math, is presented in Section 6. The ES responsible for providing step-by-step guid- ance in PATequation is described in Section 7. The experiment de- sign and results are reported in Section 8. Finally, Section 9 presents our conclusions. 2. Solving algebraic problems An Algebra task is generally a word problem for the student to solve. An algebraic word problem consists of one or more sen- tences representing a situation or a story, where the student needs to understand the elements in order to generate a mathematical model to represent it. The model consists of one or more equations that the pupil should solve in order to obtain the numerical values that are the solution of the problem (Gama, 2004). Take for exam- ple the word problem below (adapted from Munem & West (2003, p. 107)): ‘‘A computer store sells desktop and laptop computers. Due to space considerations, the number of laptops in inventory is seven less than twice the number of desktops in stock. How many desktops does the store have if it has a total of 272 computers?’’ The process of solving a word problem has two phases (Mayer, 1999; Polya, 2004): (i) the Problem Representation (also called Symbolization (Heffernan, Koedinger, & Razzaq, 2008)), and (ii) the Problem Solution. While the former concerns to the transfor- mation of algebra word problems into a system of equations, the second encompasses the process of solving these equations using algebraic operations. For example, for the word problem that we previously pre- sented, the student could provide the following solution: x þð2x � 7Þ¼ 272 ð1Þ 3x � 7 ¼ 272 ð2Þ 3x ¼ 279 ð3Þ x ¼ 93 ð4Þ In the example above, line (1) refers to the process of Problem Rep- resentation, and lines (2–4) to the Problem Solution phase. As shown in the above solution, solving a task involves several steps. Each line provided by the student in the above solution is a step. A step can involve the correct use of one or more Knowledge Components (KC) (also called knowledge units (Aleven, McLaren, Sewall, & Koedinger, 2009)). It comprises any unit into which the knowledge can be broken down, such as rules, concepts, facts, and procedures (Vanlehn, 2006). For instance, in order to arrive at line (2) in the above example, the student applied the operation (or KC) ‘‘add variable coefficients’’ in line (1) of the equation. In the next section, we will describe the main Algebra Intelli- gent Tutoring Systems and the tools and types of feedback they of- fer to help students solve algebra word problems in these two phases. 3. Algebra Intelligent Tutoring Systems The field of ITS has shown significantly improvements since the emergence of the first systems in the eighties (Woolf, 2009). The evolution of the Internet, the increasing performance of computers, and improvements of artificial intelligence techniques and tools have furthered the development of ITSs in several domains, such as Physics, Math, Medicine and others (see (Woolf, 2009) for an overview). Previous work has largely been applied in classroom settings, demonstrating they can improve student performance on stan- dardized and experimenter-designed tests by one-half to two stan- dards deviation (Cohen et al., 2008; Koedinger & Sueker, 1996; Shelby et al., 2000). Some of the most known research focused on the Algebra content domain. This is the case of Cognitive Alge- bra Tutor (previously PAT) (Koedinger & Sueker, 1996), Aplusix (Nicaud et al., 2006, Nicaud, Bouhineau, & Huguet, 2002), Active- Math (Goguadze & Melis, 2008; Melis, Goguadze, Libbrecht, & Ull- rich, 2009) and AnimalWatch (Birch & Beal, 2008; Cohen et al., 2008). We believe there are two main reasons for this. First, Alge- bra is a content domain (or task domain (Vanlehn, 2006)) in which a great number of students experience poor achievement (Carpen- ter, Kepner, Corbitt, Lindquist, & Reys, 1982; National Commission on Excellence in Education, 1983). Secondly, it requires less effort to formalize math content into computer algorithms, because it is mainly composed of procedural content, which can be easily rep- resented by computer algorithms. In the end of this section, we de- scribe the main algebraic tutors proposed by the Artificial Intelligence and Education community. P.A. Jaques et al. / Expert Systems with Applications 40 (2013) 5456–5465 5457 https://isiarticles.com/article/52573