On the Revision of Probabilistic Beliefs using Uncertain Evidence

1 Introduction

We consider in this paper the problem of revising beliefs given uncertain evidence, where beliefs are represented using a probability distribution. There are two main methods for revising probabilistic beliefs in this case. The first method is known as Jeffrey's rule and is based on the principle of proba­ bility kinematics, which can be viewed as a principle for min­ imizing belief change [Jeffrey, 1965]. The second method is called virtual evidence and is proposed by Pearl in the context of belief networks-even though it can be easily generalized to arbitrary probability distributions-and is based on reduc­ ing uncertain evidence into certain evidence on some virtual event [Pearl, 1988]. We analyze both of these methods in this paper with respect to the following four questions:

1. How should one specify uncertain evidence?
2. How should one revise a probability distribution?
3. Should, and do, iterated belief revisions commute?
4. What guarantees can be offered on the amount of belief change induced by a particular revision?

Our main findings can be summarized as follows. First, we show that Jeffrey's rule and Pearl's method both revise be­ liefs using the principle of probability kinematics. Jeffrey's rule explicitly commits to this principle, while Pearl's method is based on a different principle. Yet, we show that Pearl's method implies the principle of probability kinematics, lead­ ing to the same revision method as that of Jeffrey's. The dif­ ference between Jeffrey's rule and Pearl's method is in the way uncertain evidence is specified. Jeffrey requires uncer­ tain evidence to be specified in terms of the effect it has on beliefs once accepted, which is a function of both evidence strength and beliefs held before the evidence is obtained. Pearl, on the other hand, requires uncertain evidence to be specified in terms of its strength only. Despite this differ­ ence, we show that one can easily translate between the two methods of specifying evidence and provide the method for carrying out this translation.

The multiplicity of methods for specifying evidence also raises an important question: how should informal statements about evidence be captured formally using available meth­ ods? For example, what should the following statement trans­ late to: "Seeing these clouds, I believe there is an 80% chance that it will rain?" We will discuss this problem of interpreting informal evidential statements later, where we emphasize its subtlety.

As to the question of iterated belief revision: It is well known that Jeffrey's rule does not commute; hence, the or­ der in which evidence is incorporated matters [Diaconis & Zabell, 1982]. This has long been perceived as a problem, until clarified recently by the work of Wagner who observed that Jeffrey's method of specifying evidence is dependent on what is believed before the evidence is obtained and, hence, should not be commutative to start with [Wagner, 2002]. Wagner proposed a method for specifying evidence, based on the notion of Bayes factor, and argued that this method specifies only the strength of evidence, and is independent of the beliefs held when attaining evidence. Wagner argued that when evidence is specified in that particular way, iterated re­ visions should commute. He even showed that combining this method for specifying evidence with the principle of proba­ bility kinematics leads to a revision rule that commutes. We actually show that Pearl's method of virtual evidence is speci­ fying evidence according to Bayes factor, exactly as proposed by Wagner and, hence, corresponds exactly to the proposal he calls for. Therefore, the results we discuss in this paper unify the two main methods for probabilistic belief revision pro­ posed by Jeffrey and Pearl, and show that differences between them amount to a difference in the protocol for specifying un­ certain evidence.

Our last set of results relate to the problem of providing guarantees on the amount of belief change induced by a re­ vision. We have recently proposed a distance measure for bounding belief changes, and showed how one can use it to provide such guarantees [Chan & Darwiche, 2002] . We show in this paper how this distance measure can be com­ puted when one distribution is obtained from another using the principle of probability kinematics. We then show how the guarantees provided by this measure can be realized when applying either Jeffrey's rule or Pearl 's method, since they both are performing revision based on the principle of proba­ bility kinematics.

2 Probability Kinematics and Jeffrey's Rule

Suppose that we have two probability distributions Pr and Pr' which disagree on the probabilities they assign to a set of mutually exclusive and exhaustive events 11 , . .. , In, yet:

for i = 1, ... , n, and for every event a in the probability space. We say here that Pr' is obtained from Pr by probabil­ ity kinematics on 11 , ... , In. This concept was proposed by Jeffrey [I965] to capture the notion that even though Pr and Pr' disagree on the probabilities of events li, they agree on their relevance to every event a.

Consider now the problem of revising a probability distri­ bution Pr given uncertain evidence relating to a set of mutu­ ally exclusive and exhaustive events 11 , ... , In· One method of specifYing uncertain evidence is through the effect that it would have on beliefs once accepted. That is, we can say that the evidence is such that the probability of li becomes qi once the evidence is accepted. If we adopt this method of evidence specification, we conclude that there is only one distribution Pr' such that:

• Pr'(!i) = qi fori= 1, ... , n.
• Pr' is obtained from Pr by probability kinematics on 11, ···,In·

Moreover, this specific distribution is given by:

where w is an atomic event, also known as a world, and f= is the logical entailment relationship. This is exactly the distri­ bution that Jeffrey suggests and, hence, this method of re­ vision is known as Jeffrey's rule. We stress here that we are drawing a distinction between the principle of probabil­ ity kinematics and Jeffrey's rule, which are often considered synonymous. Specifically, Jeffrey's rule arises from a com­ bination of two proposals: (I) the principle of probability kinematics, and (2) the specification of uncertain evidence us­ ing a posterior distribution. It is possible for one to combine the principle of probability kinematics with other methods for specifYing evidence as we discuss later.

It is not hard to show that the above distribution Pr' is indeed obtained from Pr by probability kinematics on 11, . .. , In , as it satisfies Equation I:

Therefore, for any event a, its probability under the new dis­ tribution Pr' is:

which is the closed form for Jeffrey's rule. We now show an example of using Jeffrey's rule.

Example 1 (Due to Jeffrey) Assume that we are given a piece of cloth, where its color can be one of green (c 9 ), blue (cb), or violet (cv). We want to know whether, in the next day, the cloth will be sold (s), or not sold (s). Our original state of belief is given by the distribution Pr:

Therefore, our original state of belief on the color of the cloth (c9, cb, cv) is given by the distribution (.3, .3, .4). Assume that we now inspect the cloth by candlelight, and we want to revise our state of belief on the color of the cloth to the new distribution (.7, .25, .05) using Jeffrey 's rule. If we apply Jeffrey's rule (Equation 2), we get the new distribution Pr':

3 Virtual Evidence and Pearl's Method

The problem of revising a probability distribution under un­ certain evidence can be approached from a different perspec­ tive than that of probability kinematics. Specifically, when we have uncertain evidence about some mutually exclusive and exhaustive events 11 , ... , /n, we can interpret that evidence as hard evidence on some virtual event ry, where the relevance of 11, ... , In to TJ is uncertain. It is assumed that the virtual event TJ depends only on the events 11 , ... , In and, therefore, is independent of any other event a given li :

According to this approach, the uncertainty regarding evi­ dence on 11, ... , In is recast as uncertainty in the relevance of 11, . .. , In to the virtual event ry. Specifically, the uncer­ tainty is recast as the likelihood of li given virtual evidence ry: Pr(ry IIi), fori= 1, ... , n.

We next show that the new distribution obtained after ac­ cepting the uncertain evidence on /I, ... , /n, Pr( · I TJ), is:

where AI, . . . , An are ratios chosen such that:

Hence,-the specific likelihoods Pr( T} I ri) are not important here, but their ratios are. This is why this method usually specifies uncertain evidence using a set of likelihood ratios AI, . .. , An [Pearl, 1988]. The derivation of Equation 4 is based on the assumptions underlying the method of virtual evidence given by Equation 3:

The last step is based on Pr(TJ I ri) = kAi, where k is a constant. For any event a, the new probability after accom­ modating the virtual evidence is:

which is the closed form for Pearl's method.

The above revision method is a generalization of the method of virtual evidence proposed by Pearl [1988] in the context of belief networks. A belief network is a graphi­ cal probabilistic model, composed of two parts: a directed acyclic graph where nodes represent variables, and a set of conditional probability tables (CPTs), one for each variable [Pearl, 1988; Jensen, 2001]. The CPT for variable X with parents U defines a set of conditional probabilities of the form Pr(x I u), where x is a value of variable X, and u is an instantiation of parents U. Suppose now that we have some virtual evidence bearing on variable Y, which has val­ ues YI, ... , Yn. This virtual evidence is represented in the be­ lief network by adding a dummy node Z and a directed edge Y--+ Z, where one value of Z, say z, corresponds to the vir­ tual event TJ· This ensures the assumption of Equation 3, that virtual event z is independent of every other event a given ev­ ery Yi, i.e., Pr(z I Yi, a) = Pr(z I Yi), which follows from the independence semantics of belief networks [Pearl, 1988].

The uncertainty of evidence is quantified by the likelihood ra­ tios: Pr(z I yi) : ... : Pr(z I Yn) = AI : ... : An, which are specified in the CPT of variable Z . Finally, we incorporate the presence of the virtual event z by adding the observation Z = z to the rest of evidence in the belief network. We now show a simple example.

