Mutual Beliefs in Conversational Systems: Their Role in Referring Expressions

Mutual Beliefs in Conversational Systems Referring Expressions* Their Role in

Gopalan Nadathur and Aravind K. Joshi

Department of Computer and Information Science University of Pennsylvania Philadelphia, Pa 19104

built so that it mirrors in some way the r easoning process of humans, rather than doing reasoning that is pure ly logical. This latter is an important c riterion, since a system to be used i n a conversational environment must be able to reason about the be liefs of others in the same manner that they would about them.

Insofar as producing cooperative behaviour impinges on the task of understanding a nd generating natural l a nguage, it is already evident that considerations of knowledge and be lief are important for natural language processing. However, there are aspects of language processing that are affected more directly by beliefs and knowledge about others and of what beliefs a nd knowledge are shared with others. Conside r for example the aspect of using or understanding a referring expression. In trying to refer to an object one takes recourse to the facts that one thinks or knows one's audience believes or knows; and a system that does not make the assumption that it communicates with people who know all that it knows must be able to do the same .

Thus it is clear that beliefs and knowledge do play a role in underst a nding and using referring expressions. However, it is not c lear what exactly is the role they play. This aspect has been considered earlier in (Clark and Marshall, 1981) and (Pe rrault and Cohen, 1981). The intuition in these analyses seems to be that in using a definite description D to identify a particular object a, the speaker and his/her audience must mutually know (or believe) that the object a uniquely satisfies the description D.* In our opinion, however, this condition is too strong; in cort.le~onar--situations, if the speaker knows ~ believes) that the hearer knows TQribelieves) that an object a satisfies the descript_i_~ D--uniCI\iel~hen - he/she often con.iectures that this is mutualknow~ (~ mutual belie~if there ~reason to dou~it~ Thus a speaker may use-th~ phrase 'the long haired Swede who does not shave during the course of the Wimbledon' to refer to Bjorn Borg even before

* Even though in (Perrault and Cohen, 1981) it is claimed that this need not be a mutual belief, the condition there stated is only a slight weakening

of this condition.

ABSTRACT

Shared knowledge and beliefs affect conversational situations in various ways. One aspect in which they play a role is the choice of r e ferring expressions. It is of interest to analyse this role since a natural language system must be able to decide when it can use a particular referring expression; or al ternatively what a particular expression refers to. In this paper we attempt to formally characterise conditions for these. Specifically, we differ with the traditional notion of mutual knowledge and helief, state a conversational conjecture that convinces us to do so, express a weakened notion in a formal system for reasoning about knowledge, and show how this mi gh t be used to decide on satisfactory referring expressions . It is desirable to express a weakened notion of mutual belief that parallels that for mutual knowledge; this aspect is currently being investigated.

1.0 INTRODUCTION

Representing and reasoning about the knowledge and beliefs of the participants in an interaction is an important consideration for a system like a natural language interface to a knowledge base, designed to exhibit cooperative behaviour. The ability, for example, to

understand the primary intent of a query or statement,

predict the expectations of the participants so as to attempt to satisfy them, or

understand or use referring expressions appr-opriately

depend crucially on this aspect of the system. The problem of designing an adequate r e presentation and reasoning mechanism for knowledge and/or beliefs and of using this to produce the desired behaviour, however, is a non-trivial one. First it is not quite clear what an appropriate representation for knowledge and belief in general is . Then, even if one of these representations is indeed satisfactory, it is not quite clear how the reasoning system is to be

* This work was partially supported by the NSF Grant MCS 81-07290. We would like to thank Eric

Mays for his comments and suggestions.

~e/she knows that it is mutual knowledge that Borg sat i sfies this description .

We attempt to give formal expression to this idea in this paper. In Section 2 we describe a representation system that includes an axiomatisation of mutual knowledge a nd of ignorance. In Section 3 we describe how this system can be used to give expression to the conjecture discussed above.

2 . 0 REPRESENTATION OF KNOWLEDGE

We shall use the representation proposed in (Konolige, 198~) which is based on Sato's K4 (Sato, 1976) and ext ended to include an axiomatisation of ignorance. K4 is a family of languages pa ramet e rised by the choice of propositional l e tters Pr and agents Sp. For a particular choice of Pr and Sp, K4 is the propositional calculus over Pr t ogethe r with a set of indexed unary modal operators [S], S c Sp. The intended meaning of [S]A fo r a ny sen t e nce A is that S knows A. The re is a special, fictitious age nt 0 f Sp, used to axiomat i.se common knowledge; for any sentence A the intended meaning of [O]A is that A is common knowledge. The axi om schemata for K4 are

(Al) All propositional tautologies

(A2) [S]a => a

(A3) [S]a => [S] [S]a

(A4) [S](a => b) => ( [S] a => [S]b)

(AS) [O]a => [0] [S]a

arbit rary sentences. K4 where a and b are includes two rules of inference: modus ponens a => b infer h) a nd from a infer [S]a for any (i.e. from a and necessi tation (i.e. S ~ Sp) .

K4 as defined above has been shown to be decidable. Konolige uses this fact to explici tl y introduce the notion of provability in K4 into the logic. The language of K4 is extended to include a family of unary modal operators indexed by sentences of K4 : these are written as <a> where a is a sentence of K4, and the intended mean ing of <a>b, where a and b are sentences of K4, is that a => b is provable in K4. The new l anguage i s cal l ed KI4. The axioms of KI4 are the n defined to be those of K4 together with the schemat a

(A6) <a>b where K4 1- a =) b

