The Use of Explanation-Based Learning for Modeling Student Behavior in Foreign Language Tutoring

Carlo Tasso 1, Danilo Fum 2, and Paolo Giangrandi 1

1 Laboratorio di Intelligenza Artificiale - Dipartimento di Matematica e Informatica - Università di Udine, via Zanon 6, I-33100 Udine (Italy) - tasso@uduniv.infn.it.bitnet

2 Dipartimento di Psicologia - Università di Trieste, via dell'Università 7, I-34123 Trieste (Italy) - fum@uts882.units.infn.it.bitnet

Abstract: An original methodology to model student performance which features a profitable integration of the bug collection and bug construction techniques is presented. This methodology has been used for building the modelling module of a new version of ET (English Tutor), an ITS aimed at supporting the learning of the English verb system. The proposed approach is based on the idea of analyzing the reasoning process of the student by reconstructing, step by step and in reverse order, the chain of reasoning (s)he has followed in giving his/her answer. Two kinds of errors, i.e., commission and omission errors, are considered by the the modeler and the student modelling process is supported by correct domain specific knowledge and by a catalogue of stereotyped errors (mal-rules). When the system is unable to explain the student behavior by exploiting its previous knowledge, new mal-rules are generated dynamically by utilizing explanation-based learning techniques. The overall process is based on a deep modelling of the student problem solving and the discrimination among possible explicative hypotheses about the student behavior is carried on non monotonically through a truth maintenance system. The proposed approach has been fully implemented in a student modelling module developed in PROLOG.

Keywords: intelligent tutoring systems, foreign language teaching, student modeling, explanation-based learning.

1. Introduction

One of the most important features an intelligent tutoring system (ITS) should provide is the capability to adapt instruction to the specific traits of the student. To this end, a fundamental contribution is given by the ITS component aimed at building and maintaining the student model. The student model describes the knowledge and beliefs of the student in the specific subject domain and is used for designing and taking appropriate tutorial and remedial actions tailored to the peculiarities of the student.

Building an ITS with a student modelling component is hindered by several problems concerning both theoretical and practical issues. There is a sufficiently general agreement for the fact that the modelling activity cannot be based only on the knowledge provided by an expert in the domain but it is better performed by relying on an explicit description of possible student (mis)behaviors [5]. Unfortunately, no definite solution exists for this issue and the three main approaches adopted for building student modelers (i.e., overlay, bug collection and bug construction [17]) directly reflect this situation. In fact, each technique has been generally used alone and no clear methods have been proposed to combine these techniques in order to exploit their respective advantages. Considered individually, each technique has known drawbacks and falls short of constituting an ideal tool for building cognitively adequate and computationally sufficient student models. Overlay is generally considered as not sufficiently powerful to perform sophisticated modelling, collecting catalogues of bugs is notoriously a dull and labor-intensive endeavor, while bug construction has not yet proven to be a reliable and sufficiently comprehensive approach.

In this paper we present an original methodology, called backward model tracing, to model student performance which features a profitable integration of the bug collection and bug construction techniques. The work has been carried on in the framework of a research project devoted to the development of ET (English Tutor) [10], an ITS aimed at supporting the learning of the English verb system. The new methodology has been used for building a new version of the modelling module [12]. Backward model tracing is based on the idea of analyzing the reasoning process of the student by reconstructing, step by step and in reverse order, the chain of reasoning (s)he has followed in giving his/her answer. In order to do this, both correct domain specific knowledge and a catalogue of stereotyped errors (mal-rules) is utilized. When the system is unable to explain the student behavior by exploiting its previous knowledge, new mal-rules are generated dynamically by utilizing explanation-based learning techniques. The overall process is based on a deep modelling of student problem solving and the discrimination among possible explicative hypotheses about the reasons underlying the student behavior is carried on non monotonically through a truth maintenance system.

Backward model tracing seems a promising approach to tackle the hard problem of student modelling [15] for the following reasons:

- it shares the benefits of the model tracing methodology [1];

- it exploits the respective advantages of bug collection and bug construction without the limitation of the exclusive usage of a single technique;

- it exploits a sophisticated technique, i.e., explanation-based learning, to push the limits of the bug construction methodology.

The paper is organized as follows: The following section briefly presents the ET system where backward model tracing has been applied. Section 3 illustrates the general criteria upon which the methodology is grounded. Section 4 and 5 describe the modelling process focusing on its basic features, the architecture of the Modeler, and its overall operation. Section 6 presents a fully worked out example and section 7 concludes the paper. An Appendix illustrates the different kinds of knowledge utilized in the example.

2. Second Language Tutoring in ET

The backward model tracing methodology has been utilized in the new version of the ET system, an ITS aimed at supporting Italian students in the learning of the English verb tenses. ET comprises a Verb Generation Expert, an articulated knowledge-based domain expert [11] devoted to tense generation and capable of solving fill-in exercises constituted by one or more sentences in which some verbs have to be conjugated into the appropriate tenses. The operation of the domain expert is organized around a sequence of five phases each devoted to a specific subtask, namely:

- parsing the exercise sentence(s);

- recognizing the temporal relations among the events described in the sentence(s);

- identifying the reference time for every clause in the sentence(s);

- selecting the correct tense to be used for each verb;

- conjugating the verb(s) into the appropriate tense.

Each process is carried out by a dedicated processor, which is supported by a knowledge base representing the knowledge usually exploited by humans for that subtask. The main representation paradigm utilized in the knowledge bases is constituted by production rules. The Verb Generation Expert also produces a precise trace of the reasoning performed and of the knowledge utilized for solving the exercises.

The second fundamental module of ET is the Tutor which is devoted to defining the modalities of the teaching activity. More particularly, the Tutor assigns the exercises according to a given syllabus, manages the dialogue with the student, and cooperates with the Modeler in order to discriminate among alternative hypotheses about the student behavior (see the section on Tutoring Strategies and Learner Control, this volume, for more detailed information on this aspect of ITSs).

