Multiple Agents and the Heuristic Ascription of Belief

1. Introduction

We describe a computational model of beliefs for natural language understanding, planning and reason­ ing. In particular we are interested in generating com­ plex belief structures known as points of view (what an agent believes about some topic). The model is based upon prior work reported in Wilks and Bien { 1979; 1983).

A Prolog program ( ViewGen) for generating points of view is discussed, that ascribes belief using default reasoning.

2. Background

A point of view is a set of beliefs held about some topic by an agent. A nested point of view is a set of beliefs about some topic that one agent believes another agent believes ... another agent holds. For example agent A may believe that agent B believes that agent C has some set of beliefs about world hunger. We use a shorthand (as in figure 1) to represent a nested point of view.

Figure 1. A's view of B's view of C's view of World Hunger.

3. Heuristics for Constnlcting Point. ot View: a con­ textual focus ot beliefs.

The question arises of how to select the initial beliefs about a topic. Our solution to this problem is essentially simple. The system's belief space is divided into a number of topic specific sub-spaces. These sub­ spaces may be thought of as a less permanent version of frames (Minsky, 1975) or more suitably in terms of (Wilks, 1 977) as pseudo-texts (henceforth PTs). In effect, a PT is a set of unsorted, unrefined items of knowledge.

These PTs are general items and are not only stored for individual human beings, but also for groups of humans, objects, and abstract ideas. Their hierarchial and inheritance relations are discussed in Wilks (ibid).

Our method of restricting the initial set of beliefs is to form this set from a very small number of PTs; for example if the system is a medical diagnostician, being used to advise a patient on thalassemia, then the initial set of beliefs may be just those concerning thalassemia. We term the initial belief set the contextual focus. We now turn to the process of constructing a point of view from· a given contextual focus.

3.1. Generation ot Point. of View

Points of view are represented by structures known as environments; environments are structures that consist of a sequence of agents and a set of beliefs (e.g. ( <a,b>,B) represents that a believes -b believes the set of beliefs B).

The process of generating an environment may be regarded as a decision mechanism that ascribes beliefs from one environment to another.

Assume that our contextual focus is as follows:

This represents the beliefs held by the sytem that an agent known as the User dislikes another agent known as Frank; that the system likes Frank; that the Earth is round; and that the system believes that Frank believes the Earth is flat. Given this set of beliefs how do we generate what the system believes Frank believes about the contextual focus?

The proposal (Wilks & Bien, 1979;1983) is that a nesting should be generated by a form of default rea­ soning, using a default rule for ascription of beliefs. The default ascriptional rule is to assume that one's view of another person's view is the same as one's own except where there is explicit evidence to the contrary. Applying this rule to (figure 2) we get the system's view of Frank's view (figure 3).

Let us examine this example closely.· The belief of the system in (figure 2) that the system likes Frank has been ascribed into the PT for Frank, i.e. it is now a belief of the system that Frank believes that the system likes him. The same is true of the system's belief that the user dislikes Frank. However the system's belief that the Earth is round has been superceded by the already existent belief, that the system believes Frank holds, that the E"arth is flat The result is (figure 3) and we may now reason with the environment of the system's views of Frank's views 1 , (that we shall call s.,temFNolr) ·

Nested points of view are generated using a method called pushing down environmen1B 2 , that recursively ascribes beliefs from one environment to another to achieve the nesting.

Suppose that we wish to construct the system's view of the user's view of Frank's view about some context, (we shall write this as s,etemu .. ,,..o.t( 'conte:rt) as a shorthand). To construct this we firstly construct the system's view of the user's view and push the system's view of Frank's view down into this. For example presume that we have the contextual focus shown in (figure 4).

We construct the system's view of the user's view according to our default rule of ascription to get (figure 5).

We have available the system's view of Frank's view that is shown in (figure 6).

Now, pushing the environment of (figure 5) down into the environment of (figure 6) results in the environment shown in (figure 7).

To construct a deeper nesting we continually apply this method. So to construct SyBtemu ... F .. · · we SJ#tm{'u·les() push the system's view down into the user, push the result of that down into Frank, and finally push the result of that operation down into the system. The mechanism is described in more detail in (Ballim, 1986).

4. Counter Evidence to the Default Ascription of Belief

Thus far we have shown how the default rule can ascribe belief to an agent if there is no further informa­ tion (as in ascribJng the belief that Sally dislikes Frank, to Sally in figures 2,3) and how the rule can be overrid­ den by an a priori belief that contradicts the belief that we are attempting to ascribe (as in figures 4,5). We now consider more complex cases.

4.1. Atypical Beliefs

