On the Representation of Nonmontonic Relations in the Theory of Evidence

1. Introduction

In many reasoning environments we are required to represent our knowledge about a variable in a probabilistic manner. However it is often the case that our knowledge about the probability distribution of these random variables is not complete, we are not sure of the assignment of the probability weights to the individual outcomes of the variable. The mathematical theory of evidence [Dempster, 1967; Dempster, 1968; Shafer, 1976; Shafer, 1987; Lowrance and Garvey, 1982; Gordon and Shortliffe, 1984; Smets, 1988; Yager et al., 1994] allows for the representation and manipulation of this nonspecific type of knowledge. A number of different semantics can be associated with this theory, Dempster [1967], Shafer [1976] and Smets and Kennes [1994] . While in this paper we shall favor the one introduced by Dempster the basic ideas presented in this work are valid in the other interpretations.

Within this theory, a belief structure, a basic probability assignment function (bpa), provides a knowledge Pl(B) = I, Poss[B/A] * m(A), where Poss[B/A] = 1 if the A eX

set An B :t: q, and Poss[B/A] = 0 if the set An B= q,. The second measure is called the measure of belief, denoted Bel[B], and defined as Bel(B) = I, Cert[B/A] * m(A) where A eX

Cert[B/A] = 1 - Poss[B/A]. Cert[B/A] is a measure of the degree of inclusion of A in B, if A c B then Cert[B/A] = 1 otherwise it is zero.

An important aspect of these two measures is that they provide an upper and lower bound on the probability of B, that is Bel(B) ~ Prob(B) ~ Pl(B).[Dempster, 1967; Strat, 1984] For each B, we define R(B) = [Bel(B), Pl(B)], as our range of indefiniteness about the probability of the set B. The smaller Pl(B)- Bel(B) the more we know about the probability of B.

Definition: Assume m 1 and m2 are two D-S structures on X if R 1 (B) c R2(B) for all B c X, we shall say m 1 is more specific than m2 and denote this as m1 S m2.

Thus a bpa being more specific than another indicates the first provides better knowledge of the probabilities involved in the situation.

If a' ~a and b' ~ band if Prob(B) E [a, b) then we can infer that Prob(B) E [a', b'). This observation allows one to introduce a logical entailment principle associated with D-S granules [Yager, 1985; Yager, 1986]. In particular, if we know that m 1 is a valid representation of the probability structure on X and if m 1 S m2 then m2 also presents a true, although less informative, picture of the probability structure on X. We can capture this idea in the form of a logical entailment principle

Yager [1986] has introduced an idea of containment of two D-S structures.

Definition: Assume m1 and m2 are two D-S structures such that A 1, ... , Aq are the focal elements of m 1, with their weights m 1 (Ai) = ai. Let B 1, . . . , Bn be the focal elements of m2 with their weights m2(Bj) = bj. If a set of values Cij· 0 ~ Cij ~ 1, j = 1, .. , n, can be found which have the following properties, then we say m1 c m2,

and Cij > 0 only if Ai c B j. The condition Cij > 0 if Ai c Bj is equivalent to

It can be easily seen that if m 1 c m2 then m 1 S m2 and if m1 c m2 then m1 f- m2.·

Closely related ideas have been suggested by other authors. [Dubois and Prade, 1986; Lamata and Moral, 1989;

Kruse and Schwecke, 1990; Klawonn and Smets, 1992]

Assume m is a bpa on X with focal elements A 1 and A2 with m(A1) = a1 and m(A2) = a2. Let m' also be a bpa on X with focal elements B 1, B2 and B3 where m(Bi) = bi and B1 =At, B2 = A2 and B3 = A2. Furthermore assume b1 = a 1, a2 = b2 + b3. It can be shown for any subset D of X Pl'(D) = Pl(D) and Bel(D) = Bel'(D). Thus m and m' are effectively the same bpa. We say m' is an alternatjye .v..i.tn: of m.

Assume m 1 is a bpa on X with focal elements A1, ... , Aq with m1(Ai) = ai. Assume m2 is a bpa on X with focal elements B 1, .. . , Bn where m2(B j) = bj. Assume m1 c m2. The following useful alternative view m3 can be made of m2. m3 has focal elemems Qij where Oij = Bj for all i and m3(Qij) = Cij satisfy the properties in the definition of containment

