ConstraintBased Student Modeling 
a simpler way of revising Student Errors
Kai Warendorf, Colin Tan
Intelligent Systems Lab, School of Applied Science
Nanyang Technological University, Blk N4 Nanyang Avenue #2a36
Singapore 639798
Abstract
Currently, an IMTS is under development to support a university
course on Data Structures in C. The IMTS is written in Java and can rest
on a parent canvas either designed specifically for it or based on a proprietary
standard like Web Browser or Standalone Application. At the current time,
it supports algorithms on linked lists, queues, stacks and binary search
trees. The user interface is interactive with students manipulating the
nodes of onscreen data structures in order to further their understanding
or, in tutorial mode, to solve exercises set by the IMTS. The IMTS will
respond to exercises with feedback and suggestions for further study. This
paper describes our implementation of Ohlsson’s constrainedbased student
modeling [6].
1 Introduction
The traditional role of teachers and learners connotes an active teacher/passive
student relationship, usually with the teacher lecturing at the front of
the class while students sit at desks in rows and listen, take notes, and
occasionally answer questions. The knowledge obtained in these lectures
and tutorials is then applied to practical exercises conducted in laboratory
sessions. These session are usually set up as follows: the students are
given a task which they have to finish within a certain amount of time.
During that period the students usually have one session (generally two
hours) of supervised laboratory. They can ask qualified tutors questions
concerning the task. Before and afterwards they have to start or complete
their project on their own without any professional help. Giving the students
a sophisticated Intelligent Multimedia Tutoring System (IMTS) could give
them a possibility to get answers to their questions using an IMTS designed
for that particular course [12]. The students could also prepare better
for their labs using the IMTS or review part of the lecture material during
lab sessions when they need help.
An IMTS as laboratory support for a university course on Data Structures
in C is being developed an currently tested with students taking this course.
The IMTS is completely developed in Java resides on a parent canvas, either
of proprietary origin (Web Browser or Standalone Application) or on one
designed specifically for the IMTS. In the first phase it supports the
students on algorithms on linked lists, queues, stacks and binary search
trees. The user interfaces in completely interactive, meaning that the
student will interactively manipulate the data structures on the screen.
In tutorial mode the student will be given exercises, which s/he has to
solve interactively by manipulating the nodes of the data structures. Feedback
and tutoring will be given to the student upon errors. In this paper we
describe the usage and implementation of constrainedbased student modeling
as introduced in [6].
2 Assessment of Intelligent Tutoring Systems using
Student Modeling
The goal of Intelligent Tutoring Systems (ITS) is for itself to be aware
of the knowledge it contains, as well as what the student knows. Such systems
should be "... capable of automatically inducing and using a structural
model of the student’s reasoning strategies" [2]. An ITS should also be
"selfadaptive"  able to adapt tutoring sessions based on selfcontained
knowledge. Several systems are evaluated below. These represent the current
range of approaches for the ITS playing field in Student Modeling. Most
systems to date either employ one of the following techniques, a variant
of one, or a hybrid of two or more.
2.1 The Leeds Modeling System
The Leeds Modeling System (LMS) [10] approaches student modeling as
a search problem, with two goals oriented towards making the search computationally
feasible:

contain the search required in creating a student model, and

have the modeler behave in a data directed manner.
Contributions of LMS :

It is possible to constrain the search space in constructing a model such
that the search technique is computationally feasible.

A datadriven modeler is possible. In particular, the model building machinery
of LMS is relatively domain independent. Conversely, it may not work well
in factual systems or those with illdefined domains.

Student errors may be of different classes, representing fundamental differences
in the underlying cause for the error. Developing a psychological theory
for student errors will be an important step to truly effective modeling.
Criticisms of LMS :

Models produced are not psychological models of student learning. The model
may be suitable for simple algebra, but no theoretical basis can be made
that LMS can also be applied in other domains. Furthermore, though the
model is able to explain student behavior in algebra, it does not give
any indications as to why students make certain mistakes that others would
not.

