108 Automatic Generation of Analogous Problems to Help Resolving Misconceptions in an Intelligent Tutor System for Written Subtraction Christina Zeller and Ute Schmid Cognitive Systems Group, University of Bamberg An der Weberei 5, 96045 Bamberg, Germany {Christina.Zeller,Ute.Schmid}@uni-bamberg.de Abstract. In domains involving procedural skills such as mathematics or programming, students often are prone to misconceptions which result in erroneous solutions. We present the ASG algorithm for generation of analogous problems of written subtraction as an extension of an intelli- gent tutor system (ITS) proposed by Zinn (2014). The student module of this ITS does not rely on an error library but uses algorithmic de- bugging where an erroneous solution is recognized by identifying which expert rules fail when trying to reproduce the student solution. Since the ITS allows students to create their own subtraction problems, feedback generation must be online and automatic. ASG is a constraint-based al- gorithm for constructing problems which are structurally isomorphic to the current, erroneously solved student problem. 1 Introduction Learning to perform written subtraction mainly relies on the acquisition of proce- dural knowledge as is characteristic for mathematics or programming (Anderson & Reiser, 1985; Young & O’Shea, 1981). Students errors mostly can be attributed to procedural bugs (Brown & Burton, 1978) such as missing or faulty rules or the use of rules in wrong contexts. That is, incorrect solutions can be regarded as manifestation of fundamental misconceptions based on erroneous rules. Con- sequently, to support students while learning a procedural skill, it is crucial to identify these misconceptions and provide suitable feedback to overcome them. We can assume that an experienced human tutor is able to diagnose miscon- ceptions and provide helpful feedback. An intelligent tutor system (ITS) should provide similar helpful support. An ITS is a computer-based system, that monitors the problem-solving of a student, coaches, instructs, and counsels the student (Sleeman & Brown, 1982). It is composed of four modules: (a) expert knowledge module, (b) student model module, (c) tutoring module, and (d) user interface module (Nwana, 1990). The expert knowledge module contains the knowledge of the tutored domain. The student model module is used to dynamically capture the current knowledge and misconceptions of the student. The tutoring module realizes principles of teach- ing, and the user interface module addresses the interaction with the student. Copyright © 2016 for this paper by its authors. Copying permitted for private and academic purposes. In Proceedings of the ICCBR 2016 Workshops. Atlanta, Georgia, United States of America 109 In the context of learning procedural skills, typical error libraries are used which consist of a set of faulty rules explaining observed errors in student solu- tions (Anderson & Reiser, 1985; Brown & Burton, 1978; Burton, 1982; Narciss & Huth, 2006; Young & O’Shea, 1981). The diagnostic program Debuggy, for example, contains 130 primitive and compound bugs (Burton, 1982). The ad- vantage of error libraries is that misconceptions are represented explicitly and thereby can support the construction of specific feedback. However, the set of stored faulty rules might be incomplete. In this case, it is not possible to identify the underlying misconception in a student solution and to give specific feedback. An alternative to error libraries is algorithmic debugging (AD; Murray, 1988) which originally was introduced to identify errors in programs (Shapiro, 1983): Given a set of input/output examples, a program is automatically tested and the program part which is assumed to be responsible for the erroneous output is iden- tified. Zinn (2014) uses this idea in the context of ITSs: The rules representing the expert knowledge for written subtraction are applied to the current problem given to the student. If the expert and student solution di↵er, the di↵erence is described by the failing rule in the expert module. In this case the tutor model has to generate a strategy to support the student to resolve this misconception. One approach is to present the same or additional problems which a student has to solve until a correct solution is provided; a more elaborate approach is to give bug-related feedback (Narciss & Huth, 2006). In the domain of written sub- traction, early systems focused on the identification of misconceptions and did not provide a tutoring strategy (Brown & Burton, 1978; Burton, 1982; Young & O’Shea, 1981). The focus of Zinn’s system is also on diagnosis, in addition, feedback is given in form of a written statement describing the identified erro- neous rule (Zinn, 2014) while Narciss and Huth (2006) provide an explanation together with a worked-out example. Such a worked-out example for an incorrectly solved subtraction problem can be viewed as an analogy (Gick & Holyoak, 1983). That is, the example serves as a base for the current (target) problem. For the base problem the correct solution can be demonstrated step by step. Given structural isomorphy between the worked-out example and the current problem, the student should be able to transfer the solution steps (Gick & Holyoak, 1983; VanLehn, 1998). Narciss and Huth (2006) rely on predefined analogies stored together with predefined student problems. However, a more natural learning environment should allow students to input own problems and let the system provide feedback for these—for the ITS unknown—problems. In this paper, the ASG algorithm for automatic generation of analogous subtraction problems is presented. The analogies are constructed such that they capture these characteristics responsible for the diagnosed error and consequently provide support for the supposed underlying misconception. In the following, we first introduce the expert knowledge for written subtrac- tion. Then, the AD approach used to generate the student model is described. Afterwards, the use of analogies as tutoring principle is introduced and details are given about how a helpful analogy can be constructed with the ASG algo- rithm. Finally, we conclude with a short review and pointers to further work. 110 2 Expert Knowledge of Written Subtraction Knowledge concerning the process of solving a problem is stored in the expert knowledge module of the ITS. Zinn (2014) implemented the widely used decom- position method in Prolog. An illustration of the algorithm which only works correct when the result is greater or equal to zero together with an example is shown in Figure 1.1 Subtraction is defined by five production rules: – subtract [Cn , Cn 1 , ..., C1 ]: subtracts a subtrahend from a minuend. The proce- dure gets as input a non empty list of columns with Ci = (mi , si , di ) where mi stands for minuend, si for subtrahend and di for the di↵erence of the column i. C1 belongs to the rightmost and Cn to the leftmost column. If the subtrahend has fewer positions than the minuend, leading zeros are added. – process column Ci : starts with the rightmost column and compares mi and si . If mi > si the production rule take difference is applied immediately. Otherwise, a borrowing procedure is needed previously, which is the application of decrement and add ten to minuend. After processing column i the next column (i + 1) is in- spected. The process column rule ends the subtraction algorithm after processing the last column (i = n, cf. Fig. 1a). – decrement Ci : borrows ten from the minuend mi+1 . If mi+1 = 0, further borrowing is needed in Ci+2 (cf. Fig. 1b). – add ten to minuend Ci : adds the borrowed ten to mi . – take difference Ci : takes the di↵erence mi si and stores the di↵erence in di . The algorithm in Figure 1 induces an automaton for the generation of arbitrary subtraction problems (see Fig. 2) which is the backbone of the ASG algorithm.2 A subtraction problem starts with the rightmost column which needs borrow- ing (arrow m+10 ) or not (arrow m). From the second column onward a column can be borrowed from (arrow m 1 ) or be borrowed from and needs borrowing simultaneously (arrow m+101 ). In this case, it can be discriminated whether the value of the minuend is 0 (0+10 0+10 1 ) or not (6= 1 ; cf. Fig. 1b). The states of the automaton constitute column cases, that is, they characterize the structural re- lation between minuend and subtrahend in each column. All problems generated with this automaton can be solved by the provided subtraction algorithm. 3 Diagnosing Student Solutions with AD Students’ current knowledge is represented in the student model of an ITS. Once a student submits a (partial) solution of a problem, it is analyzed and possible misconceptions are diagnosed. In case of written subtraction this could, for ex- ample, be a wrong conception of when or how to perform a borrow procedure. Based on the algorithmic representation of expert knowledge for written sub- traction, AD is used to analyze a student solution (Zinn, 2014): The student solu- tion is—counter-intuitively—considered as correct output of written subtraction. That is, while processing the subtraction problem with the expert algorithm, the partial results are compared with the student solution. In case of di↵erences the 1 In contrast to Zinn (2014) we label columns from right to left. 2 The algorithm and automaton are also described in Zeller and Schmid (2016). 111 decrement Ci subtract [Cn , Cn 1 , . . . , C1 ] j=i i=1 j j+1 Ci mj = 0 mj 6= 0 m i < si m i > si 0+10 1 m+10 , m+10 1 m, m 1 mj 9 decrement Ci i i+1 add ten to minuend Ci (mj 1) > sj (mj 1) < sj m 1 0+10 6= 1 take difference Ci i si – If case m 1 (borrowing from column i, no borrowing in column i + 1): mi = mi \ 0, si = si \ 9, di = di \ 9, (mi 1) > si , di = (mi 1) si – If case m+10 (no borrowing from column i, borrowing in column i + 1): mi = mi \ 9, si = si \ 0, di = di \ 0, m < s, di = (mi + 10) si – If case m+10 1 (borrowing from column i, borrowing in column i + 1): di = ((mi 1) + 10) si 0+10 • 6= 1 (mSi 6= 0): mi = mi \ 0, si = si \ 0, di = di \ 0, (mi 1) < si • 0+10 1 (mSi = 0): mi = {0} ASG-E – Treatment of special restrictions for error types: – If take difference error: dSi = di except • If case m and dSi = 9: mi = {9}, si = {0} and final column is i • If case m 1 and dSi = 8: mi = {9}, si = {0} and final column is i • If case m+10 and dSi = 1: mi = {0}, si = {9} and final column is i + 1 with case m 1 0+10 • If case 6= 1 and dSi = 1: mi = {1}, si = {9} and final column is i + 1 with case m 1 • If case 0+10 1 : si = 9 dSi and final column is i + 1 with case m 1 0+10 – If add ten to minuend error: current column case is m+10 or 6= 1 and final column is i + 1 with case m 1 – If decrement error: current column case is m+10 or 6=0+10 1 and for column i + 1 0+10 • If case m+10 or 6= 1 (mSi+1 6= 0) then final column is i + 1 with case m 1 • If case 0+10 1 (mSi+1 = 0) then find the last successive column i + n in mS which contains value 0 and for j = i + 1 . . . i + n column case is 0+10 1 , final column is i + n + 1 with case m 1 Fig. 5: The ASG algorithm for generation of analogous subtraction problems for an erroneous student solution. To help students to focus on one misconception at a time, in our ASG algo- rithm, the first identified error is considered while generating the analogy. That is, to keep a balance between overall similarity of base and target and highlight- ing a specific misconception, we create the analogy by constructing structurally isomorphic columns from the rightmost column until the column with this error is reached. This column is created using constraints helping to identify the error. The ASG algorithm in Figure 5 is a realization of the automaton given in Fig- ure 2 with the target problem and the diagnosed error as additional constraints. Details of the Prolog implementation can be found in Zeller (2015). Input to ASG are the current (target) problem and the diagnosed error (take difference, decrement, add ten to minuend). To generate an analogous problem whose so- lution path is identical for all columns of the target problem up to the diagnosed error column, the column cases (m, m 1 , m+10 , m+10 1 ) have to be considered. 115 In general, each column i of the minuend, subtrahend and di↵erence of a problem can be a single digit natural number. Accordingly, the solution set for each mi , si , and di is initialized with {0, . . . 9}. The constraints mi = mi \ mSi and si = si \ sSi exclude the use of the same values in a column for base and target. To generate a column isomorphic to the respective column in the target, the relation given between minuend and subtrahend needs to be preserved in the analogy. This is reflected by the specific constraints induced by each column case. For the example given in Figure 3, in the student solution (target) the rightmost column has the column case m. Therefore, the constraint in this case is mi > si . In the generated problem, both mi and si were instantiated with 0. There are many further legal instantiations, such as mi = 1 and si = 0 or mi = 9 and si = 2. The second column is case m+10 . Because mS2 < sS2 , it is necessary to borrow from mS3 . Consequently, m2 cannot be instantiated with 9 and s2 cannot be instantiated with 0 and the relation m2 < s2 needs to hold. Case m+10 always induces case m 1 or m+10 1 for the next column (cf. Fig. 2). In the target problem of Figure 3, Column 3 is a m 1 case. That is, m3 cannot be instantiated with 0 and s3 cannot be instantiated with 9 and the relation (m3 1) > s3 needs to hold. For case m+101 , two special cases have to be considered depending whether the minuend of the column in the target problem is 0 or not. With the ASG-C part of the algorithm, the set of all structural isomorphic problems to a given problem can be generated. However, most of these problems might not highlight the misconception. Therefore, for the first column from the right for which an error was diagnosed with AD, additional constraints are in- troduced. In the example in Figure 3, the student made an add ten to minuend error. ASG-E restricts the solution set for Column 2 and 3 according to m+10 and m 1 , respectively. ASG always terminates after the column(s) highlighting the first error with a m or m 1 column (cf. Fig. 2). If a student makes an take difference error, there exist additional special cases. For example, if a student cannot solve 7 4, a structural analogous problem (case m), such as 9 1 seems not to be helpful. To create problems which cover the take difference error, one can make use of arithmetic analogies (Gentner, 1983, p. 156). One arithmetic analogy might be such that the di↵erence of mi and si is identical for both problems (i.e., dSi = di ). However, this structural restriction cannot be obeyed in all cases. The exceptions are given in ASG-E.3 ASG generates structural isomorphic problems by construction (the defini- tions given in Fig. 5) and it is guaranteed that ASG never returns an empty so- lution set (proof in Zeller, 2015). However, the generated minuend could include leading 0s and the subtrahend can be 0. Both cases are not plausible analogies. These cases can be excluded by the simple inclusion of additional constraints. 5 Conclusion We presented the ASG algorithm for online automatic generation of analogous subtraction problems. The constructed analogies specifically address the diag- 3 Details for decrement and add ten to minuend error are given in Zeller (2015). 116 nosed student error, that is, they capture the structural relevant relations be- tween minuend and subtrahend of a student solution and highlight the student’s misconceptions. Our work builds on an ITS of Zinn (2014) which does not use an error library (Brown & Burton, 1978; Young & O’Shea, 1981; Narciss & Huth, 2006) but performs diagnosis with AD. This results in a more flexible system, because every possible error in arbitrary subtraction problems can be identi- fied based on the expert production rules. In consequence, the system is not restricted to a predefined set of problems. Instead, students can input their own problems, or problems from text books or assignments. Our ASG approach allows the generation of structural isomorphic problems for all possible subtraction problems. The solution path of the generated analogy is guaranteed to be identical to the student problem until the erroneous column or columns. Then, the student error is highlighted. Since these characteristics of ASG are guaranteed by construction (proofs see Zeller, 2015) an empirical evaluation of the algorithm is not necessary. However, empirical studies about the impact of ASG generated examples on learning success of elementary school students should be conducted to evaluate the usefulness of our approach. To investigate whether analogies generated by ASG facilitate the identifi- cation of misconceptions and thereby support learning of written subtraction, we plan to conduct several empirical studies. In a first study, we want to com- pare analogies created by ASG with analogies created by a human tutor. We will construct a set of hypothetical erroneous student solutions which we will present to experienced elementary school teachers. The teachers have to identify the error and are instructed to create an analogous problem which they assume to be helpful to the student. Teacher provided analogies will be compared with the analogies generated by ASG with respect to path congruence of the written subtraction algorithm (cf. Fig. 1). The AD approach and ASG can easily be adapted to other written subtrac- tion methods. We plan to transfer the concepts underlying AD and ASG to teaching other mathematical operations (written addition, multiplication, and division) and to other domains strongly depending on procedural skills such as teaching computer programming. References Anderson, J. R., & Reiser, B. J. (1985). The LISP tutor. Byte, 10 , 159–175. Brown, J. S., & Burton, R. R. (1978). Diagnostic models for procedural bugs in basic mathematical skills. Cognitive Science, 2 , 155–192. Burton, R. R. (1982). Diagnosing bugs in a simple procedural skill. In D. Sleeman & J. S. Brown (Eds.), Intelligent tutoring systems (pp. 157–183). Boston, NY: Academic Press. Gentner, D. (1983). Structure-mapping: A theoretical framework for analogy. Cognitive Science, 7 , 155–170. Gick, M. L., & Holyoak, K. J. (1983). Schema induction and analogical transfer. Cognitive Psychology, 15 , 1–38. 117 10 Christina Zeller and Ute Schmid Goldwater, M. B., & Gentner, D. (2015). On the acquisition of abstract knowl- edge: Structural alignment and explication in learning causal system cat- egories. Cognition, 137 , 137–153. Murray, W. R. (1988). Automatic program debugging for intelligent tutoring systems. San Francisco, CA: Morgan Kaufmann. Narciss, S., & Huth, K. (2006). Fostering achievement and motivation with bug-related tutoring feedback in a computer based training for written subtraction. Learning and Instruction, 16 , 310–322. Novick, L. R. (1988). Analogical transfer, problem similarity, and expertise. J. of Exp. Psy.: Learning, Memory, and Cognition, 14 , 510–520. Nwana, H. S. (1990). Intelligent tutoring systems: An overview. Artificial Intelligence Review , 4 , 251–277. Reed, S. K., & Bolstad, C. A. (1991). Use of examples and procedures in problem solving. J. of Exp. Psy.: Learning, Memory, and Cognition, 17 , 753–766. Renkl, A. (2014). The worked examples principle in multimedia learning. In R. E. Mayer (Ed.), The Cambridge handbook of multimedia learning (Sec- ond ed., pp. 391–412). Cambridge University Press. Shapiro, E. Y. (1983). Algorithmic program debugging. Cambridge: MIT Press. Sleeman, D., & Brown, J. S. (1982). Introduction: Intelligent tutoring system. In D. Sleeman & J. S. Brown (Eds.), Intelligent tutoring systems (pp. 1–11). Boston, NY: Academic Press. Sweller, J., & Cooper, G. A. (1985). The use of worked examples as a substitute for problem solving in learning algebra. Cognition & Instruction, 2 , 59–89. VanLehn, K. (1998). Analogy events: How examples are used during problem solving. Cognitive Science, 22 , 347–388. Wiese, E., Konerding, U., & Schmid, U. (2008). Mapping and inference in analogical problem solving: As much as needed or as much as possible? In Proceedings of the 30th CogSci (pp. 927–932). Mahwah, NJ: Lawrence Erlbaum. Young, R. M., & O’Shea, T. (1981). Errors in children’s subtraction. Cognitive Science, 5 , 153–177. Zeller, C. (2015). Automatische Erzeugung analoger Beispiele aus Debugging- Traces [Automatic generation of analogue examples from debugging- traces] (Master’s thesis, University of Bamberg, Germany). Retrieved from http://www.cogsys.wiai.uni-bamberg.de/theses/zeller/ ma zeller-christina online.pdf Zeller, C., & Schmid, U. (2016). Automatic generation of analogous problems for written subtraction. In D. Reitter & F. E. Ritter (Eds.), Proceedings of the 14th International Conference on Cognitive Modeling (ICCM 2016) (pp. 241–242). University Park, PA: Penn State. Zinn, C. (2013). Program analysis and manipulation to reproduce learners’ erroneous reasoning. In LOPSTR 2012 (pp. 228–243). Springer. Zinn, C. (2014). Algorithmic debugging and literate programming to generate feedback in intelligent tutoring systems. In KI 2014, LNCS 8736 (pp. 37–48). Springer.