We shall call m3 an alternative view of m2 tagged to m 1· Alternatively, we can say that if m 1 and m2 are two bpa on X and if there exists an alternative view, m3, of m2 tagged to m1 then m1 c m2 and m1 c m3 and m2 = m3.

Assume m 1 and m2 are two bpa on X relating information about V. The effect of both these pieces of information is a conjuncted bpa m on X denoted

where m is obtained via Dempster's rule [De~r.;>:>t':!!, 1967] such that for each A :t: q,

where Ai and B j are the focal elements of m 1 and m2 and

If K :t: 1, we call m1 and m2 combinable or non-conflicting.

3. Compatibility Relations and Inference in D-S Structures

Assume V and U are two variables taking their values in the sets X and Y, respectively. A compatibility relation C between V and U is a relation on X x Y such that for each x E X there exists at least one y such that (x, y) E C and for each y E Y there exists at least one x E X such that (x, y) E C. Formally, we shall call this a type I compatibility relation. If Ai = {y I C(xi, y) = 1} and Bj = {:;,: I C(x, Yj) = 1} then we require Ai :t: q, and Bj :t: q>. Intuitively, we shall use a compatibility relation to represent the idea that if we know that V = xi then Ai equals the subset of values of Y that are possible solutions for the variable U.

We note that any C can be naturally represented in matrix form,

where Cij = 1 means (xi, Yj) E C and Cjj = 0 means (xi, Yj) e C

Compatibility relations are effectively rules. Let A and B be subsets of X andY. The rule if V E A then U E B is represented by the compatibility relation C(x, y) = 1 for x E A and y E B; C(x, y) = 0 for x E A and y e B and C(x, y) = 1 for x e A.

A general principle for combining these type I compatibility relations can be established. Assume K 1, K2, ... , Kr are r pieces of knowledge about the relationship between V and U each of which is representable as a compatibility relation C1, ... , Cr. The effect of all of these pieces of knowledge is a conjunction of the individual pieces of knowledge "K 1 and K2 . ... and K," which results in an overall compatibility relation C, where C = C1 n C2, ... , nCr. An important implication of this principle is that if C is the effective compatibility relation under K 1, ... , Kr and if we get further information about the relationship between V and U in terms of another piece of information, Kr+ 1, resulting in an effective relation C* = C n Cr+1 where C* c C. We recall C* c C if C*(x, y) ~ C(x, y) for all x, y. Thus more information usually results in a smaller compatibility relation in the sense of cardinality.

An important class of inference problems involves the situation in which we have some knowledge about the probability structure of the variable V in terms of a bpa m on X, we have knowledge about the relationship between V and U in terms of a compatibility function C on X x Y and we are interested in obtaining knowledge about the probability structure on U in terms of a bpa m* on Y. The procedure for securing this information in essence involves an application of Dempster's rule.

Assume Ai are the focal elements of m such that m(Ai) = ai. We proceed as follows

1. Extend m to be a bpa on X x Y where m(Ai x Y) = m(Aj).
2. Apply Dempster's rule to C and m to obtain a conjuncted structure m+ such that

where Ei = (Ai x Y) n C.

3. Obtain the bpa on Y, m* by projecting Ei onto Y. That is m*(Fi) = m(Ai) where Fi = Projy[Ei] = {y I if E i(x, y) = 1 for some x}. Effectively, Fj(Y) = Maxx Ej(X, y).

Since it is possible for two different E's to project into the same F,

Essentially we call a compatibility relation monotonic if an increase in knowledge about the antecedent does not result in a decrease in knowledge about the cqnsequent. In the following definition we formalize this idea.

Definition: Assume C is a compatibility relation on X x Y. Let m1 and m2 be two bpa on X such that m 1 S m2. If m1 and C allows us to infer m~ on Y and m2 and C allows us to infer m; on Y then C is said to be · ·f · s · monotoDJc 1 m1 m2.

