Epistemic Logics, Probability, and the Calculus of Evidence

I Introduction

The research work presented here was motivated by the need to improve the understanding of issues in the analy­ sis and interpretation of evidence. In the context of this paper, the term evidence is used to describe the informa­ tion, usually imprecise and uncertain, that is conveyed by observations and measurements of real-world systems. We have sought to gain such an understanding by examining the basic concepts, structures, and ideas relevant to the characterization of imprecise and uncertain knowledge.

Our approach is strongly based on Carnap 's method­ ology (Carnap 1956, 1962) for the development of logical foundations of probability theory. In his formulation, Car­ nap developed an universe of possible worlds that encom­ passes all possible valid states of a real-world system. Infor­ mation about that system, if precise and certain, identifies its actual state (e.g., a detailed diagnosis of a disease). If imprecise but certain, this information identifies a subset of possible system states (e.g., a number of possible diag­ noses). If uncertain, then the information induces a pro­ bability distribution over system states (e.g., probability values for specific diagnoses).

It is important to note, however, that in Carnap's char­ acterization no distinction is drawn between degrees of pre­ cision or detail when the information is uncertain. This representational shortcoming renders impossible the mod­ eling of information that only assigns degrees of likelihood values to some subsets of possible states (i.e., instead of prescribing those values over all such subsets that are of relevance to the modeler). This type of information, pro­ viding some knowledge about the underlying probability distributions but not all the distribution values, is quite common in practical applications (e.g., in a medical diag­ nosis problem, tests and existing medical knowledge indi­ cate that there is a 60% chance of liver disease but fail to provide any information about the likelihood of individual instances thereof).

Seeking to generalize Carnap's approach to allow for the treatment of this type of uncertain information we di­ rected our attention to epistemic logics - a form of modal logics developed to deal with problems of representation and manipulation of the states of knowledge of rational agents. Originally studied by Hintikka (Hintikka 1962), their use in artificial intelligence problems was proposed by Moore (Moore 1980). Recently epistemic logics have also been applied to the design of intelligent robots (Rosenschein and Kaelbling 1986).

In our extension of the Carnapian ideas the starting point is a generalization of Carnap 's space of possible worlds, or universe. This generalization, obtained by consider­ ing representations of both the state of the world and the knowledge of rational agents, is called the epistemic uni­ verse. Described in the next section, the epistemic universe contains several interesting and important subset families. Two of these collections have as members truth sets and support sets, which are related, respectively, to different on­ tological and epistemological properties of possible worlds. Furthermore, these families have the properties of sigma algebras, i.e. the basic domain of definition of probability functions .

Again following Carnap's lead we define probabilities on these sigma algebras and consider their relationships. We differ from Carnap, however, in that we view evidence as generally providing information about the truth of some propositions while failing to give any indication about the truth of others. Evidence is further regarded as a poten­ tial modifier of our state of knowledge; accordingly, uncer­ tain evidence is represented as a conventionaJl probability function defined on the algebra of epistemic sets. This probability is then shown to have the structure of the ba­ sic functions of the Dempster-Shafer calculus of evidence (Dempster 1967, Shafer 1976). Furthermore, if such an epistemic probability is extended to the sigma algebra of the truth sets (representing probabilities of the truth of propositions that describe the world), then the extension must satisfy the bounds of the Dempster-Shafer theory. These bounds correspond to the well-known concepts of lower and upper probability funct ions and, in this partic­ ular regard, our results are in agreement with the char­ acterization made by Suppes (Suppes 1974) of the role of uncertain information in determining the probability dis­ tribution values that underlie rational choices in decision problems.

Our approach is also related in several ways to the prob­ abilistic logic approach of Nilsson (Nilsson 1986) - the major differences being in the use of epistemic concepts and the derivation of global conditions for probability ex­ tension, in contrast to formulas derived from interval pro­ bability theory or from approximate-estimation techniques.