The Student Modeler (or simply the Modeler) is the module which implements the backward model tracing methodology. The general goal of this module is to discover the domain specific knowledge the student has utilized in order to derive her/his answer(s). The modelling process aims at constructing a model of the student's beliefs in which both correct knowledge and misconceptions are explicitly represented. The student model, which is partitioned into different parts, one for each computational phase, contains, therefore, a collection of facts and rules that have been utilized in order to interpret the student behavior and that are supposed to mirror what the student knows/believes about the subject domain. The student model supplies the basis for remedial activity which is aimed at correcting the student misconceptions.

The structure and the functioning of the Student Modeler constitutes the subject of this paper. More precisely, we will introduce in section 3 the general methodology of backward model tracing and then, in the following sections, we will focus on the mechanisms utilized in the modeling process devoted to reconstructing the student reasoning within a single phase (subtask) of the tense generation process.

3. Backward Model Tracing: A General Strategy for Modelling Student Performance

Backward model tracing relies on two basic assumptions:

(i) in achieving the solution, the student follows a process akin to that used by the Verb Generation Expert module i.e., it goes through the same phases and performs essentially the same kind of computations, and

(ii) the student mistakes can be modelled by appropriately perturbing the knowledge utilized by the Verb Generation Expert module.

Some words are needed in order to justify these assumptions. It could be claimed that assumption (i) is unrealistic. In fact, it is easy to find evidence that novices solve problems by using strategies that are different from those utilized by experts (see for example [8, 14]). While this cannot be denied, it is also true that, in order to be able to model possible student misbehaviors, a model of the correct performance is required. The student behavior needs thus to be compared with that of an 'expert', being this a real domain expert, a teacher or an 'ideal student' [1]. The general philosophy followed in ITS development is to locate the relevant domain knowledge in the Domain Expert module which plays therefore a twofold role: it acts as the source for the knowledge to be presented and, at the same time, it serves as the standard for evaluating the student's performance [17]. In our context we assume that a student, trying to figure out the correct answer for an exercise, follows the same reasoning steps of the expert module, i.e., after interpreting the meaning of the exercise sentences (s)he computes the temporal relations between the states/events described in the sentence, calculates the reference times for every clause of the sentence, chooses the tense for the verb and, finally, conjugates the verb in that tense. Assumption (i) implies that the errors the student makes could derive only from the fact that some of the rules (s)he applies are 'bugged', not from the fact that (s)he can follow computational paths different from those of the expert. Assumption (ii), (shared by other authors [3, 4, 16]) states that it is possible to model these bugs by assuming more or less severe deviations from the knowledge base actually represented in the expert module.

