Summary For Mitrovic Ohlsson 99

The key difficulty is that the formal knowledge representations that intelligent tutoring system (ITS) researchers have inherited from the field of artificail intelligence demand overly detailed and specific models of the student knowledge. If the student model is to be executable, these knowledge elements have to be as specific as program code. This level of specificity cannot be attained. It is impossible to know in such detail exactly what is in a student's head on the basis of in-depth interviews. The purpose of constraint-based modeling (CBM) is to overcome the overspecificity problem via abstraction (Ohlsson 92). THe key idea is that knowledge about a domain can be reprsented by constraints on correct solutions in tha domain. Each constraint indirectly represents a set of erroneous solutions, namely all solutions that violate that constraint. An expert model consists of a set of constraints that partitions problem solutions into acceptable and unacceptable in the same way as an expert. A student model consists of the set of constraints that he or she does and does not violate.

Constraint-Based Modeling

• A formalism for constraints: Ohlsson and Rees (1991) introduced a formal notation for constraints. The unit knowledge is called a state constraint. Each state constraint is an ordered pair <Cr,Cs>, where Cr, the relevance condition, identifies the class of problem states for which the constraint is relevant, and Cs, the satisfaction condition, identifies the class of relevant states in which the constraint is satisfied. The computations required to test whether a given problem state is consistent with a set of constraints are straightforward: Compare the state against all constraints and notice any constraint violations. This is a two step process.. In a first step, all the relevance patterns are tested against the problem state to identify those constraints that are relevant n that state. In a second step, the satisfaction patterns of the relevant constraints are tested against the problem state.

• Instructional Application: The state constraint approach circumvents the overspecificity problem by providing two pedagogically relevant forms of abstraction. First, a constraint base enables selective evaluation of problem solving steps. Not all problem solving steps are equally informative or important in diagnosing a student's knowledge. No additional mechanism needs to be implemented to allow a constraint-based system to ignore pedagogically uninformative steps. If the step does not evoke any constraint, then the step is de facto ignored. Constraints can be written so as to react only to problem states that do contain pedagogically significant information about learner (Ohlsson 1992). Second, a constraint base circumvents the overspecificity problem by allowing an instructional system to operate with classes of pedagogically equivalent solution paths. The basic purpose of an instructional system is to map student performances onto instructional actions (e.g., typing out a particular instructional message). Hence, the system neeeds to groupstudent solutions into classes of solutions that require the same instructional response from the system. A constraint C implicitly defines a bundle of solution paths, namely all paths that pass through some problem state that violates C. If C is a pedagogically motivated constraint, all those paths should require the same instructional response.
• Discussion
  • Distinction between generative and evaluative knowledge (Norman 1981, Ohlsson 1996a). The function of generative knowledge (e.g rule set) is to produce actions vis-avis the current problem and the function of evaluative knowledge (a set of constraint) is to evaluate action outcomes as desirable or undesirable. This distinction suggests that the acquisition of a new cognitive skill consists, in part, of the transfer of knowledge from the evaluative to the generative component. (Ohlsson 1993, 1996a).
  • Constraint-based modeling does not, in principle, require an ideal solution. However, in the SQL domain, such solutions were readily available and they allowed us to formulate certain constraints, particularly semantic constraints, which would have been much more difficult to formulate if the system had not had access to ideal solutions.
  • The incomplete and fuzzy information available to an instrucxtional computer system connot support detailed and precise inferences about the student's cognitive strategy. In contrast, the state constraint representation is not designe to encode executable programs. A state constraint is a piece of evaluative knowledge. It is a tool for passing judgment, not for computing new results or inferring new conclusions.
  • *Relations to Alternative Approaches: * Beacuse each constraint encodes piece of correct knowledge, a constraint base is not a bug library. A set of constraints nevertheless supports come of the functions of a bug library. A constraint violation provides the same information as a positive match between a theoretical bug description and a student behavior.
  • Yet another strenght of CBM is that it can regnize a correct solution, submitted by the student, even if that solution is different from the ideal solution.If no constraint is violated, then the student's solution is correct with repsect to the notion of correctness embodied in the constraint base.
  • 4 potential limitaitons and problems (Ohlsson 1992)
    • It is notcertain that pedagogically appropriate constraints can be identified in each and every domain: no probelm for arithmetic and chemistry, SQL.
    • even if appropriate constraints can be found, they might provide too loose a net so that too many student errors go unnoticed by the tutor: SQL-Tutor deals with all types of pedagogical situation encountered to date in the database query domain. SQL-tutor does, in fact, select appropriate problems and generate appropriate feedback messages.
    • CBM is limited to domains in which the purpose of student modeling is to judge the correctness of successive problem solving steps (Ohlsson 1992): SQL-Tutor proved that constraint-based diagnosis on final solutions will work in any domain in which those solutions have a rich internal structure.
    • The aquisition of constraints might turn out to be no easier than the acquisition of expert rules or bug libraries: ech constraint in SQL-Tutor required an average of 1.1 hours of work, a significant saving. This may be a consequence of the fact that the same person served as both domain expert, knowledge engineer and the system developer, but may also be due to the appropriateness of the state constraint formalism.

• Knowledge Base Two types of constraints: Constraints of the first type represent syntactic properties of queries. They refer only to the student's solution. Constraints of the second type represent semantic properties of queries. They operate on the relation between the student#s solution and the ideal solution.

• Student Modeler When SQL-tutor is initialized, the constraints are compiled into two structures, called the relevance and satisfaction networks, which resemble RETE networks (mitrovic1997). There are three types of nodes in these structures: input, test and output nodes. The difference to RETE networks is that test nodes have a single inout each, so the structures are trees, not unrestricted networks. Constraint violations are identified by inspecting the student's solution and by comparing it to the stored ideal solution. This is a two-step process:
  • In the first step, the student's solution and the corresponding ideal solution are propagated through the relevance network. The result is a list of constriants the relevance conditions of which match the current situation.
  • In the second step, the satisfaction components of constraints whose relevance conditions match the current situation are compared to the current problem state. That is, the student's solution and the idela solution are propagated through the satisfaction network. If the constraint is vioalted, this outcome is recorded. The student model consists of the list of vioalted constraints. The student modeler records the history of each constraint. This record contains information about how often the constraint was relevant for the ideal solution to the practice problems the student attempted, how often it was relevant for the student's solution and how often it was satisfied or vioalted. This information is accumulated in nthree indicators, called relevant, used, correct. This record is used by the pedagogical module.

• Pedagogical Module A student's solution to a query problem can violate several constraints. In such cases, SQL-Tutor examines all vioalted constraints and targets one of them for instruction. SQL-tutor consults the history of each vioalted constraint and selects the constraint with the largest number of violations, computed as the difference between the used and correct indicators. The rationale for this rule is that if the student has violated the same constraint several times, then it is appropriate to target that constraint for instruction.

-- LeNguyenThinh -- 29 Dec 2004