In addition, this work has similarities with that of Halpern and McAllester (Halpern and McAllester 1984)- the dis­ similarities in this case being in the methods used to model uncertainty. It is important to note, however, that Halpern and McAllester represent likelihood formally as the probability of knowledge (in the epistemic-logic sense) of propo­ sitional truth, using an interpretation that is similar to ours in several significant respects.

'This function, satisfying the axioms of probability theory, is de­ fined unambiguously on the sigma algebra of epistemic sets.

Section 4 deals with the problems associated with the combination of the knowledge of several mutually trusting agents. Under assumptions that guarantee that the inte­ grated knowledge is solely the logical consequence of the states of knowledge of the agents, several results are pre­ sented, including a general formula for knowledge combi­ nation. This additive combination formula may be applied to several knowledge integration problems involving either dependent or independent evidential bodies. For the latter case, the corresponding result generalizes the Dempster's rule of combination.

It is important to emphasize that the results of Sec­ tions 3 and 4, identifying the Dempster-Shafer calculus of evidence with the probability calculus in the epistemic universe, were derived by the direct application of conven­ tional probability theory concepts without having to intro­ duce other multivalued logic notions. The insight gained by using an epistemic model as the basic foundation of the Dempster-Shafer calculus of evidence has made possible the extension of this evidential formalism by the incorpo­ ration of new formulas for combining dependent evidence and for utilizing conditional knowledge.

In the exposition that follows, we have not included the proofs of any of the theoretical results obtained in the research being discussed, as such extensive discussion is well outside the scope of this paper. The reader interested in the actual details will find them discussed in a related work (Ruspini 1986a).

II The Epistemic Universe

A. The Carnapian Universe

Carnap's logical approach to probability starts with the construction of a space of possible worlds that encompasses all valid states of a system of interest. First, all proposi­ tions (actually instantiated first-order-logic predicates in Carnap's formulation) of relevance to the system

are considered. All possible conjunctions of the type

where every proposition appears only once either as itself or as its negation, are then considered. After discarding log­ ical impossibilities, the resulting set of logical expressions includes all possible system states that may be represented using the propositions p, q, .. ..

Each such state corresponds to the truth of an atomic proposition about the system in question. These atomic propositions are equivalent to the elementary events in­ troduced in most treatments of basic probability theory.

Obviously, by construction, only one such proposition can truly describe the state of the world. The space of atomic propositions, or universe, is therefore a collection of all possible alternative states of the system.

Possible worlds can also be regarded as functions that map each relevant proposition into its truth-value (i.e. true or false) or, alternatively, as subsets of true propositions (i.e., those mapped into the true truth-value). If a possi­ ble world is viewed through a "conceptual microscope" as illustrated in Figure 1, it can be seen to contain all true propositions in that world, including the negations of those that are false. Two possible worlds will always be different since at least one proposition which is true in one of them will be false in the other.

The space of possible worlds. (considered as a proba­ bilistic space) is the basic structure used by Carnap to relate the values of probability functions of subsets associ­ ated with relevant propositions on the basis of the logical relationships between those propositions.

B. Epistemic Considerations

Carnap's logical approach, while enabling a clearer un­ derstanding of the relations between logical and probabilis­ tic concepts, suffers from a major handicap: it assumes that observations of the real world always determine unambigu­ ously probability values for every subset in the universe. This assumption leads inevitably to problems associated with the need to define probability values when the under­ lying information is not rich enough to furnish them.

If, for example, we have certain (i.e., sure) information that a guest to a party we are hosting is fond of French wine, we would ordinarily consider, in a non probabilis­ tic setting, that this information constrains our spectrum of beverage choices ( assu~ing, of course, that we aim to please our guest and are able to do so) without identify­ ing what particular label or vintage he is likely to prefer. If, instead of being sure, our informant is uncertain and believes there is an 80% chance that our caller will like French wine and a 20% chance that he will opt for beer, it is unreasonable (simply because uncertainty has now en­ tered the picture) to assume that this information can be used to assign probabilities for particular choices of wine or beer when before, in a world of certainty, we regarded similar information as being only capable of identifying a subset of possibilities.