(A7) - <a>b where K4 y.. a => b The two rules of inference a r e retained. Since K4 is decidable, (A6) and (A7) form a recursive set. Further for eve ry a and b that are sentences of K4, eit her <a>b or -<a)b is a theo r em of KI4. Given this and tha t K4 is decidable, it is easy to see that KI4 is also dec idable .

The new logical system is of interest since in it it is possible t o partially characterise an age nt's ignorance. We can partition a n agent's knowledge into two sets - the f irst corresponds to his/her 'co re' knowledge, and the second to the knowledge that is derived from the core knowledge.

Let 8 be the conjunction of the set of sentences that form the core knowledge of the agent S. If now A is [S]B, then if -<A>C is provable in KI4 it can be concluded that the agent S i s ignorant of C. Note that this is only a partial charac t e risati on of S's ignorance; the claim that S knows D if <A>D is deducible in the system is problematic since an agent need not know a ll the logical consequences of his/her core knowledge.

In the rest of this paper we shal l be i nt e r es t ed in interactions tha t involve two participants only. These will be identified as the speaker S and the hea r e r H. Any r eference to KI4 made henceforth will refer t o t he c l ass of those theories for which Sp = {O,H,S}.

3.0 USING AND UNDERSTANDING REFERRING EXPRESSIONS

In thi s discussion we shall restri ct our attenti on to one kind of refe rring expression - definite descriptions. A speaker who uses a definite description refe rentially may be thought of as doing so to enabl e hi s/he r audience t o pick out an object that he/she is talking about. Our objective is to characterise the conditions under which it is safe to use a description D to refer to an ohiect a.

Let P stand for the proposition "the description D in the context C is uniquely satisfied by a". In (Clark and Marshall, 1981) it is c laimed that in order for the speaker t o use D to refer to a, it must be the case that P is mutual knowledge; with respec t to KI4 this amoun ts to saying that [O]P is provable. It i s argued in (Pe rrault and Cohen, 1981) tha t this condi tion is too strong; they present a se ries of exampl es f rom which they conclude (ignoring for the mome nt tha t they are dealing with bel ief rather tha n knowledge) that what is necessary is tha t i n