Example 2 (Due to Pearl) We are given a belief network with two variables: A represents whether the alarm of Mr. Holmes' house goes off, and B represents whether there is a burglary. To represent the influence between the two vari­ ables, there is a directed edge B --+ A. The CPTs of A and Bare given by: Pr(a I b)= .95, meaning the alarm goes off if there is a burglary with probability .95; Pr(a I b) = .01, meaning the alarm goes off if there is no burglary with prob­ ability .01; and Pr(b) = w- 4 , meaning on any given day, there is a burglary on any given house with probability w- 4 .

One day, Mr. Holmes' receives a call from his neighbor, Mrs. Gibbons, saying she may have heard the alarm of his house going off. Since Mrs. Gibbons suffers from a hearing problem, Mr. Holmes concludes that there is an 80% chance that Mrs. Gibbons did hear the alarm going off. According to the method of virtual evidence, this uncertain evidence can be specified by the virtual event T} and the likelihood ratio: Pr(TJ I a) : Pr(TJ I a) = 4 : 1. To incorporate the virtual evidence into the belief network, we add the variable Z, and the directed edge A --+ Z, and specify the CPT of Z such that Pr(z I a) : Pr(z I a) = 4 : 1. For example, we can assign Pr(z I a) = .4 and Pr(z I a) = .1. After incorporating the virtual evidence by adding the observation Z = z to the evidence, we can easily compute the answers to queries in the belief network. For example, the probability that there is a burglary at Mr. Holmes' house is now Pr(b I z) ~ 3.85 x w- 4 .

4 Comparing the Revision Methods

From the illustrations of the two belief revision methods, Jef­ frey's rule and Pearl's method of virtual evidence, we can see that a belief revision method can be broken into two parts: a formal method of specifying uncertain evidence, and a prin­ ciple of belief revision that commits to a unique distribution among many which satisfy the uncertain evidence.

4.1 Pearl's method and Probability Kinematics

We now show that Pearl's method, like Jeffrey's rule, also obeys the principle of probability kinematics; what they differ in is how uncertain evidence is specified.

Suppose that a probability distribution Pr was revised us­ ing the method of virtual evidence, with likelihood ratios AI, ... , An bearing on events /I, ... , /n, obtaining the new distribution Pr(· I TJ). We can easily see that the revision sat­ isfies the principle of probability kinematics, i.e. Equation 1:

Therefore, both Jeffrey's rule and Pearl's method obey the principle of probability kinematics for belief revision.

4.2 From Pearl's Method to Jeffrey's Rule

With the previous result, we now show how we can easily translate between the two methods of specifying uncertain evidence. For example, to translate from Pearl's method to Jeffrey's rule, we note that the new probabilities of events 11 , . . . , In after applying virtual evidence, with likelihood ra­ tios A1 , ... , An. are given by:

Suppose instead that we want to revise the distribution Pr using Jeffrey's rule, assuming that after accepting uncertain evidence, the probability of /i becomes:

Substituting the above probability qi in Jeffrey's rule (Equa­ tion 2), we get:

which is exactly the distribution obtained by the method of virtual evidence (Equation 4). We now illustrate this transla­ tion by revisiting Example 2.

Example 3 In Example 2, we applied the method of virtual evidence on Pr, by specifying the virtual evidence: Pr( rJ I a) : Pr(rJ I a) = Aa : Aa; = 4 : 1. The original prob­ abilities of a and a are given by: Pr(a) = .010094, and Pr(a) = .989906. After applying the virtual evidence, the new probabilities of a and a are given by:

Alternatively, we can apply Jeffrey's rule to obtain the new distribution Pr' such that Pr'(a) = Pr(a I rJ) ~ .039189 and Pr' (a) = Pr(a I rJ) ~ .960811, and Pr' will be the same to the distribution Pr(- I rJ) obtained by virtual evi­ dence.

4.3 From Jeffrey's Rule to Pearl's Method

We can also easily translate from Jeffrey's rule to Pearl's method. Specifically, the new probabilities of events /I , . . . , In after applying Jeffrey's rule are given by:

Suppose instead that we want to revise the distribution Pr using Pearl's method. We can do this by applying the method of virtual evidence, with likelihood ratios A1 , . . . , An, such that:

Therefore, A; = kq;j Pr(!;), where k is a constant. Substi­ tuting Ai in Pearl's method (Equation 4 ), we get: .