Backward model tracing is grounded on the idea of trying to reconstruct, step by step and in reverse order, the chain of reasoning the student has followed in building the answer. Backward model tracing is triggered by the discovery of a mismatch between the answer given by the student and that provided by the expert module. The goal of the modelling process is to identify the phase(s) where the reasoning process of the student and of the expert differ, and the specific erroneous rules (mal-rules) applied by the student (see [5] for a method of describing learners' mal-rules). Backward model tracing analyzes the reasoning process performed by the student starting from the last phase and going back toward the first ones. For each phase, the Modeler tries to determine the input to the phase and the knowledge the student has utilized in order to produce the corresponding output. If a mismatch between the student and the expert output is discovered, it could mean that:

(a) some of the rules contained in the knowledge base utilized by the student in that phase, or

(b) some of the data utilized as input for that phase or,

(c) both some of the rules and the data

differ from those utilized by the expert.

The goal of the diagnostic process performed by the Modeler is to realize which of the above alternatives holds. Case (a) is true when both the expert and the student work with the same input data but their output is different because some of the rules contained in the student knowledge base are actually bugged. In this case a remedial activity could be planned in order to clarify the student misconceptions. As an example of case (a) let us consider the case when both the student and the expert have to form the present perfect of to study and the student produces as an answer has studied. If (b) is true, then at least one of the previous phases should be blamed for producing the erroneous data and the diagnostic process is repeated focusing on the phase immediately preceding the current one. As an example of (b) let us consider the case of the student answering has studied when in fact the correct verb tense is the past perfect. If (c) is true, then both the above mentioned activities should occur, i.e., the mal-rules responsible for the mistake made in that phase have to be identified and the diagnostic process will continue with the preceding phases. An example of case (c) is the wrong answer has studyed when the past perfect is required.

Backward model tracing shares all the features of the model tracing methodology [1], i.e., it tries to simulate dynamically a student's problem solving and uses that simulation to interpret the student behavior. Differently from Anderson's approach [1]:

- it does not rely only on an a priori established catalogue of correct and incorrect productions but is able to dynamically generate the mal-rules necessary to explain the student performance;

- the tracing occurs after the student has produced his/her performance and it is not used to monitor the student during the solution process just to assure that the correct path will be followed.

As a result, backward model tracing possibly represents a less intrusive modelling methodology and a more general diagnostic procedure.

Having established the general features of our approach to student modelling, we concentrate now on the technical details of the diagnostic process as it is performed within a single phase.

4. Reconstructing the Student Reasoning within a Single Phase of the Tense Generation Task

The process of modelling the student reasoning within a single phase is aimed at discovering the status of the student knowledge utilized in that specific phase of the tense generation task. The approach utilized is the same for each phase, so we will concentrate on a single, generic one. During the diagnostic process, the Modeler interacts with the student and collects information which is utilized to analyze his/her behavior. The status of student knowledge is represented in the Student Model, a dynamically updated information structure which stores the knowledge which can be reasonably considered as present in the student mind, given the results obtained from the analysis of the observed behavior.

An important feature of our approach concerns the method adopted for evaluating the student performance. At each step of the interaction, the observed student behavior is not compared simply with an 'ideal' behavior (like that which could be obtained by utilizing only the correct expert knowledge), but with an 'expected' behavior. By this we mean the behavior which the student should manifest provided (s)he would reason according to the knowledge present in the Student Model. The expected behavior is computed by means of a simulation of the reasoning processes carried out by the student, and this is accomplished by taking into account the knowledge contained in the Student Model. From this perspective, therefore, the Student Model not only serves as a repository of the current representation of the student knowledge, but it also plays a fundamental role in the simulation of the student.

The main task performed by the Modeler is error analysis. When the student behavior differs from the expected behavior a twofold problem arises. On one hand, the student has made some mistake and this fact means (s)he has applied some kind of incorrect knowledge (this error is called commission error). On the other hand, the student has not performed in the expected way because (s)he has ignored some knowledge and possibly replaced it with some other knowledge (this error is called omission error). The operation of the Modeler reflects this twofold problem. In fact, the Modeler proceeds during its analysis in two different directions. First, it analyzes the student behavior and tries to reconstruct the student reasoning (the so-called commission error analysis). Second, it analyzes the expected answer and tries to identify which knowledge has been ignored by the student (the so-called omission error analysis). Due to this twofold nature of errors, the knowledge contained in the Student Model appears in two different modalities. The first modality is suitable for encoding the fact that the student believes (correctly or incorrectly) something, i.e., there is evidence that (s)he has utilized it during an interaction. This knowledge is labelled as applied. The second modality is used for keeping an account of the pieces of information which are not known by the student. This knowledge is labelled as missing.

After each interaction with the student, the Modeler produces two kinds of results. The first concerns new information (applied and/or missing) that has to be inserted into the Student Model. This situation arises whenever the new information adequately justifies and explains the current interaction, and it is also consistent with conclusions drawn from the previously observed behavior. A second possible outcome is constituted only by hypothetical results, which are not inserted into the Student Model and which need further observations in order to be accepted or rejected. This second case arises when the Modeler produces multiple mutually exclusive hypotheses, or hypotheses which contradict previous conclusions.

It might happen that the Student Model, being incomplete, could not give a precise account of the observed behavior since on some specific aspects only preliminary hypotheses have been made which have yet to be validated. Due to this incompleteness, during the analysis of the student behavior or during the simulation of the expected behavior, whenever the need arises to consider aspects of domain knowledge not present in the Student Model, the Modeler has to find this knowledge somewhere else. The precise strategy utilized is the following: First the Modeler tries to refer to the correct expert knowledge. If this fails, it looks in a bug library of stereotyped mal-rules, and if this also fails, it generates at run time new mal-rules that adequately explain the behavior. This means that the Modeler first assumes that the student knows what (s)he should know, and only later hypothesizes some misconception. A consequence of this approach is that, at the beginning of the interaction when the Student Model is still empty, the first assumption made by the Modeler is that the student behaves correctly as an 'ideal' student. Only later, when the Modeler detects some misconceptions in the student knowledge, the expected behavior is found to differ from the ideal behavior by taking into account the specific individualities of the student.

The mal-rule generation (or bug construction) process is based on machine learning techniques and on general diagnostic knowledge about possible perturbations of correct knowledge which may occur in the learning process of a student. Among the possible machine learning techniques usable for generating new mal-rules, we have adopted an explanation-based approach [7, 13]. This approach, which has been already exploited in the field of ITSs [2], seems particularly promising to be utilized for student modelling for the following reasons:

- in contrast to other machine learning techniques, this approach requires a few training instances (possibly only one) and seems therefore particularly suitable for modelling when only a few student answers are available;

- it is an intensive knowledge-based technique and seems suitable in a field where a lot of domain-dependent knowledge is available in terms of both the expert knowledge base and of diagnostic knowledge (i.e., knowledge about possible student errors).

Bug construction thus constitutes the major tool in the Modeler when no a priori information about a specific student (mis)behavior is available, i.e., when a student makes an error not contained in the bug library.

Another major characteristic of the Modeler is its ability to deal non-monotonically with the incremental development and refinement of the Student Model. Since at each step of the interaction a better understanding of the status of student knowledge is reached and new hypotheses are made in order to further refine it, continuous updates (both insertions and deletions) are performed on the Student Model. A truth maintenance system [9] is specifically devoted to manage this process.

Before describing the architecture and the overall operation of the Modeler we point out that the kind of interactions considered in the current versions of the ET system is restricted only to exercises proposed by the system to the student. We are planning to extend this capability to other kinds of interaction modes such as direct questioning from the system about specific aspects of the student's reasoning process or the provision of interactive graphical ways to represent and manipulate information related to the student's reasoning process.

5. Modeler Architecture and Overall Operation

In this section we illustrate the main modules of the Modeler and we describe its overall operation. The Modeler, whose overall architecture is illustrated in figure 1, is made up of three main modules:

- the Commission Error Analyzer, devoted to analyze the answer produced by the student and to produce hypothetical explanations of his/her reasoning. These explanations are represented in the form of derivation trees which contain reference to knowledge present in the Student Model or to correct domain knowledge or to diagnostic knowledge (i.e. stereotyped mal-rules or newly generated mal-rules).

- the Omission Error Analyzer, devoted to identifying possible hypotheses of omission errors in the student reasoning by considering the expected behavior of the student. The expected behavior, in the current version of the system, is constituted only by an expected answer to the current exercise. The process devoted to simulating the student reasoning and to identifying the expected answer is performed by utilizing the same inference engine of the Verb Generation Expert and the current Student Model as the knowledge base;

- the Hypotheses Discriminator, devoted to evaluating all the hypotheses produced by the above two modules and to identifying the specific update operations to be performed on the Student Model. This module operates only on the so called active hypotheses, i.e., hypotheses which have not yet been either confirmed or disproved. In general, after its activity is completed, some hypotheses may possibly remain active, since the Hypotheses Discriminator may not have been capable of confirming or disproving them. Therefore, other interactions with the student will be needed in order to gather new observations related to these hypotheses.

The above mentioned modules are supported by the following three knowledge bases:

- the Domain Knowledge Base, which contains the correct knowledge necessary for solving the task corresponding to the specific phase at hand;

- the Stereotyped Mal-Rule Catalogue, which includes specific stereotyped mal-rules identified a priori through the analysis of protocols taken from students working in the domain of interest;

- the Meta-Bug Library, which includes generic perturbation patterns called meta-bugs describing generic ways of altering correct knowledge, and producing in such a way possible student misconceptions. Meta-bugs are identified a priori through the analysis of protocols taken from students working in the domain of interest.

The modeling process is also supported by the Exercise Data Base, i.e., a collection of exercises in the domain at hand, and the Syllabus, i.e., an organized collection of the specific topics included in the domain. The overall operation of the Modeler conforms to the general iterative procedure shown in figure 2. At the beginning of each cycle an exercise is selected in order to be presented to the student. The choice is performed by the Tutor. If there are still active hypotheses from the preceding cycle, the exercise is chosen in order to support the Modeler in its operation. Otherwise the Tutor selects an exercise according to the Syllabus.

After the student answer has been acquired, the Modeler carries out a simulation of the student's expected reasoning and identifies the expected answer. A comparison of the actual and the expected answer allows an evaluation of the student behavior. If the two answers are equal, the Modeler assumes that the student has applied the same knowledge utilized in the simulation process and this constitutes a useful piece of information for discriminating among possible hypotheses still active from preceding cycles. On the other hand, if the two answers are different, the Modeler executes the two analyses of commission and omission errors, which will eventually produce new hypotheses about the student knowledge. In both cases, the Modeler will then discriminate among the different active hypotheses with the aim of confirming or disproving them, and then execute the corresponding update operations on the Student Model.

At the end of the cycle, if no more hypotheses are active, the Modeler terminates the specific diagnostic activity and all the conclusions produced about the student knowledge are usable by other modules (such as the Tutor) for specific remediation activities. If there are still active hypotheses, the cycle starts again.

Start-cycle

Select exercise

Assign exercise to the student

Get student answer

Simulate student expected reasoning and Identify expected answer

IF student answer = expected answer

THEN assume student has applied the same knowledge of the simulation process

ELSE begin

activate Analysis of Commission Errors

activate Analysis of Omission Errors

end

activate Hypotheses Discriminator and update Student Model

IF no more active hypotheses

THEN terminate diagnosis session

End-cycle

In the next section we will further clarify our approach by means of an example which will also allow us to point out more specific details of the modeling process.

6. An Example

In this section we present an example of interaction with the ET system. We will consider only the last phase of the tense generation process, i.e., verb conjugation. More precisely, we will utilize the conjugation exercises and show how the Modeler is able to diagnose the status of student knowledge with reference to this task. The domain knowledge includes conjugation rules (represented as productions) and a dictionary of English verbs. Diagnostic knowledge is comprized of both stereotyped mal-rules and meta-bugs which have been collected from an analysis of protocols taken from Italian students.

At the beginning of the interaction the Tutor selects an exercise according to the Syllabus and assigns it to the student:

ex1: Please conjugate the present perfect, third person singular, of the verb to go.

Let us assume that the student gives the incorrect answer is gone. Since we are at the beginning of the interaction, the Student Model is still empty and the simulation process is performed taking into account the correct conjugation rules. The expected answer therefore coincides with the correct answer, i.e., has gone. Since the expected and actual behavior are different, the Modeler carries out an analysis of the exercise following the three standard steps: commission error analysis, omission error analysis, and discrimination of the hypotheses.

As the system is implemented in PROLOG, we will utilize a PROLOG-like notation for describing the knowledge and the data utilized in this example (the minus sign meaning difference list). All the knowledge utilized in the example is reported in the Appendix.

6.1 Commission error analysis

In order to analyze the student answer, the Modeler transforms it into the PROLOG goal

conjugate(go, present_perfect, 3, singular, [is, gone]-[]).

This goal embodies information concerning the kind of task to be performed (verb conjugation), the input data (verb root, tense, person, and number) and, finally, the answer given by the student (is gone in our example). The Modeler starts to build the derivation tree(s) for the above goal. To this end, the system searches in the Student Model for those rules whose right hand side matches the current goal (if various rules match the goal, the Modeler constructs several derivation trees in parallel). Since the Student Model is still empty, the Modeler looks for appropriate rules in the knowledge base of correct conjugation rules. When a rule is found, the process continues by proving each antecedent clause in the left hand side of the rule. If a clause constitutes a primitive goal (i.e., a fact contained in the Dictionary or an elementary operation, e.g., string concatenation) it is directly solved by looking in the Dictionary or by executing the elementary operation; otherwise the Modeler proceeds recursively by trying to build a derivation (sub)tree for that clause. When a clause has been solved, the Modeler goes on with a new one until all the clauses have been analyzed.

The main improvement of our algorithm in comparison with similar approaches (e.g., classic backward chaining, the resolution plus oracle method reported in [6], and the technique utilized in [16]) concerns the treatment of failing situations. When the Modeler finds a subgoal which is unprovable (i.e., which is neither a primitive goal nor can be solved by utilizing the rules contained in the Student Model or in the base of correct knowledge) it tries to recover from this situation by exploiting two different modelling strategies. First, it can resort on the bug collection by selecting an appropriate mal-rule in the Stereotyped Mal-rules Catalogue which could be used to prove the current goal. If none of the available mal-rules is suitable to prove the goal, the Modeler follows a bug construction strategy and tries to generate a new mal-rule by perturbing an expert rule in accordance to some generic perturbation pattern specified in a meta-bug. While the first strategy simply utilizes the classic bug collection approach, the second strategy exploits explanation-based learning in order to generate new mal-rules. Meta-bugs are represented by productions whose condition specifies a failing situation (a general pattern for a clause which cannot be otherwise proven) and whose conclusion specifies an action to perturb the given clause.

Coming back to the example, when the Modeler tries to account for the incorrect use of the auxiliary verb is, it fails to explain it and thus attempts to recover from this situation by exploiting the Meta-Bug Library. In fact, trying to prove the original goal

conjugate(go, present_perfect, 3, singular, [is,gone]-[]).

the Modeler finds a match with the right hand side of the following correct conjugation rule:

%% r2:

%% The present perfect of a verb is formed with the simple present of 'to have' followed %% by the past participle of the verb.

IF conjugate(have, simple_present, Person, Number, V1-V2),

conjugate(Verb, past_participle, V2-V3)

THEN conjugate(Verb, present_perfect, Person, Number, V1-V3).

The substitution needed for the unification, i.e., {Verb/go, Person/3, Number/singular, V1/[is, gone], V3/[]} is then applied to the antecedent clauses which must be proven in order to prove the original goal. The second clause is transformed into the goal

conjugate(go, past_participle, [gone]-[]).

which is proven by means of rule r4

%% r4:

%% The past participle of an irregular verb is given in the dictionary

IF word(Verb, irregular_form(past_participle, V1-V2))

THEN conjugate(Verb, past_participle, V1-V2).

and by looking up in the Dictionary, while the first clause is transformed into the goal

conjugate(have, simple_present, Person, Number, [is]-[])

(i.e., the simple present of to have is is ) which is obviously unprovable. The Modeler can proceed to the construction of the derivation tree by exploiting the following meta-bug

%% mb2:

%% It is possible for a student to utilize 'to be' instead of 'to have'

IF LHS CLAUSE: conjugate(have, Tense, Person, Number,V1-V2),

THEN REPLACE WITH: conjugate(be, Tense, Person, Number, V1-V2).

This meta-bug takes care of the case in which a student could use the auxiliary to be instead of to have (auxiliary inversion with intransitive verbs represents a typical error made by Italian students) by specifying that, in order to prove a failing clause containing the auxiliary to have, it is possible to replace it with a clause containing the verb to be. By applying mb2 we obtain the clause

conjugate(be, simple_present, Person, Number, [is]-[]).

which is proven by means of rule r1 and by looking up in the Dictionary. By means of this new clause it is possible to positively conclude the construction of the derivation tree (labelled for reference dtree1) which is illustrated in figure 3.

Each node of the derivation tree (with the exception of the root) specifies a (partial) conclusion produced during the hypothesized reasoning process of the student, while the root contains the student answer.

Since a derivation tree describes a possible reasoning path followed by the student in a very specific situation, in order to model his/her misconceptions in a more general way it is necessary to generalize the derivation tree containing the mistake. To this end, the Modeler considers a more general structure, called explanation structure, which contains reference to the various rules utilized in the derivation tree and to the specific unifications performed. The explanation structure for the example is shown in figure 4, where each thick horizontal line within a box indicates the pair of rule clauses unified during the construction of the derivation tree.

At this point, while the standard explanation-based learning technique works on the whole structure in order to extract a single general concept, our algorithm focuses only on the subtree(s) containing meta-bugs in order to induce general mal-rules representing the student misconceptions. In our example, the Modeler concentrates upon the subtree constituted by rule r2 and the meta-bug mb2, it unifies the rule clauses to which a meta-bug has been applied with the left hand side of the meta-bug, and then it applies the substitution to the right hand side of the meta-bug. In our example, the antecedent clause of r2

conjugate(have, simple_present, Person, Number, V1-V2).

is unified with the left hand side of meta-bug mb2 and, after the appropriate substitution has been applied to the right hand side of the meta-bug, the following clause results:

conjugate(be, simple_present, Person , Number , V1-V2).

The final step consists in substituting this clause to the antecedent of the rule r2, generating in such a way the following new mal-rule

%% bug1:

%% the present perfect of a verb is formed with the simple present of 'to be' and the past

%% participle of the verb

IF conjugate(be, simple_present, Person, Number, V1-V2),

conjugate(Verb, past_participle, V2-V3)

THEN conjugate(Verb, present_perfect, Person, Number,V1-V3).

This concludes the commission error analysis. It must be noticed again that the results obtained at this stage of the modeling process, i.e., the derivation tree dtree1 and the new mal-rule bug1, are considered only as hypotheses and they do not yet affect the content of the Student Model.

6.2 Omission Error Analysis

This phase is aimed at explaining why the student has not given the answer foreseen according to the simulated behavior. In fact, the expected answer is here has gone while the student has given the answer is gone. The Modeler tries to formulate possible causes, called omission causes, for the omission error. In general, an omission cause specifies a pair of rules (or facts): a rule/fact ignored by the student that will be deleted from the Student Model and an incorrect rule/fact, which the student believes should be applied to the situation at hand, that will be inserted into the Student Model. In some cases, when the student completely misses a rule/fact and is unable to replace it with something else, the omission cause specifies only what is ignored by the student.

In order to discover the omission causes, the Modeler starts its analysis by considering the expected answer and the derivation tree (labelled exp_dt1) generated by the simulation of the student reasoning which is illustrated in figure 5.

The expected answer, contained in the root of exp_dt1, is not provable if some of the lower level goals contained in the tree become unprovable. In particular, a goal contained in the tree becomes unprovable if the rule (or fact) used to solve it is labelled as missing in the Student Model, or it is replaced with a mal-rule not applicable to the given goal. For example, the goal contained in the root of the derivation tree exp_dt1 becomes unprovable if the student ignores the rule r2, or if he knows a perturbed form of the rule which is not applicable to the goal in the root.

For each node of the derivation tree two general types of hypotheses about the omission causes can be formulated by the Modeler:

i) omission by ignorance: the student totally ignores a rule/fact utilized to build the derivation tree (if this hypothesis of omission is later validated the corresponding rule/fact will be inserted into the Student Model with the label 'missing'); and

