=Paper=
{{Paper
|id=Vol-1815/paper11
|storemode=property
|title=Automatic Generation of Analogous Problems to Help Resolving Misconceptions in an Intelligent Tutor System for Written Subtraction
|pdfUrl=https://ceur-ws.org/Vol-1815/paper11.pdf
|volume=Vol-1815
|authors=Christina Zeller,Ute Schmid
|dblpUrl=https://dblp.org/rec/conf/iccbr/ZellerS16
}}
==Automatic Generation of Analogous Problems to Help Resolving Misconceptions in an Intelligent Tutor System for Written Subtraction==
https://ceur-ws.org/Vol-1815/paper11.pdf
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.