These considerations have led to the development of schemes to represent uncertain information as constraints on the values of valid probability distributions. Interval probability theories (Williams 1976), of which the Dempster­ Shafer calculus .is a particular case, are important examples of this technique.

The approach we have followed here, however, proceds from a different logical foundation. Starting from the no­ tion that certain information improves our knowledge by reducing the scope of possible valid states, it considers that uncertain information is associated with a probability func­ tion defined on some subsets (actually a sigma algebra) of the universe, rather than on every subset of the universe. While in the case of certain information we say that we know that the system state is in a subset of possible states, in the case of uncertain information we similarly affirm, with some degree of likelihood, that that state is in in a certain region of the universe. The corresponding proba­ bility values constrain the values of other probability func­ tions defined over richer subset collections (i.e., probability extensions).

To identify a model that constitutes the basis for defin­ ing probabilities that take values over epistemic structures,. we must look at abstract formalisms that allow proper differentiation between states of the world and states of knowledge. This framework is provided by epistemic log­ ics.

C. Epistemic Logics and Epistemic Universes

The starting point for our generalization of the Car­ napian universe is again a collection of propositions about the real world, denoted by p, q, r, s, .. .. We consider, in ad­ dition, more complex propositions obtained therefrom by negation, conjunction, and disjunction. 2 The resulting set of propositions is called a frame of discernment. Each of its members, describing a state of the world, is called an objective proposition or objective sentence.

In addition to objective sentences, we shall also deal with propositions that represent states of knowledge about the real world. When only one rational agent is concerned, the simplest of these epistemic propositions are denoted by Kp, Kq, Kr, ... , representing knowledge of their corre­ sponding objective counterparts. We shall also consider ex­ pressions formed by combination of epistemic and objective propositions through disjunction, conjunction, implication, and negation, as in the examples ·Kr, or p V K(q V Ks). The set of all such propositions, which encompasses the frame of discernment as a subset, is called the sentence space, denoted by S .

~We also consider the material implication--+ defined, as usual, in terms of the negation and disjunction operations.

The next step in constructing an extension of the Car­ napian universe is the generation of all possible states by the assignment of truth-values to propositions in the sen­ tence space. In addition to compliance with the axioms of ordinary propositional logic, we shall also need the follow­ ing axioms, which supply the unary operator K with the required epistemilogical semantics:

• (El) If Kp is true, then p is true.
• (E2) If Kp is true, then KKp is true (positive introspec­ tion).
• (E3) If K(p-+q) is true, then Kp-+Kq is also true.
• (E4) If ·Kp is true, then K ·Kp is true (negative intro­ spection) .
• (ES) If pis an axiom, then Kp is an axiom.

This system is equivalent to the modal logic system 85 (Hughes and Creswell1968).

The space of possible worlds generated on the basis of the above schemata is called the epistemic universe and is denoted by U ( S). When seen through our imaginary conceptual microscope, as shown in Figure 2, each pos­ sible world includes, as before, all objective propositions that are true in that world. Each possible world, however, includes also all true epistemic propositions representing knowledge of the truth (e.g., Kp) or falsehood (K ·p) of propositions and, in addition, propositions describing ig­ norance regarding the truth or falsehood of certain propo­ sitions (e.g., · Kp t\·K·p) .

It is important to note that, in the epistemic universe, possible worlds may share the same set of true objective propositions, even though the states of knowledge (i.e., true epistemic propositions) will be different in each case.

In the remainder of this work we will require to employ two important relations.

The first, called logical implication and denoted by =>, holds between propositions in sentence space. This rela­ tion, well known in modal logic, is used to indicate the fact that in any possible world the truth of some proposition implies that of another. In other words, if p=>q, then it is logically impossible for q 'to be false if p is true.

The second relation, called the accessibility relation and denoted by~, holds between possible worlds in the episte­ mic universe. Two possible worlds are related through the accessibility relation if the same epistemic propositions are true in both worlds. 3 Clearly, such world pairs cannnot be discriminated on the basis of the information (i.e. knowl­ edge) available in each of them.

