How to program a domain independent tracer for explanations.

Explanations are essential in the teaching process. Tracers are one possibility to provide students with explanations in an intelligent tutoring system. Their development can be divided into four steps: (a) the definition of the trace model, (b) the extraction of the information from this model, (c) the analysis and abstraction of the extracted information, and (d) the visualization of the result of the analysis. This article describes the architecture of a domain independent tracer developed in Visual Prolog displaying explanations in the form of a textual dialog or a graphical tree.

**********

Explanations are an integral part of any teaching process. A tutorial system should be able not only to solve problems but also to explain them. For this purpose, the steps leading to the solution must be recorded to be presented to the student in case of difficulties. Two techniques are generally used: meta-interpreters and tracers.

In meta-programming data are programs (Yalcinalp, 1991). Since Prolog code and data have the same format (i.e., Horn clauses), this language is particularly appropriate for meta-programming. Meta-interpreters are generally used to add supplementary functions to an existing interpreter. We developed several domain dependent and domain independent meta-interpreters (Ratz & Lusti, 1992; Ratz, 1993; Trapp & Lusti, 1999; Trapp, 2000). Meta-programming in standard Prolog is easy because its source code is interpreted and therefore accessible at run-time. Other Prolog systems produce compiled code, which is faster but complicates meta-programming (Lusti, 1990). FA-Tutor, for example, is an Intelligent Tutoring System for financial analysis developed in a compiled variant of Prolog (Lusti, 1995). This article describes the architecture of a tracer for AHP-Tutor, a system teaching the theoretical background of the Analytic Hierarchy Process. AHP-Tutor has been developed in Visual Prolog, a compiled Prolog (Ishizaka & Lusti, 2003).

TRACER

A tracer collects a detailed protocol (trace) of the execution of a program. To understand how a program reaches its result, we add side effects producing supplementary information on the intermediary states of the execution. This information is analysed and summarised before being presented to the user. The construction of a tracer can be divided into four steps (Ducasse & Noye, 1994):

1. definition of a trace model;

2. extraction of information from this model;

3. analysis/abstraction of the extracted information; and

4. visualisation of the result of the analysis.

These four steps are often considered neither explicitly nor separately. In AHP-Tutor (Ishizaka & Lusti, 2003), for example, the steps 2 and 3 are concomitant.

The literature is rich in tracers producing information on program execution for debugging purposes (Lakhotia, Sterling, & Bojantchev, 1995; Dichev & Du Boulay, 1989; Ducasse, 1999; Ducasse, Langevine, & Deransart, 2003). It has been noted that the produced information, with some enrichment, could be used as explanations in teaching courses. The tracers have been modified to be used as an explanation component in support of Prolog language teaching courses such as the Prolog Trace Package (Eisenstadt, 1984, 1985) and the Textual Tree Tracer (Taylor, Du Boulay, & Patel, 1991; Patel, Taylor, & Du Boulay, 1994). This technique has been also introduced in intelligent tutoring systems, for example LP-Tutor (Born, 1995; Born & Lusti, 1996), ROSA (Muntjewerff & Winkels, 1995) or SlideTutor (Crowley & Medvedeva, 2003). At each project a new tracer has been implemented. This article aims to present a universal explanation component reusable in different intelligent tutoring systems independently of the domain.

DEFINITION OF A TRACE MODEL

An additional argument is added to selected Prolog predicates (Figure 1). It protocols the execution trace of the predicate. Thus the resolution process and the explanation of the problem are closely connected. A problem cannot be solved without generating a trace and vice versa.

The structure of a trace t is defined in the explanation component (Figure 2).

The additional trace argument is tree structured (Figure 3). A trace (or protocol tree) contains rules (intermediate nodes) and facts (terminal nodes or leaves). A fact is a consequence without premise.

The following example shows the construction of simple trace:

Example 1

(1) knowledge base:

a (t (A, [TraceB, TraceC])) :- b (TraceB), c (TraceC).

b (t (B, [TraceD, TraceE])) :- d (TraceD), e (TraceE).

c (t (C, [??])).

d (t (D, [??])).

e (t (E, [??])).