It can be shown [Yager, 1988] that every type I compatibility relation is monotonic and thus it is impossible to represent a nonmonotonic relationship with these type I compatibility relations. Since many kinds of commonsense knowledge have a nonmonotonic aspect there is a need to provide compatibility structures to represent this type of knowledge. In the following we introduce such a structure.

4. Non-monotonicity and Type II Compatibility Relations

Assume V and U are two variables taking values in the set X and Y respectively. Let eX be the power set of X minus the null element, thus T E eX is a non-null subset of X.

Definition: A type II compatibility relation R is a relation on eX x Y such that for each T E eX there exists a y E Y such that R(T, y) = 1.

The understanding to be accorded a type II compatibility relation is that if R(T, y) = 1 then if Vis known to be some element in T then y is a possible value for U, thus R(T, y) implies (x, y), for all x E T, are possible solution pairs for V and U.

The following terminology and definitions shall be useful in our future discussions. We shall call the subsets of X which are singletons the principle elements of ..X. With each T E eX we shall denote W to be the subset of Y that are the possible values of U when x E T, W = { y I if R(T, y) = 1}. W is called the associated set in Y ofT and sometimes we shall denote this pair as T ~ W.

With X= {x1, x2, x3} andY= {yt, Y2· y3}a type II compatibility relation would be as shown in the following matrix.