because 2: 1 q1 = 1. This is exactly the distribution obtained by Jeffrey's rule (Equation 2). We now illustrate this transla­ tion by revisiting Example 1.

Example 4 In Example I, we applied Jeffrey's rule on the original distribution Pr to obtain new distribution Pr'. We can also do this by applying the method of virtual evidence. We can interpret the inspection of the cloth by candlelight as virtual evidence rJ, where Pr(rJ I c 9 ) : Pr(rJ I cb) : Pr(rJ I Cv) = Ag : Ab : Av = 7 : 2.5 : .375. 1 The probability distribution of the color of the cloth after applying virtual evidence is therefore given by:

We can easily verify that this probability distribution Pr( · I rJ) obtained by virtual evidence is the same as the distribution Pr' obtained by Jeffrey's rule.

5 Interpreting Evidential Statements

The evidence specification protocols adopted by Jeffrey's rule and Pearl's method have been discussed by Pearl [2001], in relation to the problem of formally interpreting evidential statements. Consider the following statement as an example:

Looking at this evidence, I am willing to bet 2: 1 that David is not the killer.

This statement can be formally interpreted using either pro­ tocol. For example, if a denotes the event "David is not the killer," this statement can be interpreted in two ways:

1 The .\'s are chosen such that Ai = kPr'(ci)/ Pr(ci), where k is a constant.

1. After accepting the evidence, the probability that David is not the killer becomes twice the probability that David is the killer: Pr'(a) = 2/3 and Pr'(a) = 1/3.
2. The probability that I will see this evidence T} given that David is not the killer is twice the probability that I will see it given that David is the killer: Pr( T} I a) : Pr( T} I a)= 2 : 1.

The first interpretation translates directly into a formal piece of evidence, Jeffrey's style, and can be characterized as an "All things considered" interpretation since it is a statement about the agent's final beliefs, which are a function of both his prior beliefs and the evidence [Pearl, 2001]. On the other hand, the second interpretation translates directly into a for­ mal piece of evidence, Pearl's style, and can be character­ ized as a "Nothing else considered" interpretation since it is a statement about the evidence only [Pearl, 200 1].

The two interpretations can lead to contradictory conclu­ sions about the evidence. For example, if we use the "Nothing else considered" approach to interpret our statement, we will conclude that the evidence is against David being the killer. However, if we use the "All things considered" interpretation, it is not clear whether the evidence is for or against, unless we know the original probability that David is the killer. If, for example, David is one of four suspects who are equally likely to be the killer, we will originally have: Pr(a) = 3/4. Therefore, this evidence has actually increased the probabil­ ity that David is the killer! Because of this, Pearl argues for the "Nothing else considered" interpretation, as it provides a summary of the evidence and the evidence alone, and dis­ cusses how people tend to use betting odds to quantify their beliefs even when they are based on the evidence only [Pearl, 2001].

Example 2 provides another opportunity to illustrate the subtlety involved in interpreting evidential statements. The evidential statement in this case is "Mr. Holmes concludes that there is an 80% chance that Mrs. Gibbons did hear the alarm going off." Interpreting this statement using the "All things considered" approach gives us the conclusion that Pr' (a) : Pr' (a) = 4 : 1, where a denotes the event that the alarm has gone off. This interpretation assumes that the 4 : 1 ratio applies to the posterior beliefs in a and a, after Mr. Holmes has accommodated the evidence provided by Mrs. Gibson. However, in Example 2, this statement was given a "Nothing else considered" interpretation, as by Pearl [1988, Page 44-47], where the 4 : 1 ratio is taken as a quantification of the evidence strength. That is, the statement is interpreted as Pr( T} I a) : Pr( T} I a) = 4 : 1, where TJ stands for the evidence. In fact, the two interpretations will lead to two dif­ ferent probability distributions and, hence, give us different answers to further probabilistic queries. For example, if we use the "All things considered" approach in interpreting this evidential statement, the probability of having a burglary will be Pr' (b) = 7.53 x 10- 3 , which is much larger than the prob­ ~bility we get using the "Nothing else considered" approach m Example 2, which is 3.85 x 10- 4 .

From the discussions above, the formal interpretation of evidential statements appears to be a non-trivial task, which can be sensitive to context and communication protocols. Regardless of how this is accomplished though, we need to stress that the process of mapping an informal evidential statement into a revised probability distribution involves three distinct elements:

1. One must adopt a formal method for specifying evi­ dence.
2. One must interpret the informal evidential statement, by translating it into a formal piece of evidence.
3. One must apply a revision, by mapping the original probability distribution and formal piece of evidence into a new distribution.

Our main point here is that Jeffrey's rule and Pearl's method employs the same belief revision principle, i.e. probability kinematics. Moreover, although they adopt different, formal methods for specifying evidence, one can translate between the two methods of specification. Finally, one may take the view that Jeffrey's rule and Pearl's method constitute com­ mitments to how informal evidential statements should be in­ terpreted, making the first and second elements the same, but we do not take this view here. Instead, we regard the issue of interpretation as a third, orthogonal dimension which is best addressed independently.

6 Commutativity of Iterated Revisions

We now discuss the problem of commutativity of iterated re­ visions, that is, whether the order in which we incorporate uncertain evidence matters. 2

It is well known that iterated revisions by Jeffrey's rule are not commutative [Diaconis & Zabell, 1982]. As a simple ex­ ample, assume that we are given a piece of uncertain evidence which suggests that the probability of event a is . 7, followed by another piece of uncertain evidence which suggests that the probability of a is .8. After incorporating both pieces in that order, we will believe that the probability of a is .8. However, if the reversed order of revision is employed, we will believe that the probability of a is . 7. In general, even if we are given pieces of uncertain evidence on different events iterated revisions by Jeffrey's rule are not commutative. '

This was viewed as a problematic aspect of Jeffrey's rule for a long time, until clarified recently by Wagner [2002]. First, Wagner observed and stressed that the evidence spec­ ification method adopted by Jeffrey is suitable for the "All things considered" interpretation of evidential statements. Moreover, he argued convincingly that when evidential state­ ments carry this interpretation, they must not be commutative to start with. So the lack of commutativity is not a problem of the revision method, but a property of the method used to specify evidence. In fact, Wagner suggested a third method for specifying evidence based on Bayes factors [Good, 1950; 1983; Jeffrey, 1992], which leads to commutativity. Specif­ ically, if Pr and Pr' are two probability distributions, and

2 There is a key distinction between iterated revisions using cer­ tain evidence versus uncertain evidence. In the former case, pieces of evidence may be logically inconsistent, which adds another di­ mension of complexity to the problem [Darwiche & Pearl, 1997], leading to different properties and treatments.

