Adaptive Provision of Evaluation-Oriented Information: Tasks and Techniques

1 Task 1: Predict Overall Evaluations

It is almost inevitable for an EOIP to try to predict how the user£ would evaluate individual objects in the domain if he 2 had complete information about them. For example, though it is clear in the used-car domain that the buying decision will ultimately be made by£, I needs to predict £'s overall evaluations in order to narrow the discussion to one or more

2 For clarity, masculine and neuter pronouns will be used to refer

to£ and I , respectively.

Table 2: Overview of Five General Tasks for an Evaluation­ Oriented Information Provider

1. Predict Overall Evaluations: Anticipate how £ would evaluate one or more domain objects, perhaps relative to one another, given complete knowledge about them.
2. Predict Partial Evaluations: Anticipate the impact that informa­ tion about an attribute of an object would have on £'s evaluation of that object.
3. Interpret Evidence: Update the model of £'s evaluation criteria on the basis of evidence in £'s actions.
4. Elicit Evidence: Induce£ to perform actions that will constitute evidence for the task "Interpret Evidence".
5. Select Dialog Moves: Determine what type of dialog move to make (e.g. formulate recommendation; ask question about £'s criteria; allow £ to act next).

objects.

Almost all EOIPs appear to be based on some particular conceptualization of how £ would evaluate an object given complete information about it. 3 In most cases the concep­ tualization can be seen as a variant of a conceptualization known by the name Multi-Attribute Utility Theory (MAUT) and similar names (see, e.g., [von Winterfeldt and Edwards, 1986]).

1.1 The MAUT Conceptualization

Some basic concepts of this conceptualization are illustrated in Figure 1, which shows part of a value tree that a used-car customer consulting PRACMA might use to evaluate a particu­ lar car. Each leaf corresponds to an attribute, which for each particular object has a level within a given range. For each at­ tribute, £ has a value function which assigns to each possible level a value between 0 and 10 (for example, for the attribute "Mileage", the values might be 10, 3, and 0 for the levels "0 -10,000", "40,000-50,000", and "80,000-90,000", respec­ tively). To take into account differences in the importance of attributes, each branch in the value tree has an importance weight between 0.0 and 1.0. For example, the importance weights on the branches leading down to "Mileage" and "Time to Inspection" specify their relative weights with respect to the value dimension of "Reliability"; the weights on the branch­ es leading down to "Reliability" and "Safety" in turn specify the relative weights of these dimensions with respect to the overall evaluation of the car. The absolute importance weight of each individual attribute (shown below the corresponding leaf in Figure 1) is the product of the weights on the branches leading to it. If£ had complete information about an object, £ could arrive at an overall evaluation by determining the ob­ ject's value with respect to each attribute, multiplying each such value by its absolute importance weight, and adding up the weighted values. 4

3 Strictly speaking, I need not presuppose that£ really evaluates objects in accordance with the conceptualization used, only that it is useful for I to act as if £ did so. Given the constructive, task­ dependent, and situation-dependent nature of human evaluation pro­ cesses (see, e.g., [Payne et at., 1992]), for descriptive purposes any single conceptualization is best viewed as a rough approximation.

Variants of MAUT Used in EO IPs

This basic conceptualization takes different forms in different EOIP systems and sometimes remains implicit.

• t> The SALES ASSISTANT treats the value function for an attribute as a fuzzy membership function representing a concept like "Has at least 32Mb RAM", and the weight of an attribute is represented by a membership func­ tion corresponding to a natural language formulation like "quite important".
• t> CONSULT may, for example, ascribe to £ a "negative preference" for courses beginning after 6 p.m., in effect ascribing a particular value function mapping times of day onto values; the characterization of this negative preference as "strong" in effect assigns to this attribute a high importance weight.
• t> The INFORMATION FILTERING SYSTEM, which uses tech­ niques from Artificial Life, provides an evolving pop­ ulation of agents. Each agent in effect ascribes to £ a simple value tree that it uses to evaluate and recommend news articles. Each attribute corresponds to the presence or absence of a particular keyword (or other feature) in the article being evaluated, and each attribute has at any

4 A single attribute can affect the evaluation of an object with re­ spect to more than one value dimension (e.g., "Horsepower" has im­ plications for both "Sportiness" and "Environmental Friendliness"). Although cases involving these and additional complications are han­ dled by PRACMA (cf. [Schafer, 1994]), a discussion of their proper treatment would exceed the scope of this paper.

time an importance weight, which can change as the agent adapts to £.

Throughout this paper, terminology from the MAUT lit­ erature will be used instead of the terminology used in the original publications on the reference systems.

1.2 Handling Uncertainty About the Evaluator's Criteria

Even assuming that £'s evaluation processes can be described perfectly in terms of a value tree, an EOIP can rarely have a complete and accurate view of £'s evaluation criteria. For ex­ ample, with respect to the value tree in Figure 1, £scan differ widely in the importance weights they attach to value dimen­ sions like "Reliability", and independently of this they may attach idiosyncratic relative weights to individual attributes like "Mileage" .

Treatment in Other EOIPs

Some systems, such as the INFORMATION FILTERING SYSTEM and the SALES ASSISTANT, in effect make use of their best specific estimate as to the content of £'s value tree. They therefore do not distinguish between predictions in which they are confident and those which represent mere guesses. This distinction may in fact be of minor importance if the EOIP evaluates a large number of objects on £'s behalf and if the consequences of an incorrect prediction are not serious.

Other EO IPs represent uncertainty about £'s evaluation cri­ teria explicitly.

• t> When ascribing to £ a particular value function, CoN­ SULT associates with this ascription (a) a confidence rat­ ing and (b) a list of endorsements for the ascription. When predicting how £ would evaluate various courses, the system takes into account only attributes about whose value functions it has at least moderate confidence.

Note that if an EOIP restricts its attention to attributes about which it is confident, it still cannot be confident that its overall predictions are accurate. For example, an object that rates highly with respect to one attribute may be extremely attractive to £ even though I as yet has no evidence that £ assigns high importance to that attribute. It is therefore desirable for I to be able to derive some sort of confidence interval for its predictions of £'s overall evaluations.

to predict and interpret evaluative reactions to a statement.

(Arrows point from parent to child nodes. The darker histograms represent the beliefs the system derives through upward propagation on the basis of t:'s positive reaction to the statement "Its mileage is 40,000"-cf. section 3.)

Managing Uncertainty with Bayesian Networks

This problem (and others to be discussed below) can be han­ dled effectively with the help of Bayesian networks. 5 This approach will be discussed in most detail in connection with PRACMA's handlin~ of Task 2, "Predict partial evaluations"; but some of the basic concepts can be illustrated in terms of the three network nodes depicted in the upper left-hand part of Figure 2. These nodes show how I's uncertainty concerning the importance weights relevant to the attribute "Mileage" can be handled. (Until section 3 we will refer only to the first of the two histograms shown for each node.)

In the node RELATIVE IMPORTANCE OF RELIABILITY FOR E, the first histogram depicts a probability distribution represent­ ing I's initial belief about a variable X, namely the relative weight that the current £ attaches to "Reliability". Where­ as in Figure 1 X simply had the value .30, here I's belief about X is a probability distribution over the possible values that X can assume. For reasons of computational tractability, X is approximated as a discrete variable with five possible values, corresponding to the midpoints of the intervals .00.10, .10- .20, .20- .30, .30-.40, and .40- .50. I's probability distribution for X can therefore be viewed as a five-element vector BEL(x ). 6 In the example, I considers it most prob­ able that [ 's weight is around .1 0 but that the weight might also be as high as about .35. The node RELATIVE IMPORTANCE OF MILEAGE FOR RELIABILITY FOR CUSTOMERS IN GENERAL represents I's belief about the average weight of the mileage attribute, relative to the value dimension of reliability, in the population of customers that I deals with.

5 For theoretical and technical background on Bayesian networks see, e.g. , [Pearl, 1988], whose notation and concepts are adopted in the present paper, or [Neapolitan, 1990].

On the basis of its beliefs about these two variables, I can form a belief about the IMPORTANCE OF MILEAGE FOR E, as indicated by the arrows showing that this third node is a child of the former two parent nodes. But the relationship between the parent nodes and the child node is probabilistic: Even if I knew the exact values of the two variables in the parent nodes, it could not be sure that the value of the variable in the child node was simply their product, because the relative weight that this particular£ attaches to "Mileage" may deviate from the relative weight for customers in general.

In a Bayesian network, a probabilistic relation between two parent nodes corresponding to variables X and Y and a child node corresponding to a variable Z is represented by a matrix of conditional probabilities P(zJx, y) which contains one probability for each possible combination of values of Z, X, and Y . For these particular three nodes, the matrix is generated using a function which specifies that the probability of Z taking a given value z is highest when that value is close to the product of the values x andy of the two parent variables.?

I arrives at a belief concerning the child variable through the standard top-down profagation procedure for singly con­ nected Bayesian networks. In this example, we see that I has a moderate amount of uncertainty about the weight that in­ formation about a car's mileage will have in determining £'s evaluation of it; the probability distribution for IMPORTANCE OF MILEAGE FOR E would be still narrower, for example, if I somehow had acquired a definite belief about the RELATIVE IMPORTANCE OF RELIABILITY FOR E.

This type of uncertainty ultimately affects I's prediction of [ 's overall evaluation of a given car. This prediction task involves many nodes not depicted in Figure 2, but its treat­ ment is largely analogous to that of the prediction of partial evaluations, which is discussed in the following section.

6 For each possible value x of X ,

where e represents all of the evidence received so far.

7 The basic function is given by

where F is the cumulative distribution function for a normal distri­ bution with mean 0 and standard deviation 0.1 0.

8 See, e.g., [Pearl, 1988, chap. 4l. In the present relatively simple case, where there is initially no other evidence concerning the child variable, the resulting belief vector is related to those for the parent nodes as follow:

2 Task 2: Predict Partial Evaluations

In addition to predicting the evaluation of entire objects, an EOIP should be able to anticipate the impact that information about a particular attribute of an object will have on ['s eval­ uation of that object. First, even if I is already certain that a given object should be recommended to £ , I may have to ex­ plain its recommendation. 9 Second, I may in some cases not attempt to evaluate entire objects for£ at all, pursuing instead the more modest goal of efficiently supplying information that allows £ to arrive at evaluations of his own.

2.1 Treatment in Other EOIPs

Some EOIPs supplement their recommendations of an object with a description of those attributes of the object that the system expects to have the greatest impact on £'s evaluation.

• t> In particular, CONSULT illustrates that this sort of selec­ tion of attributes must sometimes concern relative eval­ uations: When recommending an alternative to a uni ­ versity course selected by the user, the system describes only those attributes with respect to which the alternative course is likely to be evaluated substantially higher by£ than the original choice.

This capability for selective description of objects is not required only in natural language systems with a narrow com­ munication bandwidth. For example, systems like the INFOR­ MATION FILTERING SYSTEM often present an overview of a fairly large set of objects, each of which has to be character­ ized briefly. So it may be worthwhile, for example, for I to select an especially evaluation-relevant subset of each object's attributes to be displayed in graphical or tabular form.

2.2 Predicting Partial Evaluations with Bayesian Networks

The way in which Bayesian networks can be applied to this task will be illustrated for a particular type of relative partial evaluation: An evaluation shift is the change in ['s evaluation of an object with respect to a given attribute after £ has re­ ceived information about the object's level with respect to that attribute (cf. [Jameson, 1989]). An evaluation shift is actual­ ly more relevant than an absolute evaluation for determining which facts I should mention. For example, even if I knows that£ assigns a high weight to the attribute "Mileage", there is little point in mentioning that a given car has low mileage if£ already has been told that it is only a few weeks old: The statement could in this case hardly produce a substantial shift in £'s evaluation.

A straightforward way of using Bayesian networks to pre­ dict an evaluation shift would be to make separate predictions of £'s evaluations of an object bef ore and after I's state­ ment with respect to an attribute (e.g., that Car 5's mileage is 40,000). Each of these predictions would make use of I's prediction of IMPORTANCE OF MILEAGE FORE (cf. Figure 2 and the discussion in the previous section); a compari son of the nodes representing the two resulting predictions would give some indication of ['s likely evaluation shift. This method would be invalid, however: I's uncertainty about ['s impor­ tance weights would enter into both of the predictions, leading to much more uncertainty in the prediction of the evaluation shift than would be necessary or justified.

9 [Klein and Shortliffe, 1994] present sophisticated techniques for explaining evaluative decisions which have been arrived at using a particular, known value tree-which may have been acquired either from the user or from an independent expert.

The remaining part of Figure 2 (except for the bottom­ most node, which will be discussed in the next two sections) shows how this problem can be avoided. PRACMA dynamically constructs a partial network like this whenever it considers making a statement about a particular attribute of a ear-in this case, the statement "Its mileage is 40,000". The node E'S PRIOR EXPECTATION ABOUT CARS'S MILEAGE represents I's belief about what [ would consider the most likely mileage for Car 5 before [ obtained any information from I; as the first histogram for the node illustrates, I can initially have only a rather indefinite belief about this expectation. On the basis of this variable, I can try to predict the extent to which ['s unweighted evaluation of Car 5's mileage (on a scale from 0 to 1 0) will shift upward or downward after I's statement. I's belief about this shift is shown in the first histogram for E'S UNWEIGHTED EVALUATION SHIFT FOR CARS'S MILEAGE: I considers it slightly more probable that the shift will be positive than that it will be negative (because 40,000 is a bit more likely to be a lower mileage than [ expects than it is to be a higher one). 10

The node E'S EVALUATION SHIFT FOR CAR S'S MILEAGE is of most relevance for I in deciding what to say, as it reflects the impact that I's statement is likely to have on ['s overall evaluation of Car 5, which of course depends in part on IMPORTANCE OF MILEAGE FOR E. The prediction of this variable on the basis of its two parent variables proceeds in a way similar to that de­ scribed in section 1 for the prediction of IMPORTANCE OF MILEAGE FOR E itself (in both cases the basic underlying relationship is multiplicative). The first histogram for E'S EVALUATION SHIFT FOR CAR s·s MILEAGE shows that I considers it unlikely that its statement will influence ['s overall evaluation (which will be on a scale from 0 to 10) by more than about .1 in either direc­ tion. This example illustrates that it is often possible to make a fairly definite prediction about a change in a variable even if one has only indefinite beliefs about the initial and later levels of the variable- if the uncertainty that is common to the two beliefs is handled appropriately.

3 Task 3: Interpret Evidence

Most EO IPs refine their models of [ on the basis of evidence supplied by [during the interaction. The ways in which [can give useful clues include: explicitly characterizing his evalua­ tion criteria ("I'm interested in politics"), making requests for particular types of information ("What books/courses/articles do you have that involve politics?"), expressing evaluative judgments he has arrived at ("This object [which involves politics] looks good"), and reporting personal characteristics that have implications for his evaluation criteria ("I'm a law student").

3.1 Treatment in Other EOIPs

The most common approach to processing this type of evi­ dence is to adjust one or more parameters of I's model of [

10 The matrix of conditional probabilities linking these two nodes presupposes that E's value function for "Mileage" is similar to the one that I assumes for customers in general, but it takes into account possible idiosyncratic variation.

(e.g., I's representation of the importance of politics for f) in the direction suggested by the evidence, with the magnitude of the adjustment depending on the nature of the evidence.

• t> When an article suggested by one of the INFORMATION FILTERING SYSTEM's agents is evaluated positively by the user, the importance weight associated with each of the article's keywords is increased.
• t> Whenever GRUNDY processes a self-description or an evaluative reaction to a library book from the user, the system adjusts a number of quantitative assessments it has made,-for example, concerning the specific [ 'sin­ terest or concerning the long-term content of the general stereotypes that the system has associated. with the user.

In these systems, the direction and relative magnitudes of the adjustments in I's model of [can be justified fairly plau­ sibly, but there is a good deal of arbitrariness in the details. This limitation may be of minor importance if I will have the opportunity to process a large amount of evidence con­ cerning a given aspect of its model; in such cases the model can ultimately converge on realistic values even if the indi­ vidual adjustments are not optimal. Where evidence is much more limited-for example, when it concerns a specific £ and is acquired during a single interaction-it is desirable for adjustments to I's model to be justifiable more specifically.

3.2 Probabilistic Evidence Interpretation

This goal can be achieved within the Bayesian network frame­ work used by PRACMA, if the relevant aspects of ['s behavior are represented by nodes which have precisely defined proba­ bilistic links to the nodes that represent unobservable states of E. Although the conditional probabilities defining these links may be based on intuitively plausible assumptions made by the designer rather than on empirical data, at least the details of the system's inferences can be understood and justified in terms of these assumptions.

This way of handling evidence in ['s actions is illustrated by the way PRACMA interprets an explicit evaluative reaction like "That's good" following a statement that it has made (cf. Table 3). The type of reaction (including possibly "<no reaction>") that [ produces is represented by a node in the Bayesian network-E'S VERBAL REACTION TO CARS'S MILEAGE in Figure 2. This node distinguishes several categories of eval­ uative verbal reactions that were observed in an unpublished empirical study. The matrix of conditional probabilities link­ ing this node with its parent E'S EVALUATION SHIFT FOR CARS'S MILEAGE were derived indirectly from the data of this study.

Before I observes ['s reaction, I has only an indefinite belief as to what E'S VERBAL REACTION TO CAR S'S MILEAGE will be, as shown in the first histogram for the node. But after [has responded with "That's good", I has a completely definite be­ lief, shown in the second histogram. Now a process of upward propagation can begin, in which the beliefs associated with the ancestor nodes of E'S VERBAL REACTION TO CAR S'S MILEAGE

are updated in the light of the new evidence. 11 The second his­ togram for each ancestor node shows the updated beliefs. I's belief about E'S EVALUATION SHIFT FOR CAR 5'S MILEAGE is most directly affected: It is now almost certain that ['s evaluation shift was in fact positive. Less directly, I confirms that [ex­ pected Car 5 a priori to have a higher mileage than 40,000 (E'S PRIOR EXPECTATION ABOUT CAR 5'S MILEAGE), and I also increases the extent to which it believes that [ assigns high importance to "Reliability" in general and to "Mileage" in particular. Note also the slight positive shift in RELATIVE IMPORTANCE OF MILEAGE FOR RELIABILITY FOR CUSTOMERS IN GENERAL, which shows that I is gradually learning, on the basis of [s actions, about the evaluation criteria of customers in general.

An entirely analogous approach is used in PRACMA to in­ terpret the fact that [ has asked a question about a specific attribute. When, on the other hand, evidence becomes avail­ able that is directly related to ['s evaluation criteria or to a relevant personal characteristic (cf. the examples in Table 3), less complex processing is required. For example, when E says ''I'm especially interested in reliability", a correspond­ ing node is attached directly as a child under the node RELATIVE IMPORTANCE OF RELIABILITY FOR E. The conditional probabilities linking the child node to the parent node reflect the fact that the likelihood of ['s making a statement like this is a posi­ tive function of the actual importance of reliability for E but that the utterance does not uniquely determine any particular degree of importance.

4 Task 4: Elicit Evidence

Given I's need for evidence from [ in order to update its model of [, one natural task for I is to take steps so as to increase the likelihood that useful evidence of particular types will become available. For example, in the car sales domain, professional salespersons emphasize that they actively acquire a model of the customer by asking questions about personal characteristics and evaluation criteria and by encouraging the customer to express evaluative responses ([Simons, 1994 ]).

4.1 Treatment in Other EO IPs

EOIPs that exploit the broad band-width of modern human­ computer interfaces can make it' easy for [to enter information about himself optionally and with a minimum of distraction from his primary task.

• t> The INFORMATION FILTERING SYSTEM allows [, after reading an article, to express his evaluation by clicking on a thumbs-up or thumbs-down icon displayed above the article; and to express interest in particular attributes by highlighting words in the text of the article.

In cases where techniques such as these are not applicable and/or where the consequences of I's use of an inaccurate

11 Upward propagation essentially uses Bayes' Rule to adjust the probability associated with each possible value of a variable in an ancestor node in accordance with the conditional probability of the observed evidence given that value. Although the computations are in general more complex, in the simple case of the two nodes at the bottom of Figure 2, the updated belief vector BEL' ( x) for the parent variable X after the observation Y = y' is related to the prior belief vector BEL( x) as follows:

model can be serious, some more obtrusive elicitation of in­ formation from E may prove inevitable. One issue that then arises is how I can selectively elicit the information that will be of the greatest value. In EO IPs to date, this kind of selection decision has typically been made by the designer, not by the system itself on-line.

• t> GRUNDY always asks a new user to supply some self­ descriptive words, and when it has described a potentially interesting book, it asks [ "Does that sound good?". It is only when [ has given a negative response to a question like this that GRUNDY asks questions chosen for their expected information value: It asks about ['s evaluation of individual attributes of the book, starting with attributes for which I is most uncertain about ['s evaluation.

4.2 Systematic Assessment of Information Value

If I's model of ['s evaluation processes is cast in the form of a Bayesian network, general techniques for predicting the value of new information within this framework (cf. [Pearl, 1988, 6.3-6.4 ]) can be applied. A well-known approach with­ in decision theory involves comparing the expected value of an outcome if a decision is made on the basis of some new information to the expected value if it is made without that information. For example, how much more is a used-car buy­ er's purchase likely to be worth if he performs particular tests on a candidate car before making his choice (see, e.g., [Qi et al., 1994 ])? In the context of evaluation-oriented information provision, this approach would require quantitative evalua­ tion of the ultimate consequences of a decision made by the informant I to elicit (or not to elicit) a given piece of infor­ mation from[. But such consequences are in general hard to anticipate and to quantify. For example, I's failure to elicit a relevant fact about [ might ultimately lead to a less satisfac­ tory decision by [, or it might just cause a lengthening of the interaction between [ and I.

In such cases a useful criterion is often the extent to which new information will reduce the system's uncertainty about particular target variables whose values importantly influence the system's behavior. 12 In an EOIP that uses Bayesian net­ works in the way PRACMA does, interesting target variables include the importance weights that [ assigns to the various value dimensions.

For example, suppose that in the example dialog (Table 3) [ did not spontaneously express any evaluative reaction to I's statement about Car 5's mileage. Then I would have had to decide whether to elicit such a reaction (e.g., by asking "What do you think of that?"). One of the main benefits of doing so would be the kind of reduction in I's uncertainty about the node RELATIVE IMPORTANCE OF RELIABILITY FOR E that

12 The cost C(X) of £ 's uncertainty about a quantitative variable X can be defined in terms of the variance of the probability distribution representing £'s belief about X, i.e.

where J.Lx is the mean of the distribution for X , i.e .

is illustrated by the change from the first to the second his­ togram for that node in Figure 2. Since I doesn't know in advance what type of reaction £ wiJI express, I must in ef­ fect perform the updating shown in Figure 2 for each possible reaction type, weighting the resulting uncertainty reductions by the prior probabilities of the reaction types 13 (these are shown in the first histogram forE'S VERBAL REACTION TO CAR 5'S MILEAGE). Generally speaking, eliciting evaluative reactions is especially worthwhile when a fact has contrary implications for two different relevant dimensions (e.g., high horsepower is positive for "Sportiness" and negative for "Environmental Friendliness"); in such cases, a single reaction by £ often yields considerable information about the importance he as­ signs to the two value dimensions.

I can use the same general technique when deciding whether to elicit other types of reaction by £, such as state­ ments about personal characteristics and evaluation criteria ( cf. the remarks at the end of section 3 on how such state­ ments are interpreted by PRACMA).

5 Task 5: Select Dialog Moves

The five reference systems discussed have iJlustrated a number of types of dialog move that I can make, for example: asking about ['s personal characteristics, answering questions, and volunteering unsolicited information. Though some criteria have been discussed in the preceding sections for choosing a move of a particular type (e.g., deciding which object to recommend), the more general question remains of how I should decide which type of move to make at which time; and when to give£ the chance to make a move.

5.1 Treatment in Other EOIPs

A survey of other EOIPs suggests three general principles with respect to this question:

I . I should try to achieve an efficient and coherent sequence of dialog moves.

• C> The default ordering of the screens in the SALES ASSIS­ TANT follows a sequence that is presumably efficient in most cases: obtaining information about various aspects of [ and then making use of it to recommend products.

2. The criteria for selecting dialog moves should take into account evaluation-relevant information.

• C> CONSULT's decision as to whether to suggest a different university course than the one chosen by [ depends not only on the dialog state but also on whether I has found a course which seems clearly superior.

This dependence of dialog moves on dynamically applied evaluation-relevant criteria makes sense in that the whole point of the interaction is to support £'s evaluation process.

3. Both [ and I should be able to influence the course of the interaction.

• C> The user of the SALES ASSISTANT has the option of ig­ noring the default screen sequence and navigating freely through the system.

Not only do users appreciate this sort of freedom, it also supports the goal of efficiency: Although I knows more about the domain objects than£ does,£ in general knows more about his own evaluation criteria. Because of this distribution of relevant knowledge over the two participants, each participant may at any point be in a better position to determine the direction the dialog should take.

13 Efficient techniques for performing the relevant computations are discussed by [Pearl, 1988, 6.4.2].

5.2 Dialog Control Through Flexible Planning

PRACMA models the process of participating in a dialog in terms of the generation and execution of dialog plans. It uses a planner ([Weis, 1994]) which implements a basically hi­ erarchical planning approach ( cf. [Moore and Paris, 1989 ]) extended by special plan operators for modeling iterations on subgoals.

1. Efficiency and coherence. On the highest level, PRAC­ MA's hierarchy of plan operators divides the dialog into phases corresponding to those found in sales dialogs ( e:g. the phase in which I actively tries to acquire information about£ precedes the phase for presenting information about relevant objects). On a lower level in the hierarchy, for each dialog phase there are several optional strategies that specify sequences which are efficient and correspond to dialog conventions (e.g., for the active acquisition phase, the strategies include "Ask about personal characteristics" and "Ask about requirements").

2. Evaluation-dependence. The applicability conditions of the plan operators refer not only to the nature of the preceding dialog moves but also to aspects of the model of E's evaluation process. In other words, the considerations mentioned in the previous sections that determine which particular move of a given type PRACMA makes-e.g., what kind of evaluation shift a given statement would produce in £-are also used to determine which type of move the system makes at a given moment. This evaluation-dependent determination of what to do next often requires iteration: repeatedly achieving a given subgoal until it no longer appears worthwhile to do so.

3. Mixed initiative. After each of I' s dialog moves, I gives [ a chance to make the next move, even when I has already planned an appropriate next move of its own. 14 To enable PRACMA to accommodate a variety of dialog moves by £, including those which don't fit well into I's plan, the dialog strategies include lower-level tactics, whose selection is in­ fluenced by £'s actions. For example, the strategy "Ask about personal characteristics" includes a tactic which is applicable when£ (unexpectedly) asks a specific question: I answers the question minimally and, after executing this tactic, continues to pursue the same strategy.

6 Conclusions

Table 4 summarizes the advances achieved by the tech­ niques discussed in this paper relative to the overall state of the art in evaluation-oriented information provision.

A more general conclusion is that research in this area can benefit from increased use of relevant theoretical frameworks and techniques that are not specific to this topic. This strategy is analogous, for example, to the strategy underlying recent work that applies numerical uncertainty management tech­ niques to the problem of plan recognition (see, e.g., [Charniak and Goldman, 1993; Bauer, 1995]). This type of research has

14 Simulated facial expressions are currently being integrated through which I will be able to signal, among other things, the extent to which it considers it desirable for [ to make the next move.

Tasks 1 and 2: Predict Overall and Partial Evaluations

• Prediction in terms of a probability distribution, yielding differ­ entiated information to support 'I.'s dialog decisions.
• Simultaneous management of uncertainty with respect to a broad range of variables, from importance weights for t: s in general to the prior expectation of a particular t: concerning an attribute of a particular object.
• Appropriate treatment of uncertainty in the prediction of evalu­ ation shifts and other relative evaluations.

Task 3: Interpret Evidence

• Principled adjustment of 'I.'s beliefs concerning a variety of possible causes of ['s observed behavior.
• Explicit representation of the probabilistic relationships be­ tween the observable behavior oft: and unobservable variables.

Task 4: Elicit Evidence

• Dynamic selection of information-eliciting moves on the basis of context-dependent estimation of the value of the resulting information.

Task 5: Select Dialog Moves

• Integration of dialog planning with quantitative user modeling, permitting flexible support of t:'s evaluation processes.

shown that there is often a good fit between the tasks recur­ rently performed by a particular type of system and existing more general techniques; but that it is nonetheless a challeng­ ing research goal to work out an appropriate conceptualization of a task in terms of these techniques.