Characterizing Belief with Minimum Commitment

1 Introduction

Belief functions [Shafer, 1976; Smets, 1988] serve as a way to quantify human beliefs. It is a non-additive formalism. That is, Bel(A) + Bel(AC):::; 1, where A is a set formalizing some proposition and A c is A's complement with respect to some underlying universe of discourse. This is different from probability theory where P(A) + P(A C) = 1 is assumed. The reasoning mechanism of belief functions consists of two rules: Dempster's rule of conditioning allows us to update a given belief function in light of new information about the actual situation, whereas Dempster's rule of combination allows us to combine "distinct" or "independent" belief functions [Shafer, 1976; Smets, 1990].1

Researchers interested in belief functions often try to understand this formalism from the perspectives of probability theory (e.g., [Halpern and Fagin, 1990; Kyburg 1987; Nguyen, 1978; Pearl, 1988, Chapter 9]). This is understandable, as the origin of belief functions lies in the seminal paper of Dempster [1967], where he set out to study a particular subclass of upper and lower probabilities. However, Dempster's original view of belief functions is nowhere to be found in Shafer's 1976 monograph, where he offered a re-interpretation of Dempster's work and coined this formalism the term "belief functions."

Nevertheless, three questions about belief functions are of interests. One, why should human beliefs be quantified by belief functions? Two, why should Dempster's rule of conditioning be used for updating belief functions? Three, when is Dempster's rule of combination applicable in conditioning for updating belief functions.4 The third benefit is that we can now use Dempster's rule of conditioning to justify Dempster's rule of combination, thereby investigating the issue of "when is Dempster's rule of combination applicable?". The fourth and final benefit is that our restructured belief-function framework is more "robust" against potential misuse of belief functions. Because now whenever one wants to use Dempster's rule of combination to combine belief functions within our framework, he or she will have to explicitly justify the use of this rule. Without such a justification, the use of Dempster's rule of combination would only amount to what we call "inappropriate use of Dempster's rule of combination."

· This work was supported in part by the DRUMS project funded by the Commission of the European Communities under the ESPRIT IT-Program, Basic Research Project 3085.

I Formally, Dempster's rule of conditioning is a special case of Dempster's rule of combination. However, the underlying intuitions are completely different. One is concerned with belief updating, while the other is concerned with belief combination.

The reader might rightfully ask at this point: is this proposed reasoning approach consistent with Shafer and Tversky's canonical examples? The answer is "yes", and we will give more detail about this answer later in the paper.

The remainder of this paper is organized as follows. Sections Two and Three describe our restructured belief­ function framework. Section Four shows that our approach is consistent with Shafer and Tversky's canonical examples. Finally, Section Five concludes.

2 Basic concepts

The purpose of this section is to introduce the basic concepts of belief functions. We wish to emphasize the fact that only Dempster's rule of conditioning is introduced here, as Dempster's rule of combination is no longer considered an integrated part of our belief-function framework.

Let X= {Xt. X2, ... , XN} be a finite non-empty set of variables and let e1, 92, ... , 8N be the respective frames of these variables (each ei is a finite non-empty set of values Xi can take; these values are mutually exclusive and exhaustive). Xi is boolean if ei = {Yes, No}. Let h be a non-empty subset of X. eh is the Cartesian product of the frames of the elements of h . . ex. the set of all possible situations, is abbreviated as e. By the "Xi-value" (1 :S i :S N) of an element <a1. a2, ... ,aN> of e, we mean ai.

We will need to work with subsets of e in specifying a belief function. However, it is often desirable that we only work with some of the variables in specifying a particular fragment of our belief. Therefore we allow the use of logical formulas in referring to subsets of e, and we list in the appendix the formal correspondence between f, a formula, and [f), fs corresponding subset of e. This allows us to use a notation like [(Rain = Yes) :::::> (Wet= Yes)] to refer to 8 "minus" all those situations (elements of 8) that have Rain-value Yes and Wet-value No. It also allows us to use [-,(Temp = high)] in referring to 8 "minus" all those situations (elements of 8) that have Temp-value high. This is a rather effective way to refer to subsets of e. (In addition, we will use "Rain" as a shorthand for "Rain= Yes" in the case of boolean variables.) This way, we can unambiguously refer to subsets of e without committing ourselves to explicitly stating what variables are in X.

