JI. of Arfificial Intelligence in Education ( 1 994) 5(3), 37 1 -4 13

THEMIS: A Nonmonotonic Inductive
Student Modeling System

YASUYUKI KONO, MJTSURU IKEDA, AND RIICHIRO MIZOGUCHIThe Institute of Scientific and Industrial Research, Osaka University
8-1 Mihogaoka, Ibaraki, Osaka 567, JAPANNonmonotonicities of students7behavior and the student model
inference process itself are discussed including the usage of themodel in tutoring. They are classified into two classes, i.e., single
world contradictions and multi-world contradictions (student
knowledge contradictions). Student knowledge contradictions are
the essentials of the learning processes of a student. This paper
presents a new perspective to capture them formulating a student discrimination structure. A student model description language SMDL and modeling algorithm HSMIS, which is a nonmonotonic inductive student modeling system, are formulated tocope with single world contradictions. SMDL is based on a logic
programming language taking 4 truth values. THEMIS is a newnonmonotonic and inductive model inference system which incorporates deKleer's ATMS as a vehicle for formulating both
nonmonotonicities (contradictions). The formulated THEMIS
embodies advanced representation power, sufficiently highadaptability and generality. Not only can it follow a student's
change of understanding, but it can model a student who has inconsistent knowledge.

INTRODUCTION

Student modeling is one of the most important topics of ITS research,
because the behavior of an ITS largely depends on a student model, which
represents a snapshot of the student's knowledge. This is a reason why
many efforts concerning student modeling have been made, for instance,

372

Kono, Ikeda, and Mizoguchi

overlay model, buggy model, perturbation model, etc. (Wenger, 1987). Mostof the conventional modeling methods have simple pragmatic structures andhave been incorporated into many ITSs. However, all the methods havesome limitations and no complete and sound inference procedure for modeling has been obtained yet. In this paper, we formulate the student modelingproblem as an inductive inference problem, i.e., a problem of constructing amodel explaining observed data which are, in our case, student's answers to
the problems given.
A student who is in the fixing stage1 of the acquired knowledge often
shows contradictory behavior. This means a student is apt to apply problem
solving methods unstably, since he2 has not built them or since he has notcompleted in a formulation of related concepts, etc. It is clear that he showssuch nonmonotonic learning processes in fixing his knowledge in the process of acquiring new knowledge. There are other types of contradiction to
be considered in designing a student modeling system. A modeling system
often gets an answer from the student that is consistent with his current belief but inconsistent with his past answers, because he has changed his
mind as his learning proceeds or he sometimes makes careless mistakes, socalled "slips."
Contradictions which a modeling system should cope with are classified
into the following two types:
1. contradictions which should be resolved by revising the student model,
and
2. contradictions which should be captured as they are.
Generally speaking, an ITS should follow a student's nonmonotonic
change. Furthermore, a student modeling system should realize more flexible
modeling behavior and construct reasonable student models from didactic
viewpoints by embodying a teacher's insight, e.g., the ability to capture her
student's status by asking fewer questions. Contradictions of type (I) inevitably appear in the student modeling process. Therefore, a student modelingsystem is required to have the ability to cope with various kinds of nonmonotonicities. To this end, a student modeling system should always makebelief revisions to keep data for inference consistent. Surprisingly, however,
only Huang et al. (199 la; 1991b) have tackled this problem, except that Woolfet al. (1993) have pointed out its significance. The authors have been attacking this issue and developing an inductive student model inference algorithm HSMIS (Kawai et al., 1987; Mizoguchi et al., 1987; Mizoguchi etal., 1991). HSMIS (Hypothetical Student Model Inference System) employs

1

