How to Represent Evidence - Aspects of Uncertain Reasoning

ABSTRACT

In order to represent uncertain knowledge especially inference rules matching uncertain knowledge structures - several extensions of a representation schema are described. First a two­ dimensional evidence space is introduced to express positive and negative evidence. It is shown how indicators of evidence (as parts of NL-utterances) modify evidence values by modification rules. Evidence values (points of the evidence space) can be used in place of truth values in order to represent inference rules. To do this the extensions deal with the goal point concept for redefining 'verify' (together with the concepts of neighborhood, deviation, and direction), and the concept of relevance reflecting the relationship between a single premise and the conclusion.

I In trod uc tion

Research in common sense reasoning, natural language systems, expert systems (and almost all the other subfields of AI) is concerned with knowledge representation as the main problem of AI. Central topics are vagueness (e.g. LeFaivre, 1974), uncertainty (e.g. Shortlife, 1976; Wahlster, 1981), and partial (or incomplete) knowledge (e.g. Fox, 1981, Joshi, 1978). In this paper I concentrate on uncertainty and present a proposal on how to represent inference rules that are able to match uncertain knowledge structures (macro structures) partially. Several properties of the representation schema and the rule system are under investigation. I present some basic extensions that have already been implemented to varying degrees (in PROLOG). The first and most important extension is the representation of uncertainty with pairs of

evidence values.

Two important problems arise if we enrich a traditional representation schema (e.g. logic) with evidence values: first, how can truth values be related to evidence values and secondly, what are the dependencies between evidence values?

• This work was supported (Bundesministerium fuer Forschung under grant PT 135.01. by the BMFT und Technologie)

Glaus-Rainer Rollinger Technische Universitaet Berlin PROJEKT KIT , Sekr. FR 5-8 Franklinstr. 28/29 D-1000 Berlin 10 Fed. Rep. of Germany

I give no direct answer to either of these questions, but on the one hand I demonstrate how evidence values can accomplish the task of truth values, and on the other hand I illustrate how to handle the dependencies between evidence values.

In the following I introduce a two-dimensional evidence space and point out the consequences for

the formulation of inference rules.

II The evidence space

In contrast to Wahlster, who uses one dimension to represent evidence**, I distinguish be tween po si tiv e and negative evidence as dimensions of a two-dimensional evidence ·space.

1. Mary believes that Jim will travel to IJCAI-83.

With (1) as part of my personal knowledge base I can say that I have some positive . evidence

(namely Mary's belief) for the propo;ition 'Jim will travel to IJCAI-83'.

1. John tells me that Jim will not travel to
2. IJCAI-83.
3. gives me some negative evidence for the same proposition. So I can have both: positive and negative evidence for one and the same proposition at the same time.

Because I often am not able to resolve conflicts immediately (Doyle, 1979) I will answer "Maybe" *** if someone asks me in the meantime whether or not Jim will travel to IJCAI-83.

Being able to generate answers like that implies the ability to represent such "conflict situations" to ' represent uncertain and contradictory knowledge. It is essential in this

• ** Wahlster uses a linear scale like the z-value scale of Fuzzy (Zadeh, 1965) in his fuzzy sorted evidence calculus (Wahlster, 1981).
• *** Many other answers especially interested towards a proposition. are possible, but I am in the mental attitude

context to be positive and corresponding sources having able to mark a proposition for negative evidence with their values as well as the different caused the "conflict".

We have to differentiate between the following four important situations:

1. (strong) positive and no negative evidence.
2. ii) No positive and (strong) negative evidence.
3. iii) No evidence at all.
4. iv) Both, (some) positive and (some) negative evidence.

Using a one-dimensional linear scale to represent degrees of evidence for propositions, Wahlster is not able to distinguish between 'some positive and no negative evidence' and 'strong positive and some negative evidence', if the difference between positive and negative evidence remains constant. Usually it is the latter which is not allowed (cf. Wahlster, 1981).

These cases reflect four ways in which something can be known: i) stands for 'I am sure that a proposition is true', ii) stands for 'I am sure that a proposition is false', iii) says that I know nothing about the 'truth' of a proposition, and iv) says that my knowledge is contradictory - that I can not decide whether a proposition is 'true' or 'false'. All the other possible combinations of negative and positive evidence (= points/regions of the evidence space) can be verbalized in a similar way *·