ii) omission by perturbation: the student knows a perturbed form of a rule utilized to build the derivation tree (if this hypothesis of omission is later validated the corresponding perturbed version of the rule will be inserted into the Student Model with the label 'applied').

According to the first type of omission cause, from the derivation tree exp_dt1 the Modeler could hypothesize as missing the rules r1, r2, r4, and the facts d6 and d8. However, there is some evidence that the student has used these facts and rules for solving the exercise ex1. The Modeler labels a fact or a rule as applied when it is contained in all the derivation trees concerning the student answer. In our case, since the only explanation tree is dtree1, all the knowledge utilized in it (i.e., r1, r4, d5, d6 and bug1) can be considered as applied. For this reason, the only remaining concepts which can be hypothesized as missing are r2 and d8. This conforms to a general heuristic followed by the Modeler: Hypotheses of omission cannot be made about rules and facts which have likely been applied by the student.

The identification of the second type of omission cause (omission by perturbation) follows a more complex process based on the exploitation of diagnostic knowledge (stereotyped mal-rules and meta-bugs). In this case, the Modeler tries to substitute a rule (or a fact) utilized in some node of the derivation tree exp_dt1 with a perturbed version of it. More precisely, for each rule (or fact) applied in the derivation tree, the Modeler tries to find a perturbation which makes the goal solved by this rule (or fact) unprovable. In order to clarify how this procedure works, we illustrate the perturbation of rule r2 (applied to the root of the derivation tree exp_dt1).