Possibility of nonmonotonicity as the model is built incrementally. A
later rule may supercede a rule already present in the model. As a result
the system may not be able to explain student behavior earlier observed.

Large amounts of handcoded information required by system builder. In
addition to the basic rules, all associated malrules of the domain as
well as any problems used to distinguish between the various rules during
model building must also be encoded. This requires a great deal of anticipation
of the student’s behavior.
This technique does not appear suitable for this project. The project’s
domain has no algebraic roots, and it is uncertain if the technique can
perform correctly in a fuzzy environment. Because the domain is not as
predictable or consistent as in algebra, a more flexible model is required.
The inability of previous rules to be applied together with newer ones
seriously limits the pedagogical capabilities of this technique. The large
amount of data required should be minimized if at all possible.
2.2 BUGGY, DEBUGGY, and IDEBUGGY
BUGGY [9] was used to help arithmetic teachers recognize student bugs.
The program selects a bug, and asks teachers to provide it sample problems
to solve using the incorrect procedure. Teachers have to select problems
that isolate the error, tell the program when they think they have found
the bug, and then prove it by simulating the bug on several system generated
problems. DEBUGGY [3] reads student’s test answers and proposes bugs that
most likely caused the errors, while IDEBUGGY is the interactive form,
with the added capability of dynamically generating problems to help identify
students bugs.
The BUGGY model attempts to build a diagnostic model of the student,
by capturing an internalized set of incorrect instructions or rules capable
of duplicating student’s behavior. A successful diagnostic model can predict
not only which problems a student should get wrong, but exactly what the
wrong answer will be.
Contributions of BUGGY:

Irrefutable proof that students make systematic errors in multicolumn
subtraction, and usually incorrect procedures were the cause of error.
These identifiable misconceptions can be recognized and modeled.

BUGGY provides a detailed model of the subtraction procedure, revealing
that even simple procedures can be rather complex, and that students can
err in many ways. The skill lattice representing the possible correct and
buggy procedures of students was found useful in determining how effectively
a test measures each of the component subtraction skills.

DEBUGGY introduced a method for dealing with noise in student test data.
Occasional mistakes due to copying or number fact errors are reflected
as coercions and can be applied to problems, thus reducing problems arising
from random noise.
Criticisms of BUGGY:

Listed bugs tend to be superficial and many can be broken down as variants
of a few core bugs. The model can reproduce student mistakes, but cannot
explain why the mistakes were made.

The expert knowledge of the system encodes the necessary procedural knowledge
for subtraction, but is only a black box. It cannot be used to justify
nor explain the reasoning of the expert and students.

All system knowledge had to be handcoded. Manpower was required to determine
what bug or combination of bugs could account for answers given. New bugs
were then added to the system as they were found. There was no facility
to augment the system’s knowledge directly from each interaction.
The main problem with BUGGY is the inability of the system to reason why
student errors were made. The project requires a more intelligent expert
that can access occurrences of errors and differentiate between carelessness
and a partial or complete lack of understanding of the underlying concept,
and take appropriate actions to remedy the situation. The system knowledge
base data entry limitations are the same as LMS.
3 ConstraintBased Student Modeling
No perfect solution has been found and perhaps none should be expected.
The extent of false knowledge is so overwhelming that the problem of inferring
what the student "knows that is not so" is computationally intractable
in its general form and perhaps even conceptually incoherent. Instead of
a single general solution, there has been a slowly growing library of imperfect
but useful techniques. Each technique has a unique combination of advantages
and disadvantages. What is required is to match a suitable technique for
each pedagogical purpose.
The approaches to student modeling can be divided into three broad but
distinct groups of thought:

Bug Library technique Map the student’s solution onto a predefined library
of error types [4].

Machine Learning approach Search the procedure space for a fitting model
online [7].

