Uncertainty, Belief, and Probability

1 Introduction

Dealing with uncertainty is a fundamental issue for AI. The most widely-used approach to dealing with uncer­ tainty is undoubtedly the Bayesian approach. It has the advantage of relying on well-understood techniques from probability theory, as well as some philosophical justifi­ cation on the grounds that a "rational" agent must as­ sign uncertainties to events in a way that satisfies the ax­ ioms of probability [Cox46, Sav54] . On the other hand , the Bayesian approach has been widely criticized for re­ quiring an agent to assign a subjective probability to every event. While this can be done in principle by hav­ ing the agent play a suitable betting game (Je£83],1 it does have a number of drawbacks. Among others, there is the computational difficulty of arriving at the proba­ bility. There is also the issue of whether it is reasonable to describe confidence by a single point rather than a range. While an agent might be prepared to agree that the probability of an event lies within a given range, say between 1/3 and 1/2, he might not be prepared to say that it is precisely .435.

1 This idea is due to Ramsey (Ram31] and was rediscovered by von Neumann and Morgenstern (vNM47); a clear exposi­ tion can be found in (LR57).

Not surprisingly, there has been a great deal of debate regarding the Bayesian approach (see [Che85) and (Sha76) for some of the arguments). Numerous other approaches to dealing with uncertainty have been proposed, including Dempster-Shafer theory [Dem68, Sha76), Cohen's model of endorsements (Coh85), and various nonstandard, modal, and fuzzy logics (for ex­ ample, (HR87, Zad75]) . A recent overview of the field can be found in (Saf88]. Of particular interest to us here is the Dempster-Shafer approach, which uses belief func­ tions and plausibility Junctions to attach numerical lower and upper bounds on the likelihoods of events .

Although the Bayesian approach requires an agent to assign a probability to every event, probability theory does not . The usual reason that mathematicians deal with nonmeasurable events (those that are not assigned a probability) is out of mathematical necessity. For ex­ ample, it is well known that if the sample space of the probability space consists of all numbers in the real in­ terval (0, 1], then we cannot allow every set to be mea­ surable if (like Lebesgue measure) the measure is to be translation-invariant (see (Roy64, page 54]) . However , in this paper we allow nonmeasurable events out of choice, rather than out of mathematical necessity. An event E for which an agent has insufficient information to assign a probability is modelled as a nonmeasurable set. The agent is not forced to assign a probability to E in our approach. We can provide meaningful lower and upper bounds on our degree of belief in E by using the standard mathematical notions of inner measure and outer mea­ sure induced by the probability measure [Hal50], which, roughly speaking, are the probability of the largest mea­ surable event contained in E and the smallest measur­ able event containing E, respectively.

Allowing nonmeasurable events has its advantages. The uncertainty of event E is no longer given by a single number , but rather by an interval defined by .the inner and outer measures. Furthermore, it is possible for the belief (i.e., inner measure) of event E to be a without the belief of -,£ being 1 - a. Rather than nonmeasura­ bility being a mathematical nuisance, we have turned it here into a desirable feature!

We feel that this paper makes three major contribu­ tions. The first is conceptual: In certain situations, our approach gives a useful way to think about and reason about uncertainty. In particular , the use of nonmeasur­ able sets seems to provide a useful way to capture our uncertainty about the probability of an event. The sec­ ond is technical: We prove that, in a precise sense, inner measures induced by probability measures are equivalent to Shafer's belief functions (and so outer measures in­ duced by probability measures are equivalent to Shafer's plausibility functions). The implications of this equiv­ alence are significant. Although some, such as Cheese­ man [Che85), consider the theory of belief functions as ad hoc and essentially nonprobabilistic (see discussion by Shafer [Sha86)), our results help show that a key part of the Dempster-Shafer theory of evidence is firmly rooted in classical probability theory. The last contribution is also technical: by combining our results here with those of a companion paper [FHM88), we are able to obtain a sound and complete axiomatization for a rich propo­ sitional logic of evidence, and provide a decision proce­ dure for the satisfiability problem, which we show is no harder than that of propositional logic (NP-complete). Our techniques may provide a means for automatically deducing the consequences of a body of evidence.

2 Probability theory