D. Special Sets in the Epistemic Universe

Several subsets of the epistemic universe are of impor­ tance in the definition of probability functions that ade­ quately represent the effects of uncertain evidence in know!­ . edge states.

The subset of all possible worlds where an objective proposition p is known to be true, i.e. in which the episte­ mic sentence Kp is true, is called the support set of p and is denoted by k (p) .

The epistemic set for an objective proposition p is the set of all possible worlds in which p is the most specific proposition that is known to be true (i.e., p is the conjunc­ tion of all objective propositions q such that Kq is true). The epistemic set e(p) consists of possible worlds where Kq is true if and only if q is logically implied by p, i.e., p=>q. Pairs of possible worlds in the same epistemic set are always related by the accessibility relation ~.

Epistemic sets and support sets are related by the set

3 As characterised here, this relation is identical to the accessibility relation of modal logic only in the case of systems such as 85, where the accessibility relation is assumed to have the properties of a classical equivalence relation.

which is of essential importance to establish the relation­ ship between epistemic constructs and the Dempster-Shafer calculus. Epistemic sets corresponding to different propo­ sitions (i.e., those that are not logically equivalent - de­ noted simply by f. in this work) are disjoint - the above expression, therefore, represents the disjoint partition of support sets in terms of epistemic sets. Furthermore it can be proved that

Finally, truth sets are important subsets of the episte­ mic universe that are directly related to the truth of ob­ jective, rather than epistemic, propositions. The truth set t(p) for an objective proposition p is the collection of all possible worlds where the prposition p is true.

Since p is true in a possible world W whenever Kp is true in W, then it follows that the support set k(p) is a subset of the truth set t(p). It is also true that k(p) is the largest support set contained in t(p). 4

The inclusion relations between truth, support and epis­ temic sets are graphically illustrated in Figure 3. This figure shows the truth set t(p) for a proposition p; its cor­ responding support set k(p); and the epistemic sets for several propositions which imply p (including the episte­ mic set for p itself). As noted before, epistemic sets e(q) for propositions q that do not imply p are disjoint from the support set k(p) and intersect the complement t(p) of the truth-set t(p).

III Epistemic Probabilities

A. Sigma Algebras

The collections of subsets defined in the previous sec­ tion are of particular importance in a number of respects.

First, epistemic and support sets have a clear epistemo­ logical interpretation as representations of similar states of certain (i.e., sure) knowledge. Furthermore, the effect of uncertain information on states of knowledge can be rep­ resented by probability values assigned to these sets.

Truth sets, on the other hand, represent states of the world that share some ontological property. Probability values assigned to these sets represent the likelihood of certain events in the real world- namely, the truth of the proposition associated with the truth set. Because of the relations between knowledge and truth embodied in the ax­ iom schema {E), these probability values can be expected to bear some relation, however, to probability values over support and epistemic sets. This relationship is discussed below.

4 Furthermore, use of the negative introspective axiom (E5) shows that that k (p) is the largest union of epistemic sets that is contained in t(p) . This axiom, however, is not required to prove any of the other results discussed in this work.

Truth sets, on one hand, and epistemic and support sets, on the other, generate (by union, intersection, and complementation) sigma algebras of the epistemic universe, called the truth algebra and the epistemic algebra, respec­ tively. Sigma algebras 5 are the proper domain of definition for probability functions. This fact has often been ignored in the past when, usually for the sake of simplicity, proba­ bilities have been assumed to be defined on' every subset of some space. Consideration of the proper domain of defini­ tion for probabilities is, however, a most important issue in probability theory (e.g., when relating joint and marginal distributions).

B. Probabilities, Supports and Masses

