Hypothetically Speaking Default Reasoning and Discourse-Structure

1 Introduction

The theory of non-monotonic reasoning is young (see, e.g., [Reiter, 1980]), and serious implementations are few. Not surprisingly, there is very little methodological background for would-be practitioners to draw upon. 1 There does not yet exist a handbook for the effective use of a default reasoning framework, and we have of­ ten wished for one in our efforts to construct applica­ tions. Such a handbook would include a chapter on good methodologies for building default reasoning ap­ plications, just as the informative and complete Pascal textbook of today includes a chapter on top-down pro­ gramming.

We are trying to build a body of methodological prin­ ciples which may be of use to future practitioners of de­ fault reasoning.

Although we illustrate some of the issues with an ex­ ample that deals with knowledge representation prob­ lems arising in natural language understanding and user modelling, the focus of this paper is the development and application of (default) reasoning methodologies.

·scholar, Canadian Institute for Advanced Research.

1 But see [Etherington, 1983; Poole, 1989b; Poole, 1990;

Kautz, 1987].

The other issues have been dealt with elsewhere (see e.g. [Joshi et al., 1981] and [Csinger, 1991]).

We have considered some of the elements that might participate in a theory of communications, and have ar­ gued that these can be represented within a default rea­ soning framework [Csinger and Poole, 1989]. 2 Through the following example, we examine some general design issues we have faced in implementing our theory.

Example 1- Gas or Cigarettes?: Someone stops you on the road and asks you for the lo­ cation of the nearest gas station. What do you say or do? It depends, of course, on the reasons for which you believe you are being asked, and upon what you happen to know at the time. 3 For instance, in addition to knowing the location of the gas station ("around the corner ... "), you might know that it is closed. Under reasonable assumptions of cooperative­ ness [Grice, 1975], you might want to include this knowledge in your response (" ... but it's closed") [Mercer and Rosenberg, 1984]. If, how­ ever, you think the question arises not from the need for gas but from the desire for cigarettes or cold Beer, you might want to explain that there is a 24 hour shop in another direction ...

This example is intended to show that the mental states of interlocutors should participate in a theory of communication. It also provides a useful excursion into representation issues for hypothetical reasoning systems.

The rest of this paper is structured as follows: Sec­ tion 2 is a brief review of some existing work on method­ ology, introducing the terms by which our method will be described. Section 3 considers the alternatives for for­ malizing our domain, in terms of a search for appropriate constraints on the communication process. We conclude with a brief summary.

2 That paper showed how to use a hypothetical reasoning system in a natural language environment to determine the presuppositions and implicatures of utterances as part of the process by which to derive the beliefs of the speaker.

3 The example is presented from the point of view of a fic­ titious hearer, but similar considerations apply to the dual of the example, presented from the point of view of the speaker. Such a dual rendition might begin as follows: You are out of cigarettes and don't know what to do. You know that in this part of the world, gas stations generally sell cigarettes .. .

2 Default-Programming Methodology

To make the following presentation more precise, we use the simple hypothetical reasoning framework of Theo­ rist [Poole et al., 1987], where F is a set of closed for­ mulae, called the "facts", and H is a set of (possibly open) formulae called "possible hypotheses." The fol­ lowing definitions are relevant:

Definition 1 (Scenario) A scenario is F U D where D is a set of ground instances of ele­ ments of H such that F U D is consistent.

Definition 2 (Explanation) If g is a closed formula, an explanation of g is a scenario that implies g. Such a g is referred to here as an explanandum (the plural being, of course, explananda).

Definition 3 {Extension) an extension is the set of logical consequences of a maximal (with respect to set inclusion) scenario.

There's more than one way to use a hypothetical rea­ soning formalism. You can use it at least for prediction and for abduction, often in a single domain or problem.

Theorist is particularly of interest because the same formal definition allows for both default and abductive reasoning [Poole, 1989a]. It is also implemented; the examples provided in this paper have been tested on a running version of the program.

These different uses of Theorist can be characterized along two dimensions:

• Status of Explananda, and
• Status of Assumptions

2.1 Status of Explananda

The first dimension concerns whether the explanandum is known or not. This distinction corresponds to a choice between the following:

• Abduction: The system regards the explanandum {the observation of the world or the design objective) as given, and needs to find an explanation for it. The idea is to find assumptions that imply the goal. We consider all explanations of the goal as possible descriptions of the world.
• Prediction: The system does not know if the explanan­ dum is true, and the idea is to determine what can be predicted from the facts (the general knowledge and the observation or design objective).

The issue is whether the explanandum is known to be true or whether it is something that has to be de­ termined. For instance, if a reasoning agent knows (or has as defaults) that a -+ b and that a, the agent can predict b from its knowledge. Another agent who also knows that a -+ b, as well as b, might be able to assume in the absence of contradictory evidence that a. The first agent is using prediction, while the second agent is using abduction.

One interesting difference between abduction and pre­ diction is in the relevance of counter-arguments. For in­ stance, when predicting g, it is important to know if -.g can also be explained. In abduction, however, an expla· nation of -.g is irrelevant [Poole, 1989a].

2.2 Status of Assumptions

Along the other dimension we can distinguish between the two types of tasks:

• Design tasks [Finger and Genesereth, 1985] are those in which the system can choose any hypotheses it wants. For example, a system can choose the com· ponents of the design in order to fulfil its design objective, or choose utterances to make in order to achieve a discourse goal.

A consistency check is used to rule out impossible designs. All other sets of components that fulfil the goal are possible, and the system can choose the "best design" to suit its goal.

Design can be done abductively to try to hypothe­ size components in order to imply a design goal [Fin· ger and Genesereth, 1985]. Alternatively, design can be done predictively to derive a design from goals and any hypotheses we care to choose.

• Recognition tasks are those in which the underlying reality is unknown, and all we can do is to guess at it based on the observations we make about it. This definition includes diagnosis, scene recognition and plan recognition.

Recognition can also be l_>erformed abductively or predictively [Poole, 1989bj. In an abductive frame­ work, each explanation is a possible description of the world, while the disjunction of all explanations is the description of the world. In the predic­ tive framework, an appealing strategy is to predict something only if it is explained from the observa· tions even when an adversary chooses the hypothe­ ses [Poole, 1989a], which corresponds to member· ship in all extensions.

This distinction turns on whether the system is free to choose any hypothesis that it wants or whether it must try to "guess" some hypothesis that "nature" or an adversary has already chosen.

For example, agents who know only that there is to be a meeting on the hour, sometime between 09:00 and 12:30, but not at 10:00, are able to make only disjune· tive statements about when it will take place; they rec· ognize that the meeting is at 09:00 or 11:00 or 12:00. In contrast, the agent organizing (designing) the meeting is free to pick any time that is consistent with its own knowledge. The planning agent is free to choose that the meeting will take place at 11:00.

Referring to our gas-station example, the Speaker is free to design any utterance she thinks will satisfy her goal. The Hearer, on the other hand, may be able to derive only that the Speaker wants gas or cigarettes or beer. The Speaker hopefully knows what she means; the Hearer is never certain.

Note that these frameworks are different ways to use the same formal system for different purposes. In order to use the system we have to choose one way to imple­ ment our domain.

In general, there are not enough constraints in a do­ main to uniquely determine the approach that the rea­ soning system should take in formalizing its characteris­ tics [Poole, 1989b]. The 'causality' in the domain does not uniquely constrain its default-reasoning axiomatiza­ tion.

3 Domain Formulation

We now turn to formulating the simple gas station do­ main within the default reasoning framework. The prob­ lem of finding the right constraints on the domain breaks down into the problem of where to place the interlocutors of the Speaker-Hearer pair on the domain-formulation grid of Table 1. 4

As we have presented the domain, there are essentially two kinds of information available to, and distributed be­ tween, the interlocutor pair: the Speaker knows mental­ state5 and designs utterances, while the Hearer knows utterances and recognizes mental-state. These aspects of the domain allow us to conclude that it is the Speaker­ agent that occupies the first row of the domain formu­ lation grid, and that the Hearer-agent will occupy the second. For convenience, we have labelled the agents in Table 2 with the coordinates of the box they occupy in it.

3.1 Axiomatizing the Domain

Let us consider each of the four blocks in the Domain­ Formulation Grid, beginning with the top-left corner, which represents a speaker performing abduction for de­ sign of the utterance.

• Speakern When the Speaker is doing design by abduc­ tion, she seeks to find explanations of her goals in terms of suitable utterances. These considerations force an axiomatization of the domain according to the schema: utterance::::}mental-state.
• Speaker12 When the Speaker is doing design by predic­ tion, she attempts to derive utterances from knowl­ edge of her goals, which enforces an axiomatization that adheres to: mental-state::::}utterance.