4we acknowledge that this does not make Dempster's rule of conditioning any more feasible than any other updating rule one might think of. However, the point here is that Dempster's rule of conditioning now becomes as competitive as any other updating rule. What we need to do, then, is perhaps to find some axiomatic justification of this rule.

A belief function on e is a function Bel: 2e ~ [0, 1] which is characterized by an m-value function mBel (written as "m" whenever confusions can be avoided; m is also called "the m-values of Bel"), where m: 2e ~ [0, 1] satisfies two conditions:

and for every subset B of e , Bel(B) is defined as LA:A~Bm(A). 5 A subset A of e is called afocal element of Bel if m(A) > 0. When Bel is such that m(8) = 1, we call Bel the vacuous belief function.

Intuitively, Bel(A) = c > 0 means that "I believe that the actual situation is one of the situations in A, and c corresponds to how confident I am in entertaining this belief', Bel( A) = 0 means that "I do not entertain the belief that the actual situation is one of the situations in A" , 6 and m(A) = d means that "in the course of establishing Bel, A is found to be the most specific subset of e that deserves this particular amount (d) of intuitive support." As such, Bel serves to characterize (part of) some distinguished state of mind, with m being the "internal structure" of Bel.

Once we accept this intuitive view of Bel and m, it is only natural that we extend this intuitive interpretation to Bel(. I B) and m(. I B), where, for example, Bel(A I B) = c > 0 means that "given that the actual situation is in B, I believe that the actual situation is in A, and c corresponds to how confident I am in entertaining this belief." This gives rise to the following conditioning rule known as Dempster's rule of conditioning [Shafer, 1976]. Let Bel be a belief function one and m be its associated m-values. Let B be a non-empty subset of e such that Bel(Bc) -:;:. 1.

where K = 1 - Bel(Bc) is the normalization constant. (Note that for every subset S of e, Bel(S n B I B) = Bel(S I B), but in general, m(S n B I B) -:;:. m(S I B).) Intuitively, Dempster's rule of conditioning may be understood from two perspectives. First perspective (C ~ B): originally we committed m(CuD) = s to CuD, as we thought CuD as a whole deserves this much (s) intuitive support and we did not want to further "split" s among the elements of CuD; now we learn that the actual situation is in B; as a result, we decide that C should "inherit" s, as we still think C as a whole deserves this much intuitive support and we still do not want to further "split" s among the elements of C. Second perspective (C !'::Be): originally we considered C the most specific subset of 8 that deserves m(C) = v; now we learn that the actual situation is not in Be; as our intuitions satisfy Bel(B I B) = 1 and Bel(C I B) = 0, rationality requires that we make m(C I B) zero and redistribute v in some way; what we do then is that we redistribute v among the focal elements of Bel(. I B) by proportions - a normalization process that is similar in spirit to what Bayes' rule of conditioning does.

SThis definition is consistent with [Shafer, 1976]. Smets [1988] has a slightly more general definition (called an "open world" defmition) in which m(0) does not have to be 0 and Bel(A) is defmed as the sum of the m-values of those non-empty subsets of A.

6 Consider the belief that the actual situation is in A. Here, according to our interpretation, an agent either entertains this belief or does not entertain this belief. And when the agent does entertain this belief, he/she/it is entitled to a degree of confidence (c) in doing so. In other words, we do not think of Bel(A) as the extent to which an agent entertains this belief

3 A reasoning paradigm

Now we are in the position to present our approach for reasoning with belief functions. We start by posing the following question: suppose we are able to come up with fragmentary specifications of what our intuitions satisfy, where a fragmentary specification is either a marginal (e.g., Bel([WET]) = 0), a conditional (e.g., Bel([RAIN] I [WET])= .3), or a mathematical relation among some of the marginals and conditionals (e.g., Bel([PARTY]) = Bel([PARTY] I [RAIN])), how should the system make inferences from these fragmentary specifications?