To make our discussion precise, it is helpful to re­ call some basic definitions from probability theory (see [Fel57) for more details). A probability space (S,X,J.t) consists of a set S (called the sample space), a a--algebra X of subsets of S (i.e., a set of subsets of S contain­ ing S and closed under complementation and countable union, but not necessarily consisting of all subsets of S) whose elements are called measurable sets, and a proba­ bility measure w X --+ [0, 1) satisfying the following prop­ erties:

Pl. J.t(X) :::: 0 for all X E X

P2. J.t(S) = 1

P3. J.t(U~ 1 X;) = ~~ 1 J.t(X;), if the X; 's are pairwise disjoint members of X.

Property P3 is called countable additivity. Of course, the fact that X is closed under countable union guarantees that if each X; E X, then so is U~ 1 X; . If X is a finite set, then we can simplify property P3 above to

P3'. J.t(X U Y) = J.t(X) + 11-(Y), if X andY are disjoint members of X .

This property is called finite additivity. Properties P 1, P2, and P3' characterize probability measures in finite spaces.

In a probability space (S, X, Jl ), the probability mea­ sure Jl is not defined on 2 5 (the set of all subset of S), but only on X. We can extend Jl to 2 5 in two standard ways, by defining functions J.l· and J.l*, traditionally called the inner measure and outer measure induced by Jl [Hal50) . For an arbitrary subset A ~ S, we define

Jl·(A) = sup{J.t(X) I X~ A and X EX}

If there are only finitely many measurable sets (in par­ ticular, if S is finite), then it is easy to see that the inner measure of A is the measure of the largest mea­ surable set contained in A, while the outer measure of A is the measure of the smallest measurable set contain­ ing A. In any case, it is not hard to show by countable additivity that for each set A, there are measurable sets B and C where B ~ A ~ C such that J.t(B) = J.t.(A) and J.t( C) = Jl* (A). Note that if there are no nonempty measurable sets contained in A, then J.t.(A) = 0, and if there are no measurable sets containing A other than the whole space S, then J.t*(A) = 1. The properties of probability spaces guarantee that if X is a measurable set, then J.t.(X) = Jl*(X) = J.t(X). In general we have J.t*(A) = 1- J.t.(A).

Suppose we have a situation we want to reason about. Typically we do so by fixing a finite set ~ = {P1, ... , Pn} of primitive propositions, which can be thought of as cor­ responding to basic events, such as "it is raining now'' or "the coin landed heads". The set .C(~) of (proposi­ tional) formulas is the closure of~ under the Boolean operations /\ and -.. The primitive propositions in ~ do not in general describe mutually exclusive events . To get mutually exclusive events, we can consider all the atoms, that is, all the formulas of the form p~ /\ .. . /\ p~, where p: is either p; or -.p;. Let At denote the set of atoms.

We have been using the word "event" informally, sometimes meaning "set" and sometimes meaning ''for­ mula" . We now want to be more formal, and to be able to talk explicitly about the probability of a for­ mula. However, a probability measure is a function on sets, not formulas. Fortunately, it is easy to go from sets to formulas.