Hearer21 When the Hearer is doing recognition by ab­ duction, he makes assumptions about the mental state of the speaker to explain what he knows (the utterance). Such a process is supported by an ax­ iomatization of the form: mental-state::::}utterance.

4 The grid merely summarizes some of the different pos­ sible uses of the hypothetical reasoning formalism; different problems/domains fall into different boxes, corresponding to different uses of the reasoning system.

5 We do not attach ontological significance to the use of terms like 'belief' and 'goal'; they are merely components of the (mental) states ·of the agents participating in a discourse. These agents may or may not be human, and the anthropo­ morphism is purely illustrative.

H earer12 When the Hearer is doing recognition by pre­ diction, he reasons from what he knows (the ut­ terance) to find possible speaker mental states that might be responsible. This process requires an ax­ iomatization of the form: utterance::::}mental-state.

The domain can be implemented in at least four dif­ ferent ways, corresponding to the four different possible combinations of Speaker and Hearer, as represented in the domain formulation grid.

3.2 The Shared-Information Constraint

When an agent alternates between speaking and hearing, we want to support both of these roles with a single, minimal knowledge base. Note that this is not possible if we insist that a single agent use only one reasoning strategy: if we implement an agent with only abductive reasoning capabilities, we force different representations upon the knowledge required for design and recognition (as described in Section 3.1).

Regardless of which view of the communication do­ main 'causality' we adopt as the developer of a hypo­ thetical reasoning system ( i.e.,whether we adopt the view that mental state influences utterance content - a speaker's view, or that utterances have perlocution­ ary effects upon mental state - a hearer's view), the domain-formulation grid encourages an interesting dual­ ity: for the Speaker and Hearer to use the same repre­ sentation, they must use different reasoning strategies. I.e., one agent will be an abductive one, and the other predictive.

Of the four possible implementations, only two per­ mit the sharing of information in the aforementioned, desired fashion. These are I) Speaker11 with Hearer22 , and II) Speaker12 with Hearer21 · These two combina­ tions of Speaker and Hearer are referred to from now on as Case I and Case II, respectively.

3.3 The Two Alternative Strategies

Accepting the argument for mutually represented infor­ mation, and adopting the Shared Information Constraint in the formulation of the domain, there remain two al­ ternatives: any domain is likely to admit of this kind of 'vagueness', which is not unlike the problem of choosing an algorithm in a conventional programming language.

In both Case I and Case II, some beliefs are assum­ able by both the Speaker and the Hearer agents. These have been provided to Theorist by setting H, the set of hypotheses, to the following:

The following interpretations are intended 6 :

• h m {hearer believes) speaker believes speaker has money,
• go (hearer believes) speaker believes the gas station is open,
• kw (hearer believes) speaker believes hearer knows where the gas station is located,
• atk (hearer believes) speaker is asking to know (relevance),
• d kw (hearer believes) speaker doesn't know lo­ cation of station,
• gg (hearer believes) speaker wants to know where the gas station is in order to get gas.
• goa l{get-gas) (hearer believes) it is a goal of speaker to go and get gas,
• subgoal(know-where) (hearer believes) it is a subgoal 7 of speaker to know where the nearest gas station is,
• subgoal(go-to-gas) (hearer believes) it is a sub­ goal of speaker to go (now) to the nearest gas station,
• utt(ask-where-gas) speaker asks where the nearest gas station is.

3.3.1 Case I: Design by Abduction, Recognition by Prediction

Choosing the axiomatization of Case I means the Hearer agent uses prediction, while the Speaker agent uses abduction, and that the facts will be of the form: utterance => mental-state. For example: 8