The Modeler starts by considering all the meta-bugs applicable to the rule r2. In particular, a suitable meta-bug for r2 is the meta-bug b3:

%% mb3:

%% The conjugation of the present perfect depends on the transitiveness of the verb (as in

%% Italian)

IF RHS CLAUSE: conjugate(Verb, present_perfect, Person, Number, V1-V2),

THEN ADD IN LHS: word(Verb, transitive).

which is applicable to r2 because its condition part is satisfied by the right hand side of r2.

The perturbation of r2 is performed by unifying the condition part of the meta-bug mb3 with the right hand side of r2 , and by adding the clause specified in the right hand side of the meta-bug to the condition part of the rule r2. The following new mal-rule is thus obtained:

%% bug 2:

%% If a verb is transitive, its present perfect is formed with the simple present of the

%% verb 'to have' and the past participle of the verb

IF conjugate(have, simple_present, Person, Number, V1-V2),

conjugate(Verb, past_participle, V2-V3),

word(Verb,transitive)

THEN conjugate(Verb, present_perfect, Person, Number,V1-V3).

Not all the possible perturbations resulting by applying meta-bugs to a rule are allowed as omission causes. In order to be accepted as an explanation for a student omission error, a mal-rule should not be applicable to a node of the derivation tree where the original (not perturbed) rule has already been applied. In our case, the goal solved by the original rule r2 becomes unprovable if we use the new constructed mal-rule bug2: in fact, bug2 requires a transitive verb while to go is classified as intransitive in the Dictionary. For this reason, a student who knows bug2 instead of r2 cannot give the answer has gone. Thus, a first hypothesis about a perturbation omission cause is that the student knows the mal-rule bug2 instead of the correct rule r2.