'Yi and /j are two events, the Bayes factor (or odds factor), :FPr',Pr(/i : {j), is defined as the ratio of new-to-old odds:

Given this notion, one can specify uncertain evidence on a set of mutually exclusive and exhaustive events 11 , ... , In by specifying the Bayes factor for every pair of events /i and /j. One interesting property of this method of specification is that Bayes factors do not constrain the probability distribu­ tion Pr, i.e., any evidence specified in this way is compatible with every distribution Pr. 3 Hence, they are suitable for a "Nothing else considered" interpretation of evidential state­ ments.

Interestingly enough, Wagner [2002] showed that when evidence is specified using Bayes factors and revisions are accomplished by probability kinematics, belief revision be­ comes commutative. 4 This was an illustration that Jeffrey's rule is indeed composed of two independent elements: an ev­ idence specification method, and a revision method.

In fact, we now show that the evidence specification method adopted by Pearl's method corresponds to the method of specifying evidence by Bayes factors. This has a number of implications. First, it shows that revisions by the virtual evidence method are commutative. Second, it provides an alternate, more classical, semantics for the virtual evidence method. Finally, it shows again that Jeffrey's rule and Pearl's method both revise distributions using probability kinemat­ ICS.

Specifically, suppose that we revise a probability distribu­ tion Pr using the method of virtual evidence, with likelihood ratios A1 , ... , An bearing on events 11 , ... , {n, and suppose that we get distribution Pr' as a result. We then have:

That is, if we specify evidence by Bayes factor A;/ Aj for ev­ ery pair of events 'Yi and /j, and then revise distribution Pr using probability kinematics, we obtain the same distribution that arises from applying the virtual evidence method.

7 Bounding Belief Change Induced by Probability Kinematics

One important question relating to belief revision is that of measuring the extent to which a revision disturbs existing beliefs. We have recently proposed a distance measure de­ fined between two probability distributions which can be used to bound the amount of belief change induced by a revision [Chan & Darwiche, 2002]. We review this measure next and then use it to provide some guarantees on any revision which is based on probability kinematics. 5

3 This is not true if we use ratios of probabilities instead of ratios of odds. For example, if Pr'(a) = 2Pr(a), we must have Pr(a) ~ .5 because Pr'(a) ~ 1 [Wagner, 2002].

4 Wagner shows not only that the representation of uncertain ev­ idence using Bayes factors is sufficient for commutativity, but in a large number of cases, necessary.

Definition 1 [Chan & Darwiche, 2002} Let Pr and Pr' be two probability distributions over the same set of worlds w. We define a measure D(Pr, Pr') as follows:

where 010 is defined as 1.

This distance measure can also be expressed using the Bayes factor:

This measure satisfies the three properties of distance: posi­ tiveness, symmetry, and the triangle inequality. It is useful to compute this distance measure between two probability dis­ tributions as it allows us to bound the difference in beliefs captured by them.

Theorem 1 [Chan & Darwiche, 2002} Let Pr and Pr' be two probability distributions over the same set of worlds. Let a and {3 be two events. We then have:

where O(a I {3) = Pr(a I {3)1 Pr(Ci I {3) is the odds of event a given {3 with respect to Fr. and 0' (a I {3) = Pr' (a I {3) I Pr' (Ci I {3) is the odds of event a given {3 with respect to Pr'. 6 The bound is tight in the sense that for every pair of distributions Pr and Pr', there are events a and {3 such that:

According to Theorem 1, if we are able to compute the dis­ tance measure between the original and revised distributions, we can get a tight bound on the new belief in any conditional event given our original belief in that event. The following theorem computes this distance measure for belief revision methods based on probability kinematics.

Theorem 2 If Pr' comes from Pr by probability kinematics on 11 , . . . , {n. the distance measure between Pr and Pr' is given by:

5 The results in this section are reformulations of previous results [Chan & Darwiche, 2002], and are inspired by a new understand­ ing of Jeffrey's rule and Pearl's method as two specific instances of revision based on probability kinematics, and the understanding of Pearl's method in terms of Bayes factors .

6 0f course, we must have Pr({J) =f. 0 and Pr' ({3) =f. 0 for the odds to be defined.

Theorem 2 allows us to compute the distance measure for revisions based on Jeffrey's rule and virtual evidence.

Corollary 1 If Pr' comes from Pr by applying Jeffrey's rule to events ')'1 , .. . , l'n· with posterior probabilities q1 , ... , Qn, the distance measure between Pr and Pr' is given by:

Corollary 2 If Pr' comes from Pr by applying the method of virtual evidence, with likelihood ratios A1 , ... , An bearing on ')'1 , . .. , l'n· the distance measure between Pr and Pr' is given by:

The significance of Corollaries 1 and 2 is that we can com­ pute the distance measure easily in both cases. For Jeffrey's rule, we can compute the distance measure by knowing only the prior and posterior probabilities of events ')'1 , ... , l'n. For Pearl's method, we can compute the distance measure by knowing only the likelihood ratios A1, ... , An· For both revi­ sion methods, the distance measure can be computed in con­ stant time from the uncertain evidence, and we can guarantee a bound on the belief change due to the revision principle of probability kinematics, without explicitly knowing the re­ vised probability distribution.

We close this section by showing that the principle of prob­ ability kinematics is optimal in a very precise sense: it com­ mits to a probability distribution that minimizes our distance measure.

Theorem 3 If Pr' comes from Pr by probability kinematics on ')'1 , .. . , /'n. it is optimal in the following sense. Among all possible distributions that agree with Pr' on the probabilities of events ')'1 , ... , l'n· Pr' is the closest to Pr according to the distance measure given by Definition 1.

8 Conclusion

In this paper, we analyzed two main methods for revising probability distributions given uncertain evidence: Jeffrey's rule and Pearl's method of virtual evidence. We showed that the two methods use the same belief revision principle, i.e. probability kinematics, with their difference being only in the manner in which they specify uncertain evidence, and showed how to translate between the two methods for specifying evi­ dence. We also discussed the much debated problem of inter­ preting evidential statements. Moreover, we showed that the method of virtual evidence can be reformulated in terms of Bayes factors, which implies a number of results, including the commutativity of revisions based on this method. Finally, we showed that revisions based on probability kinematics are optimal in a very specific way, and pointed to a distance mea­ sure for bounding belief change triggered by any revision based on probability kinematics. Our bounds included Jef­ frey's rule and Pearl's method as special cases.

Acknowledgments

This work has been partially supported by NSF grant IIS9988543, MURI grant N00014-00-1-0617, and DiMI grant

00-10065. We also wish to thank Carl Wagner, Judea Pearl, and the late Richard Jeffrey, for their valuable comments and discussions.