Generating Concise Discourse that Addresses a Users Inferences

1 Introduction

Traditional Natural Language Generation (NLG) sys­ tems, e.g., [Hovy, 1988; Moore and Swartout, 1989; Cawsey, _19901, operate under the assumption that a h~arer will o~ly make direct inferences from a piece of discourse. :r'hts assumption causes two problems:

1. Poss1ble erroneous indirect inferences from the dis­ cour~e are not addressed. For example, a possible indi­ r~ct, I~ference fro~ the statement "plants photosynthe­ stz.e . IS that f':ingt also photosynthesize. Even though thts mference IS wrong, it would not be addressed by current systems.
2. The resulting text is overly explicit due to the fact ~hat all th~ information to be conveyed is stated. For mstance, given. the 15oal of conveying the propositions [Mary went-to cmemaJ and [Mary saw film], existing NLG s~ste!lls w~mld generate a sentence for each proposition, yteldmg dtscourse such as "Mary went to the cinema and .s~e s~w a film." However, this discourse is overly exphctt, smce, unless told otherwise, most people infer from the first sentence that Mary saw a film.

T~ese problems have been considered separately in prevwus research. The first of these problems has been addressed in [Joshi et a/., 1984; Zukerman 1990] in the context of a~ding explanat!ons to expert r~sponses, and complementmg planned dtscourse with Contradictions and Revisions, respectively. (Horacek, 1991; Lascarides an~ C?berlander, 19921 address the second problem by omittmg from planned explanations information that is easily inferred from the discourse.

*This research was supported in part by grant A49030462 from the Australian Research Council.

In this paper, we present an integrated content plan­ ning mechanism which addresses both of the above problems. Our mechanism generates Rhetorical Devices {!f,Ds), where each RD is composed of a rhetorical ac­ tion, sue~. as Assert,. Negate or Instantiate, applied to a proposition. To this effect, our mechanism models a user's inferences by means of inference rules which re­ ~ate RD~ to beliefs (Sect~on 2). These rules are applied m two dtfferent ways. durmg the discourse planning pro­ cess: forward reasonmg and backward reasoning.

. Forward reaso_ning reasons from RDs to their pos­ st?le ~ffe~ts. For mstance, the application of a gener­ ·~hz.atwn mference rule to the Assertion "kangaroos are mdtgenous of Australia" conjectures that the hearer will conclude that marsupials are indigenous of Australia.

Backward reasoning reasons from a communicative goal to the RDs that may be used to accomplish it. For instance, the concept of a stack may be conveyed to a student by mean~ of a Definition, an Analogy (say to a sta~k o~ plates m a cafeteria), an Instantiation, or a combmatwn of these RDs. This reasoning mechanism has been widely used in NLG systems, e.~., [Hovy, 1988; Moore and Swartout, 1989; Cawsey, 1990J: In particular, [Moore.and Swartout, 1989; Cawsey, 1990] have encoded Analogies and Instantiations into discourse planning op­ erators. However, this encoding does not represent ex­ plicitly the inferences that allow a hearer to deduce a belief from a rhetorical device. In addition, according to these operators, the user acquires only the intended beliefs, and no unintended ones.

Our c.ontent planning mechanism has been imple­ men~ed 1~ a system ~ailed WISHFUL which generates conc,tse dt~course while ~t the same time addressing a user s posstble erroneous mferences. Our mechanism first applies backward reasoning in order to determine which R~s are su~table for communicating a particular piece of mformatwn, and then applies forward reasoning in order to conjecture the effect of these RDs on a user's beliefs. If a wrong inference is conjectured from an RD ~hen an additional RD may be required to address thi~ mfer~nce. If a correct inf~rence is conjectured, then a prev.wusly planned RD whtch conveys the inferred infor­ mation may no longer be required. Owing to these interactions between the inferences from the RDs generated to convey different information items, an optimization process is applied in order to achieve a global minimum of the number of generated RDs (Section 3.4).

In the next section, we discuss our model of the stu­ dent's beliefs and inferences. In Section 3, we describe the operation of the content planner. We then discuss our results and present concluding remarks.

2 The Student Model

Our student model represents (1) a student's profile, (2) his/her beliefs, and (3) his/her inferences.

Profile: [Sleeman, 1984] observed that good students retain more correct conclusions than incorrect ones, while the opposite happens for mediocre students. In addition, we have observed that good students are more certain of their conclusions than mediocre students. In order to model these behaviours, we maintain profiles of different types of students. The profile attributed to a student determines the correctness and strength of the initial beliefs in the model of the student, and the degree of belief in the conclusions drawn by sound and unsound inferences. For example, the profile of a mediocre stu­ dent is characterized by weak convictions with respect to both facts and inference rules, and lack of discrimination between correct and incorrect beliefs, and between sound and unsound inferences. In the current implementation of WISHFUL we maintain five profiles which range from EXCELLENT to BAD.

Beliefs: Since it is easier to make broad assessments rather than pinpoint numerical assessments with respect to a student's beliefs, we represent a student's conjec­ tured beliefs by means of the following qualitative be­ lief states [Bonarini et al., 1990]: {BELIEVED, RATHER BELIEVED, CONTRADICTORY, UNKNOWN, RATHER DISBELIEVED, DISBELIEVED} .

Inferences: Our mechanism uses inference rules to model three types of inferences made by the user: (1) Di­ rect inferences, (2) Indirect inferences, and (3) Unique­ ness implicatures.

Direct inferences reproduce directly the content of the discourse. The abstract-understand inference rule assesses the likelihood that a hearer will understand a statement by means of a direct inference. This likelihood is influenced by the complexity and abstractness of the information in the statement and by the hearer's ability to understand abstract explanations, such as stand-alone descriptions or definitions. This ability in turn is repre­ sented in the hearer's profile.

Indirect inferences produce inferences that add in­ formation to what was said. These inferences are not always sound. The indirect inference rules considered in our model are based on the ones described in [Zukerman, 1990], e.g., generalization, specialization and similarity. The likelihood that a hearer will acquire a belief through an indirect inference depends on his/her confidence in the corresponding inference rule and on the strength of the beliefs which participate in the inference process.

Finally, given a proposition P(O) , a uniqueness im­ plicature licenses the inference that P is true only with respect to 0. For example, upon hearing the statement "Joe has one leg,'' most people will infer that Joe has one leg only [Hirschberg, 1985].

3 Operation of the Content Planner

Our content planner receives as input a concept to be conveyed to the hearer, e.g., Distributive Law, a list of aspects that must be conveyed about this concept, e.g., steps and domain, and an attitude, which may be ei­ ther cautious or daring. A cautious attitude demands that the information relevant to the given aspects be BELIEVED by the user, while a daring attitude is satis­ fied with RATHER BELIEVED. The output of the con­ tent planner is a set of RDs which conveys the intended aspects of the given concept. Typically, a set of RDs generated with the cautious attitude contains more RDs and more complex RDs than a set of RDs produced with the daring attitude. That is, the explanations generated with the cautious attitude are typically longer and more thorough than those generated with the daring attitude.

Our content planner performs the following steps: First it determines the information to be presented based on the given aspects (Step 1) . Next it takes into consid­ eration a user's possible inferences in order to propose alternative sets of RDs which convey this information (Step 2). However, it is possible that the user does not understand the concepts mentioned in a particular RD well enough to understand this RD. Therefore, the generation process is applied recursively with a revised attitude and new aspects with respect to the concepts mentioned in the proposed sets of RDs (Step 3). If necessary, this process generates alternative sets of RDs which convey these concepts. Thus, Steps 1-3 of WISH­ FUL yield several alternative sets of RDs, where each set contains enough information to convey the intended concept. However, owing to the interactions between the inferences from the RDs in each set, it is possible that some of the proposed RDs are no longer necessary. In or­ der to remove the redundant RDs from each set of RDs, WISHFUL applies an optimization process to each set (Step 4) . It then selects the set with the least number of RDs from the resulting sets (Step 5).

Throughout this section, we use the following sam­ ple input to illustrate the operation of the content plan­ ner: (Bracket-Simplification, {steps, domain}, daring). In this input, the communicative goal is for the hearer to RATHER BELIEVE the information relevant to the domain and steps of Bracket Simplification.

3.1 Deciding which Information to Present

In this step, WISHFUL produces a list of propositions that must be conveyed in order to satisfy a given com­ municative goal with respect to the specified aspects of a given concept. To this effect, WISHFUL first retrieves from a knowledge base the propositions relevant to the given aspects. For instance, in order to satisfy the as­ pects in our sample input, the propositions in Table 1 must be known by the hearer 1 .

1 The relationships use-1 and use-2 indicate the temporal ordering of a mathematical operation.

The retrieved list of propositions is then refined based on consultation with our model of the hearer's beliefs. The propositions already known by the hearer are fil­ tered out, and propositions which address the hearer's misconceptions are added. Thus, in our example, if the hearer is presumed to believe correctly that [Bracket­ Simplification use-2 x] and [Bracket-Simplification apply­ to Numbers], and incorrectly that [Bracket-Simplification apply-to Algebraic-Terms], the final list of propositions will be as shown in Table 2.

3.2 Proposing Rhetorical Devices

In this step, the content planner activates the proce­ dure Propose-RDs to propose alternative sets of RDs that convey the propositions produced in the previous step. Our procedure takes into consideration the infer­ ences a hearer is likely to make from the RDs in each alternative in order to conjecture the effect of this al­ ternative on the hearer's beliefs. The operation of our procedure is based on the tenet that people draw im­ mediate inferences while processing a piece of discourse, but make farther reaching inferences only after the entire discourse has been processed. In order to address these immediate inferences, our procedure applies one round of inference rules to each RD in an alternative. For instance, given the RD Assert [Bracket-Simplification apply-to Like-Terms], the generalization rule infers in­ correctly that [Bracket-Simplification apply-to Algebraic­ Terms], and the similarity rule yields the correct infer­ ence that [Bracket-Simplification apply-to Numbers] .

Procedure Propose-RDs( {propositions})

1. If {propositions }=0 Then return( nil) .
2. Get a propositionE{propositionsJ, and remove it from {propositions} .
3. Backward reasoning: propose a set {RD}, where each RD in the set conveys this proposition.
4. Forward reasoning: 'V RD; E { RD} Do (each RD; is the root of a different alternative) 4.1 Draw inferences from RD;.
5. Append to {propositions} any new proposition inferred from RDi .
6. Create a link between RD; and each of the propositions Ph , ... , Pi .. that are affected by it.
7. Assign to each link a weight w; ik equal to the effect of RD; on the belief in pj k ·
8. RDs +- cons(RD;,

Propose-RDs( {propositions})) .

Propose-RDs is a recursive procedure, where each cy­ cle of the recursion generates alternative RDs that con­ vey one proposition. The alternatives generated during a cycle constitute the basis for the next cycle of the recursion. In each cycle, Propose-RDs first performs backward reasoning and then forward reasoning. Dur­ ing backward reasoning (Step 3), the system applies in­ ference rules to propose alternative RDs that convey a proposition. In this process, the system also takes into consideration the attributes of the information to be con­ veyed and the information in the system's knowledge base and in the model of the user's beliefs. During for­ ward reasoning (Step 4), the inference rules are applied to each proposed RD and to our model of the user's be­ liefs in order to postulate the user's possible inferences from this RD. Any new propositions affected by these inferences are then added to the list of propositions to be conveyed (Step 4.2), and are addressed in subsequent calls to Propose-RDs if necessary (Step 4.5). In prin­ ciple, if the system keeps postulating that the user will infer new erroneous beliefs, the algorithm will not termi­ nate. However, in conversations in general, and in tutor­ ing situations in particular, the transfer of information typically takes place at the horizon of a body knowledge that is mutually believed by the conversational partners. Thus, in practice, the inferences from the presented in­ formation reach this body of knowledge quickly, thereby leading to a bounded inference process.

The RDs relevant to our domain are (A) Assertion; (N) Negation; (M) Mention, which acknowledges a cor­ rect belief held by the hearer, e.g., "In addition to Num­ bers, Bracket Simplification applies to Like Terms"; (I) Instantiation; and (J+) Expanded Instantiation, which is an Instantiation annotated with brief comments, e.g.,

Assertions and Negations may be complemented either with Instantiations or with Expanded Instantiations in order to have a stronger effect on a hearer's beliefs. How­ ever, the suitability of a combination of RDs depends on the aspect being conveyed and on the RD being com­ plemented. For example, when conveying the steps of a procedure, A, A+ I and A+ I+ are possible candidates. However, when conveying the domain of a procedure, only A and A+I are applicable, since what is being con­ veyed is that the procedure applies to some domain, not how this is done. Finally, when refuting the domain of a procedure, only Nand N+I+ are applicable, since when illustrating that a procedure does not apply to an object, it is essential to explain where the procedure fails.

Figure 1 depicts a partial trace of the alternatives gen­ erated by Propose-RDs in order to convey the proposi­ tions {PloP3,Ps} in Table 2. The backward reasoning process appears in boldface, and the forward reasoning process in roman font and italics. After each backward reasoning step, the state of the resulting alternative is presented. A state contains (1) the RDs proposed so far; (2) the propositions affected by these RDs; (3) the degree of belief in these ~ropositions as a result from the RDs generated so far tBELIEVED (B), RATHER BE­ LIEVED (RB), CONTRADICTORY {C), UNKNOWN {U), RATHER DISBELIEVED (RD) and DISBELIEVED (D)); and ( 4) the effect of the inferences from the RDs on the user's beliefs in these propositions. This effect is either a quantitative increment or reduction in belief. However, for clarity of presentation, we represent only the trend of this effect, i.e., + (increment), - (reduction) and ± (two or more inferences with opposite effects) .

In the first cycle in Figure 1, the backward reasoning sta~e proposes the following RDs to convey proposition p1 t[Bracket-Simplification use-1 +/-]): (1) A, (2) A+I, and (3) A+J+. Since Bracket Simplification applies to Numbers and to Like Terms, an Instantiation may be generated for each of these domains. Thus, alternatives t2) and (3) spawn two options each: one where the In­ stantiation is performed with respect to Numbers, and another where the Instantiation is performed with re­ spect to Like Terms. However, for the sake of brevity, we limit our discussion to the latter. In the forward reasoning stage, p1 is directly inferred from all three alternatives. In addition, a generalization from A+ I and A+J+, which are instantiated with respect to Like Terms, conveys p3 ([Bracket-Simplification apply-to Like-Terms]).

In the second cycle, the backward reasoning stage pro­ poses the RDs A and A+I to convey proposition Pa (re­ call that A+[+ is not an option in this case). In the forward reasoning stage, the following inferences ensue from both options: (1) a direct inference which yields P3, (2) a generalization which supports the user's incor­ rect belief that [Bracket-Simplification apply-to Algebraic­ Terms] (-,p5), (3) a similarity-based inference which sup­ ports the user's correct belief that [Bracket-Simplification apply-to Numbers] (p4 ), and (4) a uniqueness implicature which infers that Bracket Simplification applies only to Like Terms, thereby contradicting inferences (2) and (3). Note that proposition p4 , which was previously removed from the list of propositions to be conveyed (Section 3.1), is added to this list, since it is affected by a forward infer­ ence. In addition, although p3 is now BELIEVED in both alternatives, in the alternative on the right hand side, this belief is a relatively small increment from RATHER BELIEVED, which was obtained in the first cycle.

In the third cycle, the backward reasoning stage pro­ poses the RD M to convey p4 ([Bracket-Simplification apply-to Numbers]). As stated above, a Mention acknowl­ edges a correct belief held by the hearer, rather than presenting new information. Since inferences from this belief were drawn at the time the belief was acquired, indirect inferences from the Mention should not be con­ sidered. Hence, in the forward inference stage, only p4 is inferred from this RD.

Finally, in the fourth cycle, the backward reason­ ing stage proposes the RDs N and N +I+ to convey proposition p5 UBracket-Simplification ...,(always) apply-to Algebraic-Terms]) (as stated above, N +I is not an op­ tion in this case). In the forward reasoning sta~e, the following inferences ensue from both options: (1) a di­ rect inference which yields p5 , (2) a specialization which contradicts p3 , and (3) a similarity-based inference which contradicts p4 . Note that N + J+ reverses the belief in p5 from RATHER DISBELIEVED to BELIEVED, while N takes it only to CONTRADICTORY.

An alternative can be discarded based on insufficient belief in one or more of the propositions to be conveyed only after RDs for all the propositions have been gener­ ated. This is because an inference from an RD proposed late in the process may support a marginal belief result­ ing from an earlier RD. For instance, upon completion of Propose-RDs, the belief in p5 has not reached an accept­ able level in the leftmost alternative in Figure 1. Hence, this alternative is discarded.

As seen in this process, RDs may be generated at a later stage to convey propositions that have already been conveyed by indirect inferences from earlier RDs. For in­ stance, in cycle 2, right hand column, RDs are generated to convey p3 even though it has been inferred from the A+I which was generated to convey Pl · The rationale for this policy is twofold. Firstly, it is possible that an inference from a later RD will lower the belief in pa, thus requiring that we generate RDs that convey p3 after all. But more importantly, an RD that conveys P3 may be necessary to achieve optimality. For example, this hap­ pens when an RD that conveys P3 directly is also capable of conveying every other proposition in our list. In this case, if the RDs that convey p3 are not generated, the optimal solution will be missed.

The alternatives produced by Propose-RDs may con­ tain redundant RDs. However, at this stage of the con­ tent planning process it is premature to minimize the number of RDs in each alternative, since alternatives that appear promising at this stage may be expanded by RDs that explain the concepts mentioned in these alternatives (Step 3 of WISHFUL). Therefore, the min­ imization process must be performed only after all the RDs have been generated for each alternative.

3.3 Conveying the Concepts in an Alternative

This step receives as input the sets of RDs produced in the previous step . For each of these alternatives, WISH­ FUL ascertains that the hearer understands the concepts mentioned in its RDs well enough to understand these RDs. To this effect, it performs the following actions for each concept in an alternative: (1) it determines the aspects of the concept which are relevant to the under­ standing of the RDs which contain this concept, (2) it determines an attitude for conveying this concept, and (3) it re-activates Steps 1-3 of WISHFUL to generate RDs that convey this concept.

The aspects a hearer must know about a concept in order to understand an RD which contains this concept depend on (1) the main predicate of the propositional part of the RD, and (2) the role of the concept with respect to this predicate. For example, in order to un­ derstand the RD Assert [Bracket-Simplification apply-to Like-Terms], the hearer must know what Like-Terms are and what they look like. Hence, the system returns the aspects membership-class and structure. Since a con­ cept may appear in more than one RD, this process is repeated with respect to all the RDs which mention a particular concept.

The determination of an attitude for conveying the newly determined aspects of a concept is based on the relevance of this concept to the original concept given to the system. That is, the more relevant the concept is to the original concept, the better it should be known by the hearer, and vice versa. This consideration is im­ plemented by changing an initially cautious attitude to daring as the recursive calls to Steps 1-3 of WISHFUL become deeper. A daring attitude is not changed, since it already requires a low level of expertise.

3.4 Minimizing the Number of RDs

This step receives as input several complete sets of RDs, such as the one in Figure 2, which fully convey the in­ tended concept. However, as seen in Section 3.2, these sets of RDs may contain redundant RDs. The problem of selecting the minimum number of RDs which convey the intended information is an optimization problem, which is formally expressed as follows with respect the graph in Figure 2:

The second constraint stipulates that the final belief in each proposition must be greater than a threshold T, which is determined by the attitude of the system. The final belief in a proposition Pk is composed of the pre­ vious belief in Pk plus the effect of the RDs on it. The effect of an RD RD; on the belief in Pk is represented by the weight w;,J:, which is obtained from Step 4.4 of Propose-RDs (Section 3.2). This effect is in turn influ­ enced by the sets of RDs which are used to convey the concepts in this RD. Each of these sets of RDs has an "all or nothing" effect. That is, if { RDj} is required to understand RD;, and { RDj} is removed, then RD; will have no effect on the propositions it addresses. This is represented in the rr component of the second con­ straint, where Vj,i = 1 if {RDj} is required to explain a concept in RD;, and 0, otherwise. The values of v are obtained from Step 3 of WISHFUL (Section 3.3).

Even the easier problem of minimizing the num­ ber of RDs in the middle column of the graph, i.e., Minimize{L;: 1 RD;}, is NP-hard (shown by reduction to the Minimum Cover problem [Garey and Johnson, 1979]). Hence, we need a weak optimization method to minimize each alternative. To this effect, we have chosen Algorithm A* [Nilsson, 1980].

When activating A*, a node in the search graph repre­ sents the conjectured state of the hearer's beliefs, and the operators are the RDs that are applicable to a particular node. A* uses the evaluation function f( n) = g(n)+h(n) for each node n in the search graph, and terminates the search at the node with the lowest value of f. The con­ ditions for the admissibility of A* are: ( 1) g* ( n) ~ g( n), and (2) 0 ~ h(n) ~ h*(n). The first condition is easily satisfied by setting g(n) to the number of RDs generated up to node n. The second condition is satisfied by h = number of cut-sets of the propositions still to be conveyed at node n, where a cut-set is a group of propositions which might be conveyed by means of a single RD. That is, if the propositions to be conveyed are divided into n cut-sets, we will need at least n RDs to convey these propositions. The number of cut-sets for a set of RDs is obtained by iterating over all the RDs in the set, and for each RD, putting in the same cut-set all the propositions which are affected positively by direct or indirect inferences from this RD. Uniqueness implicatures are not consid­ ered, since by themselves they do not convey proposi­ tions, rather they perturb existing beliefs.

To illustrate the calculation of a cut-set, let us consider two of the sets of RDs which were generated by Propose­ RDs to convey propositions {Pl,pa,Ps} (Figure 3). The main difference between these sets stems from the RDs that convey proposition p1 . In the set on the left, A affects only p1 , while in the set on the right, A+I affects both p1 and p3 . In order to calculate the number of cut­ sets in the set on the left, we first inspect A, which results in one cut-set containing p1 . Next, we inspect A+I, which yields a second cut-set for P3 and p4, meaning that these two propositions could conceivably be conveyed by means of the same RD. Note that p5 is not in this cut-set, since it is affected negatively by A+I. Upon inspection of M, no new cut-sets are created, since p4 already belongs to the second cut-set. Finally, when N +I+ is inspected, a third cut-set consisting only of p5 is generated. Like before, p5 is not added to the second cut-set, since N+I+ has a negative effect on p3 and p4 . Thus, the minimum number of RDs we can possibly have in the set on the left is 3. By the same method, we reach a result of 2 for the set on the right.

After activating A*, the alternative on the left remains unchanged with 4 RDs, while the alternative on the right is reduced to 2 RDs, viz A+ I - P1 and N +I+ - PS· Note that the RD which conveys p1 also yields a belief of RATHER BELIEVED with respect to Pa (top right al­ ternative in Figure 1). This belief is acceptable when the system is run with a daring attitude.

3.5 Selecting the Most Concise Set of RDs

When selecting the most concise among the minimized alternatives produced in the previous step, WISHFUL initially retains all the alternatives with the minimal number of RDs. For instance, since the alternative on the left in Figure 3 has 4 RDs after optimization, while that on the right has 2 RDs, the former is discarded. In order to discriminate among the remaining alternatives, those with simple RDs, e.g., A or N, are preferred to those with complex RDs, e.g., A+I or N +I+.

Table 3 contains the final alternative selected by WISHFUL for the example (Bracket-Simplification,

{steps,domain}, daring) which was discussed through­ out this section. The possible realization of these RDs is included as an illustration.

4 Results

WISHFUL was implemented in Sun Common Lisp on a SPARCstation 2. It was run with the cautious and the daring attitude on a variety of examples and student profiles on a small animal classification and on a subset of high-school Algebra. However, owing to space limita­ tions, we report on 8 representative trials in the Algebra domain. These trials where run with two student pro­ files, namely VERY GOOD and MEDIOCRE, and with a cautious and a daring attitude on the example discussed throughout this paper, and on an example where the following propositions had to be conveyed: [Distributive­ law apply-to Algebraic-Termsl, [Distributive-law apply-to like-Terms) and [Distributive-law apply-to Unlike-Terms). The former example took 4 seconds of CPU time, while the latter took 1.25 seconds, with negligible variations for the . different system attitudes and student profiles. The difference in the timings can be attributed to the larger number of alternatives in the longer example, and to the absence of adverse interactions between the infer­ ences from the RDs in the shorter example.

As expected, WISHFUL produced more RDs and ex­ amples for the MEDIOCRE student than for the VERY GOOD student. In addition, WISHFUL's output showed a clear trend whereby a change from a daring attitude to a cautious attitude led to the addition of examples to the already explicit output generated for the MEDIOCRE student. This change was more ·dramatic for the VERY GOOD student. In this case, the daring attitude pro­ duced output such as the one in Table 3, where some of the information is implicitly conveyed, while the cau­ tious attitude stated explicitly all the information to be conveyed, albeit with significantly less examples than for the MEDIOCRE student. This output was informally evaluated by presenting it to several lecturers and tu­ tors in the Department of Computer Science at Monash University. There was general agreement among the in­ terviewed staff regarding the suitability of WJSHFUL's output for both types of students.

5 Conclusion

In this paper, we have offered a mechanism that achieves the seemingly incompatible objectives of generating concise discourse and addressing a hearer's inferences. These inferences have been modeled by means of in­ ference rules, which are applied in backward teasoning mode to propose RDs that are suitable for conveying the intended information, and in forward reasoning mode to <tOnjecture the effect of these RDs on a hearer's beliefs.

These conjectures constitute an essential input to the process which optimizes the number of RDs that convey the intended information.

The discourse generated by WISHFUL is an initial ex­ planation presented to a user. In a complete assistance system or an ITS, such an explanation is typically fol­ lowed by some interaction with the user. Hence, in such a system the beliefs conj((ctured by WISHFUL must be verified and possibly revis'ed after the user asks follow-up questions, or upon inspection of his/her performance.