The Speaker's View: In adopting the abductive ap­ proach for the Speaker, we add to H 1 the predicate utt(X), for some X, indicating that the Speaker is free to use any utterance available to her in achieving her goal. We engage the abductive mechanism of Theorist by ask­ ing it to explain goal(get-gas), for which it provides the explanation:

6 Inferences with these predicates actually take place within modal contexts, but such details would only obfus­ cate the message we are trying to get across in this paper. hm, for instance, should read for the speaker: bel(s,hm(s)), and for the hearer: bel(h,bel(s,hm(s))).

7 The distinction between goals and subgoals is purely syn­ tactic. The subgoals are those goals of the speaker that are not appropriate for the hearer to refer to as the goals of the speaker.

8 The hypothesis gg can be seen as the name of the de­ fault [Poole, 1989a).

In other words, Theorist has licensed, via the stated assumptions, the design of utt(ask-where-gas). This is to be interpreted as utterance of the question Where is the (nearest) gas station?

The Hearer's View: In adopting the predictive ap­ proach for the Hearer, we augment F1 with the predicate utt(ask-where-gas) and ask Theorist to predict goai{X), for some X; in other words, we ask for the goal of the Speaker given the utterance. There is a single extension containing:

From this extension we predict goal(get-gas), i.e.,that it is a goal of the Speaker to get gas.

3.3.2 Case II: Design by Prediction, Recognition by Abduction

Choosing the axiomatization of Case II means the Hearer agent uses abduction, while the Speaker agent uses prediction, and that the facts will be represented in the form: mental-state => utterance.

The Speaker's View: To use Theorist to predict the Speaker's discourse goal, we add to Fu what the Speaker knows: goal(get-gas), and we instruct Theorist to explain utt(X) for some X; i.e., we see what utterance is in an extension given the goal. There is one extension contain­ ing the following explanation for utt( ask-where-gas):

So the agent should ask where the gas station is.

The Hearer's View: The Hearer needs to arrive at an explanation of his observation of the Speaker's utterance. To use Theorist in this way, we add to HI I a predicate licensing assumptions about the Speaker's mental state: goal(X). We then ask the system to explain the observa­ tion utt( ask-where-gas). Theorist provides the following explanation:

3.4 Multiple Extensions

So far, we have ignored the myriad other reasons why the speaker agent of our example might have uttered her query; there are many reasons to ask for the location of the nearest gas station. There might also be other ways to find gas stations besides asking potentially unreliable strangers. To complete the picture, we add to the rep­ resentations new facts and defaults to express the ideas that another reason for going to gas stations is to buy cigarettes, and that just driving around is also a way to find gas stations.

H is first of all augmented with the following:

{ gc, dtk, gggc }

The following interpretations are intended:

• gc (hearer believes) speaker wants to know where the gas station is in order to get cigarettes,
• dtk (hearer believes) speaker is going to drive around in order to find out where a gas station is,
• gggc (hearer believes) speaker wants to go to the gas station in order to get cigarettes (as opposed to going to the corner store, for example),
• do{drive) agent (who would otherwise be the speaker) drives car around,
• goal(get-cigs) (hearer believes) it is a goal of speaker to go and get cigarettes.

3.4.1 Case I Revisited

To Fr we add:

{ subgoal(know-where) A go A gc A hm => goal{get-cigs ), dtk A do( drive) => subgoal(know-where) }

Speaker: With the addition to Hr of utt(X) and do(X), there are two designs (two explanations) for either goal(get-cigs) or goal(get-gas). For example, goal(get­ gas) has explanations:

D1·k = { hm, go, kw, atk, gg, utt.(ask-where-gas)} Ddrive = { hm, go, dtk, gg, do(dnve)}

So the Speaker can ask where the gas station is or drive around to find one. Suppose that she asks.

Hearer: We once again augment the set of facts with what the Hearer knows, namely utt(ask-where-gas), 9 and ask Theorist to predict goai(X).

There are two extensions, corresponding to the fol­ lowing explanations, from which we predict goal(get­ cigs)Vgoal(get-gas ).

3.4.2 Case II Revisited

To FII we add 10 :

{ goal(get-cigs) A go A hm A gggc => subgoal(go-to-gas), dtk A subgoal(know-where) => do(drive),

atk A dtk => false }

