Combining Bodies of Dependent Information

1. Background

Many systems using artificial intelligence concepts must com­ bine information from disparate sources of knowledge to make a decision. Often the information that is given is incomplete: evi­ dence is accumulated suggesting one alternative or another, but in a quantitatively inconclusive way. The use of purely Bayesian techniques sometimes encounters difficulties, due to the lack of sufficient information. There are thus many different ways that have been proposed for combining evidence. One method, called here the Dempster/Shafer theory of evidence [1), has received considerable interest and some use in experts systems.

Central to the Dempster/Shafer theory, and several other formulations of combination of evidence, is a way of handling uncertainty in propositions. Rather than assigning probabilities to possible labels (from a "frame of !Jiscernment"), these theories attempt to assign degrees of confidence to the various proposi­ tions. In Shafer's explanation of the Dempster/Shafer theory of evidence, this is done through the use of "belief functions" to assign weights to subsets of labels in their theory. In general, there is a set of possible labels, and a set of numbers representing a current state of belief. When additional information is obtained, the numbers are changed to a new state. Each state is associated with the body of evidence obtained to that point, and the updating method represents the combination of the current body of evidence with the incremental evidence.

For example, for medical diagnosis applications, a patient can have one of a set of possible diseases. Evidence is obtained in the form of symptoms and test results. Given a current set of symptoms and results, a doctor might decide to run an additional test, and update the assessment of the patient's condition based on the results, in conjunction with the information already present.

In the theory of "belief functions," a state is represented by a probability distribution over the power set of the set of possible labels. Thus a number is assigned to every subset of labels. New evidence is represented, in the Dempater/Shafer theory, by a new state, also aasigning a number to every subset. The Dempster Ot.her possibilities include "Bayesian" approaches, for which a state ts generally represented as a probability distribution over the set of possible labels. Each value is regarded as a "subjec­ ~ve" or "inferential" probability, and the use of Bayes' formula m the presence of various independence or simplifying assump­ tions is defended by a body of research and results, especially those developed by Good, Savage, De Finitti, and Ramsey et al. A survey treatment is given in [3) .

In a recent work by ·Hummel and Landy [4,5), it is shown that th~ ~empster/Shafer formulation is equivalent to the tracking of statistics of sets of experts expressing Boolean opinions over the set of labels. The sets of experts update by combining, using Bayesian updating, in pairs over the product space of experts. Further, an alternate formulation is suggested. In this formula­ tion, experts have probabilistic opinions, rather than Boolean opinions, and the state of the system is represented by the mean and covariance (of logarithmic values) of those opinions.

A drawback of both developments is that conditional independence assumptions regarding the sources of information must be imposed. These assumptions are often unrealistic. Roughly speaking, the assumptions state that the probability of a particular piece of information in the context of a single label, given some existing information, is the same as the probability without the existing information. Independence is defined in terms of probabilities taken over the set of all labeling situations. Consider, for example, the case of a medical diagnosis example. Assume that .r 1 represents the set of symptoms and information obtained to date, and .r2 is the new information. What is required is that the probability of the existence of the symptoms .r 1 amongst the set of all patients having a given disease A must be the same as the probability of the existence of the same set of symptoms "t among the set of patients having the symptoms s 2 and the disease A. Further, this equivalence must hold for all diseases A. In essence, this says that information about the symp­ toms s2 yield no information as to the probability of the . symptoms "t. in the presence of any given disease. Since symp­ toms generally have a common basis, this assumption rarely holds.

In fact, the independence assumption is not very realistic for most applications. It is required to justify the updating formulas, and is so predominant in most formulations for the combination of evidence that the limitations are generally overlooked.

. In this paper, we introduce a model for measuring a "degree of mdependence" between sets of information. The degree of independence is measured by a single variable a, Osa<oo, which ~n in tum depend upon the information values (the symptoms), t.e. , a = a(.r~o.rz). We then extend the Hummel/Landy formula­ tion for the combination of information to the case where the information is a-independent. The case a = 1 will correspond to the same independence assumption as before. The case a = 0 corresponds to completely dependent information, in the sense that .r1 implies the information .r2.