Definition: Assume Ti are the principle elements of tX, Ti = {xiJ and let Ti ~ W i· Assume T is some arbitrary non-principle element in X where T ~ W. We call a relation R normal if

Thus we see that a relation is normal if an associated set is contained in the union of the associated sets of principle elements making it up.

In point of fact, all reasonable compatibility relations can be seen to be normal. Assume there exists y E W but y e u Wi· Since the knowledge V E T implies that the 1

value of V must be some x E T, the value for U must be possible under an x E T, but if y is not associated with any x E T then it can't be a solution.

Definition: A normal compatibility relation R of type II shall be called regular if for all T1 ~ W 1, T2 ~ W 2· T3 ~ W3 such that T3 = T1 u T2 then W3 = W1 u W2. It is called irregular if there exists such a triple where WcW1 uW2.

We shall now describe the reasoning process used when we have a type II compatibility relation. Assume R is a type two compatibility relation on tX x Y Let our information about V be given in terms of a bpa m on X such that A 1, ... , Ap are the focal elements of m where m(Ai) = ai. We are here interested in obtaining a bpa m* on Y providing the information about U. The procedure is essentially the same as in the case of a type I compatibility relation after an initial space transformation is made.

1. Transform m to an equivalent bpa m' on tX as follows:

m' is a bpa on ,X with focal elements Ai' E tXwhere

That is the focal elements of m are singleton subsets of ,X whose element is the corresponding focal element in X. Thus if Ai ={xi, x2} then Ai' = ((xl, x2} }.

1. Extend m' to be a bpa on ,X x Y such that m'(Aj' x Y) = m'(Aj') = m(Ai) = ai
2. Conjunct R and m' to obtain a bpa m+ also on tXx Y such that m+(Ej') = ai where

1. Obtain the bpa m* on Y by projecting Ei' onto Y. That is m*(Fj') = ai where

Using this inference mechanism we can show that every regular type II relation is monotonic. We will now proceed to show that all all irregular relations are non­ monotonic. We recall that a relation R is non-monotone if there exists a pair m 1 and m2 on X where m 1 c m2 such that, R o m1 ex R o m2.

Theorem: All irregular relations are non-monotone.

Proof: Assume R is an irregular relation. This implies that there exists at least three elements T 1, T 2 and T of tX such that T1 u T2 = T with W1, W2 and W being their associated sets in Y such that W is strictly less than W 1 u W2, ie. there exists one y* E y such that y* e W and but where y* E W 1 or y* E W 2· Consider the two bpa m1 and m2 on X such that m1 is defined by m1(T1) =a and m 1 (T2) = 1 -a where a> 0 and where m2 is defined by m2(T) = 1. It is obvious that m1 c m2, since Tt c T and T2 c T. We first note that if m~ = R o m 1 then m~(Wt) =a and m~(W2) = 1- a and ifm; = R o m2 then m;(W) = 1. Consider the subset D = { y*} of Y,

Pit (D)= a Poss[D/W tl + (1 -a) Poss[D/Wil and Pl2(D) = Poss[D/W]. Since y* e W then Poss[D/W] = 0 and Pl2(D) = 0. Since y is in at least one of W1 or W2 without loss of generality assume it is definitely in W 1 then Poss[D/W tl = 1 and hence Pit (D) :::=:a. Therefore

thus m~ ex m2 and the theorem is proven.

This result taken with our previous observation indicates that not only are all irregular relations nonmonotonic but the only way to represent a nonmonotonic compatibility in terms of normal relations is via an irregular relation. Thus these irregular type II compatibility relations provide the desired structure for representing nonmonotonic knowledge.

5. Default Compatibility Relations

A particularly important class of nonmonotonic relations are the so-called default relations [Reiter, 1980; McCarthy, 1986; McDermott and Doyle, 1980; Ginsberg, 1987]. Default type knowledge plays a crucial role in the representation of commonsense knowledge. Basically, a default rule is used to represent situations in which, when we are uncertain as to the value of V, we act as if the value of V was known to be the default value. For example, if we have a bird but we are sure of what type it is we act as if it was a flying bird. Another type of default rule is when you are uncertain as to the cause of some symptom and act as if it were the one simplest to fix. We now look at the representation of these default relations as irregular compatibility relations.

The essential structure of a default relation is captured in the following relation. Assume V and U are two variables taking their values in X= {xJ. x2l andY= {YI· Y2l respectively. Assume that the relation between U and V is

Since {xJ} u {x2l = {xJ. x2} we have T1 u T2 = T3 ~ W c WI u W2.

A fruitful way of interpreting this relationship is by observing that we infer the default consequent YI when our antecedent knowledge allows for the possibility that the value of V can be x 1· Thus we infer YI for T such that Poss[ { x 1 } {f] = 1. A natural reading of this default relation would be

A more general pattern for default relations can be introduced. Let X = {xJ ·... , xq} and let Y = {YI· . . , Yp}. Let A be a subset of X and let B 1 and B2 be subsets of Y where B2 ~ B1 . Let the relationship R between V and U be characterized by the following, R: X ~ Y such that for any T E X

Thus we see that R is a function of Poss[A{f]. We shall indicate this as R = D(A, B 1· B2) and call it a standard default rule. We can read this as "if V is in A is possible then U is in B 1 else it is in B2" . An important special case occurs when B1 = Y. This is called a simple default rule.

Theorem: A standard default rule generates an irregular compatibility relation.

Proof: 1) IfT1 , T2 c A then

3) If it is not contained in either A or A then T = T 1 u T 2 where T 1 c A and T 2 c B since T 1 ~ B 1 and T2 ~ B2 and T ~ B then T = T1 u T2 ~ W c B1 u B2.

Assume our knowledge of V is expressed by the bpa A l· .. . , Ar where m(Ai) = Ai. Let our relation between V and U be expressed by the standard default rule D(A, B1 B2). Then if m* is our expression of knowledge ofU

where Wi is the associated Y set of Aj. Furthermore Ai = B1 if Poss[NAi] = 1 and Ai = B2 if Poss[A/Ail = 0 thus m* is obtained as

An interesting type of default rule is what we shall call a hierarchical default rule. Assume A 1· ... , Ak are a collection exclusive and exhaustive subsets of X, ie

i=l subsets of Y such that for i > j, Bi ~ Bj. We shall call R a hierarchical relation,

Poss[A2ff1 = 1

and Poss[Aeff] = 1.

We shall denote such a relation as

We see that

A prototypical rule which generates a hierarchical compatibility relation is the rule always do the easiest thing. Consider a device made up of three parts QJ. Q2, q3Let xi indicate the proposition "part i is busted" and let Yi indicate the action "replace part i". Assume the parts are such that QJ. q2, q3 is the order in ascending difficulty of fixing the parts. Then the following hierarchical relation implements this rule

such that We can easily show that these hierarchical default relations result in a irregular compatibility relation.

6. References

[Dempster, 1967] Arthur P. Dempster. Upper and lower probabilities induced by a multi-valued mapping. Ann. of Mathematical Statistics 38: 325-339, 1967.

[Dempster, 1968] Arthur P. Dempster. A generalization of Bayesian inference. Journal of the Royal Statistical Society, 205-247, 1968.

[Dubois and Prade, 1986] Didier Dubois and Henri Prade. A set-theoretic view of belief functions. International Journal of General Systems 12: 193- 226, 1986.

[Ginsberg, 1987] Matthew L. Ginsberg. Readings in Nonmonotonic Reasoning, Morgan Kaufmann, Los Altos, CA, 1987.

[Gordon and Shortliffe, 1984] Jean Gordon and Edward H. Shortliffe. The Dempster-Shafer theory of evidence. In Rule-Based Expert Systems: the MYCIN Experiments of the Stanford Heuristic Programming Project, Buchanan, B.G. & Shortliffe, E.H. (eds.), Reading, MA: Addison Wesley, 272292, 1984.

[Klawonn and Smets, 1992] Frank Klawonn and Philippe Smets. The dynamic of belief in the transferable belief model and specialization-generalization matrices. In Uncertainty in AI 92, edited by Dubois, D., Wellman, M., D'ambrosio, B. and Smets, P., Morgan-Kaufmann: San Mateo, CA, 130-137, 1992.

[Kruse and. Schwecke, 1990]. Rudolf Kruse and E. Schwecke. Specialization: a new concept for uncertainty handling with belief functions. International Journal of General Systems 18: 49-60, 1990.

[Lamata and Moral, 1989] Maria T.Lamata and Serafin Moral. Classification of fuzzy measures. Fuzzy Sets and Systems 33: 243-243, 1989.

[Lowrance and Garvey, 1982] John D. Lowrance and Thomas D. Garvey. Evidential reasoning: A developing concept," In Proceedings of the IEEE International. Conf. on Cybernetics and Society, pages 6-9, Seattle, WA, 1982.

[McCarthy, 1986] John McCarthy. Applications of circumscription to formalizing common sense knowledge. Artificial Intelligence 28: 89-116, 1986.

[McDermott and Doyle, 1980]. Drew McDermot and Jon Doyle. Non-monotonic logic I. Artificial Intelligence 13: 41-72, 1980.

[Reiter, 1980] Raymond Reiter. A logic for default reasoning. Artificial Intelligence 13: 81-132, 1980.

[Shafer, 1976] Glenn Shafer. A Mathematical Theory of Evidence, Princeton University Press, Princeton, N.J., 1976.

[Shafer, 1987] Glenn Shafer. Belief functions and possibility measures. In Analysis of Fuzzy Information, Vol 1: Mathematics and Logic, edited by Bezdek, J. C., CRC Press, Boca Raton: Florida, 1987.

[Smets, 1988]. Philippe Smets. Belief Functions. In Non­ Standard Logics for Automated Reasoning, Smets, P. , Mamdani, E.H., Dubois, D. & Prade, H. (eds.), London: Academic Press, 253-277, 1988.

[Smets and Kennes, 1994] Philippe Smets and Robert Kennes. The transferable belief model. Artificial Intelligence 66: 191-234, 1994.

[Strat, 1984] Thomas M. Strat. Continuous belief functions for evidential reasoning. In Proceedings 4th American Association for Artificial Intelligence Conference pages 308-313, Austin, TX, 1984.

[Yager, 1985] Ronald R. Yager. Reasoning with uncertainty for expert systems. In the Proceedings of the Ninth International Joint Conference on Artificial Intelligence pages 1295-1297, Los Angeles, 1985.

[Yager, 1986] Ronald R. Yager. The entailment principle for Dempster-Shafer granules," Int. J. of Intelligent Systems 1: 247-262, 1986.

[Yager, 1988 Ronald R. Yager. Non-monotonic compatibility relations in the theory of evidence. Int. J. of Man-Machine Studies 29: 517-537, 1988.

[Yager et al., 1994] Ronald R. Yager, Janus Kacprzyk and Mario Fedrizzi. Advances in the Dempster-Shafer Theory of Evidence, John Wiley & Sons, New York, 1994.