Another meta-bug applicable to the rule r2 is:

%% mb2:

%% It is possible for a student to utilize 'to be' instead of 'to have'

IF LHS CLAUSE: conjugate(have,Tense, Person, Number,V1-V2),

THEN REPLACE WITH: conjugate(be,Tense, Person, Number,V1-V2).

With a procedure similar to the previous one, the Modeler can generate the following mal-rule for explaining the student omission error:

%% bug1:

%% The present perfect of a verb is formed with the simple present of 'to be' and the past

%% participle of the verb.

IF conjugate(be, simple_present, Person, Number, V1-V2),

conjugate(Verb, past_participle, V2-V3)

THEN conjugate(Verb, present_perfect, Person, Number ,V1-V3).

which is exactly the same mal-rule generated during the analysis of commission errors. Also in this case the root goal of the derivation tree exp_dt1 becomes unprovable when we substitute the rule r2 with the mal-rule bug1. Thus this bug represents another possible explanation for the omission error.

By utilizing the knowledge contained in the Meta-Bugs Library illustrated in the Appendix, the Modeler ends up this phase by formulating the following hypotheses for possible omission causes:

- omiss1: the student does not know the rule r2;

- omiss2: the student does not know the fact d8;

- omiss3: the student believes bug2 instead of the correct rule r2;

- omiss4: the student believes bug1 instead of the correct rule r2.

If some of these hypotheses are later confirmed, the missing rules or concepts will be inserted into the Student Model with the label missing and the replacing mal-rules will be inserted with the label applied.

6.3 Discriminating among the Hypotheses

This last phase aims at analyzing all the active hypotheses generated in the previous phases or in previous interactions. During this phase the Modeler tests the various hypotheses and tries to discriminate among them. The confirmed hypotheses are then taken into account for updating the Student Model and the discharged hypotheses are eliminated. The specific criteria utilized to discriminate among the different hypotheses and to update the Student Model are the following:

(a) If the student answer is explained by a single derivation tree, the mal-rules contained in that tree are inserted into the Student Model.

(b) If the student answer is explained by a single omission cause, the corresponding missing rules or facts are inserted into the Student Model with the label missing and the replacing mal-rules (if any) are inserted with the label applied.

(c) If a hypothesized mal-rule appears in all the alternative derivation trees explaining the student answer, it can be considered as applied and is inserted into the Student Model.

(d) If a hypothesized mal-rule, utilized to simulate the student reasoning in an exercise different from that in which it was originally derived, produces an answer different from that given by the student, then the mal-rule is discharged.

(e) If a hypothesized omission cause, applied to simulate the student reasoning in an exercise different from that in which it was originally derived, produces an answer different from that given by the student, then the hypothesis of omission is discharged.

Note that, for testing the alternative hypotheses according to the above criteria (d) and (e), the Hypotheses Discriminator utilizes the capability to simulate the student reasoning. In our example, according to the criterion (a) the Modeler validates the derivation tree dtree1 (in fact, this tree is the only explanation for the incorrect student answer) and the mal-rule bug1 (utilized in dtree1) is introduced in the Student Model. The other hypotheses (omiss1, omiss2, omiss3 and omiss4) remain active.

6.4 Managing the Hypotheses with a Truth Maintenance System

All the hypotheses made by the Modeler about the student behavior are managed through the TMS included in the Modeler. In particular, the hypotheses are organized into a network (called dependency network) which describes the dependency relations among different hypotheses. We say that a derivation tree is justified by all the facts and rules (correct or incorrect) utilized for its construction. More precisely, this fact is represented with a justification link which specifies the supported tree and the supporting facts and rules. For example, the derivation tree dtree1 is supported by the rules r1 and r4, by the malrule bug1 and by the facts d5, d6. This is represented by the assertion:

just(j1, dtree1, [bug1, r1,r 4, d5, d6]).

In general, an omission cause is justified by the missing fact or rule and by the new replacing fact or rule (not always present). The omission causes generated from the first exercise have therefore the following justifications:

just(j2, omiss1, [missing(r2)]).

just(j3, omiss2, [missing(d8)]).

just(j4, omiss3, [missing(r2), bug2]).

just(j5, omiss4, [missing(r2), bug1]).