Moreover, we develop formulas so that the statistics are taken over the union of the sets of experts, rather than over the product space. We find the use of the product sets of experts "less natural" than simply combining all experts into one collec­ tion. The difficulty, of course, is that when combining the experts into one collection, each expert must be required to update his opinion baaed on some other opinion, and it is not a priori speci­ fied which other opin~on should be used. We suggest a solution.

l. Formuladon

Let E be a set of experts. Each expert e E E is privy to a body of information (symptoms) about the current situation. We denote by .r the information shared by the associated experts. The goal is to label the current situation (i.e., the current patient) witll a label~ from the set of possible labels A. It is assumed that A is mutually exclusive and exhaustive. Each expert e E E evaluates the information .r and assigns a probability distribution to the set of possible labels A, represented by the set of values p,(e.~). The average opinion, computed by taking a mean over all e E E, is denoted by J.L 1(~). Likewise, the covariance values are given by the formula

Logarithmic opinions are denoted by y1 (e.~). and are given by the formula

where Prob(~) is a prior probability of label ~ over all situations (e.g., the probability of the given disease among all patients). The value c 1 is an indeterminate constant, meaning that the y, values are defined only to within an additive constant independent of ~ and of e. Means and covariances of the y's are also defined, yielding means and covariances of the logarithms, and are denoted by J.l.(l) and c<l) respectively. The use of the logarithmic opinions simplifies the formulas, and is suggested in [6).

Now, suppose that we have two collections of experts E 1 and E 2 and thus two bodies of information .r 1 and .r2. We wish to combine the information J.1. 1 1' J.1.12, C,l' and C,2 to obtain a new mean J.L1119, 2 and a new covariance Cq1912 . Similarly, we should combine the means and covariances of logarithms.

In Hummel and Landy [4], the formula is given for the log's, with complete independence. The formulas are:

These formulas are derived by assuming that updating takes place using the set of all committees of two consisting of one expert from E1 and one expert from E2 (i.e. , the product space), and that within each committee, Bayesian updating is used with a con­ ditional independence assumption.

3. Unions of experts and at -Independence

Conditional independence, used in the formulas above, assert that Prob(.r2 1.r~o~) = Prob(.r2 1~) for all ~. where the pro­ babilities are taken over the set of all labeling situations (e.g., patients), and not over the experts.

We now define the information .r1 and .r2 to be a(.r~o.r2 )­ independent if:

for all ~ - It is important to realize that a-independence is not symmetric, that a(.r1,.r2) ~ a(.r2,.r1) in general. Note that for a= 1, the assumption reverts to conditional independence. For a=O, we have that the information .r1 implies (with probability one) the information .r2. The case a> 1 corresponds to negative evidence. The existence of such an a constitutes an assumption, and is not a completely general measure of independence or dependence. Specifically, we are assuming that a(.r1,.r2) is independent of ~. This is a strong assumption, but is not as strong as the assumption of independence.

One possibility for obtaining the a(.r1,.r2)'s would be to poll experts for their estimates. Alternatively, a might be obtained from the formula:

Of course, these kind of joint statistics are often hard to obtain.

In the presence of a(.r~o.r2)-independence, it is not hard to show that log-probabilities now update according to the formula

Ystes2((t!t,t!2).~) = Yq(t!~o~) + a(.r~o.r2)·y12(t!2,~). The new updating formulas become .... ~~1!12(~) = J.l.~~(~) + a(.r~o.r2)·J.I.~~(~). C~~es2(~1o~2) = C~~(~t.~2) + a 2 (.r~o.r2) ·C~~(~to~2)·

Obviously, the formulas have changed very little: the updating term giving the new inform!ltion is simply weighted by the degree of independence of the new information. While this idea is fun­ damentally simple, we have justified the use of this weighted updating through a precise definition of a-independence.

We now introduce a second new concept to the formulation, that of union-based combination. In the formulas from the previ­ ous section, the information in .r 1$.r2 is based on the product space of experts E 1 x E 2. We find it more desirable to base for­ mulas on the union space of experts E 1 UE2. The resulting set of informati9n, .r 10 .r2, contains updated opinions for each expert t! E E 1 U E 2. However, we must specify the manner in which each expert performs the updating, since there are no longer obvious pairs of opinions for each resultant expert. The method advo­ cated here is to have the experts in E 1 update In a Bayesian fashion based on the mean opinion from the set E2 · Likewise, the experts in E2 update using the information obtained from the mean opinion of experts in E 1. This changes the component for­ mulas, so that, for t!EE1,