In answering this question, we simply regard all fragmentary specifications as constraints that a belief function must satisfy, and we ask the system to identify or construct a belief function that has the minimum commitment property (defined below) among all belief functions satisfying the specified constraints; if there is such a belief function, the system uses it to make inferences (by conditioning this belief function on the current context - information we currently have about the actual situation); if such a belief function does not exist, something else would have to be done, and we will briefly discuss about this problem in Section Five.

The principle of minimum commitment: 7 Let c t, ... , CM be an enumeration of fragmentary specifications (i.e., constraints), and let 1B be the set of belief functions {Bel: Bel satisfies ct, ... , and CM}. If there is an element <J of IB such that 'V t e B, 'V A !':: 8, cr(A) :S t(A), then <J should be preferred to all other elements of lB (i.e., <J should be used for making inferences), and we say <J is a characterization of (our intuitions) C}, ... , and CM with minimum commitment.

Why this principle? Well, assuming that the user was serious in providing the fragmentary specifications (i.e., constraints that his or her intuition satisfies), we think that the principle of minimum commitment can serve as a useful "general agreement" between the user and the system. In essence, what this agreement says is that "Bei(A) is, by default, as small as it is formally allowed." In other words, the principle of minimum of commitment formalizes the following intuition: if I (the user) do not say whether I entertain a belief (or how confident I am in entertaining this belief), then it would be an error in inferring that the extent to which I am confident in entertaining this belief (if I entertain this belief at all) is larger than what it formally has to be the case. Thus, for example, if the user only specifies an empty set of constraints (and clearly any belief function satisfies these constraints), then according to the principle of minimum commitment, what the user actually means is that Bel( A) should be 0 for every subset A of 8 (and for obvious reasons, the user simply did not bother to specify it).

7Formally, the principle of minimum commitment is a variant of the principle of minimum specificity [Dubois and Prade, 1986a].

To recap, we summarize our reasoning approach as a twostep process below.

Step One - knowledge solicitation: the user specifies what his or her intuition satisfies. The resulting specifications are ct, ... , CM.

Step Two - reasoning: given the fragmentary specifications q, ... , CM, the system tries to identify a characterization of the Ci's with minimum commitment; if there is such a belief function, the system uses it to make inferences (by conditioning the constructed belief function on the current context).

4 Relation with the canonical examples

One interesting aspect of our reasoning approach is that it is consistent with Shafer and Tversky's canonical examples. We now show that this is the case. We first introduce some terminology. Then, we give a general independence result. As it turns out, Shafer and Tversky's canonical examples are special applications of this general independence result

4.1 Some definitions

We start by introducing Dempster's rule of combination ($b), which is regarded as a purely syntactical operation by itself in our framework.

Let h be a non-empty subset of X. Let Belt and Bel2 be two belief functions on 8h (and let mt and m2 be their respective m-values). Belt $h Bel2 is defmed to be the following belief function Bel on ~:

'V S !':: ~. msei(S) = LA,B: AnB=Sm1(A)m2(B) I K, where K = L A,B: AnB,t0m 1 (A)m2(B) is the renormalization constant. (In what follows, E9x is abbreviated as$.)

Next come the notions of belief projection and belief extension. Let h and g be two subsets of X such that h ~ g (g is X by default).

The projection of an element x of 8g (e.g., g = {Xt. X2, X3, X5, X7} and x = <al, a2, a3, a5, a7>) to~. denoted as xlh, is simply this element with the extra coordinates dropped (e.g., h = {Xt. X3, Xs} and xJ.h = <al, a3, a5>). The projection of a subset A of 8g to ~. denoted as A J.h, is {x!h: x E A}.

Let Bel be a belief function on a 8 (and let m be its associated m-values), th~projection (or marginalization) of m to h, denoted as m h, is defmed as

!h ~ m (A) = ""'B: B!h=Am(B).

Bel!h (the projection of Bel to h) is, as usual, characterized by m!h.

The extension of S (S ~ ah) to a 8 , denoted asS fa, is the se~ {x: X E ag and X!h E S}.

Let Bel be a belief function on ~ (and let m be its as~iated m-values), the extension ofm tog, denoted as m 1 , is defined as

VA~~. m T 1 (AT 1 ) = m(A), and m T 1 (B) = 0 for all otherB ~ a 8 .

Belf 1 (the extension of Bel to g) is, as usual, characterized by mr1.