Model Tracing technique follow the student step by step [1].
Two considerations have helped guide the present approach to student modeling:

The main purpose of student modeling in an ITS is to guide pedagogical
decision making. A description of the student’s knowledge is not necessary,
unless there is some way for the tutoring system to make use of or react
to it.

The abundance of false knowledge requires that abstractions be used to
reduce the scope. The numerous combinations hinder student modeling efforts
because most techniques deal with the specifics of student’s solution paths.
They also try to infer the particular mental process/strategy students
are employing. Current AI algorithms fall short of being able to perform
this complicated diagnostic task during ongoing interactions with students.
What is required is a type of description that can extract detail from
a student’s mental process while preserving pedagogically important properties
of the student’s current knowledge.
These two considerations imply that the student should be modeled in terms
of equivalence classes of solutions rather than specific solutions or strategies.
The members of a particular equivalence class are those learner states
that require the same instructional response. In short, student modeling
can be conceptualized as the problem of defining instructionally relevant
equivalence classes in a computationally tractable way.
The ConstraintBased approach to student modeling [6] suggests representing
subject matter knowledge in sets of constraints. A student violating one
of these constraints indicates incomplete or incorrect knowledge. These
violations can be used to guide an ITS in its response. This approach suggests
that runnable models of either the expert or the student may no longer
be needed. It also proposes that the computations required for student
modeling can be reduced to just simple pattern matching.
Constraintbased student modeling is based on the notion that students
can be described in terms of entities more abstract than particular solution
paths or strategies. Abstraction can be achieved in two ways:

Some problemsolving steps are highly diagnostic because they follow from
the fundamental ideas of the subject matter, while other steps are only
a mechanical function of the task and would thus provide less information.

The diagnostic information associated with a highly informative step may
not necessarily reside in the step, but can also be in the properties of
the problem state. Classes of problem states can therefore be defined by
expressing the fundamental ideas of a domain in terms of constraints on
correct problem states.
The constraintbased technique displays potential to significantly reduce
the effort required to implement an ITS [6]. Its advantages are:

There is no need to create a runnable expert (or ideal student) model.
Hence, large empirical studies of domain experts can be omitted (interviews
with experts may help identify key ideas in a domain).

There is no need to create a bug library. Although BUGGY showed that a
bug library had its merit, the constraintbased technique provides a much
cheaper alternative especially in computational overheads. There is no
need for sophisticated and computationally expensive AI inference mechanisms.
Constraints can be compared to problem states with pattern matching algorithms,
which can be easily implemented.

A constraintbased student model ignores the student’s problemsolving
strategy. This allows the flexibility to monitor free exploration, recognize
creative solutions as correct, and succeed in the face of various types
of inconsistency on the part of the student, including radical strategy
variability. These two features are not offered by any of the systems previously
studied.

The constraintbased technique is neutral with respect to pedagogy. A student
can be tutored after each constraint violation of after a sequence of them,
as seems most appropriate for the domain. A particularly useful feature
is the ability to adjust the pedagogical level of coaching. With this added
flexibility, the expert model can immediately step in and guide the student,
or the system can elect to offer only advice or hints, or to monitor for
a sequence of erroneous actions before taking corrective actions.
The potential disadvantages of the constraintbased technique are:

For some domains it might be impossible to identify properties of problem
states which are highly informative with respect to the student’s understanding.

The set of constraints might provide too loose a net, such that many incorrect
solutions slip through without violating any constraints. This might result
in underinstruction or failure to respond to errors made by students,
which may be misinterpreted by students as active endorsement by the system
for their solution.