th
to I
TI )
g(
a:

1

W.

p2 I
ni
ar I
ar 1
tal 1

1

kr 1

sc I

wl 1
kr
P'
st1
st1
gr
to:
be
sit
ev
19

in:
ioi
kn
M
tyl

el3
H!
Pa
tra
co
sy

THEMIS: A Nonmonotonic Inductive Student Modeling System

the ATMS (Assumption-based Truth Maintenance System) (deKleer, 1986)
to maintain consistency of the student modeling process (Ikeda et al., 1988).
The architecture of HSMIS is based on a logic-based inductive inference algorithm SMIS (Ikeda et al., 1989), whose model description language is alsoa logic-based language called SMDL (Student Model Description Language)
which takes four truth values to represent a student's understanding. This
paper first discusses the characteristics of contradictions and nonmonotonicities observed in the student modeling process. Then a student modelingarchitecture to deal with those nonmonotonicities is presented, after SMDLand SMIS are defined. Thus HSMIS realizes relatively high model representation power and modeling ability.
The second problem, that is, to capture a student's contradictoryknowledge as it is, seems more important from educational viewpoints. The
Socratic method, for example, is a contradiction-based tutoring strategy
which teachers use especially to help students in the fixing stage. It is a wellknown and already verified method that gives such a student a strong impression that he misapplied his knowledge. Although building high-fidelity
student models is an intractable problem (Self, 1988), an ITS should have a
student model which is precise enough to handle tutoring strategies integrated into the ITS (Diller~bourg,1989). In order to generate sophisticated tutoring behavior like the Socratic method, student modeling methods shouldbe able to cover a student's contradictory knowledge. His knowledge acquisition and fixing processes should be captured by modeling him as he is,even if he has contradictory knowledge (Kono et al., 1992; Kono et al.,1993b; Kono et al., 1994a).
Some might say that some ITSs, for example, WHY (Stevens et al., 1977),
have realized the Socratic method. Tutoring behaviors generated by most
Socratic tutors, however, do not notice or suggest contradictions that exist
inside a student in spite of the fact that such a suggestion is the real behavior of the Socratic method. They only give a new negative example of his
knowledge. They do not realize the real and complete Socratic method. HSMIS is equipped with a mechanism to cope with all the contradictions oftype (1) which are formulated in this paper. HSMIS generates student models in SMDL which has more expressiveness than Horn clauses. Therefore,
HSMIS realizes a high modeling ability and model expressiveness which surpasses most other modeling methods.
This paper presents a new methodology for handling a student's contradictory knowledge in conjunction with Socratic tutoring based on theconcrete foundation of student modeling. It is difficult for not only modelingsystems but also human teachers to distinguish the two types of contradic-

Kono, Ikeda, and Mizoguchi

THEMIS: I

tion, that is, one where a modeling system should treat the student's knowledge as contradictory and the other where the system should follow the student's nonmonotonic change, because all of their indications are very similar. Two types of contradictions are formulated. Type (1) is named "single
world contradiction" which is coped with by HSMIS, and type (2) is named"multi-world contradiction" which is coped with by the structure of a concept discrimination tree. The two methodologies, HSMIS and a multi-world
inference mechanism, are successfully incorporated into the architecture of
THEMIS by enumerating and equipping domain independent heuristics todistinguish the two types of contradiction. In the newly formulated THEMIS, ATMS plays another important role of managing multiple worlds whichenable the modeling of students with contradictions.
First, this paper classifies and formulates the above two types of contradiction which should be dealt with in student modeling. HSMIS, a nonmonotonic inductive student modeling system, which is able to cope with single
world contradictions is then formulated. Next, a mechanism which copeswith multi-world contradictions is formulated, which is incorporated into
THEMIS based on HSMIS. Finally, THEMIS is evaluated and compared withother representative systems.

[A3]Stuc.
tent ,

374

CONTRADICTIONS IN STUDENT MODELING

A student's answer to a question is represented by a pair of a fact andits truth value and is called an oracle. The student modeling problem can beformulated as an inductive inference problem, i.e., a problem of constructing
a model explaining observed data. A set of oracles acquired by observationof a student's behavior within a certain period tends to be inconsistent forseveral reasons. Such inconsistent behavior is classified into the following
three types of contradiction according to the causes of them:[AlIOracle contradictions caused by change of student's mind: A student's learning process is essentially attained by acquiring new knowledge causing change of his mind. The consistency of his answers within the whole learning process can be easily lost, because he behavesbased on his current knowledge independent of his previous knowledge.
[A2]0racle contradictions caused by slips: A student often makes carelessmistakes. Oracles based on them are inconsistent with his actual knowledge, hence, the set of oracles that contains slips is inconsistent.

I

These th 1
tions," si Ior know1
The
complete I
pectation I
often difl I
ly represt
current n
atypeof I
Con. 1category Iof themother ha:dent's UI I
them efft
Som I
next sub:the multi
tradictio~
the view
cess.

1

,

~

1

What is i

Let .
concept
cepts heapplying
concept.
ed concc"uniforrr
Questioncelerated
ed motiofor unifc
the two c

THEMIS: A Nonmonotonic Inductive Student Modeling System[A3]Student knowledge contradictions: A student sometimes has inconsistent knowledge in his head which also causes contradictory oracles.
These three kinds of contradiction are referred to as "student contradictions," since they are related to nonmonotonicities of a student's behavior
or knowledge.
The student modeling process is essentially hypothetical; hence, thecompleteness of an inferred student model is not always guaranteed. The expectation of a student's answer deduced from the current student model isoften different from new oracles, when the current model does not completely represent his current status. Assumptions which were assumed when thecurrent model was inferred become inconsistent with the set of oracles. Sucha type of contradiction is called [B] assumption contradiction in modeling.
Contradictions of type [All, [A21 and p ] should be placed in the same
category when classlfling them according to how to treat them, because allof them should be resolved by revising the current student model. On theother hand, contradictions of type [A31 should not be resolved, but a student's contradictory knowledge should be represented as it is so as to utilize
them effectively in tutoring.
Some examples of student knowledge contradictions are given in thenext subsection, and a formulation of the contradictions is made based on
the multi-world logic in subsequent subsections. All types of the above contradictions in student modeling are then classified and discriminated fromthe viewpoint of how they should be handled in the student modeling process.
What is a Student Knowledge Contradiction?

Let us assume that a student is in the stage of acquiring a certain new
concept and that he has not fully discriminated it from other related concepts he has already acquired. Such a student is apt to behave unstably inapplying knowledge to solve problems which contain the undifferentiatedconcept. Figure 1 indicates the behavior of a student who has undifferentiated concepts, that is, the concept of "uniform motion" and the concept of"uniformly accelerated motion." He correctly calculated the location of P in
Question 1, which specifies the type of motion as "linear and uniformly accelerated motion." In Question 2, however, he mistook a uniformly accelerated motion for a uniform motion, and so applied problem solving knowledge
for uniform motion. Such a situation occurs due to his confusion between
the two concepts. As a result, his problem solving ability becomes unstable.

Kono, Ikeda, and Mizoguchi

376

Question 1
Question 2
Question 3
A aplrere Ir;u pa.sseil t l ~ r n ~ ~tlkc
f i l ori511~
wit11 vc- A s[>llcre lriw pmsecl Llrro~~gl~An sphere is tlrrown directly u plocity l'J.G~rr/xlo tile rig111at 1 = O*. It c o l ~ t i l ~ ~ ltlrec a origiu with velocity I ~ . ~ I ~wards
I / J with initid velocity 19.6m/s
lilrear aucl rraifor~lrlyaccclcrarctl ~nr>tiolr;rlor~:: I- to the riglrt at t = Oa along z- a t t=Os. It reacl~esa t the maximum
axis of a llorizo~~talplallu. ;illd stopped ;it t = 2s. axis of a Irorizo~~tel
11Iane. P is lrigl~ta t t = l . Determine the direcIt I~ILSS = ?kg. Get it# clisl~lnr.crr~et~t
at t = Is. I I I O V ~ I withI~
lirrear 111otio11with ti011 of the applied force a t t=lr.
D e t e r ~ r ~ i rhot11~ e the tlirectio~i;iricl t l ~ ct~ri~grrit~~tlc
its velmiry dccre;wiag at ;L ani- S t u d e n t ' s a n s w e rof the ;ipplicd force.
forlllecl rate. I t stopped a t t = 7s =1 vo =
1 0
2-0
Is. Det~:rl~li~reits dinpl.ueurent
Student's answer=
g,g,/,
0-19.6
2-U-~.SIII/S=
R I 1 = 1s.
It ia still moving upward a t L = Is.
Studen'''S, = Su+,)ot+ t a t 2 = 0+13.Grl+= 14.7 St = So+vl = 0+1D.G*1 = 13.G Tlrerefore. it is still receiving upward
force at t = ls,
T l ~ cdisl>lacc~ner~t
is 14.7~11fronr t l a~r i a~i ~ ~ .
The d i r l ~ l a c e r ~in~ r13.Gm.
~~t
F = rrbn = 2 r -9.8 = -13.6kg.~n/r2
It receiver 13.6 kg.t~t/*2of force to tlnc It:fl.

++, , = H =---&

stance. I
the na: 1
formlythe forworld. I

1"S I

tus wlviewedtradict 1
He

1
I

Figure 1. Examples of behavior of a student who has undifferentiated concepts

A student can choose certain problem solving methods appropriate forthe problem given, if he has well-discriminated concepts and has adequate
knowledge of their attributes. If he has not, however, he might misapply aprocedure which belongs to another world by taking no notice of particularattributes of the problem. For instance, methods to "calculate the location ofa moving object" are associated with both concepts, such as uniformly accelerated linear motion (St = So + vot + at212 or St = So + (vo + vt ) * 112) anduniform motion (S, = So + vt). In solving Question 2 in Figure 1, he retrieves
the method defined in the concept of uniform motion, while he should apply
the method defined in the concept of uniformly accelerated linear motion.
A more interesting example of student knowledge contradiction is foundin Question 3 in Figure 1. The student who had correctly calculated the force
that the sphere receives in Question 1 could not determine the correct direction of the force in Question 3 in spite of the fact that the two motions are
physically identical except for the direction of the motion.
Such conflicts among his answers suggest the "multi-world inference"
assumption that he partitions his whole storage and inference space. Eachsmall partition in his inference space with relevant storage is called a"world." He stores problem solving methods and rules which he can handle
at once in each world. He can retrieve and utilize these methods in a certain
world, only when he makes inferences in the world. A contradiction can befound when he utilized two different worlds in solving problems. One is theworld of well-formulated physics for Question 1 in which he stores theknowledge learned through the curriculum of physics-for example, forrnulas and definitions-and another is his naive physical world for Question 3
which has been deeply engraved on his memory since his childhood, for in-

gar 1
the:
He
cer
Formu

Multi-\
HI
based
tionednot re]digm i

TI
organiby:

1. fir$ao

2. rettheT

on a clcrimir

THEMIS: A Nonmonotonic Inductive Student Modeling Systemstance. He has a "motion implies a force" misconception (Clement, 1982) inthe naive one in this case. It is inconsistent with the knowledge for "uniformly accelerated motion" in the well-formulated one. He has answered thatthe force is directed upward because he used the naively misconceptualized
world.
"Student knowledge contradictions" are defined in this paper as the status which causes behaviors which can be regarded as a contradiction
viewed from the standpoint of an observer. A typical interpretation of contradiction is as follows:
He places more than two series of problem solving methods, which are
originally placed in different worlds of concepts, in the same world regardless of their attributes. This is caused by his failure in differentiatingthem from each other.
He makes decisions which are able to derive different truth values for acertain fact within a limited time, since his knowledge is unstable.
Formulations of Student Knowledge Contradictions Based on theMulti-World Logic

Here we discuss a formulation of student knowledge contradictions
based on the concept discrimination structure and multi-world logic mentioned in the previous subsection. It is an intractable problem to try to modela student's inconsistent knowledge in a single reasoning space, since it cannot represent contradiction. This suggests we need another modeling paradigm which is able to cope with inconsistency.
The formulation is based on the authors' speculation that human beings
partition their whole storage and inference space into multiple ccworlds"andorganize them in a discrimination tree to retrieve their knowledge efficientlyby:
1: first retrieving which world (concept) the given problem belongs to alonga certain discriminating structure, and2. retrieving and executing methods that contribute to problem solving in
the world corresponding to the problem.

The first step, the decision on the target world, is regarded as a search
on a concept discrimination tree as depicted in Figure 2. Each node of a discrimination tree corresponds to a concept and each leaf node to a world.

Kono, Ikeda, and Mizoguchi

378

When a problem is given to the current model, the discrimination tree in themodel is at first interpreted to retrieve the conceptual world the problem belongs to by searching the tree from its root. The searching and retrieval process is called discrintination level reasoning. The second step is regarded
as a search for and execution of methods that contribute to solving the problem. A set of problem solving methods is defined inside each world. Method
level reasoning is thus carried out in the retrieved world, each of which consists of consistent knowledge. Contradiction is modeled as a mixture of multiple worlds which is caused by an incorrect discrimination tree structure.
Roughly speaking, therefore, student knowledge contradictions are represented as wrong concept discrimination conditions, while conventionalbugs are represented as wrong methods inside each world.
Problem solving knowledge is represented as a set of predicates whose
formula is either solve (G, 2 in,X" ), or goa~(Rin ,T,,). G denotes the goalof the problem, that is, what should be determined under what constraints.
X" in is a vector of input variables which are instantiated and 2 out is a vector of ouput variables which are not instantiated when the predicate iscalled. { X in ,X" .,) represents whole the articulation of the problem space.
For instance, the problem space "motion" is represented as{m,(s(t),ASL(v(t)A (a(')#' a),(f(t)9A3[(To,So:"o,ao,Fo) *.I1, where the elements are the mass of the moving object, location ,velocity, acceleration andapplied force as functions of time elapsed, and sets of the elements of the
motion, respectively. Each function of time elapsed is denoted as a couple ofthe function itself and the attribute of the function. The problem space,which is adopted in Question 1 in Figure 1, is represented as
f 2,(s(t)).(v(t)),(~(t)~J~~d),(RI)),[(2,So,(o,o),a9,Fo),(O,(O,O),(
19.6,0),a1,F1)l1.
When the problem solving begins, input variables are given in the formula
as instantiated variables. For instance, the location and the velocity on t-0
are instantiated as (0,O) and (19.6,0), because they are given in the problem.
Problem solving is a retrieval and an execution of methods described in the
problem solving knowledge base, to get the output parameter list {X" ,) instantiated from the given input parameter list { X in).
The given problem is represented as a vector of primitive attributes
which is used for deciding the worlds the problem belongs to by tracing the
given tree from its root. Each conceptual node on the tree that is not a leaf
node has no problem solving methods but discrimination knowledge,
which defines what children nodes the node has and what conditions the
problem must satisfy to discriminate each child concept from others. The
conceptual node Ni that has children concepts N,,.-Nq has discrimination
knowledge d(N,,[Nil,*--,Nv],[Cil,*..,Cij])in general. To go forward through the$3,:path frc
lem, shthe disc
ceptualN, to R
N1 corrand W2
Questic
the w o ~examplworld,
en. A ncorrespworldscontribof met1
is retril
problennationand boltakes o:Stlconcepous trecas men
OUS wodiscrirr
nodes cis reviCiq,*-,(
C@v (scenda:space ri
into it,worldswho lxmotionedge oflevel rc
model

'

1

I
1

I

,
I

I
I

I

I

'I

I
I

I
I

I

I

THEMIS: A Nonmonotonic Inductive Student Modeling System379

path from Ni to Nk(15 k 5j) requires that (2h), input variables of the problem, should satisfy Cik, the discrimination condition for Nik In Figure 2(a),the discrimination knowledge d(Nl,[Wl, W2],[Cl,C2])is defined for the conceptual node Nl that has children worlds Wl and W2; for instance, to go fromN, to Wl requires the problem to satisfy the condition C,. Let us assume that
Nl corresponds to the concept of "linear motion," Wl to "uniform motion,"and W2 to "linear and uniformly accelerated motion." Given the vector for
Question 1 in Figure 1, it traces a path on the tree from the root and reaches
the world W2 via N1, because it satisfies the discrimination condition C2, forexample, constant (A,) which means "the acceleration is constant." In eachworld, m(Wi ), a set of problem solving methods which belong to W, , is given. A method level student model-that is, model of the method set m(W, )corresponds to a conventional student model. When S, the set of theworlds to which the given problem belongs, is identified, methods which
contribute to solving the problem are retrieved and executed from the unionof method sets, each of which is an element of S., When only one world W2
is retrieved, method level reasoning takes place inside the world; that is,
problem solving methods are retrieved from )?I( W2) and executed. A discrimination condition has a predicate formula, which is called a worldpredicate,and both C1 and C2 are world predicates in Figure 2. Each world predicate
takes only input variables, that is, (2;,), as its argument.
Student knowledge contradictions are modeled in terms of erroneousconcept discrimination trees, because the student who has such an erroneous tree cannot manage consistency in retrieving problem solving methods
as mentioned above. Such kinds of contradiction can be modeled by erroneous world predicates in the multi-world model. When a student has not fully
discriminated concepts N, and Nlq(l 5 p < q 3)
which are both children
nodes of N.1, the discrimination knowledge of Ni in the student model for him
is revised to be d(Ni,[Nll,~~~,NIP,~~,N,,.-.,No], [Cl1,.-,C, v Clq,~~-,CIpv
Clq,.-*,C,]); that is, discrimination con8itions for both NIPand Niq becomeC, v Ciq. Method level reasoning of the problem that belongs to any descendant worlds of either N, or Nlq takes place in the combined reasoning
space m(Nlq@Ni) such that &oth method sets rn(N@)and nt(NIq)are merged
into it, where m&@) contains all the methods defined in all the descendantworlds of N, and m(N!q) contains those of Nlq. The model of the student
who has not fully discriminated uniform motion and uniformly accelerated
motion, in the above example, is represented by the discrimination knowledge of N,, d(Nl,[ Wl, W,], [C,vC2,C1vC2])as depicted in Figure 2(b). Method
level reasoning is done in the combined reasoning space m(?V1@ W2). Suchmodel representation and interpretation enables the capture of his unstable

Kono, Ikeda, and Mizoguchi

380

discrrmination

method level reasoningd(No, [.-.,NI,...], -.-)d(N1, [W~,WZ],[C1,C2])m(W1, [ m: rn: rn: in: 1)m(W2, [ m: rn: m: m: 1)(a)d(No, [.-.,NI,...], ...)d(Ni, [Wi,W2], [Ci UCZ,Ci u C2])~(w,@wz,[[ "'l rnl ] @ [ m:11)rn, m,
m: rn.

THEMIS:

solve inthoughjunctive
represerwrong kis movilwrong nthe work
MOI
ing the 1
dent unr
Souther]sea cum
rect fact
the disc]
and "nomi(b)

Figure 2. Concept discrimination tree

applications of knowledge. When he becomes able to discriminate theseconcepts, the discrimination model is revised again to be correct and method
sets that had been combined since then are restored.
Figure 3 illustrates a few instances of simplified student models. Each
predicate written beside each arc of the tree-for
example,solve-in-naive world-is the world predicate which discriminates the childconceptual nodes of the parent one. The student model for a student who
has not yet discriminated between uniform motion and uniformly accelerated
motion is illustrated in Figure 3 (a). World predicates for these concepts arerevised to be uniform rnotion(8 ,)v uniformly accelerated-motioi~(G).
Figure 3 (b) represents the status of the student who has the "motion implies aforce" misconception in his naive world and unstably applies it in solving
physics problems. World predicates for the naive world"solve-in-naive world (2,)''and that for formulated worlds"solve-in_/or~latedworld(
are both revised to be

Figure 3

and "noEach in1
discrimi
region i;(Place) illevel
version (the figu
stulTHEMIS: A Nonmonotonic Inductive Student Modeling System381

solve informulated world(y ), v solve-in-naive-world (2,,,). Although students' undifferentiation of concepts is represented by the disjunctive of world predicates as is explained above, conventional bugs are
represented by wrong methods in a certain world. The student who has
wrong knowledge, say knowledge for calculating location of the object thatis moving linearly and uniformly, is modeled so that there exists at least awrong method-for instance, 'Sf = Vo* t" in place of "St = So+ Vo*t9'- in
the world of uniform motion.
More detailed multi-world model descriptions are given in Figure 4 using the geographic domain. The domain is structured aiming to make a student understand that climates of seaside regions are different between theSouthern hemisphere and the Northern hemisphere because of the effects ofsea currents. The whole correct model except knowledge of instances (correct facts) is given in Figure 4(a). The conceptual node "earth is the root of
the discrimination tree and has two children worlds "southern-hemisphere"
and "northern-hemisphere." World predicates "southern-hemisphere(~1ace)"

Figure 3. Interpretation o f the student contradictionand "northern-hemisphere(P1ace)" are given for discrimination conditions.
Each input variable, that is, Place, is bound to a name of the region and thediscrimination knowledge evaluates which world the region belongs to. If aregion is in the Northern hemisphere, world predicate northern-hemisphere(Place) indicates true and world northern-hemisphere is selected. Method
level student models are actually represented in SMDL which is an extended
version of Prolog and is formulated later, though they are written in Prolog in
the figure. In each clause of method level models, only the last parameter,382

Kono, Ikeda, and Mizoguchi

the truth variable, is the output variable, and all other parameters, that is,
Crop and Place, are input variables. The correct method level student modelof the world southern-hemisphere consists of two clauses, which mean
"The Crop grows in a certain Place, if the temperature, the soil, and the lay of
the Place is suitable and there exists enough irrigation," and "The temperature of a certain Place is suitable for the Crop, if the Place is the middle latitudes," respectively. The correct method level model of the world
northern hemisphere is additionally given a clause that means "The temperature of ;certain Place is suitable for the Crop even if the Place is in relatively
high latitude, if the Place is on the west cost of a continent," because warm
currents and wind from the west bring such regions a warm climate in the
Northern hemisphere.
The discrimination knowledge of the student model in Figure 4(b) is revised from the correct one (underlined); that is, both world predicates forsouthern-hemisphere world and northern-hemisphere world aresouthern-hemisphere(P1ace) v northern-hemisphere(P1ace). Such a representation of the discrimination knowledge denotes that the student has not yetcorrectly discriminated the two worlds. Given a problem on this subject, forinstance, "Does wheat grow in the southern part of Chile?," both of the discrimination conditions indicate true, so the student model interpreter generates a combined method set of the two worlds. Then the model in thesouthern-hemisphere world correctly returns false, but the model in thenorthern-hemisphere world returns true which causes a contradiction.

THEM I

FigurtP 1

dent Ia predent Ito revedge:

Classification and Handling of Contradictions

Contradictions enumerated at the beginning of this section are classified by their causes into two categories:
1. Student contradictions ([All [A21[A3]),
2. hiodeling contradictions ([B]).
Student contradictions are caused by inconsistencies of a student's behavior or his knowledge itself. On the other hand, modeling contradictions
are caused by inconsistencies between the knowledge that a student actually has and the knowledge that is represented in the student model. This classification is summarized in Table l(a).
Next, let us classifL these contradictions from the viewpoint of how
they should be handled in student modeling. This classification is summarized in Table 1@).

C
model
tradicistudersumpt

THEMIS: A Nonmonotonic Inductive Student Modeling Systemdcearth. Csouthernhemisphere. northernhemisphere].
Csouthern4emiaphere(Place).
northernhemisphers(Plac.)l).
m(aouthernhemisphere, [(grov(Crop, Place. T) :suitable-temperatur.(Crop, Place, TI),
suitablesoil(Crop. Place. Tl) ,suitablelay (Crop, Place. Tl).
has-irrigation(P1ace. T,)
and(T1 .T2 .TJ.Ti .TI).
(suitable-temperature(Crop. Place. T ) : middlelatitude(Placa, T))]).
m(nortbernhamisph*re. C(grou(Crop. Place. T ) :suitablefemperatura(Crop, Place, TI).
suitablesoil(Crop. Place. Tl)
suitablelay (Crop. Place. Tl).
has-irrigation(P1acs. T,)
and(T1 ,T2.Tl ,T4,T)),(suitable~temperatura(Crop. Place. )'7:middlelatitude(P1ace. 2').
(suitable-tsmpereture(Crop. Place. T) :middlehighlatitude(P1acs. T I )uest~corst(P1ace. Tz)
and(T1 .Tz.T))l).

-

.

.

.

(4

.

.

.

d(earth. [southsrnhemisphsre. northsrnhemispberel~southarnhemirph~re(Place)Vnorthe~ipheraPlac.
southernhsmisphere(Place)Vnorthemhemiaphere(Place)l).
southernhe hemisphere, [(grou(Crop. Place. T ) :suitable_temperatur.(Crop , Place, TI) ,suiteble~oil(Crop. Place. Tl) ,suitablelay (Crop. Place. Tl )has-irrigation(P1ace. Ti).
md(T1 .Tz .T,,Ti .TI).
(suitable-tomperatue(Crop, Place. T) :middlelatitude(P1aco. T))I ) .
m(northernhrisphere. C(grov(Crop. Place. T) :suitable-temperaturs(Cr0p. Place. TI1 .
ruitablesoil(Crop. Place. Tz)
suitablalay(Crop. Place. Tl).
haslrrigatxon(P1ace. T,),md(T1 .Tz .TI.T,.T)).
(suitable-temperature(Crop. Place. )'7 !middlelatitude(Place, T))(suitable-temperature(Crop. Placa, T) :middlohighlatitude(P1ace. TI1 .
uemt_coast(Place, Tz)
and(T1 .Tl.T))I).

.

-

.

.

.

(b)

Figure 4. Examples of multi-world student model representatiot~in Prolog

An inconsistency between a student's actual understanding and a student model must be caused by faulty assumptions that were hypothesized ina previous inference stage and have been believed. A nonmonotonic student modeling process is required to get rid of these inconsistencies, that is,
to revise the student model so as to be consistent with the student's knowledge:
1. Set up assumptions that are necessary to construct the student model
which satisfies the set of given oracles in each phase of student modeling,
2. Derive the model from these assumptions and record the derivation process,3. When a certain inconsistency between the oracle set and the model isdetected, find a set of assumptions which causes the inconsistency,
4. Resolve the contradiction by revising the system-made assumptions inthe set and continue the modeling.

Considering each oracle as an assumption, the above nonnlonotonic
modeling methodology to resolve the inconsistencies is applicable to contradictions of types [All and [A2]. Oracles that are not consistent with astudent's current understanding should be removed from the current assumption (oracle) set. A student model that is consistent with a student's

Kono, Ikeda, and Mizoguchi

Table 1

Classification of Contradictions in Student Modeling(a)Clczssification by cause

Cia-ssificcl name
S tuclcn t Contradiction

Type

.

[Al][A2][A31
Modcling Contrac!iciion[B](1)) Classification by handling
C1;~ssifictln:~nle
Type
Sillgle Woslcl Contradiction [All[A21[B]Ml~lti-Wol-lclCo~lt~raclictioil [A31

understanding can be constructed from the assunzption set manipulated insuch a way inside a single world. Single world contradiction is a generalterm for these types of contradictions, that is, [All, [A21 and [B], which amodeling system should try to build a consistent model of in a single world
by finding an appropriate set of oracles (assumptions).
The above four steps of the belief revision process suggest that ATMS
is appropriate for a core module of the controlling mechanism for student
modeling. In ATMS-based problem solving systems, ATMS and an inference system work in collaboration with each other. The inference system executes problem solving and informs ATMS of its inference process. The
consistency among data dealt with by the inference system are managed by
ATMS. ATMS holds and revises a set of valid assumptions which is the origin of the inference and derivation process of data by the inference system.
When derivation of a contradiction is informed, ATMS calculates the set ofassumptions which causes the contradiction by tracing back the informedderivation paths fiom the contradiction. When an assumption is denied, data
which rely on it can not hold any more and hence are automatically denied
by ATMS. In addition, ATMS is able to avoid redundant calculations whichhave previously been made, which is usehl to make the inference process
very efficient.
All the single world contradictions-that is, [All, [A21 and [B]-aredealt with by the same mechanism, which is realized by formulating the inductive student modeling process on the basis of ATMS in HSMIS. A detailed description of this topic is given in the next section.

THEMIS:In thother ha:should bc
tions, sucworld 101
single wc
knowled]tency whinference
hence poing its deTheworld comultiplewith anddiction i!
It revise:
representhe secol
Heuristic

It isdistingui[A31 anc
tioned, t
1992; Sttion of tl
actual a1
ic and fi
kinds olthem is I
Let
student I
world cction fror
cedures
world ccthe curr

THEMIS: A Nonmonotonic Inductive Student Modeling System
In the case of student knowledge contradictions, i.e., type [A3], on theother hand, contradictions in his knowledge should not be resolved but
should be represented as they are. As is discussed in the above two subsections, such a type of contradiction is represented well on the basis of multiworld logic, and is called a "multi-world contradiction in contrast with asingle world contradiction. Based on the multi-world formulation, a student
knowledge contradiction can also be defined as a certain kind of inconsistency which arises among some assumptions that have been assumed in theinference process in a manner similar to a single world contradiction. It is
hence possible to capture a student's contradictory knowledge by formulating its detectinglhandling methodology.
The student modeling system THEMIS which is able to cope with multiworld contradictions consists of HSMIS and the controlling mechanism ofmultiple worlds. HSMIS makes inferences consistently in each world copingwith and resolving single world contradictions. When a multi-world contradiction is detected, HSMIS passes the control to the Multi-World Controller.
It revises the concept discrimination tree of the given domain knowledge torepresent the contradiction. A detailed description of this topic is given in
the second next section.
"

Heuristics to Distinguish Contradictions

It is difficult for not only modeling systems but also human teachers to
distinguish and detect the four types of contradictions-type [All, [A2],[A31 and [B]-which are the essentials in student modeling as already mentioned, because all of their indications are very similar (Dillenbourg et al.,
1992; Self, 1993b). They are triggered by a difference between the expectation of the student answer deduced from the current student model and his
actual answer. One of the research goals of this paper is to produce a generic and formulated modeling mechanism which is able to cope with thesekinds of contradictions. Although a generic methodology to distinguishthem is not fully developed, some heuristics are employed as shown below.
Let us assume that the certainty of every given oracle and clause in thestudent model can be available. Both single world contradictions and multiworld contradictions are detectable by quite similar triggers, i.e., the expectation from the model and the actual oracles. The contradiction resolving procedures of those contradictions are quite different from each other. Single
world contradictions need to be resolved by revising the set of oracles orthe current model in general. The contradiction resolution procedure for386

Kono, Ikeda, and Mizoguchi

each type of single world contradiction is a bit different, and hence the detection processes for them are different from each other. In the heuristics,
multi-world contradictions are first distinguished from single world contradictions.
Student knowledge contradictions, type [A3], should not be resolved,
because the student's inconsistency should be modeled as he is. Student
knowledge contradictions require the revision of neither the oracle set nor
the clauses that are inconsistent with oracles, but the discrimination structure to permit it to contain the inconsistency. Such a difference in treatmentof multi-world contradictions and single world contradictions suggests thefollowing way of discriminating them. If either the certainty of a clause whichis inconsistent with valid oracles or certainties of some of the oracles areless than a certain threshold, the inconsistency should be considered to be asingle world contradiction and hence should be resolved. On the other hand,
if all the certainties are high enough, the inconsistency is considered to be a
student knowledge contradiction. They are not revised but put into someworlds; that is, all the reliable data can be alive in the multi-world formulation. The following heuristics to detect contradictions of each sub categoryof single world contradictions are incorporated.
The change of student's knowledge which causes type [All of contradictions occurs especially right after his errors are corrected. He then generally changes his understanding from an erroneous to a correct status. It isappropriate to apply revision procedures for type [All when correct oracles
are obtained right after tutoring, that is, the system resolves the contradiction by excluding the past oracles inconsistent with correct clauses or byasking him truth values of the oracles. The revision of oracles results in therevision of the model; erroneous clauses are dismissed and correct clauses
are appended.
Independently of the correctness, generally speaking, the student
ought to have consistently applied the clauses that are inconsistent with
newly obtained oracles throughout a certain period, in the case that hemakes careless mistakes which cause type [A21 of student contradictions.
Thus such a type of contradiction is detected by similar criteria as those forstudent knowledge contradictions; that is, the inconsistent oracles andclauses would be both reliable enough. There are two ways to distinguishthem; one is to consider a situation as a type [A21 only when the situation
could not be treated as a student knowledge contradiction, and another is to
ask him a very similar question to get a confirmation.
These contradictions can be more sufficiently distinguished by introducing and enriching domain dependent heuristics-for instance, "Students

tend tomotionplainec:
Tf
dent rr
hardlypropriz
studenithe stues, thetor oft

0
1

tions i:inductiworld
ments
cussed

1. Ac(
bec
eve
cos
aPF
trac
2. u17,
for
len
an3
infi
pla
req
3. Thc
ti01
ute

mo
of1

THEMIS: A Nonmonotonic Inductive Student Modeling Systemtend to mistake a uniformly accelerated motion for a uniform motion if the
motion is vertical"-in addition to the domain independent heuristics explained above.
There is one more point which should be considered in designing a student modeling system. It can be assumed that there exists a student who
hardly behaves consistently, because of his low ability or the system's inappropriate selection of the level of task. It does not make sense to let such a
student complete the current task. It is possible to detect such a status of
the student by diagnosing the past record of acquired oracles. In such cases, the modeling system should give up modeling him and inform the monitor of the failure so as to let the student go back to elementary tasks.
NONMONOTONIC STUDENT MODELING IN A SINGLE WORLD

On the basis of the above conceptual-level discussion on contradictions in student modeling, this section proposes a powefil nonmonotonic
inductive student modeling methodology which is able to cope with single
world contradictions. Student models have to satisfy the following requirements in addition to the requirements for the nonmonotonicities already discussed:
1. Accuracy-cost trade08 In general, the more accurate the student model
becomes, the more effective the behavior of the system becomes. However, there exists a tradeoff between the accuracy of the model and thecost of constructing it. From a pragmatic viewpoint, we must set up an
appropriate representation scheme for student models by taking thetradeoff into consideration.
2. Unknown assertions: When a student fails to deduce his own solution
for a problem, he would say to his teacher "I could not solve the problem." Needless to say, this assertion does not mean he does not haveany knowledge. The student model module should use this assertion as
informative data about his knowledge and construct a model which explains why he cannot deduce the answer from his own knowledge. Thisrequires the student model to deduce "unknown" assertions.
3. Theoretical foundation: Domain-independent and theoretical foundations for the student modeling mechanism should be defined. It contributes to both the clarification of the inherent properties of the student
modeling problem and to the articulation of the scalability and reusabilityof the proposed mechanism.

388

Kono, Ikeda, and Mizoguchi

To meet these requirements, the authors have developed a student
model description language SMDL and a hypothetical student model inference system HSMIS. SMDL is an extended version of Prolog and takes four
truth values including "unknown" to model the student precisely. HSMIS,an extended version of Shapiro's MIS (Model Inference System) (Shapiro,
1981, 1982), is an inductive inference system for SMDL. In HSMIS, ATMS:
Assumption-based Truth Maintenance System (deKleer, 1986) is employedfor dealing with nonmonotonicities. HSMIS has been implemented in Common ESP (Exqended Selfcontained Prolog) on SPARC station (AIR, 1990).
This paper briefly presents the formulation because of the space limitation. The complete formal definitions are given in (Kono et al., 1994b).

1

Ther
ate z I
the (
cate2
SMt 1
wet(P

cord
man 1

SMDL: A Student Model Description Language

In addition to the above requirements, a student model is required torepresent not only students but also the systems' understanding of the students, which implies the model has to distinguish the two states: The system
can predict the behavior of the student and the system cannot. When themodel is based on logic, which is our case, it has to have two truth values,
true and false, to denote the above two states, respectively. Needless to say,the former state, that is, the one corresponding to "true," should represent
the student's logical state such as "true," "false," and "unknown" which
stand for "the student believes a statement is true," "the student believes it
is false," and "the student does not ascertain its truth," respectively. Then,
we have two seemingly the same truth values "false," which can be discriminated as follows: Employing Prolog terminology, the former "false" is treatedas "fail" and the latter as one of the three values corresponding to "success." Discrimination among the three values is done by introducing an auxiliary argument interpreted by a meta-interpreter.
Facts are represented in SMDL as follows.

)
I

,

tion
log;
clau
soml
valu
goal
goal
trutl
SUCC

clau
grow

falst
These three facts represent "The student believes Paris is not in the torrid
zone but in the temperate zone and does not know whether it is fertile ornot."
Clauses are written in the form of
A ::-B,,B2;.*,Bktorrid

falst
ing 1

THEMIS: A Nonmonotonic Inductive Student Modeling System389

A is called a head and the RHS of the clause is called a body. Some simplified
examples are shown below.

These two clauses show that the student thinks "If place X is in the temperate zone or in the torrid and wet zone then the plant grows in X." Intuitively,
the clauses with the same head have a disjunctive relation and the predicates in the body have a conjunctive relation. Given a goal grow(paris,T), the
SMDL interpreter calls the subgoals temperate(paris,TI), torrid(paris,T,), andwet(paris,T3)in this order. The truth value T of grow(paris,T) is obtained according to T = T4 v Tj = TI v (T2 A T3) = true v wise A unknown). The semantics of the logical operators " A " and "v " are shown in Table 2.
The predicate of SMDL is of the form p(X1,X2,-.,Xm ,T), where p is apredicate name and Xi(1s i I m) is a variable. From now on, a sequence ofvariables, for example Xl,X2,--,Xm, is abbreviated as ? . T is a truth variable
or one of four truth values.
An SMDL clause is of the form: H::-BIB2,...,B,,, n 2 0,where H, B , ( l I i
I n) are predicates. In the case of n = 0,it is called a fact. The SMDL program P is a finite set of clauses.
The execution process is defined as two different forms: weak-resolution and strong-resolution. The former is like the execution process of Prolog; that is, "a goal succeeds in weak-resolution if there exists at least one
clause which derives the goal." On the other hand, strong-resolution issomewhat different and complicated. Roughly speaking, a goal with truth
value T succeeds in strong-resolution, if all the OR clauses unifiable with thegoal succeed and the result of the OR evaluation is T. Generally speaking, agoal with truth value true can be weakly derived but a goal with anothertruth value needs to be strongly derived. For instance, a goal grow(paris,T)
succeeds in weak-resolution with truth value true by executing only the firstclause, if a subgoal temperate(paris,true) succeeds. On the other hand, a goalgrow(antarctica,T) needs to succeed in strong-resolution with truth value
false by executing both clauses to call the subgoals temperate(antarctica,T,),
torrid(antarctica,T2)and wet(antarctica,T3), whose execution results are false,@lse, and true, respectively, and to obtain the truth value of the goal according tofilse v (true ~filse).

Kono, Ikeda, and Mizoguchi

Table 2
Definition of A and v

data ;<p(anddersorac 11(h) V operatorA(a) A opcri\t.or
tri~e 1111k.
false

faii

V

true

unk.

false

fail

true
unk.
false
fail

true
1111k.
false
fail

rink.
unk.
false
fi~il

faii
fail
fail
fail

true
unk.
false
fail

true
true
true
tm~e

true
unk.
unk.
fail

true
unk.
false

true
fail
fail
fail

false
false
fidsc
fail

1

SMIS: Inductive Student Model Inference System

Figure 5 shows the block diagram of THEMIS. HSMIS, the core moduleof THEMIS, consists of SMIS (Ikeda et al., 1989), ATMS (explained below),
The Virtual oracle generator (also explained below) and the Contradiction resolving system (CRS). The main task of ATMS is to manage the consistencyof a set of assumptions (environment) used by the problem solver, SMIS in
our case. The Virtual oracle generator is responsible for improving the performance of model inference by generating assumed student answers basedon the reliability of the student without asking the student questions. CRS
resolves the inconsistency identified by changing the environment.

Stuc

the c
Proc
clau;
whic
decic
tivat
valu

Figure 5. Block diagram of THEMIS

391

THEMIS: A Nonmonotonic Inductive Student Modeling System

A pair of a problem and an answer to it is called an oracle and is used asdata to be covered by the model obtained. An oracle is of the form
< p ( R ',T),T ' >,where ' is a sequence of ground terms, T is a truth variable
and T' E ( true, false, unknown ). Because fail represents the system's understanding of the student, it cannot be the truth value of an oracle. A set oforacles given to the system is called an oracle set and denoted by a.
SMIS applies the following procedure repeatedly to the model:
1. If there is a difference between an oracle and the fact derived from thestudent model, activate the student model diagnosis system, SMDS, toidentify the cause of the difference.
2. According to the diagnosis, SMIS selects an appropriate operation, either removal of an -refuted clause or addition of a new clause, and informs ATMS of the process.
Table 3
Activation of SMDS Subprocedures

truth value derived from student model

true

unknown

false

fail

IL

Q)

4'cE;.
5g
flh

u 0

true

ip

unknown

failp

false

failp

1

Student model diagnosis system. SMDS traces the resolution process ofthe current model and checks the results with oracles. SMDS has three subprocedures, that is, ip ,fp and failp. The procedure ip finds out where a newclause should be added. The procedure fp detects an -refuted clause
which should be removed from the model. The procedurefailp dynamicallydecides which procedure,& or ip, should be activated. SMDS selectively activates one of them according to the difference between the oracle's truth
value and the one derived fiom the student model (see Table 3).
Let us assume that there exists an oracle H= < p ( R ' ,T),T ' >, a clause C=p(X , ~ ) : : - q , ( y,,T,), q 2 ( y 2,~t),".74k( 2 k , ~ k1, and the set of oracles
q l ( x ',,Tq,(X b T ',),.-,q,(~'J that derives p ( x ', T ' ) with C. The
I,),

392

Kono, Ikeda, and Mizoguchi

set of oracles is called a top-level-trace of C for H. A simplified but concrete
example of a top level trace is shown in Figure 6, where the oracles O,;.*,O,
correspond to student's answers (a) through (f), respectively. In this case,the clause C covers 0,,where the toplevel trace is made by O2and 03.

I grow(Plant,Place,T)::-C
y...7.....,....."

suitable-temperature( Plant, Place,T~),
suitable-soil( Plant, Place,Tz).

............

101 1s covered by C , where thei (suitable-ternperat~~e(riee,o~aka)made by 0 2 and 03.
suitable-soil( rice, egipt, true) ). ).

#01: <grow(rice.osaka. Tt). true,
0 2 : <suitable-temperaIure(rice, osaka. Tz). true.>-

0 3 : <suitable-soil(rice, osaka. Ts), true.>-..,.. -A.<>-".,-.v

+
,,.

-.-.:

(a) Does rice grow in Osaka?
(b) In the temperature of Osaka suitable for rice ? s(c) Is the soil of Osaka suitable for rice ?

04: <grow(rice,egypl. T1), false,
05: <suitabb~temperature(rice,egypt, T5), true.>
06: <suitable-soil(rice, egypt. To), true.>--<----....
(d) Does rice grow in Egypt? no,(el Is the temperature of Egypt suitable for rice ?
(D Is the soil of Egypt suitable for rice ? ~ e s .

--Figure 6. Examples of the top-level trace and the refutation for a clauseLet us assume that there exists an oracle 07:~grow(rice,kiev,T7),true>.
The top-level trace of C for 0, can be made, if there exist the following two
oracles:
0,: ~suitable~temperature(rice,kiev,T,),true~and
09: <suitable-soil(rice, kiev,T,),true>.
However, when there exists an oracle O<suitable-temperature(rice,kiev,T',), false, instead of 0, and there are no OR clauses unifiable withthe goal O,, O, cannot be weakly-derived from the current model. In such asituation, the model P is said to be too weak with respect to a goal 0,.
When a weakness is detected in P, ip is activated and it searches for thecause of the weakness by proving each clause in the proof tree of the oracle.
Figure 7 shows a Prolog implementation of ip. The goal good-oracle-top( p(X ,7), T ', Body, Tb)finds a clause p(X ,T): :-Body E P which has a correct top-level trace. If such a clause does not exist, the goal p(X ,T' )is uncovered by P and returned as an output by ip. Otherwise, ip is recursively
called.
I
,
:

clau:
the
rekt
Cl -r(
strer
( P(.

deril
chec

THEMIS: A Nonmonotonic Inductive Student Modeling System393

i p ( ( A , B ) , (Ta, T b ) , C ) : weakly-derive( A, Ta)-i p ( B , Tb, C 1;
i p (A , T a , C ) .

i p ( A , T a , C ) :g o o d - o r a c l e - t o p ( A , T a , Body, T b )i p ( B o d y , T b , C 1;
C = [(A ,Ta) , uncover]-.

Figure 7. Prolog implementation of ip

To cover the uncovered goal detected by ip, HSMIS searches for a newclause to add into the model.
We define a binary relation > " over truth values. When two clauses
derive different truth values, T I and T,, for a goal, we say TI is stronger thanT, ifTl = Tl v T, and write T, > T,.
We say a model is too strong with respect to a goal if it has at least one
clause which derives a stronger truth value than the oracle with respect tothe goal. A too strong model has at least one $2 -refuted clause which has arefutation. In Figure 6 , the clause C is rehted by oracles 04, O5 and 06.The
R -refuted clause, which should be removed from the model as a cause ofstrength, is identified by the procedure@.
Figure 8 shows a Prolog implementation of $. The goal refutation( p ( 2 ',T), T ', Body, Tb) finds the clause p(g,T)::-Body E P which weakly
derives p(2 ',Tg) such that T, >T '. The goal check-rehtation(Body, Ta, C )checks each goal of the Body with R .
"f p ( A , T, C ) :r e f u t a t i o n ( A , T , Body, T b ) ,c h e c k x e f u t a t i o n ( Body, Tb, ~ b ,)( Cb==ok- > C = [ A : :-Body, i n c o r r e c t ] ;C = Cb).
c h e c k z e f u t a t i o n ( (A,B), ( ~ a , ~ b C) , ) :c h e c k r e f u t a t i o n ( A , T a , Ca)( Ca==ok-> c h e c k r e f u t a t i o n ( B , Tb, C ) ;C = Ca).
c h e c k x e f u t a t i o n ( A, T a , C ) : oracle( A, T )( g e ( T , Ta)-> C = o k ; f p ( A , T , C ) ) .

Figure 8. Prolog implementation of fp

Kono, Ikeda, and Mizoguchi

Let us assume that check refutation@, ( 2 ',T,),T '. C) is activated under the condition that q , ( i ZT;) is derived from P and >qi(H ',Ti)T>; is in
R . If T," iT. ' then the cause of strength should be found in the resolution
process of q, ',,T,'). Therefore check-refutation calls ~ ( ~',T,),T~ ('I,, 2C)
recursively. Otherwise it returns C=ok.
The model P is said to be incomplete, if P derives the truth value fail toa certain fact which is contained in R . The procedure failp identifies thecause of the inconnpleteness, which is either an uncovered goal or an R -refuted clause. Figure 9 shows a Prolog implementation of failp. The procedure
failp@(X ', 0,T I, C) is activated when the model P cannot derive p ( 2 ',T ')and q ( d',7),T '> is in . If P cannot weakly-derive p ( 2 ',T '), it calls
ip(p(X
T ', C). Otherwise, it calls f&2g2@(2',T ), T I, C). The procedure fp2
selects the clause which derives p(X', fail) and finds a correct top-leveltrace of the clause. If the correct top-level trace derives p ( Y ',Tg) and Tg >T ' then fp2 returns the clause as an R -refuted clause. Otherwise @2 calls
fnilp for the body of the clause.

(k

',n,

failp( (A,B), (Ta,Tb), C ) :smdl( A, fail )-> failp( A, Ta, C ) ;failp( B, Tb, C ) .
failp( A, Ta, C ) : not ( weakly-derive( A, Ta) )-> i p ( A , Ta, C 1;
fp2( B, Tb, C 1.
fp2( A, Ta, C ) : smdl-clause( A , Body ) ,smdl( Body, fail ) ,good-oracle-top( A, Tg, Body, Tb),
( le( Tg, Ta), failp( Body. Tb, C 1;
( gt ( Tg, Ta) , C = [A: : -~ody,incorrect] ) ) .

Figure 9. Prolog irnplemer~tationof failp
Search for a new clause. A candidate clause to be added into the model isgenerated using the refinement graph which is defined by refinement operators. The generation process is viewed as a kind of search on a dynamicallygenerated tree. The refinement graph is rooted by a most general clause. Itsnodes correspond to candidate clauses and directed arcs c-&> C ' to therefinement operations applied to clauses. Typical examples of refinement operations include adding a predicate into the body and unification of variables. The graph has the following important characteristic:

THEM

7searclP

searclany a
fixed
here 1well.
eratia
make:
ATMS

v
(NIJ
7
kinds
defintone p
er dat
F
reach
sump
assun
to reccons1
the clwhicl
calleccan b
main1
recorcdoes I

THEMIS: A Nonmonotonic Inductive Student Modeling System
If the clause C does not cover a goal A, then any C ' satisflingC+C ' does not cover it either.
This is used for pruning the unnecessary branches, which makes thesearch efficient.
A refinement graph represents knowledge which enables an efficient
search for a clause to be added into the model. However, it does not haveany a priori knowledge of bugs. So, it always tries to find a clause from afixed root, that is, the most general clause, independently of material. Notehere that we can introduce the concept of bug when we know the material
well. Given some typical bugs specific to the teaching material under consideration, the search procedure can begin searching from these bugs, whichmakes the search very efficient.

ATMS
This section briefly explains ATMS.
The information given by the inference system takes a form of
N,,& ,..., Nk =$D
which means that the datum D is derived from a set of the data
(N,f12 ,...,Nk). (N1,N2,...&) is called a jW1cation of D .
The data dealt with in the inference system are classified into threekinds of data, i.e., premise data, assumed data and derived data. A premise isdefined as a datum that can be true under any context. An assumed datum is
one produced with an assumption that holds without depending on any other data. A derived datum is one inferred from other data.
Following each justification back from a certain derived datum finallyreaches a set of assumptions and premises. That is to say, the set of assumptions that an individual datum depends on can be calculated. A set ofassumptions is called an environment. It is one of the major tasks for ATMS
to record justifications informed from the inference system and to calculate aconsistent environment where the data can be inferred. When derivation of
the contradiction is informed, ATMS calculates the nogood environment,
which is the cause of the contradiction and recorded in ATMS (hereafter
called the nogood record). Every environment included in the nogood record
can be regarded as an inadequate combination of the assumptions. ATMS
maintains the consistency of the inference process by using the nogood
record. The inference system selects a new consistent environment, which
does not include the nogood record elements, and continues inference.

Kono, Ikeda, and Mizoguchi

THEN I

A situation in the problem solving process is called a context, which isdefined by the set of the data that hold in the situation. An environment deriving all the data included in the context is called a characteristic environment of the context.
When the derivation of an inconsistency is informed, ATMS calculates
and records the environment of I.The inference system ceases to solve theproblem in the contradicted context and transfers to a new consistent characteristic environment.
With regard to the nodes which have been derived before that time,
ATMS determines whether each node holds (in) or does not hold (out) in
the new characteristic environment. Thus a new context is composed with aset of in nodes.

virtu

396

Managing Consistency to Control the Model Building Process

Single world contradictions are formulated in a unified architecture in
HSMIS by combining SMIS and ATMS. With the aid of the schematic diagram shown in Figure 5, the overall behavior of the system for single worldcontradictions will be made clear in this subsection. (a) Given student answers ("real oracle"), the Virtual oracle generator generates virtual oracles ifnecessary and passes them to ATMS with the real oracles. (b) SMIS informs
ATMS of all the inference processes that are explained in detail in (Kono etal, 1994b). When a contradiction is informed, ATMS computes the label responsible for the inconsistency based on the information given up to thatpoint of time and stores it in the nogood record. (c) SMIS asks CRS to resolve the inconsistency. (d) According to the cause of inconsistency identified, CRS selects a new environment which is consistent by asking ATMS tocheck its consistency. (e) ATMS answers the queries by inspecting thenogood record and (f) passes the control to SMIS together with a new context supported by the new consistent environment.
HSMIS tries to model the student from his behavior during which it auton~aticallyasks questions which contribute to the disambiguation of alternative clause selection and diagnosis. In other words, HSMIS asks questions regardless of their appropriateness in the sense of tutoring. This requires some control mechanism of the HSMlS behavior. The following additional mechanisms are introduced to augment the HSMIS.

;

terna I
knocl 1kno~
derst; 1syste: 1aboulcase
the n I
sonal 1main
withc )

1

based 1
tions,
dent'
asks
swer:
cles"
consi
1

as thc
whicl
Mefa.

form
stude
examl

In thi

The c

THEMIS: A Nonmonotonic Inductive Student Modeling System
Virlual Oracles. Let us discuss the initial model problem. There are two al-

ternative initial models: one is empty, which means the teacher does notknow anything about the student in advance, and the other is complete
knowledge (teaching material), which means she assumes that he usually understands the material very well. Although the former case is reasonable, thesystem would tend to ask many questions to get sufficient information
about how well he understands the material. On the other hand, the lattercase does not require many questions, at least for excellent students, since
the model can explain their correct behavior. This characteristic is very reasonable in real tutoring. The latter is employed. A serious problem still remains, however. One cannot simply put a clause into the student model
without any justification.
The Virtual oracle generator, which generates plausible student answers
based on the certainty of the current student model instead of asking questions, has been devised in order to cope with this problem. When a student's behavior is confined within the scope of his teacher's prediction, sheasks fewer questions by replacing the necessary information with correct answers. This type of oracle is called a "virtual oracle." SMIS treats "real oracles" and "virtual oracles" in the same manner, while ATMS manages theirconsistency.
When a clause supported by virtual oracles turns out to be no longer inas the inference proceeds, ATMS withdraws it and backs up to the point
which causes the problem.
Meta-Oracles. Students sometimes want to express their knowledge in theform of knowledge instead of facts. The system sometimes wants to ask thestudent the reason why he answers a question that way. The following is an
example.
System: Does rice grow in Russia?
Student: Yes, it does.
System: Why do you think rice grows in Russia?
Student: It has wide flat fields and rivers.

In this case, HSMIS can obtain an oracle and a clause as follows.
<grow(rice,russia,T),true>grow(rice, Place) ::flat-field(Place),river(P1ace).

The clause obtained fiom the student is called a meta-oracle.

398

Kono, Ikeda, and Mizoguchi

Assumptions to Cope With Single World Contradictions

This subsection gives the formulation of assumptions to drive themechanism mentioned in the previous subsection. The nonmonotonic inference process of HSMIS is realized by controlling the status of the assumptions representing various hypothetical decisions which are made during
student modeling.
Given a consistent oracle set 6 , SMIS is able to construct a student
model which explains 6.That means SMIS is potentially able to c o p withall the modeling contradictions in terms of SMDL, if an appropriate n is given. In HSMIS, these modeling contradictions are formulated to be controlled
by the following three types of assumption in the framework of ATMS:

it coland ;tion

uncover(C,O) which represents that an oracle 0 can not be covered by acertain clause C. It holds unless cover(C,O) is derived. This type of assumption is used to prune branches in the refinement graph and to detectthat the search turns out a failure.
Q -eonsistent(C) which represents that a clause C is consistent with 6 ,the current oracle set. It holds unless fi -refutation(C) is derived. Such aconsistency is checked whenever 6 is changed by the mechanism. This
type of assumption is used for revising the student model to follow
change of 6.
general(C) which represents that any ancestor clauses of C in the refinement graph which are more general than C are not contained in the current model. It holds unless an ancestor clause of C is added to the model.
If an ancestor clause of C is added to the model, the clause C no longer
holds in the model.

SMI

In order to cope with two types of student contradictions, [All and[A2], which are both classified into the single world contradiction, it is necessary to update the oracle set itself, for example, to leave unreliable oracles
out of consideration in modeling or to mod@ truth values of some of the oracles which cause a certain inconsistency. This requirement means that t k system should be able to generate the currently reliable set of oracles a,which is considered in model inference, from the whole set of given oracles
W. The following type of assumption is formulated in addition to the above
three types to meet the requirement.

(

Dete

fied

Whc
date
sing
trus

THEMIS: A Nonmonotonic Inductive Student Modeling System399

oracle(0) which represents a question and a student's answer to it, that
is, a "real" oracle 0. If the assumption oracle(0) is in, oracle 0 is in 6.
This means the oracle is reliable at present.
A modeling system must be able to realize more appropriate behavior if
it copes with nonmonotonicities of a teacher's trust in student's knowledge
and asks reasonable numbers of questions in the didactic sense. Contradiction of trust is formulated by incorporating the following assumption:
trust(C) which represents that the system trusts the student to have theknowledge that corresponds to clause C. It is in unless R -refutation(C)is derived. Virtual oracles are generated based on this assumption andthe oracle that is unifiable with C. The number of system questions ishence reduced without losing logical consistency of the modeling process. When this assumption becomes out, virtual oracles which were derived from it are automatically withdrawn, and the system asks the student the facts which Fad been trusted and have not been asked until
then.
SMIS deals with oracles and virtual oracles in the same manner.
Detection and Resolution of Contradiction

The contradiction derived in the inference process of HSMIS is classified into the following seven types.

S1) Contradiction of R -consistency
S2) Contradiction of cover test
S3) Contradiction of generality
S4) Contradiction of trust
S5) Contradiction of meta-oracleS6) Contradiction of oracleS7) Failure of search
When any of the contradictions is detected, ATMS is informed of it and updates the nogood record.
Among the assumptions which are formulated in HSMIS to cope withsingle world contradictions, Q -consistent(C), uncover(C,A), general(C),trust(C) and metaOracle(C) are called default assunrptions, which means

400

Kono, Ikeda, and Mizoguchi"they are assumed to be in so long as no contrary evidence is found." The
set of these assumptions included in the environment is called a default environment (denoted by D,). From this, the current environment C, can be expressed by
Ce=De ufi
Contradictions can be classified into (a) ones regarding the default environment and (b) ones regarding the oracle environment (corresponding to

Beh

6).

edg
the
ing

I) The resolution method for contradictions of the default environment canbe easily derived from its definition.
Suppose that a contradiction is detected since there exist both the l2 refutatioii(C) and the R -consistent(Q in the current contest. As has alreadybeen stated, the l2 -consistent(C) can hold so long as there does not exist
the refutation for the clause C, that is, R -refbtation(C). Therefore, the inconsistency can be resolved by removing the R -consistent(C) from the default
environment. Similarly, the assumptions, uncover(C,A), trust(C) and metaOracle (C) are removed from the default environment when the contradictorydata is found.

scri
scri
den

Thi
soil
gro

Prel
ma

Q CRS generates consistent 8. The consistency is guaranteed to the ex-tent that it does not include any contradictions that have been foundthus far. In other words, it may contain a contradiction found in the future. The operations carried out for the generation are:
1. remove an oracle from R ,2. modify the truth value of an oracle in R .

CRS searches for a consistent fi in the ascending order of number ofn~odificationsfrom L
l . To improve the efficiency and educational validity of
selecting the consistent oracle set which has the minimal modifications,some domain-independent heuristics are incorporated into the search procedure: Give priority to correct or recent answers, give priority to the oracles
supporting the plausible clause which is supported by relatively many oracles, and so on. Domain-dependent heuristics may also be introduced.

cha
nici
pot'
cha
der

THEMIS: A Nonmonotonic Inductive Student Modeling System

Behavior of HSMIS

An example of how HSMIS works is given in Figure 10, in which the description is partially simplified because of space limitation; that is, the description of teaching material is not correct in the strict sense (e.g., the firstargument of grow is omitted). An example of the modeling process for a student knowledge contradiction is shown in the next section.
In order to realize the behavior of HSMIS, at least two kinds of knowledge are required. One is the knowledge for refinement graph generation. In
the above example, for example, the following knowledge is used for generating three clauses C1, C2, and C3.
declare-called(grow(Place, T),[temp(Place, Tl),soil(Place, T2)])
This means that the predicates in the second argument, tenip(Place, T1) andsoil(Place,T2), can appear in the body of a clause whose head isgrow(Place,2'). If this form of knowledge including necessary predicates isprepared, HSMIS can automatically generate a complete set of clauses as amodel of the student.
The other kind is the correct domain knowledge which provides HSMIS
with correct answers. In the above example, the knowledge is used for three
purposes: generating virtual oracles, managing the environment, and generating problems.
In the above example, the student model changed two times. The firstchange from C1 to C2 can be regarded as corresponding to the nonmonotonicity inherent in the inference process; that is, Cl is not an appropriate hypothesis of the student understanding at that time. Meanwhile, the second
change from C2 to C1 corresponds to the nonmonotonicity of student's understanding.

NONMONOTONIC STUDENT MODELING IN MULTIPLE WORLDS
Inference Process in THEMISThis subsection discusses both the modeling mechanism and the formulation of the modeling process realized in THEMIS which consists of HSMIS and Multi-World Controller (MWC). MWC uses HSMIS as a single
world modeler capable of resolving single world contradictions. THEMIS isKono, Ikeda, and Mizoguchi

the
wh: 1
his
disl Ifro]fen )to 1 1
cri~
visl
by

Is So11o f Moscow suitable for rice to grow?

v 03:so~l(japan.T~),
yes.
Becauseol is a correct answer, the correct clause CI I S
added to the model. Then. u p 2 and u-03. which arecorrect answers are enerated by Oracle- enerator They
are justified by i r m t l g l ) and omcldol). A f ~ ~ informedi sof the following assumptions and justifications.
Assume: orrle(o1). uust(Cl),nsonsismnt(CI).general(Cl)lustificatiotu:
tmsr(C1).oracl4ol) a v-orxl4v-02)
wst(C1).oracle(o1)a v-orrle(v-03)
oracle(ol),v-oracle(v~02).v-oracle(v-03) -cover(Cl.oI).
uracle(ol), fl~ o n n s t e n t ( C 1 )wver(Cl.01).
.
general(Cl)=model(
CI)-

Does rice grow i n Kiev?
ves.
04: grow(kiev.T.), yes.
v 05: soil k~ev.Ts).yes.
A buggyclauseis added to the model, because 04 is atypical incorrect answer(Kieu is too cold for rice row) A
uirtual oracle u-05, which is justified by trust(8.2) andoracle(o4). w generated bv Oracle-generator. Since the clauseC I I S a descendent node of C2 i n the refinement graph.
rnodelfCl) becomes 'out' by outing genera1lCI). Then thestatus of U-02 and U-0.3 becomes 'ouf: H o w e m , "-0.3 beconus'in: became it is jmtilied by trust(C2) and orac&(ollArsumepriom
orrc lc(o4),trust(C2).
fl-&;

07:soil(moscow.T:),yes.
SMDS: C? Is reluted by 06 and 07; Rdul;dlion: grow(morow. falalre)::sod(moxow.vue)
C2 is remoued become SIUDS found out its refhatiow
rowimoscow,no)::- s~illmoscaw,~es)J.
A contradiction isound between fl-nfutation(C.2) a n d fl-consistent(C2).
C R S resolues this by outin the default asrumption flconslstenUC2). Then modelf;C2), uirtual oracles u-0.3 andu-05 becomes 'out'. HSMIS starts to search for a clause
which couera d.
Justifiations:oraclcio6). oracle(o7ti II-refularion(C2).
orncle environmentinol :<grow(japan.Tl).yes.>
our v-o2:<tempijapm.T2). yes. >our v-03:csoil(japanl3). yes. >ind:<groru(kev.T4). yes. >our v-05:csoil()iiev.T5).yes. >ino6:cg~ow(mowow.T6).
no. >in
07:<soil(moscow.T7).yes. >IS

O f Kiev

THE 1

1

1

for rice grow?

oj:soil0riev.T$).Yes. (confirmed by the smden[)e.
I S Temperature o f Kiev suitable for rice t o grow?

08: rernp~1iev.T~).
no.
SMlS: U : g r ~ w ( q l a c c : r ) : - ~ ~ ~ r )Controdict~onu f a d . because HSIUIS s far
to search
for a cover o f g m w ( k i e ~ . ~ e s ) C. R S changes the omcie
environment
toresolvethecontradictionbas&on
the giceconsistent(C?).gen~al(C2)a-prioritv-to-correct-answerheuristics I n this case, dlusrifunrions:becomes
but'
and
09.
whose
truth
w
l
u
e
is
oppositeto 04. I S
wsdC,), oracle(o1)a v-oracle(v-03)
believed according t o give- riority-to-correct-answer
t ~ s l ( C 2 )oracldo4).
a v-orrl4v-05)
heuristic. Finally, CI isto the current model
oraclc(d),v oracldv-05) -covn(C?.o4).
oracle(cyt), I S s o n s ~ s t e n t ( ~cover(C2.04).
~).
gcneral(C?)=rrnodel((mwlel(C1) becomes 'in' again) i n the new cornistent ~ m c &enurmnment .
C?)oracle environment
oracle environment
in ol :cgowCjapan.Tt).yes.>mol :cgrow(~apan.Ta).yes. >inv-oL:<~empCiapan.Td,
yes. >
our v-02:<amp(japanT~).
yes. >
tn v-o3:<soilf~~pan.T,).
yes. >
inv_o3:csoil(japanT~).
yes. >
our oJ:<grow(k~ev.T.).yes. >inoJ:<grow(laev.T.). yes. >inoS:<ro~l(kiev.Ts).
yes. >
inv-aS:<so~l(kiev.T~).
yes. >
ino6:<~row(rnoscnw.T~~.
no. >ino7:<roil(moscow.T~).
yer. >.
.
Does rice grow in ,Moscow?
ino8:<lernp(kiev.T.),no. >o6:grow(moscow.T.). no.
in o9:<grow(k1ev.T~).
no. >
no.

"o.

merpc$F).

abed

-

4

Figure 10. An example of HMIS modeling process

hence able to represent student knowledge contradictions according to themulti-world logic, maintaining the consistencies between model and oracles
in each world. A formulation of the inference process is given in detail in(Kono et al., 1994b).
Among student contradictions, the formulation of student knowledge
contradictions is more complicated than formulations of the other two. The
following two types of assumption are introduced to formulate student
knowledge contradictions:belong(P, W,)which represents that the student is assumed to understandthat problem P belongs to world kVi'
discriminate ( W ,Wj)which represents that the student is assumed to beable to correctly discriminate between the two worlds W, and Wj.
When a correct assumption belong(P, Wi) is isin , the student is expected
to be able to correctly apply a problem solving method, say, M,, which is in
the world Wi of the current model. If he does not discriminate between kVi
and Wj, however, it can happen that he applies Mj which belongs to W, to

nel
wh
tio
be1
dic
ha:
of

THEMIS: A Nonmonotonic Inductive Student Modeling System403

the problem. A contradiction is derived from the assumptions belong(P,Wi)
which is pre-assumed and belong(P, W, ) which is newly assumed to cover
his faulty answer. Another contradiction is also derived from the assumption
discriminate(I+",W), and the datum indiscrhninate(W, W), which is derived
from assumption belong(P, $). In this case, oracles related to P are trans).:
ferred from Wi to ib; together with the belief revision of discriminate(W,, H
to be out and the system revises the discrimination conditions which discriminate the two worlds so as to resolve these contradictions. Thus the revised student model represents the student knowledge contradiction causedby his undifferentiation.
Contradictions derived in the inference process of THEMIS are classified into the following three types in addition to the contradictions formulated in HSMIS:
M1) Contradiction of belong
M2) Contradiction of discrimination
M3) Contradiction of model prediction and oracle
All these contradictions handled by MWC are resolved in a similar manner to contradictions of the default environment; that is, "the assumptions
which were hypothesized in advance and which derived the faulty expectation is denied to be out, when a contradiction is informed." The assumption
belong which has been assumed becomes out in the case of type M1 contradictions. The assumption discriminate and the assumption belong which
has derived an expectation of a student answer also become out in the caseof type M2 and M3, respectively.
Modeling Student Knowledge Contradictions

The formulation of student knowledge contradictions described earlier
works well as a student modeling method by utilizing the heuristics which
are also mentioned earlier. MWC is incorporated into THEMIS to control
multi-world inference. Concept discrimination trees are given in advance as apart of the domain dependent knowledge. MWC is given the whole set ofworlds which are handled in one course of tutoring, and it manages the status of each discrimination condition in the tree and each set of oracles thatbelong to each world. MWC is able to retrieve all the clauses in a certain
world which are unifiable with a certain oracle in the world with the help of
ATMS. Model diagnoses and revisions can be done on the discrimination
trees. In each world, the clause level student model is inductively inferredKono, Ikeda, and Mizoguchi

404

from the oracles belonging to the world. It is realized by modifying the algorithm of the SMDL interpreter; that is, a clause C in a certain world W is unifiable only with oracles belonging to W. Each clause level student model canbe consistently inferred using such a mechanism.
The construction process of the student model that represents student
knowledge contradictions is as follows:
1. The system assumes a student knowledge contradiction when newly obtained oracles are not satisfied by any unifiable clauses in the corresponding world in the model which are sufficiently reliable.
2. The system tests whether the oracles are satisfied by the clauses that exist in another world by visiting the worlds in turn in order of similarity to
the correct world according to the structure of the tree.
3. When a clause explaining the oracle is found in some world, discrimination conditions that contribute to differentiation of the two worlds are revised as depicted in Figure 3.
4. If no satisfiable world is found, the system considers the situation as asingle world contradiction and tries to revise the model in the correct
world.
Such a decision is made based on the heuristics to detect a student
knowledge contradiction mentioned earlier (subsection of "Formulation of
student knowledge contradiction based on the multi-world logic"). THEMIS
calculates the certainty of each clause in its clause (method) level student
model so that it is able to apply the heuristics. The calculation is done by referring to various kinds of information, that is, number of top-level traces
that justify the clause, whether the oracles which consist of each top-leveltrace of the clause are correct answers or not, how old the oracles are, andso forth (Kono et al., 1993a).
I, , the set of instances whose every element originally belongs to acertain conceptual world W, can be determined by applying Cw which is theworld predicate of W to I, the whole set of instances in the domain. Clauselevel representations and oracles which justifj the model are generated andstored in each world individually. Suppose that there are two worlds W,andW, which are brothers and that they have already obtain and involved oracle sets 6, and 6,. Suppose also that clauses M I and M2 are in W1and
kV2, respectively. IfMl, that currently has high certainty, is refuted by the oracle set
which is newly obtained from him, to the problem that naturally
belongs to JJ,: or if M , can not cover a certain goal in db,then the system
hesitates to dismiss Ml and tries to interpret the status of his conceptualop,THEMIS: A Nonmonotonic Inductive Student Modeling System405

discrimination as undifferentiated. If M2 satisfies a,, 0 is moved into W2
and supports M2 there. Both discrimination conditions <and C2, which areworld predicates of Wl and W2, are revised to be C1 v C2. If any clauses inany other worlds in the tree except the "another world do not support
itis assumed that he was thinking in the world that contains naive buggy
knowledge and has solved the problem informally. 6 is moved into the "another world" which is prepared to cover his unform ated problem solving, if
one of the buggy clauses, prepared in the world in advance, satisfies a*.
In our example, the student correctly answered several questions including Question 1 in the past, so that the student model had the correctclause to get the force which an object in uniformly accelerated motion receives. He made the wrong answer utilizing his naive physical world to
Question 3 later. HSMIS receives oracles made from his answer,-for
instance, oracle(subtract(l9.6,0,19.6),true), oracle(subtract(2,0,2), true).
The above clause in the world of uniformly accelerated motion does not satisfy these oracles and derives an answer different from that of him. HSMIS
recognizes the need for a new clause whose head is get-direction-offorce
to satisfj the oracles. There exists the correct clause, however, which shouldhave been applied to the problem, in the world of uniformly accelerated motion in the student model. The clause is reliable enough because the student
correctly answered some questions using the method corresponding to theclause. The student, however, does not apply the method to the latest question. Therefore, it is unreasonable to assume he solved the problem in thisworld.
For this reason, THEMIS does not choose to resolve the inconsistency
in the single world. Instead, it considers the situation as a multi-world contradiction and it searches for the world that already contains the clause
which satisfies the oracles. If the search fails, THEMIS tests "another world
which represents students' naive problem solving. In this example, the system finds out the clause that represents his erroneous "motion implies force"
misconception prepared in the naive world in advance. The system revises
discrimination conditions that partition the concept of motion into the worldof formulated physics and that of naive physics. It can explain his discrimination status, that he unstably applies physics formulas and naive knowledge.

op,dCorrecting Student Knowledge Contradictions

By modeling student knowledge contradictions, the system is able to realize very effective and "real" Socratic tutoring as follows:406

Kono, Ikeda, and Mizoguchi

1. Give him a problem such that he tries to solve it in his naive world andfails to get a correct solution.
2. Remind him of the correct answer to the problem he obtained in
Question 1.
3. Point out the inconsistency between the two results.
4. Explain the causes and guide him to build a correct concept.
In this way, he can correctly identify attributes necessary for building theconcept, which we call world predicates, and establish relationships between
them. Thus he can appropriately conceptualize the knowledge in bothworlds. Obtaining the student model that represents the student knowledge
contradiction, the system becomes able to generate an effective tutoring dialogue as in Figure l l.

Solve this problem. (Give a prol>la:111ui111ilarto Ql~eatioll1 agail~)
Tlrc ~ ~ l r r l ,:or,~crl!/~ r t
an..lr*er...
Tutor: You msvered in Question 3 that the direction of the force vhich the sphere receives is upward at
t = l a . tecause it is still moving upwards then. If chat was correct, why didn't you say that thesphere in Question 1 receives force to the right?
Strrdent:Because it was moving upvards. so it is hardly possible that it continued receiving force downward.
Tutor: The tvo problems are completely the same, e . g . , speed at each time. etc.. except for the directionof motion. If direction of force vere to be implied from motion. you should have naturally s u d(You should havethat the direction of the force is to the left in Question 1, but you didn't.
"motion implies force" misconception in your naive physical world.
Tutor:

Figure 11. A hypothetical example o f tutoring behavior using student knowledge
contradiction

The mechanism for single world contradictions explained earlier and theframework to handle multiworld contradictions explained in the previous section are integrated into THEMIS. It gives up constructing a unified consistent model and dares to build a model in multiple worlds, when newly obtained data deny the reliable current model. The control mechanism guarantees the fidelity and the accuracy of the model in each world. Student's incorrect inference methods, such as the use of abduction in his problem solving, can be formulated as contradictions. However, this topic has been kept
for future work.

THEMIS: A Nonmonotonic Inductive Student Modeling System

DISCUSSIONS

Here some basic issues of comparative student modeling methodologies
are discussed.
One cannot model students without defining a "bug" which is one of
the key concepts of student modeling. The definition of bugs in turn defines
the search space for student modeling. Bugs are defined as a mal-function
or a mal-structure of the correct knowledge from the computational point ofview. By mal-function and mal-structure, we mean a state in which a component of knowledge does not realize its function and a state in which thestructure of knowledge is incorrect, that is, some component is missing or inserted, and so on, respectively. From this point of view, there are three typesof models which model (a) what component of the correct knowledge is incorrect (mal-function-1), (b) how the component is incorrect (mal-hnction-2),and (c) how the structure of the knowledge is incorrect (mal-structure). The
second type not only identifies what component of the correct knowledge isincorrect in the student's head but also models how it is incorrect in a limited
way, for example, using fault models of each component. It cannot model,
however, why the function is so incorrect. Needless to say, the third type isthe most powerfd type of modeling, since it models what, how, and why thecomponent is incorrect by modeling the incorrect structure of the knowledge.
Although student modeling is generally viewed as an inductive process
in which a representation explaining observed data is built, we can find another view, that is, as the analysis of the expertise model using the observed
data (Hoppe, 1994). Modeling methods which obtain information of the student's understanding state by analyzing the correct knowledge based on thestudent behavior are called "analytic methods" here. A student model does
not have to explain all the behavior of the student. Considering that its function is to give necessary and sufficient information to the tutoring module,
analytic methods work very well for many types of tutoring modules. Typicalexamples of analytic methods are the overlay model (Carr et al., 1977), thelogic programming method (Hoppe, 1994), and model-based cognitive diagnosis (Self, 1993a). This type of methods does not model mal-structure, while
inductive methods try to represent it. Typical examples of inductive methods
are the buggy model (Burton, 1982), perturbation methods (Otsuki eta1.,1985), ACM (Langley et al.,1984), and THEMIS. Table 4 summarizes thecharacteristics of the methods discussed in this section.

Kono, Ikeda, and Mizoguchi

Table 4Evahation of Student Models

Systern llanle

Analytic/
MnlMxlMali~lcl~tctive f u ~ ~ c t i o t1l - f1111ction-? structl~reI n c o ~ ~ s i s t e ~ l c yTlleoreticalfoundation

Question
automaticallyAnalytic Methods

The Overlay model (Carr et al., 1977) is relatively easily used to control
the modeling processes. That is why the overlay model has been used inmany ITSs. Since it cannot represent the student's incorrect knowledge, theperformance of overlay-model-based ITSs is limited.
Hoppe ( 1991,1994) proposes a method to analyze the correct knowledge
represented as a Prolog program by executing the program with the student
answer as a goal. When the student answer is incorrect, the execution fails if
it is interpreted by a Prolog interpreter. In order to recover the execution failure, he introduces a fail-safe meta-interpreter of Prolog and detects uncovered goals which potentially correspond to the student's bug. Many uncovered goals are usually detected, so he employs the EBG (Explanation-Based
Generalization) technique to formulate rules called error patterns which areused to select the goals corresponding to the plausible bug. The search
space of this method is small, since it is restricted to the computation tree ofthe correct knowledge. This method requires pre-defined classification rules
which roughly correspond to bug rules, though they are more abstract than
bug rules. It represents bugs of type mal-function-2. This method does not
suffer from the inconsistency problem, because it builds a model from one
dat~lm.
Self (1993a) gives a characterization of student modeling as modelbased cognitive diagnosis, making an application of GDE (deKleer et al.,1987). GDE is essentially based on an exhaustive search over the search
space defined as a set of all the combinations of possible faulty components
with the aid of ATMS. The search mechanism, in principle, is hence to check
what set of components are faulty and to determine a minimum set of faulty
components. Another advantage of GDE is its automatic question genera-

THEMIS: A Nonmonotonic Inductive Student Modeling System409

tion mechanism for disambiguation of the fault hypotheses. It represents
only mal-function-1, although it does not require any bug library. Just asmall extension, such as the introduction of fault modes into each component, enables it to cover type mal-function-2 as Self indicates. It is sensitive
to inconsistent data. The theoretical foundation becomes more firm andsound in this order, though there is a large gap between the overlay modeland Hoppe's method.
Inductive Methods

IDEBUGGY (Burton, 1982) has many modular chunks of buggy procedures. It has the capability to cope with the noise problem; however, it is notcomplete. Its searching strategies depend on the assumption that each individual buggy procedure can be extracted from a combined buggy procedure.
The burden of cataloging bugs is still left.
Bugs are viewed as variants of correct knowledge. They can be generated by applying perturbation operators to correct procedures. Perturbation
methods are based on this idea. Takeuchi and Otsuki (1987) utilize this typeof method in their system BOOK (Otsuki et a1.,1985) in which two types of
perturbation operators (domain-dependent and domain-independent ones)
are introduced to augment the modeling power. The search space of thismethod is dependent on the complexity of the perturbation operators used,which is not usually so large. The method has no firm theoretical foundation
for it but does not suffer from inconsistency of the data, since it builds amodel from one observation.
Both ACM (Langley et al., 1984) and the authors' method THEMISMSMIS are based on the idea that student modeling is viewed as inductive
learning from a set of examples. These two methods are almost equivalent inrepresentation power of the student model. They can model not only malfunctions but malstructures in terms of predefined primitives. Both methods
act as domain-independent engines and their capabilities contain those ofboth the overlay and buggy methods. Besides, both of them can cope withnoisy data. In general, it seems that the method of inference in ACM is not
so sophisticated as that of HSMIS.
The major difference is their searching and diagnostic strategies for ascertaining what part of the model conflicts with the student. HSMIS canprune the search space for new clauses in a refinement graph, although
ACM originally made a blind search of all its search space. To embody efficient searching, Langley et al. (1990) have been developing DPF (Dynamic
Path Finder).

41 0Kono, Ikeda, and Mizoguchi

HSMIS can incrementally revise the model using newly obtained data.
Although the path-finding algorithm is formulated by DPF, the rule-finding
process is not formally defined. HSMIS can distinguish between noisy data
and bug migration (Ikeda et al., 1993; Kono et al., 1993a) while ACM cannot
currently (Langley et al., 1990). HSMIS asks questions which are logically required in consideration of educational appropriateness, while ACM doesnot.
Other Types of Methods

Huang (1993) proposes a logic to capture the student's inconsistentknowledge. Surprisingly, only his study, apart from THEMIS, has so far
been carried out on modeling student knowledge contradictions. Although it
is well-defined in terms of propositional calculus, it would be difficult to extend it to deal with first order predicate calculus.
The role of a student model is to provide a tutoring module with information necessary for generating adaptive behavior. There is no need to produce precise information more than required. PROTO-TEG (Dillenbourg,1989) is an interesting ITS based on this idea. It does not generate any structured information that can be regarded as a student model, but generates
heuristics to produce tutoring behavior directly by incorporating one of theinductive learning theories, LEX (Mitchel et al., 1984). It is successll in handling its simple didactic strategies.
Considering the functions the student model should perform and the intractability of modeling, Ohlsson (1993) proposes a new approach to student
modeling called constraint-based in which domain knowledge is represented
by a set of constraints and the student model is represented by constraint
violation. The idea seems good, since it can avoid many of the difficulties
wlzich current modeling technologies are suffering from. One has to identifj.,
however, sets of constraints which cover all the information the tutoring
module requires which is not an easy task.
CONCLUDING REMARKSThis paper has presented a comprehensive student modeling methodology and its use in an ITS. Contradictions we have to cope with during modeling students are first defined. As a result, we obtained four types of contradiction, including contradictory knowledge possessed by students. The

THEMIS: A Nonmonotonic Inductive Student Modeling System

41 1

modeling system of such students has to model undifferentiated concepts
and inconsistency as it is. A sophisticated control mechanism to deal withboth single world and multi-world contradictions for THEMIS has been developed.
Finally, THEMIS has been compared with other modeling systems fromvarious viewpoints to demonstrate that it is a well-defined and generic student modeling algorithm, which can build a student model of high representation power. THEMIS has been implemented in Common-ESP(Extended
Self-contained Prolog) (AIR, 1990), and HSMIS is embedded in FITS, Framework for ITS. Two ITSs have been built using FITS, one on geography andthe other on chemical reactions (Ikeda et al., 1994; Mizoguchi et al., 1987; Mizoguchi & Ikeda, 199l).
References
A1 Language Research Institute (Ed). (1 990). CESP Language Guide, 5-1-1,

Ohuna, Karnahxra, Kanagawa 247, Japan.
Burton, R. R. (1 982). Diagnosing bugs in a simple procedural skill. In D. SleeTutoring Systenls. London: Academic
man & J.S.Brown (Eds.), I~~telligerrt
Press.
Carr, B., & Goldstein, I. (1 977). Overlays: A theory of inodeling for computer
aided instruction. MIT AT Memo 406.
Clement, J. (1 982). Students' preconceptions in introductory mechanics. Amlerican Journal of Pl~ysics,50,66-7 1.
28, 127de Kleer, J. (1 986). An assumption-based TMS. Artificial I~~telligence,
162.
de Kleer, J., & Williams, B. C. (1987). Diagnosing multiple faults. Art19cial111telligence, 32,97-130.
Dillenbourg, P. (1 989). Designing a self-improving tutor: PROTO-TEG. Instructional Science, 18, 193-2 16.
Dillenbourg, P., & Self, J. (1 992). A framework for learner modelling. Interactive Learning Enviroi~ments,2(2), 11 1-137.
Hoppe, H. U. (1991). An analysis of EBG and its relation to partial evaluation:
Lessons learned. Arbeitspapiere der GMD.
Hoppe, H. U. (1 994). Deductive error diagnosis and inductive error generation
for intelligent tutoring systems. Journal of ArtiJicial Intelligence in Edzrcation, 5(1), 27-49.
Huang, X., McCalla, G. I., Greer, J. E., & Neufeld, E. (1 991a). Revising deductive knowledge and stereo-typical knowledge in a student model. User
Modeling and User-Adapted Ii~teraction,1, 87-1 15.
Huang, X., McCalla, G.I., & Neufeld, E. (1 991b). Using attention in belief revision. In Proc. R4AI-91, pp. 275-280.

412

Kono, Ikeda, and Mizoguchi

Huang, X. (1 993). Inconsistent beliefs, attention, and student modeling. Journalof ArtrJcial Intelligence in Education, 3(4), 4 17-428.
Ikeda, M., Mizoguchi, R., & Kakusho, 0. (1 988). A hypothetical model infer176 1- f77 1 (in Japanese).
ence system. Trans. of IEICE Japan, 571-0,
Ikeda, M., Mizoguchi, R., & Kakusho, 0 . (1 989). Student model description
language SMDL and student model inference system SMIS. Trans. of IEICE Japan, J72-D-11, 112-1 20 (in Japanese).
Ikeda, M., Kono, Y., & Mizoguchi, R. (1993). Nonmonotonic model inferenceA formalization of student modeling. In Proc. IJCAI'93 (pp.467-473).
Chambery, France.
Ikeda, M., & Mizoguchi, R. (1994). FITS: A framework for ITS-A computational model of tutoring. Jotrn~alofArtrJicia1 Intelligence in Education, 5(3), 3 19-348.
Kawai, K., Mizoguchi, R., Kakusho, O., & Toyoda, J. (1 987). A framework for
ICAI system based on inductive inference and logic programming. New
Generation Computing, 5(1), 115-129.
Kono, Y., Ikeda, M., & Mizoguchi, R. (1992). To contradict is human -Student
modeling of inconsistency. In C. Frasson et al. (Eds.), Intelligent tutoring
systents (pp.45 1-4 58). Springer-Verlag.
Kono, Y., Tokimori, T., Ikeda, M., Nomura, Y., & Mizoguchi, R. (1 993a). A
student model building method based on formalization of nonrnonotonicity.
Jouri~alof Japanese Society for ArtiJicial Intelligence, 8(4), 488-498. (inJapanese)
Kono, Y., Ikeda, M., & Mizoguchi, R. (1993b). A modeling method for students with contradictions. In Proc. AI-ED 93 (pp.481-488). Edinburgh,
Scotland.
Kono, Y., Ikeda, M., & Mizoguchi, R. (1 994a). An inductive student modelingmethod which deals with student contradictions. IEICE Trans. on Znforntation and Systems, E77-D(1), 39-48.
Kono, Y., Ikeda, M., & Mizoguchi, R. (1994b). THEMIS: A no~tmonotonicinductive student rioodeli~tgsystem. (Technical Report AI-TR-93-5). Artificial
Intelligence Research Group, ISIR, Osaka University.
Langley, P., & Ohlsson, S. (1 984). Automated cognitive modeling. In Proc.
AAAI-84, pp. 193-197.
Langley, P., Wogulis, J., & Ohlsson, S. (1 990). Rules and principles in cognitive
diagnosis. In N. Frederiksen et al. (Eds.), Diagnostic monitoring of skill
and Btotl~ledgeacquisitio~~(pp.2 17-2 50). Lawrence Erlbaum.
Mitchel, T., Utgoff, P., & Benerji, R. (1 984). Learning by experimentation: Acquiring and refining problem solving heuristics. In R. Michalski et al.
Springer-Verlag.
(Eds.), Machine lean~ir~g.
Mizoguchi, R., Ikeda, M., & Kakusho, 0 . (1 987). An innovative framework for
intelligent tutoring systems. In Proc. IFIP TC3 IVorking Co~tference0 1 1 AI
Tools in Education (pp. 105-120). Fascati, Italy.
Mizoguchi, R., & Ikeda, M. (1 991 ). A generic framework for ITS and its evaluation. In R. Lewis & S. Otsuki (Eds.), Advanced research on co~nputersin edrrcation (pp. 63-72). North-Holland.

THEMIS: A Nonmonotonic Inductive Student Modeling System

Ohlsson, S. (1993). Constraint-based student modeling. Journal ofArtiJicial 111telligence in Education, 3(4), 429-447.
Otsuki, S., & Takeuchi, A. (1985). Intelligent CAI system based on teachingstrategy and learner model. In Proc. WCCE 85, pp.463-468.
Self, J. (1988). Bypassing the intractable problem of student modelling. In
Proc. IT5 '88 (pp. 18-24). Montreal, Canada.
Self, J. (1 993a). Model-based cognitive diagnosis. User Modeling and UserAdapted Interaction, 3,89-106.
Self, J. (1993b). Formal approaches to student modeling. In G. 1.McCalla &J.Greer (Eds.), Student modelling. Springer-Verlag.
Shapiro, E. Y. (1981). Inductive inference of theoriesj-omfacts. (Yale University Research Report 192).
Shapiro, E. Y. (1982). Algorithmic Program Debugging. MIT Press.
Stevens, A. L., & Collins, A. (1977). The goal structure of a Socratic tutor.
Proc. National ACM Conference, pp.256-263.
Takeuchi, A,, & Otsuki, S. (1987). Formation of learner model by perturbation
method and teaching knowledge. Trans. Information Processing Society ofJapan, 28(1), 54-63. (in Japanese)
Wenger, E. (1 987). Artijcial intelligence and tutoring systems. Morgan Kaufmann Publishers.
Woolf, B. P., & Murray, T. (1993). Using machine learning to advise a student
model. Journal of ArtiJicial htelliger7ce in Education, 3(4), 40 1-4 16.

Notes
1. "Fixing stage" means an intermediate learning stage where acquired knowledge is not completely established yet.
2. For simplicity, "she" is used to refer to the teacher and "he" to refer to thestudent in general.

Acknowledgements
The authors would like to thank Takeo Tokimori for his contribution to thiswork. The authors are grateful to Geoffry Webb for his comment which motivated the research on student contradictions. The authors are also thankful toHeinz Ulrich Hoppe for his valuable comments. The authors greatly appreciate
the reviewers' precise and valuable comments. This work is supported in partby Grant-in Aid for Scientific Research on Priority Areas of the Ministry of
Education, Science, and Culture of Japan under Grant No. 03245 106.