Using standard propositional reasoning, it is easy to see that any formula can be written as a disjunction of atoms. Thus, a formula 'P can be identified with the unique set { 81 , . . . , 8k} of atoms such that 'P = 81 V ... V 8k. If we want to assign probabilities to all formulas, we can simply assign probabilities to each of the atoms, and then use the finite additivity property of probability measures to compute the probability of an arbitrary formula. This amounts to taking a probability space of the form (At, 2At, J.t). The states in the probabil­ ity space are just the atoms, and the measurable subsets are all the sets of atoms (i.e., all formulas). Once we as­ sign a measure to the singleton sets (i.e., to the atoms), we can extend by additivity to any subset. We call such a probability space a Nilsson structure, since this is es­ sentially what Nilsson used to give meaning to formulas in his probability logic [Nil86].2 Given a Nilsson struc­ ture N =(At, 2At, J.t) and a formula 'P, let WN('P) denote the weight or probability of 'P in N, which is defined to be ll(At('P)), where At('P) is the set of atoms whose dis­ junction is equivalent to 'P·

A more general approach is to take a probability struc­ ture to be a tuple (S,X,J.t,11"), where (S,X,J.t) is a prob­ ability space, and 1r associates with each s E S a truth assignment 1r(s):~--+ {true,false}. We say that pis true at s if 1r(s)(p) = true; otherwise, we say that pis false at s .

2 Actually, the use of possible worlds in giving semantics to probability formulas goes back to Carnap [Car50].

We think of S as consisting of the possible states of the world. We can associate with each state s in S a unique atom describing the truth values of the primitive propositions in s. For example, if~ = {p1 ,p2}, and if 1r( s )(pi) = true and 1r( s )(p2) = false, then we associate with s the atom PI 1\ -,P2· It is perfectly all right for there to be several states associated with the same atom (indeed, there may be an infinite number, since we allow S to be infinite, even though~ is finite). This situation may occur if a state is not completely characterized by the events that are true there . This is the case, for exam­ ple, if there are features of worlds that are not captured by the primitive propositions .

We can easily extend 1r(s) to a truth assignment on all formulas by taking the usual rules of propositional logic. Then if M is a probability structure, we can associate with every formula <p the set 'PM consisting of all the states in M where <p is true (i.e., the set {s E S l1r(s)(<p) = trueJ_) . Of course, we assume that 1r is defined so that true = S. If pM is measurable for every primitive proposition p E ~. then 'PM is also mea­ surable for every formula <p (since the set X of measur­ able sets is closed under complementation and countable union). We say M is a measurable probability structure if 'PM is measurable for every formula <p .

It makes sense to talk about the probability of <p in M only if 'PM is measurable; we can then take the.Jrob­ ability of <p, which we denote WM(<p), to be J-t('P ). If 'PM is not measurable, then we cannot talk about its probability. However, we can still talk about its inner measure and outer measure, since these are defined for all subsets. Intuitively, the inner and outer measure pro­ vide lower and upper bounds on the probability of <p. In general, if 'PM is not measurable, then we take WM('P) to be p.{<p) , i.e ., the inner measure of <pin M .

We define a probability structure M and a Nilsson structure N to be equivalent if WM('P) = WN('P) for every formula <p. Intuitively, a probability structure and a Nilsson structure are equivalent if they assign the same probability to every formula. The next theorem shows that there is a natural correspondence between Nilsson structures and measurable probability structures. 3

Theorem 2.1:

1. For every Nilsson structure there is an equivalent measurable probability structure.
2. For every measurable probability structure there is an equivalent Nilsson structure.

Why should we even allow nonmeasurable sets? As the following example shows (as do others given in the full paper), using nonmeasurability allows us to avoid assigning probabilities to those events for which we have insufficient information to assign a probability.

Example 2.2: Ron has two blue suits and two gray suits. He has a very simple method for deciding what color suit to wear on any particular day: he simply tosses a (fair) coin: if it lands heads he wears a blue suit , and if it lands tails he wears a gray suit. Once he's decided what color suit to wear, he just chooses the rightmost suit of that color on the rack. Both of Ron's blue suits are single-breasted, while one of Ron's gray suits is single-breasted and the other is double-breasted. Ron 's wife Susan is (fortunately for Ron) a little more fashion-conscious than he is. She also knows how Ron makes his sartorial choices. So, from time to time, she makes sure that the gray suit she considers preferable is to the right (which it is depends on current fashions and perhaps on other whims of Susan). 4 Suppose we don't know about the current fashions (or about Susan's cur­ rent whims). What can we say about the probability of Ron's wearing a single-breasted suit on Monday?

3 The proof of this and all other theorems mentioned here can be found in the full paper (FH88) .

In terms of possible worlds, it is clear that there are four possible worlds , one corresponding to each of the suits that Ron could choose. For definiteness, sup­ pose states s1 and 8 2 correspond to the two blue suits, 83 corresponds to the single-breasted gray suit, and s4 corresponds to the double-breasted gray suit. Let S = { s 1 , s2, s3, s4}. There are two features of interest about a suit: its color and whether it is single-breasted or double-breasted. Let the primitive proposition g de­ note "the suit is gray" and let db denote "the suit is double-breasted", and define the truth assignment 1r in the obvious way. Note that the atom -,g 1\ -,db is asso­ ciated with both states s 1 and s2. Since the two blue suits are both single-breasted, these two states cannot be distinguished by the formulas in our language.

What are the measurable events? Besides S itself and the empty set, the only other candidates are { 8 1 , s2} ( "Ron chooses a blue suit" ) and {s3, s4} ( "Ron chooses a gray suit"). However, SB = {s1 ,s2,s3} ( "Ron chooses a single-breasted suit") is nonmeasurable. The reason is that we do not have a probability on the event "Ron chooses a single-breasted suit , given that Ron chooses a gray suit", since this in turn depends on the probability that Susan put the single-breasted suit to the right of the other gray suit, which we do not know. Susan's choice might be characterizable by a probability distribution; it might also be deterministic, based on some complex al­ gorithm which even she might not be able to describe; or it might be completely nondeterministic, in which case it is not technically meaningful to talk about the "probabil­ ity" of Susan's actions! Our ignorance here is captured by nonmeasurability. Informally, we can say that the probability of Ron choosing a single-breasted suit lies somewhere in the interval [1/2, 1) , since it is bounded below by the probability of Ron choosing a blue suit. This is an informal statement because formally it does not make sense to talk about the probability of a non­ measurable event . The formal analogue is simply that the inner measure of SB is 1/2, while its outer measure is 1. I

4 Any similarity between the characters in this example and the first author of this paper and his wife Susan is not totally accidental .

3 The Dempster-Shafer theory of evidence

The Dempster-Shafer theory of evidence [Sha76] pro­ vides another approach to attaching likelihoods to events. This theory starts out with a belief function (sometimes called a support function). For every event (i.e., set) A, the belief in A, denoted Bei(A), is a number in the interval [0, 1] that places a lower bound on likelihood of A. We have a corresponding number PI(A) = 1- Bei(A), called the plausibility of A, which places an upper bound on the likelihood of A. Thus, to every event A we can attach the interval [Bel( A), PI( A)]. Like a probability measure, a belief function assigns a "weight" to subsets of a set S, but unlike a probabil­ ity measure, the domain of a belief function is always taken to be all subsets of S. Just as we defined prob­ ability structures, we can define a DS structure (where, of course, "DS" stands for Dempster-Shafer) to be a tu­ ple (S, Bel, 1r), where S and 1r are as before, and where Bel: 2 5 -+ [0, 1] is a function satisfying:

A belieffunction is typically defined on a frame of dis­ cernment, consisting of mutually exclusive and exhaus­ tive propositions describing the domain of interest. We think of the set S of states in a belief structure as be­ ing this frame of discernment. We could always choose S to be some subset of At, the set of atoms, so that its elements are in fact propositions in the language. In general, given a DS structure D = (S, Bel, 1r) and for­ mula <p, we define the weight Wn(<p) to be Bel(<pD), where <pD is the set of states where <p is true. Thus we can talk about an agent's degree of belief in <p in D, described by Wn(<p), by identifying <p with the set <pD and considering the belief in <pD. As before, we de­ fine a probability structure M (resp., a Nilsson struc­ ture N, aDS structureD') and aDS structureD to be equivalent if WM(if!) = Wn(if!) (resp., WN(if!) = Wn(<p), Wn'(if!) = Wn(<p)) for every formula <p.

Property 83 may seem unmotivated. Perhaps the best way to understand it is as an analogue to the usual inclusion-exclusion rule for probabilities [Fel57, p. 89], which is obtained by replacing the inequality by equal­ ity (and the belieffunction Bel by a probability measure J.L). In particular, 83 holds for probability measures (we prove a more general result, namely that it holds for all inner measures induced by probability measures, in Proposition 3.1 below} Hence, if(S,X,J.L) is a probabil­ ity space and X = 2 (making every subset of S mea­ surable), then J.l is a belief function. (This fact has been observed frequently before; see, for example, [Sha76].) It follows that every Nilsson structure is a DS structure.

It is easy to see that the converse does not hold. For example, suppose there is only one primitive proposi­ tion, say p, in the language, so that At = {p, ...,p}, and let D0 = (At, Bel, 1r) be such that Bel( {p}) = 1/2, Bel( { ...,p}) = 0, and 1r is defined in the obvious way.

Intuitively, there is weight of evidence 1/2 for p, and no evidence for ...,p. Thus Wn 0 (p) = 1/2 and Wn 0 (...,p) = 0. Do is not equivalent to any Nilsson structure, since if N is a Nilsson structure such that WN(P) = 1/2, then we must have WN(...,p) = 1/2.

These observations tell us that in some sense belief functions are more general than probability measures, provided we restrict attention to probability spaces where all sets are measurable. This fact is well known. Indeed, in [Sha76], Shafer makes explicit use of the greater generality of belief functions. While he does con­ sider events E such that Bel(...,£) = 1-Bei(E) (he calls such events probabilistic), he also wants to allow non­ probabilistic events. He gives examples of events where the fact t!lat we would like to assign weight .8 to our belief in event E does not mean that we want to assign weight .2 to our belief in ...,£. In our framework, where we allow nonmeasurable sets, we can view probabilistic events as corresponding to measurable sets, while non­ probabilistic events do not. We can push this analogy much further. Not only do nonmeasurable sets corre­ spond to non-probabilistic events, but the inner mea­ sures induced by probability measures correspond to be­ lief functions.

Proposition 3.1 : If ( S, X; J.l) is a probability space, then J.l· is a belief function on 2 5 .

Proposition 3.1 says that every inner measure is a be­ lief function (and thus generalizes the statement that every probability measure is a belieffunction). The con­ verse does not. quite hold. For example, consider the DS space Do defined above. There is no probability mea­ sure J.l that we can define on {p, -,p} such that J.l· =Bel. However, it is easy to define a probability structure M such that J.l.(pM) = 1/2 and J.l·(...,pM) = 0. That is, we can find a probability structure equivalent to D0 . The next theorem generalizes this observation.

Theorem 3.2:

1. For every DS structure there is an equivalent prob­ ability structure.
2. For every probability structure there is an equivalent DS structure.

Intuitively, Theorem 3.2 says that belief functions and inner measures induced by probability measures are pre­ cisely the same if their domains are considered to be formulas rather than sets. As we shall see, this result has important implications regarding complete axioma­ tizations and decision procedures.

4 Reasoning about belief and probability

We are often interested in the inferences we can make about probabilities or beliefs given some information. In order to do this, we need a language for doing such reasoning. Such a language is given in [FHM88]. A term in this language is an expression of the form a1w(<p!) + ... + akw(if!k), where a1, ... ,ak are integers and <p1 , ... , if!k are propositional formulas. A basic weight formula is one of the form t ;:::: b, where t is a term and b is an integer. A weight formula is a Boolean combination of basic weight formulas. We sometimes use obvious abbreviations without further comment, such as w( <p) 2: w( 1/;) for w( <p) - w( 1/;) 2: 0.

We give semantics to the formulas in our language with respect to all the structures we have been considering. Let K be either a Nilsson structure, a probability struc­ ture, or a DS structure, and let f be a weight formula. We now define what it means for /{ to satisfy f, written K F f . For a basic weight formula,

We then extend f: in the obvious way to conjunctions and negations . The interpretation of w( <p) is either "the probability of <p" (for Nilsson structures or measurable probability structures), "the inner measure of <p" (for general probability structures), or "the belief in <p" (for DS structures).

Let K: be a class of structures (in the cases of inter­ est to us, K: is the class of either probability structures, measurable probability structures, Nilsson structures, or DS structures). As usual , we define a weight formula f to be satisfiable with respect to K: if !{ f: f for some K E K:. Similarly, f is valid with respect to K: if /{ f: f for all K E K:.

In [FHM88], an axiom system AXM EAS for reason­ ing about measurable probability structures is provided. The system has three parts, which deal respectively with propositional reasoning, reasoning about linear inequal­ ities, and reasoning about probability. For example, a typical axiom for reasoning about linear inequalities is

which says that both sides of an inequality can be mul­ tiplied by a positive constant. (The remaining axioms for reasoning about inequalities are described in the full paper.)

For reasoning about probability, we have the following axioms. The first three correspond to the usual laws of probability, except that W3 corresponds to finite addi­ tivity, not countable additivity.

Wl. w( <p) 2: 0 ( nonnegativity)

W2. w(true) = 1 (the probability of the event true is 1)

W3. w(<p 1\ 1/;) + w(<p 1\ · 1/;) = w(<p) (additivity)

W 4. w( <p) = w( 1/;) if <p = 1/; is a propositional tautology

As is shown in [FHM88) , AXM EAS characterizes the valid formulas for measurable probability structures.

Theorem 4.1: ([FHM88]) AXMEAS is a sound and complete axiomatization for weight formulas with respect to measurable probability structures.

This result, together with Theorem 2.1, immediately gtves us

Corollary 4.2: AXMEAS is a sound and complete ax­ iomatization for weight formulas with respect to Nilsson structures.

AXM EAS is not sound with respect to arbitrary prob­ ability structures, where w( <p) is interpreted as the inner measure of <pM. In particular, axiom W3 no longer holds: inner measures are not finitely additive. Let AX be ob­ tained from AXM EAS by replacing W3 by the following two axioms, which are obtained from conditions Bl and B3 for belief functions in an obvious way:

W5. w(false) = 0

Theorem 4.3: ([FHM88]) AX is a sound and complete axiomatization for weight formulas with respect to prob­ ability structures.

Applying Theorem 3.2, we immediately get

Corollary 4.4: AX is a sound and complete axiomati­ zation for weight formulas with respect to DS structures.

Thus, using AX, we can derive all consequences of a collection of beliefs.

Combining the preceding results with results of [FHM88] , we can also characterize the complexity of rea­ soning about probability and belief.

Theorem 4.5: The complexity of deciding whether a weight formula is satisfiable with respect to probabil­ ity structures (respectively, measurable probability struc­ tures, Nilsson structures, DS structures) is NP-complete.

(This result in the case of Nilsson structures was ob­ tained independently in [GKP88].) Note that Theo­ rem 4.5 says that reasoning about probability and belief is, in a precise sense, exactly as difficult as propositional reasoning. This is the best we could expect, since it is easy to see that reasoning about probability and belief is at least as hard as propositional reasoning (the propo­ sit ional formula <p is satisfiable iff the weight formula w( <p) > 0 is satisfiable).

5 Combining evidence

An important issue for belieffunctions, each of which can be viewed as representing a distinct body of evidence, is how to combine them to obtain a new belief function that somehow reflects the combined evidence. A way of doing so is provided by Dempster's rule of combination, which was introduced by Dempster [Dem68] and was further developed and studied in an elegant and rather complete manner by Shafer [Sha76].

In the full paper [FH88], we show that there is a nat­ ural way (in the spirit of Dempster's rule) to define the combination D1 EB D2 of two DS structures Dt and D2, and a natural way to define the combination Mt EB M2 of two probability structures M1 and M2 , such that the following theorem holds .

Theorem 5.1: Let D1 and D2 be DS structures. There are probability structures M1 and M2 such that (a) Dt is equivalent to M1 , (b) D2 is equivalent to M2, and (c) D1 EB D2 is equivalent to Mt EB M2.

This theorem shows that the spirit of Dempster's rule of combination can be captured within probabil­ ity theory. We are currently investigating alternatives to Dempster's rule of combination for rev1smg beliefs about uncertainty in the presence of new information. The idea is to consider what it means to take a condi­ tional probability with respect to a nonmeasurable set. We plan to report on this work in a future paper.

6 Related work

Although we believe we are the first to propose using inner and outer measures as a way of dealing with un­ certainty, there are a number of other works with similar themes. We briefly discuss them here.

A number of authors have argued that we should think in terms of an interval in which the probability lies, rather than a unique numerical probability (see, for example, [Kyb61, Kyb88]) . Good [Goo62], Koopman [Koo40a, Koo40b], and Smith [Smi61] try to derive rea­ sonable prop.erties for the intuitive notions of lower and upper probability, which are somehow meant to capture lower and upper bounds on an agent's belief in a propo­ sition. Good observes that "The analogy [between lower and upper probability and] inner and outer measure is obvious. But the axioms for upper and lower probabil­ ity do not all follow from the theory of inner and outer measure."

Dempster [Dem66, Dem68] gives a formal mathemat­ ical definition of lower and upper probability in terms of a tuple (S, J.l, T, f), which we call a Dempster struc­ ture. (S, 2 5 , p) is a probability space (Dempster assumes for simplicity that every subset of S is measurable) , T is another set, and r is a multi-valued mapping S to T. Thus, f(s) is a subset ofT for each s E S. Given A~ T, we define subsets A. and A · of S as follows:

Provided p(T*) f. 0, we define the lower and upper prob­ abilities of A, written P.(A) and P*(A) respectively, by

It is easy to check that T. = T*. Thus, dividing by p(T*) has the effect of normalizing so that P.(T) = P*(T) = 1.

There is a close relationship between lower and up­ per probabilities and inner and outer measures induced by a probability measure. Given a probability structure M = (S,X,p,1r) where Sis finite, let (X',p',T,f) be the Dempster structure where (1) X' is a basis for X, 5 (2) p' is a probability measure defined on 2x' by tak­ ing J.l 1 ( {A}) = p( A) for A E X' and then extending to all subsets of X' by finite additivity, (3) T consists of all propositional formulas, and ( 4) for A E X', we de­ fine f(A) to consist of all formulas t.p such that t.p is ~rue at some point in A (in the structure M). Thus r IS a multivalued mapping from X' to T. It is easy to check that P.({t.p}) = p.(t.pM) and P*({t.p}) = p*(<pM) for all formulas t.p.

5 A subset X' of X is said to be a basis (of X) if the mem­ bers of X' are nonempty and disjoint, and if X consists pre­ cisely of countable unions of members oLl''. It is easy to see that if X is finite then it has a basis. Moreover, whenever X has a basis, it is unique: it consists precisely of the minimal elements of X (the nonempt.y sets none of whose nonempty subsets are in X). Note that if X has a basis, once we know the probability of every set in the basis, we can compute the probability of every measurable set by using countable additivity.

Ruspini [Rus87] also considers giving semantics to probability formulas by using possible worlds, but he includes epistemic notions in the picture. Briefly, his approach can be described as follows (where have taken the liberty of converting some of his notation to ours, to make the ideas easier to compare) . Fix a set {PI, ... , Pn} of primitive propositions. Instead of considering just propositional formulas, Ruspini allows epistemic formu­ las; he obtains his language by closing off under the propositional connectives /\, V, :::}, and -., as well as the epistemic operator ]{. Thus, a typical formula in his language would be K(pl :::} K(p2 1\ P3)). (A for­ mula such as ]{ t.p should be read "the agent knows t.p .") Rather than considering arbitrary sample spaces as we have done here, where at each point in the sample space some subset of primitive propositions is true, Ruspini considers one fixed sample space S (which he calls a sen­ tence space) whose points consist of all the possible truth assignments to these formulas consistent with the axioms of the modal logic S5. (See, for example, [HM85] for an introduction to S5. We remark that it can be shown that there are less than 2n2 2 n consistent truth assignments, so that S is finite.) We can define an equivalence re­ lation ,...., on S by taking s ,...., t if s and t agree on the truth values of all formulas of the form /( t.p. The equiv­ alence classes form a basis for a a--algebra of measurable subsets of S. Let X be this a--algebra. For any formula t.p , let t.p 5 consist of all the truth assignments in S that make t.p true. It is easy to check that ( /( t.p ) 5 , the set of truth assignments that make ]{ t.p true, is the union of equivalence classes, and hence is measurable. Let J.l be any probability measure defined on X . Given J.l, we can consider the probability structure (S, X, J.l, 1r), where we take 1r(s)(p) = s(p). (Since sis a truth assignment, this is well defined.) The axioms of S5 guarantee us that ( J{ t.p ) 5 is the largest measurable subset contained in t.pM; thus, p.(t.pM) = p((K<p) 5 ).

Ruspini then considers the DS structure (At, Bel, 1r'), where 1r 1 is defined in the obvious way on the atoms in At, and Bel(t.pD) = p((I<<p) 5 )(= p.(t.pM)). 6 Ruspini shows that Bel defined in this way is indeed a belief function. Thus, Ruspini shows a close connection be­ tween probabilities, inner measures, and belief functions in the particular structures that he considers. He does not show a general relationship between inner measures and belieffunctions; in particular, he does not show that DS structures are equivalent to probability structures, as we do in Theorem 3.2.

In the full paper, we explore further relations between our work and that of Ruspini, as well as comparing our characterization of belief functions with those of Shafer [Sha79], Kyburg [Kyb87], and Pearl [Pea88].

6 Ruspini actually defines the belief function directly on formulas; i.e., he defines Bel( cp ) . In our notation, what he is doing is defining a weight function W D.

Acknowledgments

The authors are grateful to Glenn Shafer, Moshe Vardi, and Henry Kyburg for helpful comments and sugges­ tions.