If some node of the network is deleted during the modeling process, then all the nodes that are dependent on it are also deleted. This operation is achieved by following the justification links in the dependency network.

6.5 Selecting New Exercises

At the end of an analysis, several alternative hypotheses are usually active and therefore the system tries to collect new data from the student in order to better understand his/her misconceptions. In particular, the Tutor assigns a new exercise to the student with the purpose of supporting the Modeler in gathering new elements for discriminating among the alternative hypotheses. In order to select a new exercise the Tutor proceeds through three steps:

- it selects one or more alternative hypotheses to be further analyzed;

- it looks for an exercise related to these hypotheses in the database; and then

- it verifies whether the chosen exercise is discriminatory for the selected hypotheses.

An exercise is considered useful for discriminating among different hypotheses if the hypotheses produce different answers to it. In our example we have to discriminate among hypotheses of omission causes (omiss1, omiss2, omiss3, and omiss4). Let us consider for example the two hypotheses omiss1 and omiss3.

As the two hypotheses concern rules for the conjugation of the present perfect, the Tutor uses this element for identifying suitable exercises in the Exercise Database. A first possible exercise selected from the database is:

ex2: Please conjugate the present perfect, first person singular, of the verb to arrive.

In order to verify the discriminating degree of the exercise, the Tutor exploits the capability of simulating the student reasoning. The simulation concerns the reasoning process aimed at solving the exercise and it is performed assuming in turn each alternative hypothesis (omiss1 and omiss3). Then the results of the two simulations are compared. In our example, the simulation of the first omission cause (omiss1) produces the result:

am arrived.

The result of the simulation for the second hypothesis is again

am arrived.

As the two simulations produce the same answer, this exercise cannot be used to discriminate the two hypotheses and thus it is not considered by the Tutor. The next exercise selected from the database is:

ex3: Please conjugate the present perfect, first person singular, of the verb to ask.

In this case the two simulations give the following results:

am asked (omiss1)

have asked, am asked (omiss3).

Since this exercise gives two different sets of solutions for the two hypotheses it is considered useful for the discrimination and can thus be assigned to the student.

6.6 Concluding the diagnosis

Let us suppose now that the student gives have asked as a reply. The expected behavior of the student includes two different answers: have asked and am asked. The former answer is equal to that provided by the student and thus does not need a further analysis. The latter answer is different and therefore it is necessary to proceed with the omission error analysis. New possible omission causes are generated and all active hypotheses are again discriminated by means of the same procedure illustrated above: as a result, two omission causes (concerning respectively the fact that the student does not know that the irregular third person singular form of the verb to have is has and the fact that the correct conjugation rule r2 is replaced by the mal-rule bug2) are still active for explaining the first exercise, and two other hypotheses are active for the second exercise (concerning respectively the fact that the student does not know that the irregular first person singular form of the verb to be is am, and a new mal-rule stating that the present perfect of intransitive verbs is formed by utilizing the auxiliary to be).

The control is again given to the Tutor which selects a new exercise (about the conjugation of the present perfect, first person singular, of the verb to arrive). Assuming that the student answer is am arrived, the Modeler is able to confirm two hypotheses: one about the incorrect use of the auxiliary to be with intransitive verbs and another hypothesis (produced by the omission error analysis of the answer just given) about the use of the auxiliary to have only with transitive verbs. All the other hypotheses still pending are discarded except one concerning the possible ignorance about the simple present of to have; the Tutor assigns therefore a specific exercise about this point.

The student answer is now has, which allows to discard the last hypothesis still active. At this point, the Modeler has completed the evaluation of all the hypotheses: the diagnosis has revealed that the student has incorrect knowledge about the use of auxiliary verbs in the present perfect. More specifically, he has replaced the correct rule r2 with two different mal-rules: one rule for the case of transitive verbs (the present perfect is formed with the auxiliary to have and the past participle), and another rule for the case of intransitive verbs (the present perfect is formed with the auxiliary to be and the past participle).

6. Conclusions

A new methodology for modelling student performance has been presented which could be used in those systems that, like ET, are based on processes decomposable into a finite number of subtasks related to each other through producer-consumer dependencies. It is claimed that the deep modelling process illustrated in the paper has general significance beyond the domain of second language teaching. Our approach constitutes an attempt to deal with the problem of finding the reasons for, and giving a satisfactory explanation to, student performance. Some features of the proposed approach that we find particularly original are: (i) the integration of the bug collection and bug construction techniques, (ii) the use of diagnostic knowledge contained in a meta-bug library in order to help the process of bug construction, and (iii) the use of explanation based-learning techniques in the domain of modelling students' misconceptions. The proposed approach has been fully implemented in PROLOG on a Macintosh II.

References

1. Anderson, J.: Production Systems, Learning, and Tutoring. In: Production System Models of Learning and Development (D. Klahr, P. Langley, and R. Neches, eds.). Cambridge, MA: The MIT Press 1987

2. Bar-On, E. and Or-Bach, R.: Explanation-Based Learning in Intelligent Tutoring Systems. In: Artificial Intelligence Tools in Education (P. Ercoli and R. Lewis, eds.). Amsterdam, NL: Elsevier Science Publ. 1988

3. Bonar, J.G. and Soloway, E.M.: Pre-Programming Knowledge: A Major Source of Misconceptions in Novice Programmers. Human-Computer Interaction 1(2), 133-161 (1985)

4. Brown, J. and Burton, R.: Diagnostic Models for Procedural Bugs in Mathematical Skills. Cognitive Science 4, 379-426 (1980)

5. Chanier, T. and Pengelly, M.: Conceptual Modelling in Error Analysis in Computer-Assisted Language Learning Systems, this volume

6. Costa, E., Duchenoy, S., and Kodratoff, Y.: A Resolution Based Method for Discovering Students' Misconceptions. In Artificial Intelligence and Human Learning (J.A. Self ed.). London, UK: Chapman and Hall 1988

7. DeJong, G.F. and Mooney, R.J.: Explanation-Based Learning: An Alternative View. Machine Learning 1, 145-176 (1986)

8. diSessa, A.A.: Unlearning Aristotelian Physics: A Study of Knowledge-Based Learning. Cognitive Science 6, 37-75 (1982)

