Constraint-Based 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 #2a-36
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 on-screen 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 constrained-based 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 constrained-based 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 "self-adaptive" - able to adapt tutoring sessions based on self-contained 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:

  1. contain the search required in creating a student model, and
  2. have the modeler behave in a data directed manner.
Contributions of LMS :
  1. It is possible to constrain the search space in constructing a model such that the search technique is computationally feasible.
  2. A data-driven 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 ill-defined domains.
  3. 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 :
  1. 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.
  2. Possibility of non-monotonicity 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.
  3. Large amounts of hand-coded information required by system builder. In addition to the basic rules, all associated mal-rules 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:

  1. Irrefutable proof that students make systematic errors in multi-column subtraction, and usually incorrect procedures were the cause of error. These identifiable misconceptions can be recognized and modeled.
  2. 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.
  3. 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:
  1. 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.
  2. 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.
  3. All system knowledge had to be hand-coded. 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 Constraint-Based 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:

  1. Bug Library technique Map the studentís solution onto a predefined library of error types [4].
  2. Machine Learning approach Search the procedure space for a fitting model on-line [7].
  3. Model Tracing technique follow the student step by step [1].
Two considerations have helped guide the present approach to student modeling:
  1. 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.
  2. 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 Constraint-Based 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.

Constraint-based 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:

  1. Some problem-solving 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.
  2. 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 constraint-based technique displays potential to significantly reduce the effort required to implement an ITS [6]. Its advantages are:
  1. 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).
  2. There is no need to create a bug library. Although BUGGY showed that a bug library had its merit, the constraint-based 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.
  3. A constraint-based student model ignores the studentís problem-solving 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.
  4. The constraint-based 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 constraint-based technique are:
  1. For some domains it might be impossible to identify properties of problem states which are highly informative with respect to the studentís understanding.
  2. 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 under-instruction or failure to respond to errors made by students, which may be misinterpreted by students as active endorsement by the system for their solution.
  3. 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 constraint-based 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 off-line 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 right-hand side (node 9) from the given Binary Search Tree with node 7 as the root. The correct sequence of actions would be as follows:

  1. Move node 8 to the left sub-tree of node 12
  2. Assign a Temp pointer to point to node 9
  3. Reassign node 12 and all its Sub-trees to the right sub-tree of node 7
  4. 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:
  1. 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.
  2. 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

< Cr, Cs >, where Cr is the relevance condition, identifying the class of problem states for which the constraint is relevant, and Cs 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:

  1. The pattern matcher matches all the relevance patterns against the problem state to identify those constraints that are relevant in that state.
  2. 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 constraint-based 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 constrained-based 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 constrained-based 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. 7-49).

[2] Brown, J. S., R. Burton, M. Miller, J. DeKleer, S. Purcell, C. Hauseman and R. Bobrow: Steps towards a Theoretical Foundation for Complex, Knowledge-Based 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. 155-192).

[4] Burton, R.: "Diagnosing bugs in a simple procedural skill" in D. H. Sleeman and J. S. Brown (eds.): Intelligent Tutoring Systems, pp.17-183) , 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. 17-37).

[6] Ohlsson, S.: "Constraint-Based Student Modeling". Journal of Artificial Intelligence in Education 3(4) , 1992, (pp. 429-447).

[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. 42-62) , 1988, New York: Springer-Verlag.

[8] Ohlsson, S., and Rees, E.: "The function of conceptual understanding in the learning of arithmetic procedures". Cognition & Instruction 8, 1991, (pp. 103-179).

[9] Sacerdoti, E.: A Structure for Plans and Behavior, Amsterdam: North-Holland, 1977.

[10] Sleeman, D. H. and M. J. Smith: "Modeling Studentís Problem Solving". Artificial Intelligence 16, 1981, (pp. 171-187).

[11] Stevens, A. L. and Collins, A.: "The goal structure of a socratic tutor". Proceedings of the National ACM Conference, Seattle, Washington, (pp. 256-263), 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 ED-MEDIA 96, 1996, Boston, Pg. 814.