The two dimensions of the evidence space are given by the positive and the negative evidence. Each proposition is assigned exactly one evidence point (EP): EP(proposition)=(EP+,EP-) £ [0,1) X [0,1].

The adequacy of this approach will illustrated with the following examples: be

1. It may be true that it is false that Jim will travel to IJCAI-83.
2. Both the translation from NL to such representations (the understanding problem) and the generation of NL-utterances out of these representations are important tasks but are not in the focus of this paper.

In order to represent (3) and to determine its EP, it is helpful to interpret 'it may be true' and 'it is false' as indicators of evidence, where the first modifies the EP produced by the second. The very 'first' EP ** is created by an implicit part of the given sentence. This part is a constituent of every natural language utterance - it indicates the relationship between the real world and the proposition and says that

1. In the real world IT IS THE ( proposition) . CASE that
2. is successively modified by evidence indicators until the evidence point of the proposition is obtained and the mental attitude of the utterance producer is adequately expressed.
3. I introduce 'it is the case' as the operation that assigns (1,0) to a proposition Pi.

For each indicator of evidence, modification rules can be formulated that express how they modify EPs ***· Examples can be:

'IT IS TRUE' : EP *

****{~!

'IT MAY BE' : EP *

'IT IS FALSE':

if

if

if

1 : (EP+ * 1 , EP- * 1)

0.7 : (EP+ * 0.7 , EP- * 0.7)

EP=(O,l) then (1,0)

EP=(l,O) then (0,1)

EP+ = EP- then (EP+,EP-)

EPE.positive zone then (EP+,l)

EPE:negative zone then (l,EP-)

Now we can compute the EP of (3):

Jim will travel to IJCAI-83

Jim will travel to IJCAI -83 ( 1 , 0)

Jim will travel to IJCAI-83 (0,1)

Jim will travel to IJCAI-83 (0,0.7)

IT IS THE CASE

IT IS FALSE

IT MAY BE TRUE

The next example (5) is more complicated because of the different combination of indicators, but it is solvable in the same way. As in (3) 'it is the case' is given implicitly:

1. It is false that it may be true that Jim will travel to IJCAI-83.
2. ** In order to modify something we need this very first point.
3. *** To make these modification rules more adequate the concept of neighborhood - introduced in the next section - would be helpful.
4. **** A continual function of 'it is false' would be more adequate but rather complicated. This definition shows some properties (of a continual function) relevant to the example.

Jim will travel to IJCAI-83

Jim will travel to IJCAI-83 (1, 0)

Jim will travel to IJCAI-83 (0.7,0)

Jim will travel to IJCAI-83 (0.7,1)

IT IS THE CASE

IT MAY BE TRUE

IT IS FALSE

(0.7,1) indicates that I have more negative than positive evidence for the proposition and the EP is close to the contradiction (1,1). This expresses the attitude towards the proposition 'Jim will travel to IJCAI-83' well *· The difference between (3) and (5) could be explicated in order to show in what way the ordering of the evidence indicators influences the meaning of a sentence. This difference is similar to the one between the meanings of different orderings of the modal operators 'necessity' and 'possibility' of modal logic. The aim of this example was to show that differences like this (of the ordering of evidence indicators) can be explicated in such a way.

III Inference rules

In logic premises have to be verified in order to show that a conclusion is a theorem. Substituting truth values by evidence values we have to redefine the word 'verify'. What could it mean to 'verify a premise' if the propositions which could be supporting instances for the premise have EPs but no truth values? If we provide the premises with goal points (GP) ** then we can check whether or not the evidence point of a proposition matching a premise is identical with the goal point. If this is the case, then the proposition is a 'supporting instance' for the premise. We can do exactly the same with the conclusion: it gets a GP that becomes its evidence point if all premises are

verified in the described way.

At this point the main difference between this and the predicate calculus is that in logic there is only one GP (1,0), which is given implicitly. In my proposal each EP that is possible can stand for

a GP.

To make the system more powerful the following extension is made: a proposition is a supporting instance for a premise if it matches and if its EP is compatible with the GP of the premise. In this context 'compatible' means that the neighborhood of

• Usually the receiver of (5) expects the solution of the contradictory situation by the speaker. ("It is definite that he will travel! " )
• ** The goal point of a premise tells us that the inference rule is applicable if the attitude to a proposition matching the premise (its evidence point) is identical to the wanted GP. As EPs GPs are pairs of values of the form (GP+,GP-)€ [0,1] X [0,1]. They are elements of the evidence space too.

each GP is defined * and that the EP is an element

of this neighborhood. Now we can determine the 'quality' ** of the verification of a premise by computing the distance between the EP and the GP.

We can distinguish between at least two kinds of deviation from the GP: it is positive (more certain) if the GP is an element of the positive zone (for positive and negative zone cf. the figure) and the EP is nearer than the GP to (1,0), or if the GP is an element of the negative zone and the EP is nearer to (0, 1) than the GP is·. In all other cases the deviation is negative (more uncertain) (unless the GP is identical to the EP, of course). This distinction is a first attempt to take into consideration the direction of the

deviation. ***

The evidence point of the conclusion no longer depends only on the respective goal point but also on the quality of the verification of all premises and the direction of the deviation. Thus, the GP of the conclusion is also assigned a neighborhood ****

The goal point concept is a first step towards achieving a partial matching of complex structures. With this concept we allow a premise to have the whole evidence space as its neighborhood. Such a premise is considered optional because it cannot be falsified. In carrying out an inference the system should be able to distinguish between obligatory and optional premises, because in strange situations with little time to "prove a theorem" the system should ignore the optional premises. To compute the quality of the verification of all premises the optional premises have to be taken into account differently than the obligatory ones because of their different degrees of relevance.

* The neighborhood is a sphere of the evidence

space with the goal point as its center. The GP together with a radius defines the neighborhood.

** 'Quality' is introduced here as a technical term.

• *** If the direction of the deviation of the premises is seen as a vector, then the EP of the conclusion (that is, the deviation from its goal point) can be computed with the vector calculus. This possibility is under investigation.
• **** There are many possibilities for computing the actual evidence point of a conclusion, e.g. minimum, maximum, or average of the verification qualities, and vector calculus. It also should be possible to implement a special computation procedure for a special inference rule.

The second extension is the introduction of the degree of relevance of a premise * needed to compute the quality of verification of all the premises of an inference rule. For the time being we interpret the neighborhood of a premise as its relevance the larger the neighborhood, the smaller the relevance **

The ordering of the premises should at least take into account the difference between optional and obligatory premises - it would be foolish to prove all the optional ones and then to fail with an obligatory one ***·

A special class of inference rules has to be mentioned: those regulating the dependencies between EP's, If a proposition is known to have a certain EP and new information is added, then we are able to modify the . given EP using these rules. EP's of contradictory knowledge can be computed with the rules and stored afterwards together with the different knowledge sources.

IV Conclusion

Several extensions of a representation schema for uncertain knowledge have been described. The extensions deal with an evidence space for representing uncertainty, the goal point concept for redefining 'verify' (together with the concepts of neighborhood, deviation, and direction), and the concept of relevance reflecting the relationship between a single premise and the conclusion.

Finally an important point currently under investigation is touched on only slightly. As we have pointed out elsewhere (Habel and Rollinger, 1982), we have pOSitive and negative evidence for inference rules as well as ·for propositions. This uncertainty must ultimately be expressed in the same way as the uncertainty of propositions ****·

• Similar to the 'evoking weight' (Joshi, 1978)
• which reflects the certainty with which the conclusion can be inferred from the viewpoint of one premise.
• ** This is only a tentative solution because it is
• clear to us that there are situations in which a premise is optional but nevertheless quite relevant. In order to represent these situations we have to distinguish the neighborhood from the relevance. We will do this in a later stage of our project.
• *** Proposals on how to order premises for other reasons are given in Kowalski (Kowalski, 1979).
• **** This view of uncertainty is different to the one of Joshi (Joshi, 1978), who does not differ between save rules producing uncertain consequences and uncertain rules (producing uncertain concequences too, of course).