9 For technical reasons we also need to add an integrity constraint gg A gc => false. The recognizer does not want to assume both that the speaker is going for gas and that the speaker is going for cigarettes. This does not mean that the speaker is not going for both, but rather that conservatism will not allow the assumption of both. This is a general technique for making conservative predictions [Kautz, 1987).

10 The integrity constraint (rule implying false) is again used here to make two extensions. It is up to the speaker to choose one of these two assumptions (i.e., whether to ask to know where the gas station is, or drive to know where it is).

Speaker: For either of goal(get-cigs) or goal(get-gas), added as facts, there are two extensions, corresponding to two designs. For example, for goal{get-gas), the two extensions correspond to:

Hearer: We once again augment the set of allowable assumptions with goai(X), and ask the system to explain utt(ask-where-gas). Theorist provides the following ex­ planations:

3.5 Summary

Formalisms for hypothetical reasoning can be used ab­ ductively or predictively. Theorist is one such formal­ ism; it has been applied in this section to an illustrative example in the domain of inter-agent communication. Agents in such domains rely heavily upon shared knowl­ edge [Joshi et al., 1981] [Brennan, 1991] which should be represented in a form that supports the inferences of both speakers (as utterance designers) and hearers (as goal or belief recognizers) .U These considerations motivate the modelling of agents that are dual in the sense that to share a common representation of principles which govern communication, interlocuting agents can not reason with the same strategy. In the example pre­ sented, we showed two obvious ways in which the domain might be axiomatized, and then demonstrated this du­ ality using Theorist; in each axiomatization, the shared­ information constraint results in a Speaker-Hearer pair of homogeneous agents where each agent uses a different strategy (or, equivalently, a single agent uses a different strategy for design and for recognition, respectively).

4 Conclusions

Finding enough constraints in a domain to uniquely de­ fine its default axiomatization is not usually possible. Default implementations can be classified along (at least) two dimensions: the assumption and explananda status dimensions, which we have represented as the rows and columns of the domain-formulation grid shown in Tables 1 and 2. The domain formulation task can be superfi­ cially regarded as one of finding how the domain fits into the grid's representation framework. The example of the simple communication domain demonstrates this process, and is particularly illustrative for a number of reasons:

• it exhibits aspects along both dimensions of the space defined in Section 2,
• it is characteristic of the plurality of implementation strategies of which many domains will admit,

11 These considerations are not restricted to natural lan­ guage environments. Another example of shared principles or convention is social law, highly pertinent, for instance, in the design of societies of interacting robots [Shoham, 1990), [Shoham and Tennenholtz, 1992). The observations in this paper may be also applicable to such domains.

• it brings to light a general constraining principle, the shared-information constraint, whose consid­ eration led to an implementation that allows the speaker and hearer agents to share an axiomatiza­ tion of the domain,
• it highlights a duality between interlocuting agents; applying the shared-information constraint forces homogeneous speaker and hearer agents to use dif­ ferent reasoning strategies, necessarily placing these agents at different points along the explananda di­ mension defined in Section 2.

A general observation stemming from this work and which may lead to further research is preliminary ev­ idence for the claim that extant logical databases de­ signed for planning applications might be pressed into service as databases for recognition applications, and vice-versa. An important application area which springs to mind is on-line user help systems that model the user to anticipate errors as well as to provide pro-active ad­ vice [Thies and Berger, 1992]; such a system is both hearer and speaker, as described in this paper. An im­ portant question to be answered in this regard concerns the amount of attention that must be devoted during the design of the database to ensuring that this dual usage will be possible. 12

The cognitive ramifications for designing societies of heterogeneous agents may be of interest as well. It is noteworthy that in the context of the work presented in this paper, there is no way to decide externally, whether an agent engaged in communication is employing a par­ ticular axiomatization (e.g. , Case I or Case II, etc.), or using a particular inference strategy (i .e., abduction or prediction).

Acknowledgements

This research was supported by Canadian National Sci­ ences and Engineering Research Council (NSERC) grant OGP0044121, and by Project B5 of the Institute for Robotics and Intelligent Systems. Thanks to Michael Horsch and Veronica Becher for timely and considered criticism.