A probability function defined over the sigma algebra of support and epistemic sets is called an epistemic pro­ bability. Epistemic probabilities represent the effect of un­ certain evidence on a r·ationl agent's state of knowledge. This effect can always be represented without ambiguity as the result of either previous experience or rational con­ siderations. Under conditions of perfect probabilistic in­ formation (in conventional approaches this is assumed to be always available) the corresponding probability is de­ fined for each atomic proposition. At the opposite end, the vacuous epistemic probability function assigns a probabi­ lity of 1 to the epistemic set e(U) and a probability of 0 to every other subset (i.e., the evidence does not convey any information).

Two functions, both defined in the frame of discern­ ment, can be associated in a natural manner with an epis­ temic probability.

The first of these, called a mass function and denoted by m, is defined by the expression

i.e., as the probability of the epistemic set associated with the objective proposition p.

The second function is called the support function and is denoted by S. It is defined by the expression

Support functions and mass functions are related by the equation

which is valid for every objective proposition p in the frame of discernment. From this basic equation, by using re­ sults from combinatorial theory (Hall 1986), it is possible to show that S and m are belief and mass functions, re­ spectively, in the sense of Shafer (Shafer 1976).

5 Sigma algebras are families of subsets that are closed under the set­ theoretic operations of complementation, countable union, and count­ able intersection.

In particular, it may be seen that m is expressed in terms of values of the support function S by the equation

where IP- ql is the number of different (i.e., not logically equivalent) propositions r such that q=;..r=;..p, and where the sum is over all propositions q that imply p.

Furthermore, the following inequality, utilized by Sha­ fer as an axiom for belief functions, can be derived as a necessary and sufficient condition characterizing support functions:

where III is the cardinality of the index subset I.

It is important to emphasize that the epistemic proba­ bility P associated with mass and support functions is a conventional probability defined on the epistemic algebra of the epistemic universe.

C. Lower and Upper Probabilities

Since both truth sets and epistemic sets are subsets of the epistemic universe, it is reasonable to ask what kind of relations exists between the probability values of members of either class. Answers to this question are obtained by considering the problems associated with the extension of an epistemic probability to a probability function defined over the truth algebra.

The problem of probability extension has received a great deal of attention in probability theory (see, for example, Neveu, 1964). The standard procedure for its solu­ tion is to define lower and upper probabilities for sets not included in the domain of definition (i.e., sigma algebra) of the probability function being extended.

The lower probability of a set X is the probability of the largest subset 6 of the sigma algebra (i.e., where the probability is actually defined) contained in X. Similarly, the upper probability of X is the probability of the smallest measurable subset that contains X .

If P, and P' denote the lower and upper probability functions, respectively, then well-known results of probabi­ lity theory state that probability extensions P always exist and that the value P(X) satisfies the inequality constraints

In addition, the bounds provided by P, and P' may always be attained by some extension and are therefore the best possible.

If these basic theoretical results are applied to the epis­ temic universe, it can be seen that the value P(t(p)) of any epistemic probability extension P on the truth set t(p) must satisfy the inequality

where Pl is the plausibility function of Shafer, defined by

These basic results confirms the validity of the well­ known interval bounds of the Dempster-Shafer calculus.

6 More correctly, this value is equal to the probability of any maxi­ mal measurable subsets contained in the set X under consideration.

Furthermore, lower and upper probabilities provide a gen­ eral methodology to assess the impact of evidence upon understanding of the real-world state. The basic approach, according to these results, consists of representing knowl­ edge as probabilities in an appropriate epistemic algebra, followed by estimation of the values of the lower and upper probabilities of truth sets.

IV Combination of Knowledge

This section briefly describes the results of investiga­ tions concerning the combination of the uncertain knowl­ edge of several rational agents. For the sake of simplicity the results presented here are confined to problems involv­ ing the combination of the knowledge of two agents (Ex­ tensions to an arbitrary number of agents being straight­ forward).

Each of these two agents is assumed to have obtained information about the state of the world through observa­ tion devices that may possibly be dependent or correlated to some degree.

Construction of the epistemic universe that includes both the possible states of knowledge of the two agents, as well as the results of their integration requires the intro­ duction of three unary operators: K1 and K2 , representing the knowledge of each agent, and the unsubscripted oper­ ator K, describing results of knowledge combination. It is assumed that neither agent has information about the extent or nature of the information available to the other (i.e., propositions such as K1K2p are always false), and that each agent's domain of knowledge (i.e., the sentence spaces S 1 and S 2 and their related frames of discernment) may be different.