With all these notations in place, we now have the problem of specifying sequences of conditioning, projections, and extensions (i.e., which occurs before which). As a convention, we use m !h(A I B) to mean first conditioning and then projection (and then the value of A). The meaning of m T (A I B) is similar. To signify a particular sequence, parentheses are also used. For example, (m!h)(A I B) means pro~ection first and conditioning second, whereas ((m T 1 XA I B)) h means extension first, conditioning second, and projection last This clumsiness in the notation is very unfortunate, and we ask the reader to bear with us.

In what foll?ws, we will be using a notation such as $xyz (or Bel XY) instead of its corresponding "legal" notation (e.g., $(X,Y.Zl or Bel!(X,YJ) whenever confusions can be avoided. It is also convenient to write Bel fa, m fa, or A fa instead of Bel Tx, m Tx, or A Tx.

4.2 General independence

The notion of general independence is the belief-function counterpart of the notion of stochastic independence in probability theory. It formalizes what we mean by two "independent domains." In essence, the following definition of general independence says: whatever information we learn regarding the Y domain (i.e., ay), as long as we are not expecting the contrary with total confidence, this information will not have any effect on our (marginal) belief regarding the X domain (i.e., ax); similarly, our belief regarding the Y domain is unaffected by information concerning the X domain.

Let X and Y be two variables (or, alternatively, two disjoint sets of variables g and h). Let Belx be a belief function on ax and Bely be a belief function on ay. A belief function Bel (on a) satisfies general independence with respect to X and Y, with Belx and Bely being the two corresponding marginals, if and only if

1. Bel!x = Belx,
2. Bel!Y = Bely,
3. V B !:: ay such that 3 B' ~ ay, B ~ B' and

Bely(B) '# 0, we have Bel!x(. I B T~ = Belx, and

What Theorem 1 below tells us, then, is that we can use Dempster's rule of combination to obtain the marginal belief on axy if our belief satisfies general independence with respect to X and Y, with Belx and Bely being the two corresponding marginals.

Theorem 1 Let B be the set {Bel: Bel satisfies general independence with respect to X andY, with Belx and Bely being the two corresponding marginals}. The minimum committed belief function in B is (Belx fxy $x y BelyTxY) fa.

Proof or Theorem 1: given in the appendix.

4.3 Shafer and Tversky's canonical examples

We mentioned earlier that Shafer and Tversky's canonical examples may be viewed as special applications of our reasoning approach. In this section, we describe such an application. It is slightly more general than Shafer and Tversky's canonical examples, however - instead of working with probabilities Px and Py (as Shafer and Tversky do), we work with belief functions Belx and Bely.

The first part of the (slightly generalized) canonical examples is that we specify, through the use of fragmentary specifications, a marginal belief Belx on some space~- If this is all we specify, the system will construct Belx fa and uses it to make inferences, and (Belx T~ !z (= (Belx ~ !z) is vacuous. Suppose we now receive some information regarding the actual situation and this information comes in the form of a compatibility relation C (defined below) between ax and &z, then the updated (and projected) belief on az will be ((Belx fa)(. I C Ta))!z ( = ((Belx Txz)(. I C))!z). In general, this updated belief is not the same as the original (Belx~!z.

A compatibility relation C between ax and az is a subset of ax x az such that V a E ax. 3 c E &z, (a, c) E C. 8

The second part of the canonical examples involves a third frame ay. So let us change the story a little bit. We still specify, through the use of fragmentary specifications, a belief Belx on ax. But now we also specify, again through the use of fragmentary specifications, another belief Bely on ay. On top of that, we tel~ the system that what we really want to specify is Belx fXY $xy Bely fxY on axy, as our intuitions satisfy general independence with respect to X and Y, with Belx and Bely formalizing the two corresponding marginals. Upon receiving this instruction, the system replaces Belx and Bely with BelxTxY $xy BelyTxY.

Again, if this is all we specify, the system will construct

8Shafer (1987) also requires that\;/ c E 8z, 3 a E 8)c, (a, c) E C.

9That is, we assume that the system has some pre-processing ability and, as such, it can assist us in making fragmentary specifications

(Belx fxY E9xy Bely fXY) fa and uses it to make inferences, and ((BelxfxY E9xy BelyfxY)fayl.z (= ((BelxfxY E9xy Bely fxy) fxyzyl.z = (Belx fxyz E9xyz Bely fXYzyl.z) is vacuous. Suppose we now receive some information in the form of two compatibility relations Cxz and Cyz, where Cxz is between 8x and 8z and Cyz is between 8y and 8z. Then the u~ted (and projected) belief on 8z is (((BelxtxY $xv Bely1xY) 1 ~.1 Cxz 18 '"' Cyz 1 ~)J.z

= ((BelxtxYz $xvz Bely~(. ICxzfxYZ'"' Cyz~lz

= ((Belx~(.ICxz~ $xyz (Bely~.ICyz~)J.z

= (((BelxfxZx. ICxz)) 1xYz $xvz ((Bely~(. ICyz)) ~J.z

= ((BelxfxZx.l Cxz))J.z $z ((Bely~.l Cyz))J.z.

Of course, this updated (and projfxted) belief is, in :Aeniral, not the same as the original (Belx XYZ E9xyz Bel/ 1 z.

5 Conclusion

So what have we achieved? We have restructured the current belief-function framework in such a way that belief functions are no longer linked to probabilities. We have also provided some ingredients that we feel are necessary in order to reason with belief functions. Our reasoning approach, as we have demonstrated in the last section, is in line (at least on the formal level) with Shafer and Tversky's recommendation for reasoning with belief functions. It is also not terribly limited, as formally both propositional logic and (Bayesian) probability may be viewed as special applications of this reasoning approach [Hsia, 1990].10

Nevertheless, we did not provide a specification methodology that, when followed, would allow the system to obtain a minimum committed belief function from the specified constraints. This, however, does not render our belief-function framework useless. In fact, what we have achieved is the setting up of a formal framework that would allow researchers to identify various specification methodologies (e.g., a generalized canonical example) that can be used under different circumstances.

As for the problem of finding a general specification methodology that we can use in tackling any problem, we do not consider it feasible in pursuing in this direction. The now famous Republican-Quaker-Pacifist problem is a good example. What should the system do if the user does not specify Bel([P] I [R" Q]) and Bel([-,P) I [R" Q])? As it is entirely possible that the user himself/herself cannot make up his/her mind about these two values, there is no reason why the system should come up with an "answer". How, then, should we go about it in performing reasoning in such cases? One possible alternative may be to ask the system to infer properties that are shared by all minimally committed belief functions satisfying the same set of constraints. This appears to be an issue that is worthy of further explorations.

lOin essence, propositional logic corresponds to the case in which we only specify constraints of the form Bel(A) = 1, whereas Bayesian probability corresponds to a complete specification of prior probabilities and conditional probabilities .

Acknowledgement

Tile--author thanks Philippe Smets for being the mentor of this work, Robert Kennes for explaining Yager's ordering in terms of belief refinement, Alessandro Saffiotti for demanding a better presentation, and two anonymous referees for very helpful comments.

Appendix A: Logical formulas and subsets

Let x e 8 and a e 8i (1 ~ i ~ N), we recursively define what a formula f is and whether x satisfies the formula f.

• Case 1. f is "Xi = a": x satisfies f if and only if the Xi­ value of x is a.
• Case 2. f is "-,g", where g is a formula: x satisfies f if and only if x does not satisfy g.
• Case 3. f is "g v h", where g and h are formulas: x satisfies f if and only if x satisfies at least one of g and h.
• Case 4. f is "g " h", where g and h are formulas: x satisfies f if and only if x satisfies the formula "-,(-,g v -.h)".
• Case 5. f is "g :::> h", where g and h are formulas: x satisfies f if and only if X Satisfies the formula "-,g v h".

Let fbe a formula. By the subset (of 8) theformulafrefers to (or, alternatively, the subset (of 8) the formula f corresponds to), we mean the set (x: x e 8 and x satisfies f}, which we denote as [f).

Appendix B: Proof of Theorem 1

Basically what we need~ show is that for every element Bel of B, BelJ.xy = Belx XY $xy Bely fxY. Once this is proved, it follows that (Belx fxY E9xy Bely fxY) 18 is a minimum element in 13 with respect to a partial ordering concept originally proposed by Yager [1985] (see also [Moral, 1985]) and later discussed in detail in [Dubois and Prade, 1986b]. Moreover, Dubois and Prade [1986b] showed that whenever B has a minimum element, that element (a belief function) must be the minimum committed belief function in B . The interested reader is referred to [Hsia, 1990] for the details of Yager's ordering and Dubois and Prade's lemma

Our task now is reduced to showing that for every element Bel of :5, BelJ.XY = BelxtxY EB,cy BelyfxY.

Let Bel be an element of 13, m be the m-values associated with Bel, and mJ.XY be them-values associated with BelJ.XY. Let COREx be the union of all A !:;;; 8x: such that mx(A) * 0, and let COREy be the union of all B!::: 8y such that my(B) "# 0. We know the following are satisfied.

BelJ.x = Belx, BelJ.Y = Bely,

V be COREy, BelJ.x(.l (b} f~ = ((BelJ.XY)(.I (b} fXY))J.x =Belx,and

V a e COREx, BelJ.Y(. I (a} 1 ~ = ((BelJ.XY)(. 1 (a} fXY))J.y = Bely.

Therefore BelJ.XY must satisfy the following property:

V S!;; exy, mJ.xy(S) '* 0 if and only if3 Sx ~ex. 3 Sy!:: ey, mx(Sx) '* 0, my(Sy) '* 0, and S = Sx x Sy (mx and my are them-values associated with Belx and Bely, respectively).

Suppose A ~ ex and B ~ ey are such that mx(A) '* 0, m y(B) -:F 0, and either A '# COREx or B '# COREy. Without loss of generality, assume it is the case that B '# C 0 R E y. We have (due to the stated independence conditions) Bel( A i~ = Bel(A tel COREy if\,s i~ =Bel( A ie I e\B i~ = (Bel( A ie uBi~ - Bel(B i~)/(1 - Bel(B i~) (see [Shafer, 1976, p. 67] for this equivalent formulation of Dempster's rule of conditioning).

We expand Bel(A ie u B i~ by observing the following: V S1 ~ Ai 8 n Bi 8 (St may or may not be 0), V S~ ~ A i~A ie n B ie) (S2 '# 0), V S3 ~ B i~A ie n B ~ (S3 * 0), it is not the case that 3 C ~ex. 3 D ~ ey, such that c X D = sl u s2 u s3.

In othr,r words, V S ~ A ie u B ie (S '# 0), if neither A ie nor B 8 is a superset of S, then S :F. C x D, V C ~ex, V D ~ ey (and therefore S must have 0 as its m-value (i.e., m(S) = 0) - due to the above described propert)' of BelJ.XY). Thus, Bel( A ie u B i~ = Bel( A i~ + Bel(B t~ - Bel( Ate n Bt~.

Replacin;. this into the previous conditioning formula, we get Bel( A 8 n B t~ = Bel( A t~Bel(B t~. and this is true for any A ~ ex and B ~ ey where mx(A) '# 0 and my(B) *- 0, and either A -:F COREx orB -:F COREy.

We observe further that Bel(COREx te n COREy t~ = 1 = Bel(COREx t~Bel(COREyt~.

Thus, for every A ~ 8Y and every B ~ ey where mx(A) '# 0 and my(B) '# 0, Bel(Af 8 n B t~ = Bel(A 1 ~Bel(B t~.

Since the only subsets of exy that are "eligible" (in BelJ.XY) for non-negative m-values are those that are the Cartesian product of some A in 8x and some B in ey where mx(A) -:F 0 and my(B) '# 0 and, .

J.XY :nt~ for any such su~set Ax B, Bel (A x B) = ~el((A x ft,-, J = Bel(AT 8 n B ~ = Bel(A t~Bel(B ie) =Bel x(A)Bel (B) = Belx(A)Bely(B),

it follows that m J.XY (S) (where S ~ 8xy) must be such that if3 Sx ~ex. 3 Sy ~ ey such that S = Sx x Sy,

then mJ.xy(S) = mx(Sx)my(Sy) else mJ.XY(S) = 0.

This means BelJ.XY = BelxiXY $J(y BelyiXY. Q.E.D.