9. Doyle, J.: A Truth Maintenance System. Artificial Intelligence 12, 231-272 (1979)

10. Fum, D., Giangrandi, P., and Tasso, C.: ET: An Intelligent Tutor for Foreign Language Teaching. Proceedings ITS-88, Montreal, pp. 462-468, 1988

11. Fum, D., Giangrandi, P., and Tasso, C.: Tense Generation in an Intelligent Tutor for Foreign Language Teaching: Some Issues in the Design of the Verb Expert. Proceedings 4th Conference of the European Chapter of the Association for Computational Linguistics, Manchester, pp. 124-129, Association for Computational Linguistics 1989

12. Fum, D., Giangrandi, P., and Tasso, C.: Backward Model Tracing: An Explanation-Based Approach for Reconstructing Student Reasoning. Proceedings AAAI-90, Boston, MA, pp. 426-433. Menlo Park, CA: AAAI Press 1990

13. Mitchell, T.M., Keller, R., and Kedar-Kabelli, S.: Explanation-Based Generalization: A Unifying View. Machine Learning 1, 47-80 (1986)

14. Reif, F.: Interpretation of Scientific or Mathematical Concepts: Cognitive Issues and Instructional Implications. Cognitive Science 11, 395-416 (1987)

15. Self, J.A.: Bypassing the Intractable Problem of Student Modelling. Proceedings ITS-88, Montreal, pp. 18-24, 1988

16. Sleeman, D.: Inferring (Mal) Rules from Pupils' Protocols. Proceedings Second International Machine Learning Workshop, Chicago, pp. 221-227, 1983

17. Wenger, E.: Artificial Intelligence and Tutoring Systems. Los Altos, CA: Morgan Kaufmann 1987

%% r1:

%% The simple present of an irregular verb is given in the dictionary

IF word(Verb, irregular_form(simple_present, Person, Number,V1-V2))

THEN conjugate(Verb, simple_present, Person, Number,V1-V2).

%% r2:

%% The present perfect of a verb is formed with the simple present of 'to have' followed by

%% the past participle of the verb.

IF conjugate(have, simple_present, Person, Number, V1-V2),

conjugate(Verb, past_participle, V2-V3)

THEN conjugate(Verb, present_perfect, Person, Number,V1-V3).

%% r3:

%% The past participle of a regular verb is formed with the ed-form.

IF form_ed(Verb,V1-V2),

word(Verb,regular(past_tense))

THEN conjugate(Verb,past_participle,V1-V2).

%% r4:

%% The past participle of an irregular verb is given in the dictionary

IF word(Verb, irregular_form(past_participle, V1-V2))

THEN conjugate(Verb, past_participle, V1-V2).

%% r5:

%% The ed-form of a verb whose last letter is different from 'e', which

%% does not double the last letter and whose last letter is different

%% from 'y' or its last but one letter is not a consonant, is obtained

%% by adding 'ed'.

IF add_string([Verb|X-X],ed,V_ed),

last_letters(Verb,(L1,L2)),

constraint(L2 \== e),

word(Verb,no_double_last_letter),

letter(L1,L1_type),

constraint(not((L2 == y,L1_type == consonant)))

THEN form_ed(Verb,V_ed).

%% r6:

%% The ed-form of a verb ending in 'e' is formed by adding 'd'.

IF add_string([Verb|X]-X,d,V_ed),

constraint(last_letters(Verb,(_,e)))

THEN form_ed(Verb,V_ed).

%% The verb 'to arrive' is regular in the past tense

d1: word(arrive,regular(past_tense))

%% The verb 'to ask' is regular in the past tense

d2: word(ask,regular(past_tense))

%% The verb 'to ask' does not double the last letter when

%% some suffix is added to it

d3: word(ask,no_double_last_letter)

%% The simple present of the verb to be, first person singular,

%% is 'am'.

d4: word(be,irregular_form(simple_present,1,singular,[am|X]-X))

%% The simple present of the verb 'to be', third person singular,

%% is 'is'.

d5: word(be,irregular_form(simple_present,3,singular,[is|X]-X))

%% The past participle of the verb 'to go' is 'gone'.

d6: word(go,irregular_form(past_participle,[gone|X]-X))

%% The simple present of the verb 'to have', first person singular,

%% is 'have'.

d7: word(have,irregular_form(simple_present,1,singular,[have|X]-X))

%% The simple present of the verb 'to have', third person singular,

%% is 'has'.

d8: word(have,irregular_form(simple_present,3,singular,[has|X]-X))

%% The letter 's' is a consonant.

d9: letter(s,consonant)

%% ex1:

%% Conjugate the present perfect, third person singular, of the verb 'to go'.

conjugate(go,present_perfect,3,singular,V-[])

%% ex2:

%% Conjugate the present perfect, first person singular of the verb 'to arrive'

conjugate(arrive,present_perfect,1,singular,V-[])

%% ex3:

%% Conjugate the present perfect, first person singular, of the verb 'to ask'.

conjugate(arrive,present_perfect,1,singular,V-[])

%% ex4:

%% Conjugate the simple present, third person singular, of the verb 'to have'.

conjugate(have,simple_present,3,singular,V-[])

%% mb1:

%% It is possible for a student to utilize 'to have' instead of 'to be'

IF

LHS CLAUSE: conjugate(be,T,P,N,V1-V2),

THEN REPLACE WITH: conjugate(have,T,P,N,V1-V2).

%% mb2:

%% It is possible for a student to utilize 'to be' instead of 'to have'

IF LHS CLAUSE: conjugate(have, T, P, N,V1-V2),

THEN REPLACE WITH: conjugate(be, T, P, N, V1-V2).

%% mb3:

%% The conjugation of the present perfect depends on the transitiveness of the verb (as in

%% Italian)

IF RHS CLAUSE: conjugate(Verb, present_perfect, Person, Number, V1-V2),

THEN ADD IN LHS: word(Verb, transitive).

%% mb4:

%% A conjugation rule can be restricted only to intransitive verbs

IF

RHS CLAUSE: conjugate(V,T,P,N,V1-V2),

THEN ADD IN LHS: word(V,intransitive)