The set of constraints might not provide the correct type of abstraction.
Thus there is a danger that student behaviors would not be divided into
pedagogically relevant equivalence classes.
To our knowledge the constraintbased student modeling technique was never
before implemented in an ITS. Therefore there is no evidence that the technique
can produce psychologically realistic or pedagogically useful student models
capable of guiding instruction. However, the offline diagnosis done by
Ohlsson has demonstrated its feasibility. Based on the diagnosis, this
technique is well suited with respect to the goals of the data structure
tutoring system.
How does the domain of data structures compare to fraction teaching
in mathematics and teaching of the Lewis structure in organic chemistry
as described in [6]. In both cases the student gets an exercise and tries
to solve it. Ohlsson claims that in these two particular cases, if the
student makes an error there is no need for an extensive bug library or
diagnosis system, as it is immediately clear what the student is doing.
See the following example (taken from [6]):
The first part of the equation is given by the tutor, and the numerator
of the solution is given by the student. Immediately it is clear what the
error of the student is.
Applying this to teaching of data structures, it was discovered that
this modeling technique is the best suited. Imagine that the students'
task is to learn how to delete the child node on the righthand side (node
9) from the given Binary Search Tree with node 7 as the root. The correct
sequence of actions would be as follows:

Move node 8 to the left subtree of node 12

Assign a Temp pointer to point to node 9

Reassign node 12 and all its Subtrees to the right subtree of node 7

Remove the Temp pointer or node 9
The steps are shown below in Figure 1(a)(d), with the resulting BST data
structure shown in Figure 1(e).
If the student did not have the fundamental understanding of the Binary
Search Tree (BST) and the principles behind operating on the structure,
a very predictable but erroneous first action of the student could be to
remove node 9 immediately (as in Figure 2(f)). However, if this course
of action is taken, all children associated to node 9 will also be lost.
This premature deletion violates the constraint of holding the children
of a node with a Temp pointer before deleting the node. Thus this action
will result in an incomplete BST structure. Further operations on this
resulting structure will no longer be correct or relevant
If this constraint had been properly identified and implemented in the
ITS, then it would be violated at this point, and the expert needs no further
actions or input from the student to recognize and react to the error.
The appropriate actions can be administered by the expert immediately to
explain and rectify the situation.
Figure 1: Removing a node from the Binary Search Tree correctly
(a)(e), incorrectly (f)
Two observations can be made from this example:

Some problem solving steps are more diagnostic than others, while some
others are more closely related to the conceptual rationale for the correct
solution. These two factors are interdependent. This is because highly
diagnostic steps become especially informative when they are closely related
to the conceptual rationale for the skill, and vice versa.

Pedagogically useful information does not reside in the sequence of
actions the student takes, but in the resulting problem state. A problem
state is diagnostically informative when it violates one or more of the
fundamental ideas or basic principles of the relevant domain.
These observations suggest that a tutoring system can extract the information
it needs from the student’s behavior by expressing the knowledge of the
domain as a set of constraints on correct solution paths and recording
when the student violates those constraints. Each constraint defines two
equivalence classes: solutions that violate the constraint and solutions
which do not. If the constraints are chosen to represent fundamental ideas
of the domain, then these two classes of situations require different tutorial
responses.
To implement this idea requires formal representation for constraints,
Ohlsson and Rees [8] introduced a representational format to this effect
called state constraints. Each state constraint is an ordered pair
< C_{r}, C_{s} >,
where C_{r} is the relevance condition, identifying the
class of problem states for which the constraint is relevant, and C_{s}
is the satisfaction condition, which identifies the class of (relevant)
states in which the constraint is satisfied. Each member of the pair can
be thought of as a conjunction of features or properties of a problem state.
The state constraints have to be evaluated with respect to the current
problem state. Hence, a student modeling system using this format requires
to have an internal representation of the current problem state. The system
must then update that representation appropriately as the student acts
on the problem. Although the actions themselves need not necessarily be
represented, their effect on the problem states must be. In the data structure
context, it is not important where in GUI space the node/s are drawn, but
information on how and to whom they are connected.
After encoding problem states and state constraints, the computations
required to test whether a given problem state is consistent with a particular
constraint set is trivial. All is required is any standard pattern matching
algorithm, such as a RETE network [5], to compare that state against all
constraints and notice any constraint violations.
A typical sequence of steps might be as follows:

The pattern matcher matches all the relevance patterns against the problem
state to identify those constraints that are relevant in that state.

The satisfaction patterns of the relevant constraints are matched against
the problem state. If one of the satisfaction pattern matches, then that
constraint is satisfied and the tutor need not take any action. If no match
is found, then the student has violated that constraint.
The output of such a computation would be the list of constraints that
the student has generated in a given problem state or throughout an entire
solution path. In other words, the student model will comprise the set
of constraints that the student has violated. This set of violated constraints
is an abstract specification of the student’s knowledge which is precise
enough to guide instruction and yet also computationally tractable. Thus,
the constraintbased modeling technique promises to be able to provide
an appealing and refreshing solution to the student modeling paradigm,
of attempting to describe "what the student knows that is not so"
in a compact way.
5 Conclusion
The approach of constrainedbased student modeling was proven to be
successful for an Intelligent Tutoring System on data Structures. The computational
overhead that was previously needed in other ITS was greatly reduced this
way. Instead of providing an extensive bug list or diagnosis model, a more
simple constrainedbased error list is needed. In combination with a sophisticated
tutoring method such as socratic dialogue [11] the system will serve as
an intelligent interactive tutoring system during laboratory sessions.
References
[1] Anderson, J. R., Boyle, C. F., Corbett, A. T., and
Lewis, M. W.: "Cognitive modeling and intelligent tutoring". Artificial
Intelligence 42, 1990, (pp. 749).
[2] Brown, J. S., R. Burton, M. Miller, J. DeKleer, S.
Purcell, C. Hauseman and R. Bobrow: Steps towards a Theoretical Foundation
for Complex, KnowledgeBased CAI. Technical Report 3135, 1975, Cambridge,
MA: Bolt, Beranek and Newman.
[3] Brown, J. S. and R. R. Burton: "Diagnostic Models
for Procedural Bugs in Basic Mathematical Skills". Cognitive Science 2,
1978, (pp. 155192).
[4] Burton, R.: "Diagnosing bugs in a simple procedural
skill" in D. H. Sleeman and J. S. Brown (eds.): Intelligent Tutoring Systems,
pp.17183) , 1982, New York: Academic Press.
[5] Forgy, C. L.: "Rete: A fast algorithm for the many
pattern/many object pattern match problem". Artificial Intelligence 19,
1982, (pp. 1737).
[6] Ohlsson, S.: "ConstraintBased Student Modeling".
Journal of Artificial Intelligence in Education 3(4) , 1992, (pp. 429447).
[7] Ohlsson, S., and Langley, P.: "Psychological evaluation
of path hypotheses in cognitive diagnosis" in Mandl H. and Lesgold A. (eds.):
Learning issues for intelligent tutoring systems. (pp. 4262) , 1988, New
York: SpringerVerlag.
[8] Ohlsson, S., and Rees, E.: "The function of conceptual
understanding in the learning of arithmetic procedures". Cognition &
Instruction 8, 1991, (pp. 103179).
[9] Sacerdoti, E.: A Structure for Plans and Behavior,
Amsterdam: NorthHolland, 1977.
[10] Sleeman, D. H. and M. J. Smith: "Modeling Student’s
Problem Solving". Artificial Intelligence 16, 1981, (pp. 171187).
[11] Stevens, A. L. and Collins, A.: "The goal structure
of a socratic tutor". Proceedings of the National ACM Conference, Seattle,
Washington, (pp. 256263), 1977. New York: Association for Computing Machinery.
[12] Warendorf, K.: Combining interactive multimedia and
inquiry teaching to build an intelligent multimedia tutoring system, Proceedings
of EDMEDIA 96, 1996, Boston, Pg. 814.