[S]P (\ [S][H]P 1\ [S] [H] [S]P f\ only a finite number of conjuncts should be fa l se.

Neither of these analyses is quite satisfactory. Fi rst, despite the c l aim in (Perrault and Cohen, 1981), it seems that the speaker must know (or believe) that the hearer knows (or believes ) that P is true in order to use D to refe r to a. If this were not the case the r e is no assurance for the speaker that the hearer will understand wha t he/she is referring to by D and hence will make the proper connection; in fact this is our intuition regarding the examples in (Perrault and Cohen, 1981). Second, a nd most important, in insisting that P be mutual knowledge (or 'almost' a mutual belief as in (Perrault and Cohen, 1981)) an important conversational convention is being ignored- even if P is not mutual knowledge (or a mutual belief) it is often conjectured to be so given some positive evidence and no nega tive evidence.

This consideration leads us to state tha t

<T>[S][H]P A - <T> [S]-[O]P,

where T is [S]B and B is the conjunction of the set of sentences that form the core knowledge of S, is a sufficient* condition for using D to refer to a. Intuitively, this condition says that S knows that H knows that P holds; moreover there is no reason to believe that S knows P is not mutual knowledge .

We can see the implication of this condition with reference to the example in Section 1. While the earlier analyses would permit the use of the description for Borg only in case the association between these two was mutual knowledge, this analysis permits the use of the description for Borg given that the speaker knows that the heare r knows the association.

• A similar analysis yields the following condition that we think is sufficient for understanding that D refers to a

<T')[H]P A -<T'>[H]-[O]P

whe r e T' is [H]B' and B' is the conjunction of the s e t of sentences that form the core knowledge of

H.

4.0 ON USING BELIEF

I n trying to decide whether a definite description may be used to refer, it is necessary to make the distinction between 'successful reference', where the speaker has all the right intentions and has conformed to all the right conventions in using a refe rring expression, and a 'fully consummated refe rence', where uptake is also secured; the criterion to use is that of 'successful reference', as pointed out in (Perrault and Cohen, 1981). One implication of this is that what is of interest are the beliefs of the speaker, and not his/her knowledge.

A set of axiom schemas similar to that of K4 has been developed for belief. In order to introduce the notion of provability into the logic (something that is needed to express the notion of ignorance), it must be shown that the underlying logic is decidable. Since the logic of interest is a propositional one, we conjecture that it is. However this must be proved. We are currently pursuing this aspect. We believe that in this new formal system the ideas expressed in section 3 can be use d to state conditions for the use and understanding of referring expressions that are intuit iye ly more sat is fyi ng.

* This condition is not necessary, because some situations can be constructed where reference may be successful even if it is not the case that <T>[Sl[H]P. (The examples in (Perrault and Cohen, 1981), however, do not seem to be such cases). This conjunct is needed, since otherwise it does not seem warranted to conjecture P as a mutual belief. If this condition is sufficient, then the condition in (Perrault and Cohen, 1981) is too strong, i.e. is not necessary.

5.0 CONCLUSION

In this paper we have considered an issue in which knowledge and be lief play an important role, and we have attempted to express certain intuitions in a formal manner. He grant that there are limitations in the formal expression, not the l eas t of them bei ng that we have used a crucial featur e of propositional modal logics, that they are decidable. The point however is not so much in the solution advocated. hen~-;--but in thatthereis a weaker notio;{)fmutu~kn~edge (and Ofmutuaf belief)tha·t -isoperat ive in practice; ----and"" itiS- this that a system that reasons aboutkno;ledge a~belief in- order--r0 pr~ ~oop<o_':_ative be haviour must--give expression to.

Although we have limited our attention to only referring expressions, there are other situations in which mutual knowledge and beliefs play a role. One such situation is that where in the course of an interaction the two participants discover that their beliefs are incompatible, and enter into a dialogue to correct this situation. Such interactions have been analysed in (Joshi, 1982) in the context of a question-answer system. The assumption there was that in the end one of the participants beliefs should become a mutual belief as a result of the interaction. This requires very strong assumptions on the nature of discourse. A matter to be studied is whether the weakened notion of mutual belief is sufficient for most situations where the notion of mutual belief is needed at all; and if so, whether this makes more realistic the assumptions required to ensure that a clarification dialogue succeeds.