(2) The question a? instantiates its argument with t (A, [t (B, [t (D, [??]), t (E, [??])], t (C, [??])]), where A is the result and the second argument is the protocol list, which can be read as follows:

A holds because

B holds because

D holds because it is a fact

E holds because it is a fact

C holds because it is a fact.

[FIGURE 3 OMITTED]

VISUALISATION OF THE EXPLANATION

To better understand the implementation, we anticipate the visualisation of explanations. Explanations can be represented textually (dialog of Figure 4) or graphically (tree of Figure 5). The textual explanation displays only one consequence and its conditions (Figure 4). The user can then navigate freely through the entire tree, gradually looking for deeper explanations. The graphical explanation allows the access to the entire tree by scrolling (Figure 5). The tree can be expanded or closed by clicking on a node.

When a solution is presented to the student, he or she can ask how it has been achieved. The student can choose its preferred visualisation mode (Figure 6).

Each arrow corresponds to a call of a new component. The following arguments are passed:

1. a list containing the trace and the display mode of the explanation (textual or graphical)

2. a list containing a consequence (head of the list) and its conditions (queue of the list)

3. the answer of the student (closure of the window or navigation in the explanation tree)

4. a list containing the whole explanation tree

5. nothing (closure of the window).

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

INFORMATION EXTRACTION AND ANALYSIS

The inference engine not only traces rules and facts but also reformulates the trace and comments on a solution. Explicit meta-knowledge in a declarative form is used for this purpose. This paragraph describes how the information contained in the trace is extracted, analysed, and commented. The predicate explain(rule/n), for example, adds an explanatory comment to a rule (cf. example 2).

Example 2

The following clause comments on the result of the transitivity rule:

explain (transitivity(Result)):-

write("According to the transitivity rule the multiplication of the comparisons gives" + Result).

The extraction of the information from the trace depends on the explanation mode. The next paragraphs detail on the implementation of both textual and graphical explanations.

Textual Explanation

The explanations to be displayed are in a list generated by the explanation component. The head contains the consequence and the conditions are in the tail (see Figure 6).

While passing arguments to a dialog in Visual Prolog is easy, returning the arguments without losing the context is not trivial. To keep the context of an explanation dialog we use two global variables. The first global variable records the level in the explanation tree. The following picture denotes the root by the level number 1. After each step downwards the number is incremented by 1 (Figure 7).

The second global variable communicates one of the following user alternatives to the explanation component:

* explain one of the conditions (visit a son);

* return to the predecessor (visit the father);

* return to the root of the explanation tree; and

* leave the explanation dialog.

The explanation component is initialised as follows:

- the list of explanations to display is empty;

- the initial tree level is 1 (the root); and

- the return value is 0.

[FIGURE 7 OMITTED]

For each node visited, the comments for the consequence and the conditions are displayed. When a leaf is reached, the system writes the consequence and instead of the lacking premise, it shows the message: "No further explanation possible."

Figure 8 analyses the process flow in the explanation component. Backtracking allows to explore alternatives to find a valid solution. In Figure 8, the search for alternatives backtracks to the predicate analysing the student's answer within the explanation dialog (the circle in Figure 8). Since this predicate is not deterministic, four alternatives are proposed:

1. backtracking (if the returned value is equal or lower than zero)

2. leave the dialog (if the returned value is 1)

3. cut the trace (visit a son) and restart the explanation process

4. restart the explanation process.

The 3rd and the 4th alternatives are unconditional. If the conditions of the first two alternatives do not hold, the 3rd alternative is chosen. The 4th alternative is adopted only when backtracking (Figure 9). Options 3 and 4 have distinct functions:

* Alternative 3 visits a son. Its tree is extracted and analysed.

* Alternative 4 does not modify the trace. Therefore the displayed explanation is not changed. After having visited a son, the father can be easily reviewed with backtracking.

Backtracking to the root allows reviewing the explanation tree from the start on. The number of backtracking steps is equal to the number of descendants visited. To know this number, the explanation dialog returns the current level of the tree (see Figure 7). After each backtracking step the tree level is decremented. This process is stopped at the root level.

[FIGURE 8 OMITTED]

Graphical Explanation

To prepare the generation of graphical explanations, the trace has to be collected by a depth-first traversal of the relevant clauses. Then the comments bound to the rules are read and included in the tree to be displayed (Figure 10). The tree predicate has the following arguments:

1. the text to be displayed

2. a constant indicating whether the node is initially open or closed (unmarked/marked)

3. the sons (conditions) of the node.

[FIGURE 9 OMITTED]

Figure 11 describes the generation of the explanation tree from the trace. The traversal of the trace is an application of depth-first search (Figure 12). The root is visited then the left subtree and the right subtree are traversed.

CONCLUSION AND FURTHER WORK

Explanations are essential in the teaching process. Two implementation architectures can be used: meta-interpreters and tracers. Since meta-interpreters are difficult to implement in a compiled language, we have proposed a tracer which can easily be implemented in a compiled Prolog. Our tracer is domain-independent and has been used successfully in two Intelligent Tutoring Systems. The first solves financial problems and the second teaches the theoretical foundations of AHP.

We applied our software to students of a course in Decision Support Systems. The practical experience showed that, at least initially, some students had to be motivated to appreciate system provided explanations instead of teacher help. This may be attributed to the prototype frugal user interface. Most students first chose the textual mode, because it allows a better focus on the problematic solution steps. After the clarification of selected steps, the graphical mode was used to get a global view or summary of the resolution process. So both explanation modes complemented each other.

After the initial introduction to the instructional system, the students use it for an autonomous learning process in the classroom or at home. The Intelligent Tutoring Systems are particularly well adapted to practising techniques such as financial or algorithmic calculations as those in our FA-Tutor and AHP-Tutor. It will indicate the mistakes during the exercise resolution and explain them with the piece of meta-knowledge added to each used rule. This immediate feed-back was very much appreciated by the students and relieved the teacher from performing an intensive final correction. It is in fact not a trivial job for a human teacher to find an error in a long calculation development, which has by cascading process induced the erroneous final result. The students can also exercise indefinitely the part, which they found the most difficult by solving new problems. Thus, when stuck, he/she can ask the tutor to perform the next step, or to complete the solution to the entire problem. It is an individualized learning, where they have at their disposal a personal free tutor geographically and temporally totally available, which was highly welcome. The only restriction is to have a computer. Our task has been limited to the introduction of the theory and the presentation of the intelligent tutoring system.

[FIGURE 12 OMITTED]

Our tracer is domain independent, but the domain must be modelled by rules and facts. That is why logically structured domains are more appropriated than others. For example, a mathematically based domain is more suitable than the descriptive domain of a history curriculum. Further work will focus on the reuse of the explanation component in a collaborative e-learning system in Economics.

References

Born, A., (1995). A blackboard approach to a knowledge-based tutoring system for linear programming. In J. Greer (Ed.), Al--ED 95, Proceedings of the 7th World Conference on Al in Education, (p. 569). Washington, DC.

Born, A., & Lusti, M. (1996). An architecture for knowledge based tutoring systems in algorithmic domains. In P. Brna, A. Paiva, & J. Self (Eds.), European Conference on Artificial Intelligence in Education, (pp. 291-297). Lissabon, Portugal.

Crowley, R.S., & Medvedeva, O. (2003). A general architecture for intelligent tutoring of diagnostic classification problem solving. AMIA Annual Symposium Proceedings, (pp. 185-189).

Dichev, C., & Du Boulay B., (1989). An enhanced trace tool for prolog. Proceedings of the Third International Conference: Children in the Information Age, Human Development and Emerging Technologies, (pp. 149-163). Sofia, Bulgaria.

Ducasse, M. (1999). Opium: An extendable trace analyser for Prolog. The Journal of Logic Programming, Special Issue on Synthesis, Transformation and Analysis of Logic Programs, 39, 177-223.

Ducasse, M., & Noye, J. (1994). Logic programming environments: Dynamic program analysis and debugging. The Journal of Logic Programming, 19-20, 351-384.

Ducasse, M., Langevine, L., & Deransart, P. (2003). Rigorous design of tracers: An experiment for constraint logic programming. In M. Ronsse & K. De Bosschere (Eds.), Proceedings of the Fifth International Workshop on Automated Debugging (AADEBUG 2003, pp. 171-185), Ghent, Belgium.

Eisenstadt, M. (1984). A powerful prolog trace package. In Tim O'Shea (Ed.), Proceedings of the Sixth European Conference on Artificial Intelligence (ECAI-84, pp. 149-158). Pisa, Italy.

Eisenstadt, M. (1985). Retrospective zooming: A knowledge based tracking and debugging methodology for logic programming. Proceedings of the International Joint Conferences on Artificial Intelligence, (pp. 717-719).

Ishizaka, A., & Lusti, M., (2003). An intelligent tutorial system for AHP. In K. Soric, T. Hunjak, R. Scitovski, (Eds.), Proceedings of the 9th International Conference on Operational Research KOI 2002, (pp. 215-223).

Lakhotia, A., Sterling, L., & Bojantchev, D., (1995). Development of a prolog tracer by stepwise enhancement. Proceedings of the Third International Conference on Practical Applications of Prolog, (pp. 353-393). Paris, France.

Lusti, M. (1990). Wissensbasierte systeme. Algorithmen, datenstrukturen und werkzeuge. Bibliographisches Institut/Wissenschaftsverlag, Mannheim.

Lusti, M. (1995). An authoring component for protocol driven hypertext explanations. Artificial Intelligence in Education, Proceedings of EDMEDIA (pp. 290-298). Charlottesville, VA: Association for the Advancement of Computing in Education.

Muntjewerff, A., & Winkels, R. (1995). ROSA; A model based computer system for teaching legal case solving. In J.C. Hage, T.J.M. Bench-Capon, M.J. Cohen, & H.J. Van den Herik (Eds.), Legal Knowledge Based Systems JURIX '95: Telecommunication and Al & Law, (pp. 133-141). Lelystad, Holland.

Patel, M.J., Taylor, C., & Du Boulay, J.B.H. (1994). Textual tree (prolog) tracer: An experimental evaluation. In D. Gilmore, R. Winder, & F. Detienne (Eds.), User-centred requirements for soft-ware engineering environments, (pp. 127-141). Berlin: Springer-Verlag.

Ratz, T. (1993). Erklarungen in wissenbasierten lernsystemen am beispiel eines tutors zur normalisierung von datenbanken, Doctoral dissertation, Peter Lang, Frankfurt am Main.

Ratz, T., & Lusti, M. (1992). Explanation strategies: Realization in a tutor for database normalization, European Conference on Al, (pp. 47-56). Paris, France.

Taylor, C., Du Boulay, B., & Patel, M. (1991). Outline proposal for a prolog "textual tree tracer" (TTT). Cognitive Science Research Paper 177, School of Cognitive and Computing Sciences, University of Sussex, UK.

Trapp, U. (2000). Komponententechnologien zur flexibilisierung konventioneller lernsysteme am beispiel einer wissenbasierten erklarungskomponente. Doctoral dissertation, Basle University, http://www.dissertation.de, Berlin.

Trapp, U., & Lusti, M. (1999). A domain independent authoring environment for problem solving knowledge, Artificial Intelligence in Education, International Artificial Intelligence in Education Society, (pp. 768-770). Le Mans, France.

Yalcinalp, L.U. (1991). Metaprogramming for knowledge-based systems in prolog, Unpublished doctoral dissertation, Case Western Reserve University, Cleveland, OH.

Acknowledgement

We gratefully acknowledge the financial support of the Freiwillige Akademische Gesellschaft Basel.

ALESSIO ISHIZAKA

University of Exeter, UK

[e-mail]

MARKUS LUSTI

University of Basel, CH

[e-mail]

Predicate (Argument1,..., ArgumentN, Trace)

Figure 1. The additional argument Trace is added to selected predicates

Trace = t (predicate, LTrace)  % structure of trace t
LTrace = Trace*                % list of trace structures

Figure 2. The additional trace argument is structured (syntax of Visual
Prolog)

Tree = tree(<wording of the explanation>, <unmarked/marked>, [<Tree of
the first condition>,..., <Tree of the n-th condition>])

Figure 10. Structure of an explanation tree

traverse (Conditions of the virtual root*, Explanations*)            (1)
traverse (Conditions*, Explanations*){                               (2)
  IF Conditions* is empty THEN                                       (3)
    Explanations* = empty                                            (4)
  ELSE                                                               (5)
    separate head and tail of Conditions*                            (6)
    separate the Consequence and the Conditions in the head of       (7)
    Conditions*
    explain (Consequence, Explanation)                               (8)
    traverse (Conditions of the head*, Explanations of the           (9)
    descendants*)
    traverse (Tail of Conditions*, Explanations of the brothers*)   (10)
    Explanations* = [tree(Explanation, marked, Explanations of the
    descendants*) & Explanations of the brothers*]                  (11)
  END IF                                                            (12)
}                                                                   (13)

Comments:
(1) Extraction of the explanation bound to the root. The arguments of
    the function are the list of the Conditions of the virtual root*
    (i.e. the trace) and Explanations* which contains the returned
    explanation.
(2) Recursive traversal of the rest of the tree. Conditions* is an input
    argument, Explanations* is the returned list.
(8) Explanation of the consequence of the head of Conditions*.
    Consequence is an input, Explanation is an output argument.
(9) Visit of the first son
(10) Visit of the others sons
(11) Assembling the explanations of the visited node (descendants and
     their siblings)

Figure 11. Algorithm traversing the trace and generating the explanation
tree (* means list)