We identify a special class of belief (known as atyp­ ical belie[) that requires a rule opposite to that of default ascription.

An atypical belief is a belief that is held by an agent but would not be held generally by other agents. The class of atypical beliefs covers such areas as self knowledge, secrets, expertise and knowledge of uncom­ mon domains (such as the believer's hobbies, skills, etc.).

So, for example, the belief that the Earth is flat is atypical. An important point must be made here. In terms of a specific agent the foregoing definition is insufficient. For a belief to be considered atypical, with respect to an agent, the agent must believe the belief to be atypical, i.e., I may believe you to have an atypical belief, however, I may also believe that you think it is a typically held belief. So while I believe it to be atypical, you believe it to be typical.

For the class of atypical beliefs the rule should be not to ascribe unless one has explicit evidence to justify ascribing the belief. The problem is one of represent­ ing and handling a wide range of types of atypical beliefs. The introduction of meta-beliefs is one possible solution, because meta-beliefs enable explicit represen­ tation of atypical beliefs (i.e., for atypical belief p, have the meta-belief atypical(p)). Due to the wide range of atypical beliefs, and to the problems that they pose, we use a special representation to handle them.

4.2. Intensional Descriptions and Atypical Belief

McCarthy and others have suggested that lambda expressions be used to represent knowledge of values. In (Wilks, 1986) it is proposed that expertise may be expressed within a system by use of lambda expressions with restrictions on the capable evaluators of each such lambda expression. Knowing or having the belief represented by the lambda expression means that the agent is capable of evaluating the expression. So the representation for a cure for tuberculosis is:

where the only capable evaluators are those known to be MDs (medical doctors). These lambda expressions can be viewed as intensional expressions, i.e. expres­ sions that return the value of some intensional descrip­ tion (cf. Barnden 1983; Maida, 1983). Beliefs involving such intensional expressions are generally atypical as shown by the problems of iterated propositional atti­ tudes that involve intensional descriptions ( Creary, 1979; Maida, 1983).

We feel that the problems of expressing beliefs about intensional descriptions are so closely aligned with those of atypical beliefs in general that a. represen­ tation for differing beliefs about the referent of inten­ sional descriptions can be used for atypical beliefs.

4.2.1. A Taxonomy of Meta-Beliefs about Values

The form of representation suggested in (Wilks, 1986) allows expressions that can only be evaluated by specific agents or classes of agents. This is a first step towards representing atypical belief, however, it is insufficient.

Consider the major factor that makes a belief atypical; some agent believes that a belief held by another agent is not commonly held. A belief about another belief is known as a metarbelief. It is the meta-beliefs about a belief that mark a belief as atypi­ cal. An atypical belief can have a large num her of meta-beliefs associated with it.

These meta-beliefs can often be classified accord­ ing to the relation that they define between an agent and the belief with which they are concerned. We pro­ pose a taxonomy of meta-beliefs (beliefs about what agents believe is the value of some expression) as shown in (figure 8).

Consider the standard belief about an agent's phone number (call this belief P), i.e., the belief is that the agent's phone number is some value. An agent {A) may have a number of meta-beliefs concerning this belief P. In figure 8 we see that agent A may believe

another agent (B) 3 to be either aware or else unaware of the belief (P). Somebody who does not know of John can hardly have beliefs about John's phone number, and so that person should be unaware of any beliefs about John's phone number.

Further types of meta-belief are possible if A believes B is aware of P. A may believe that B is unaware of the value of P. For example, I may believe that you kriow that John has a phone number but that you do not know what his phone number is.

If agent A believes that agent B does know the value of P, then A may either know what B believes is the value, or else A may not know what B believes is the value of P. I may know that you believe John's phone number to be "505-526-5466", or I may simply not know what you believe is his phone number.

If A knows what B believes is the value of P, then A may decide whether B is correct or incorrect in his belief, according to what A believes is the correct value, i.e., if I believe that John's phone number is 505-5255466, and I believe that you believe it's 505-526-5466, then I believe that you are incorrect in your belief about John's phone number.

If A does not know what B believes is the value of P, it is possible that A can use other information to determine whether B is correct or incorrect in his belief about the value of P. For example, if you have not seen John m years, and he has moved house since you last saw him {but you do not know that he has moved house) although you believe that you know his phone number, I believe that you have his phone number wrong. I can believe this even if I do not know what his previous phone number was.

The ability to represent meta-beliefs, of the type described above, is crucial to. the process of ascribing belief. Lambda Formulas are an extension of lambda expressions that allow the meta-beliefs of a belief to be represented with their associated belief.

4.3. Lambda Formulas

Lambda expressions are finite partial functions. They are computable and map into a finite range of values. We extend the lambda expression representa­ tion to a Lambda Formula so we can represent oppos­ ing views on the value of such an expression 4 · For example,

represents an expression that evaluates to John's phone number for John, but is unevaluable to any other agent. The imposition of John as a capable evaluator of the lambda expression {henceforth >.­ expression) is equivalent to adding an extra parameter to the expression; the extra parameter being the agent performing the evaluation.

The list of capable evaluators is not necessarily a constant because our beliefs may vary regarding who are the capable evaluators of an expression. Also different evaluators may evaluate the expression to different values, that is also subject to each individual's beliefs.

We want to express different agents as being capa­ ble of evaluating such an expression but to different values. We propose a more complex form of the capa­ ble evaluators list proposed in {Wilks, 1986). A typical expression in the augmented representation is shown in {figure 9).

Figure 9. Augmented Lambda Expression for the Cure for Tuberculosis

Figure 9 contains n sets of capable evaluators and the values to which they evaluate the expression. The basic set of capable evaluators has been replaced by a set of pairs, consisting of a set of capable evaluators and the value that they return. A typical entry, for example, <{Sally, Paul}, v.>, is called a Capable_j;valuators-Value pair (abbreviated to CEV pair). It is stipulated that each value v; must be of the same structure and that the >.-expression returns this structure.

The set of CEV pairs is a function table represen­ tation of the >.-expression. We refer to the >.-expression and its function table as a >.-formula.

4.4. Unknown Values

In the original representation, values that are unk­ nown to an agent are represented by the agent not being a capable evaluator. In other words, awareness of the value of a >.-expression is represented by being able to evaluate the >.-expression. In figure 8 this would be equivalent to replacing the section below "aware of the value of P" by "the correct value. " The original representation does not handle problems of awareness of P with sufficient power.

Being capable of evaluating the expression is still the criterion for knowing what the expression represents. Now, however, by the introduction of what we call Uncertain Values and Uncertain but Incorrect Values, we are able to express more with the ;-epresen­ tation.

An uncertain value is a value (of a CEV pair) that is unknown to an agent, i.e., the agent is aware that the value exists but not what the value is. This uncertain value may or may not be equal to a known value or some other uncertain value. Thus, the agent can represent the value that another agent believes is the value of a >.-expression without knowing what the value is.

U ncertain_but_incorrect values are known by the agent to be different from . the value that the ag~nt believes to be correct. In_ other words the value, while unknown to the agent, is believed by the agent to be wrong (the meta-beliefs that A believes that what B believes is the value of P is wrong, even though A does not know what B believes is the value of P).

We have demonstrated representations of all cases where agent B (figure 8) is believed to be aware of P. Next, we consider the case where B is unaware of P.

4.6. Awareness, and Explicit & Implicit Mention or Agents

A question is "how to represent an agent being aware of the proposition represented by a >.-formula'?" Our solution is this: An agent is said to be aware of the pro­ position represented by a >.-formula if and only if that agent is either explicitly or implicitly mentioned in the set of all agents that appear in the table for the for­ mula; otherwise the agent is said to be unaware of the proposition.

An agent is explicitly mentioned if the agent is a member of one of the sets in the table and is implicitly mentioned if the agent is a member of a class of agents5 that is explicitly mentioned in the table. This may be seen in example 5 where MDs are cap~ble evaluators. Hence, any agent who is an MD is capable of evaluating example 5. MDs are explicitly mentioned in this example, someone who is an MD is implicitly mentioned.

An agent who is neither explicitly nor implicitly mentioned is deemed to be unaware of the proposition that the formula represents. In the case where an agent is implicitly mentioned in more than one class of agent, the most specific class is chosen to determine that agent's view.

4.6. Function TransformatiODS

The use of >.-formulas poses a question, what affect does ascribing a >.-formula to an agent have upon the >.-formula?

Ascribing a >.-formula often requires altering the formula. For example, ascribing a formula to an agent, who does not know the value it returns for any agent, will require changing the formula to reflect this situar tion. Ascribing a >.-formula to an agent thus involves changing the function table far the formula. This is equivalent to saying that· ascribing a >.-formula to an agent involves changing the function that the formula represents.

Function Transformations on >.-formulas are dis­ cussed in more detail in (Ballim, lg87).

4.7. >.-expressiODS and Meta-Beliefs

We can see how >.-formulas solve the problems that were discussed in section 4. Lack of awareness is realised within >.-formulas by an agent being neither an explicit nor implicit agent of the formula's capable evaluators set. Atypical beliefs are characterised by their associated metarbeliefs. >.-formulas are very effective at representing metarbeliefs of atypical beliefs.

6. A Description ol V.ewGen and a Medical Example

V.ewGen is a Prolog program that generates nested points of view. The program has a set of beliefs that are considered held by an agent known as the system. These beliefs are partitioned into topics (held in labelled PTs). An example call to the program is shown in (figure 10).

I?- viewgen(l system], [thalassemia] ,_j. . Viewpoint of [system] is [ thalassemia is_type_of yes 17lambda( type_of( thalassemia) ,genetic_disorder) Figure 10. The System's View about Thalassemia6

The point of view represented in (figure 10) is the system's view about thalassemia. This view consists of one belief, namely that it is a genetic disorder.

ViewGen operates by forming a contextual focus from the PTs of the terms in the list that forms the second argument to the program. The first argument is a. list of agents. This list represents the nesting that is required. The third argument is a variable that is instantiated to the structure that the program returns.

In the following example assume that the system is a medical expert conducting a dialogue with a mar­ ried couple who are seeking advice about thalassemia. The system has a lambda formula for the intensional description "type_of(thalassemia)" shown in (figure 11).

lambda( type_of( thalassemia), D, [ [ [system, medically_informed_person], genetic_disorder ] , [ [ avg_man], disease ] ])

Figure 11. Lambda Formula for the type of thing that Thalassemia is

With the information that thalassemia is a type of genetic disorder the system is able to generate what it believes abc:>Ut them both. This point of view is shown in (figure 12).

I!- viewgen( [system],[ thalassemia,genetic_disorder] ,_). Viewpoint of [system] about [ thalassemia,genetic_disorder] is [ ( (D is_type_of genetic_disorder and {A1 suffers_from D and {A2 suffers_from D and (A1 married_to A2 and A3 child_of [A1,A2])))) implies A3 suffers_from D ) thalassemia is_type_of yes I!- lambda( type_of( thalassemia) ,genetic_disorder) Figure 12. The System's view of Thalassemia and Genetic_disorder( s)

The point of view in (figure 12) contains the belief that thalassemia is a genetic disorder. In addition it contains a complex belief the child of two people, who both have a genetic disorder, will suffer from the same genetic disorder from them 7 ·

Suppose that the couple in question are called Paul and Sally, and that the system has the beliefs about them shown in (figure 13).

I!- viewgen( [system], [ sally,paul] ,_). Viewpoint of [system] about [sally,paul] is [ sally is_type_of medically _informed_person sally married_to paul paul suffers_from thalassemia sally suffersJrom thalassemia I yes

I?- Figure 19. The System's view of Sally and Paul The important beliefs here are that the system believes that Sally is a medically informed person, and that they both suffer from thalassemia. We presume that we have reasoning mechanisms that allow us to reason with the viewpoints in figures 13 and 14 to hypothesise that any offspring of the pair will also suffer from thalassemia (something that they need to be warned about). If we presume that the system fol­ lows Gricean Maxims then we need to generate what the system believes eac.h of them believes about thalassemia. These points of view are shown in figures 15 and 16. I?- viewgen( [system ,sally], [thalassemia],_). Viewpoint of [system,sally] about [thalassemia] is [ thalassemia is_type_of yes I?- lambda( type_of( thalassemia) ,genetic_disorder) Figure 14. The System's View of Sally's View of Thalassemia I?- viewgen( [system, paul], [thalassemia],_). Viewpoint of [system,paul] about [thalassemia] is [ thalassemia is_type_of yes I?- lambda( type_of( thalassemia) ,disease) Figure 15. The System's View of Paul's View of Thalassemia

In (figure 14) the belief that thalassemia is a type of genetic disorder has been ascribed to Sally. This is because the system believes that Sally is a medically informed person, and the system believes that medically informed people know that thalassemia is a genetic disorder (see figure 11). Paul, however, is not believed to be a medically informed person. He is sim­ ply an average mans. The average man view of thalassemia is that it is a disease . This is just the view that the system believes Paul has about thalassemia (figure 15).

In a dialogue between three agents it can be neces­ sary Cor one agent to model what the second believes the third believes, or what the third believes the second believes about the topic. So we generate what the sys­ tem believes Sally believes Paul believes about thalassemia, and what the system believes Paul believes Sally believes about thalassemia.

Using the beliefs about Sally and Paul 'the system generates that Sally believes that Paul believes that thalassemia is a disease. However, the system has gen­ erated that Paul believes that Sally believes thalassemia is some kind of complex thing that he doesn't know about, represented by "[u,1]" which is an uncertain value. In other words, according to the default rule Paul believes that Sally is a medically informed person (since there is no evidence to contradict this) and hence Paul believes that Sally has a more complex belief about thalassemia than he does.

6. Conclusions

This work claims only to be a first implementation of a "belief engine" (Maida, 1986} that contains plausi­ ble heuristics or the default ascription of concrete, con­ tentful beliefs. Such a process will be needed by any project that proposes (e.g. Pollack, 1986) to model the interaction of agents planning on the basis of differing beliefs and plans. We believe no other system has yet tackled this problem in a practical way. Many exten­ sions will be required to the current work, particularly in the treatment of the identication of intensionally dis­ tinct but extensionally identical individuals and classes.