Likewise, for t!EE2, we have the same formula, but with all occurrences of .r1 and .r2 exchanged. In particular, we make use of the value a(.r2,.rt) ·

The combination formulas for the means and covariances over the union of the seta of experts can be calculated, and now depends on the number of experts in the component sets, IE 1 I and IE2I· For the log-probabilities, with a-independence, the for­ mulas are:

where we have suppressed the >.. argument in the first equation, andp = 1£Jit(l£1 l+l£21),and6 = 1-p.

We see that a state now consists of the mean log-opinion ... ~/)(>..) for all labels >..EA, the covariance of the opinions C~/) (>..1>>..2), and a weight of evidence, 1£1. corresponding to the number of experts participating in those opinions. In the case of complete independence, a(sl>s2 ) = a(s2 ,s1) = 1, the above for­ mulas become simple addition of the means and covariances, as in the original Rummel/Landy formulation. However, with the covariance formula, there are additional mixed terms which meas­ ure the difference in the mean opinions of the experts in £ 1 and the experts in £2.

Many other formulations are possible. For example, we can compute means and covariances of the probabilities instead of the log-probabilities. We omit the formulas here, for lack of space. We could also use only incremental evidence, so that experts in £ 1 update using the means of the opinions of £2, while the experts in £2 use their actual opinions. This leads to slightly different for­ mulas. Finally, as we have seen, the formulations can be posed for either the ·product spaces of experts, or the union set of experts: many variations are possible.

4. Discussion

The entire approach of tracking statistics of sets of experts has a number of features to commend it. For example, a belief function as used in the Dempster/Shafer theory of evidence requires the specification of 2N values, where there are N labels. If only first and second order statistics are tracked, as suggested here, then the number of values needed to specify a state is only N + (N 2 +N)/2. For large N, this can mean a substantial savings in computational effort needed to update a state.

Further, we at least in principle have replaced the notion of subjective probabilities with objective statistics. These statistics, given sufficient resources, could be measured by, for example, "polling" methods. Our formulas are thus firmly based on objec­ tive probability theory, and thus foundationally secure. Of course, the assumptions are still debatable in the context of any particular application, and the value of a(s 1 ,s 2 ) in the a­ independence of two sets of evidence is most likely to be a subjec­ tive quantity. We expect that, in practice, information will be deemed to be, for example, 0.4-independent, based on subjective criteria. In essence, the subjective component of combination of information has been pushed to a meta-level, where degrees of independence of information sources are estimated, instead of estimating degrees of confidence of labels in the presence of specific information.

The use of a collection of opinions permits a distinction between uncertainty and ignorance. A state of belief consists not of a single opinion, but of a collection of opinions. The state can be represented by a mean opinion, and a measure of the spread (or distribution) of those opinions. The spread measures a degree of uncertainty, since if all opinions are identical, there is a consid­ erable degree of certainty in the single expressed opinion. Updat­ ing is done by combining the mean opinions and combining the uncertainties. Basically, the new mean opinion becomes a compromise between the two mean opinions of the composing evidence. Uncertainties are likewise mixed, and generally accu­ mulate. Further, in the presence of dependencies in the informa­ tion sources, uncertainty increases if the opinions from the two sources of information are divergent.

Finally, we note that the theory makes explicit the depen­ dence on the order in which information is combined. That is, if information. s 1, s2 , · · · , s. are to be combined, the various a values and the outcome of the entire system will depend upon the order in which the information is mixed. The system is neither commutative nor associative, in the presence of the a­ independence formulation. This may be realistic, in the sense that decisions are often based on incrementally gaining evidence, and that the interpretation and outcome depends on the order in which information is obtained. A separate expert system could be used to decide on the order in which to combine information .

Acknowledgements

This research was supported by Office of Naval Research Grant N00014-85-K-0077, Work Unit NR 4007006. We thank Michael Landy for useful discussions . Manevitz thanks the Courant Institute for their kind hospitality during his visit to NYU.