Since the operator K describes the results of integrating the knowledge of two agents, it is necessary to introduce an axiom that assures that the combined knowledge is solely a function of the states of knowledge being fused:

( CKl) The proposition Kp is true if and onlfl if there exist propositions p1 and pz such that K 1p1 and Kzpz are true and Pt 1\ P2::}p.

The epistemic universe constructed with this augmented framework is called a logical product universe. In this uni­ verse it is possible, as before, to define epistemic, support, and truth sets. However, since three epistemic operators are involved, these sets must be distinguished by subscripts that identify the respective knowledge sources.

If e(p),e1(p),e2(p), denote the epistemic sets for the proposition p that are associated with the epistemic oper­ ators K, K1, and K2, respectively, then the basic set equa­ tion that relates these sets is

where the union is over propositions p1 and p2 (in the re­ spective domains of knowledge of K1 and K2) such that the conjunction p1 1\ P2 is logically equivalent to p.

If P is an epistemic probability in the logical universe, 7 the above set equation may be combined with basic proba­ bility results relating marginal and joint probability. dis­ tributions to derive the following general expression for knowledge combination, called the additive combination formula:

where 1t is a constant that makes L: m(p) = 1.

Under assumptions of independence of the (marginal) epistemic algebras for K1 and Kz, the above formula be­ comes a generalization of the Dempster's rule of combina­ tion

Simple cases of combination of dependent evidence, such as those governed by compatibility relations, may also be derived directly from the additive combination formula, as we have discussed elsewhere (Ruspini 1986a).

In more general cases, the corresponding expressions must combine the knowledge of the two agents (expressed by the additive combination formula) with knowledge about the dependence relations between the two evidential bod­ ies. The latter information is typically modeled as proba­ bilities defined on a subalgebra of the epistemic algebra.

V Conclusion

This paper has presented results that closely relate pro­ bability functions in epistemic universes to the concepts and constructs of the Dempster-Shafer calculus of evidence. The epistemic structures presented above also furnish im­ portant insight that is very useful to enhance the calculus of evidence by the development of expressions that allow for different types of dependent evidence to be combined. These expressions are the current object of our investiga­ tions, which focus particularly on the problems of combin­ ing multiple evidential bodies that share common informa­ tion.

In addition, we are also concerned with problems re­ lated to the use of conditional evidence (i.e., evidence that is valid only when some proposition is true). This research expands upon and enhanc;s our previous results in this area (Ruspini 1986b).

Our long term objectives include the treatment of prob­ lems involving combination of the knowledge of multiple agents that are aware, to different extents, of the informa­ tion available to one another. The corresponding issues are of central importance in the design of distributed artificial intelligence systems with planning and counterplanning ca­ pabilities.

7 More preciaely, thia iJ the case if P iJ defined in the richer product epi1tcmic algebra generated by the intersections el(pl) n e~(p,).

ACKNOWLEDGMENTS

The author benefitted from advice and suggestions re­ ceived from colleagues in the Artificial Intelligence Center. Bob Moore, Stan Rosenschein, and David Israel suggested investigation of the Carnapian viewpoint as a prospective avenue to gain a better understanding of the relationships among approaches to approximate reasoning.

John Lowrance, Tom Garvey, Tom Strat, Len Wesley, and Stephen Lesh comprised an abundant source of insight and encouragement.

I have also profited from conversations with Andy Han­ son, Haim Gaifman, Pascal Fua, Leslie Kaelbling, Martin Fischler, Ray Perrault, Kurt Konolige, Piero Bonissone, Lotfi Zadeh, Terry Cronin, Ken Laws, Lorna Shinkle, Mike Georgeff, Martha Pollack, Ivan Leclerc, Todd Davies, and Oscar Firschein. To all of them, many thanks.