Updating Probability Intervals with Uncertain Inputs

1 Introduction

Probability intervals are compact, intuitive and convenient means for representing imprecise probabilities. The theory of imprecise probabilities [Levi, 1980; Walley, 1991] is a unifying uncertainty theory particularly suited for encoding and reasoning with imprecise or ill-known information. It is used to reason with multiple expert information [Nau, 2002], perform sensitivity analysis [Bock et al., 2014], make decisions with partial information [Antonucci et al., 2007], etc. Imprecise probabilities are often associated with a robust Bayesian interpretation [Berger et al., 1994] assuming that the probability measure representing the actual beliefs exists and it is unique but it is unknown due to lack of knowledge. Imprecise probabilities are specified in the form of sets of probability measures, credal sets [Levi, 1980; Walley, 1991] or using other representations such as intervalbased probabilities [de Campos et al., 1994], probabilistic logic programs [Lukasiewicz, 2001], belief functions, etc. As for updating probability intervals, it should be noted that there are several conditionings depending on the associated interpretation of probability intervals [Moral and De Campos, 1991]. In this paper, we limit ourselves to the three most common types of conditioning that are the robust Bayesian conditioning [Moral and De Campos, 1991], Dempster conditioning [Shafer, 1976] and the geometric one [Suppes and Zanotti, 1977].

Given an initial belief set, one may learn new information which can be in the form of a hard evidence or in the form of uncertain or soft evidence (e.g. unreliable observation). The focus of the paper is updating 1 a set of probability intervals with new information also expressed by probability intervals. In the classical point-wise probabilistic setting, Jeffrey's rule [Jeffrey, 1965] generalizes the standard probabilistic conditioning to the case where the inputs are uncertain. This conditioning rule has been studied in many uncertainty settings (for instance, see [Dubois and Prade, 1997] for the possibilistic setting and [Smets, 1993; Tang and Zheng, 2006; Ma et al., 2011] for Dempster-Shafer theory).

We place ourselves in the framework of Jeffrey's rule where the new information is pervaded with uncertainty and this latter bears on a partition of the set of possible worlds. We therefore take for granted the principles underlying Jeffrey's rule and we do not focus on the foundations and justifications of such principles. The focus is on extending Jeffrey's rule for updating probability intervals with uncertain inputs. The main contributions of the paper are :

1. Extending Jeffrey's rule of conditioning to update a prior credal set with a new uncertain and imprecise input also in the form of a credal set ;
2. Casting Jeffrey's rule principles (success and probability kinematics) in the probability intervals setting and show that the proposed rules capture such principles ;
3. Proposing Jeffrey's rule counterparts for two alternative conditionings (Dempster and geometric) of probability intervals.

1 In this paper, we use interchangeably the terms update, revision and conditioning even if some authors associate different meanings to these belief change processes. See [Dubois and Prade, 1994] for a survey of belief revision and updating rules.

2 Preliminaries

2.1 Probability Intervals

Let us in the following denote by Ω={ω1,..,ωn} the set of elementary possible states and denote by ωi∈Ω a given state. Sets of states φ, ψ⊆Ω are called events. An interval-based probability distribution (IPD for short) is defined as follows:

Definition 1 (Interval-based probability distribution). Let Ω be the set of possible states. An interval-based probability distribution P is a function that maps every state ωi∈Ω to a closed interval P (ωi)=[li, ui]⊆[0, 1].

In an IPD P, every state ωi∈Ω is associated with a probability interval P(ωi)=[li, ui] where li (resp. ui) denotes the lower (resp. upper) bound of the probability of ωi. In the following, P(ωi) (resp. P(ωi)) denotes the upper (resp. lower) bound of P (ωi).

In order to be reachable and not empty, the bounds should satisfy the following constraints:

We call a model or a member of IPD P any point-wise (or single-valued) probability distribution p s.t. ∀ωi∈Ω, p(ωi)∈P(ωi)=[li,ui]. Accordingly, the semantics associated with an IPD is the set of its models, namely all probability measures that comply with the probability intervals. A credal set K on Ω compactly encoded by an IPD P denotes the closed convex set of point-wise probability distributions p that are models of P . Namely,

A commonly used way to encode a credal set K is the vertex-based representation. This is done by specifying a finite set of standard probability distributions representing the extreme points of K. An extreme point (also called vertex) p of a credal set K is a probability distribution such that it is impossible to find two different probability distributions p1∈K and p2∈K such that p=α*p1+(1-α)*p2 with α∈]0, 1[. Enumerating the set of extreme points ext(P) underlying an IPD P requires solving a linear program [de Campos et al., 1994]. An IPD P can be completely represented by the extreme points of the credal set K underlying P .

Reasoning with interval probabilities can either be done at the semantic level using the credal set induced by probability intervals or directly manipulating intervals and using interval arithmetics. Reasoning using a credal set K underlying an IPD P comes down to exploring all the models of that credal set 2 . For instance, marginalizing a credal set K(X, Y ) over two subsets of variables X and Y is done as follows:

2 Alternative approaches consist for instance in selecting the most informative model (in the sense of information entropy for example) of K to draw inferences as it is done in [Lukasiewicz, 2001].

For credal sets, the most common form of conditioning on an event φ⊆Ω is defined as follows :

This is often referred to as cautious or robust Bayesian conditioning (see [Moral and De Campos, 1991] for other forms of conditioning probability intervals).

For computational reasons, reasoning on K is done on ext(K) which provides an equivalent representation. Indeed, inference on a credal set K is equivalent to inference on its extreme points [Walley, 1991; de Campos et al., 1994]. For instance, marginalizing a credal set K(X, Y ) over two subsets of variables X and Y is done as follows :

where CH stands for the convex hull operator. Conditioning of Equation 3 comes down to :

K(ωi|φ) = CH({p(ωi|φ) : p ∈ ext(K) and p(φ) > 0}). (5) In the following, we briefly recall Jeffrey's rule in the standard probabilistic setting.

2.2 Jeffrey's Rule of Conditioning

Jeffrey's rule [Jeffrey, 1965] extends the classical probabilistic conditioning to the case where the new information is uncertain. It allows to update an initial probability distribution p into a posterior one p′ given the uncertainty bearing on a set of mutually exclusive and exhaustive events λ={λ1,..,λn} (namely, λ is a partition of Ω). In this setting, the new input is in the form (λi, αi), i=1..n where αi denotes the new probability of λi. Jeffrey's rule lies on the two following principles:

Success principle (P1).

After the update operation, the posterior probability of each event λi must be equal to αi as required in the new inputs. The uncertain inputs are seen as constraints or an effect once the new information is fully accepted.

Probability kinematics principle (P2).

This principle aims to ensure a kind of minimal change by ensuring that the posterior distribution p′ should not change the conditional probability degrees of any event φ given the uncertain events λi. Jeffrey's rule assumes that in spite of the disagreement about the events λi in the prior distribution p and the posterior one p′ , the conditional probability of any event φ⊆Ω given any uncertain event λi should remain the same in the original and the revised distributions.

Given a probability distribution p encoding the initial beliefs and new inputs in the form (λi, αi) for i=1..n, the updated probability degree of any event φ⊆Ω is obtained as follows:

The posterior distribution p′ obtained using Jeffrey's rule always exists and it is unique [Chan and Darwiche, 2005]. Note that in Jeffrey's rule, the events λi should be somewhat possible in the prior distribution (namely, ∀λi∈λ, p(λi)>0).

3 Motivating Example

To illustrate and motivate the interest in expressing and updating uncertain information in the form of probability intervals, let us take the example of the polls generally carried out in the elections and suppose that they are about presidential elections that are going to take place in a given country. Suppose for simplicity that there are only four candidates (denoted C1, C2, C3 and C4) and that in this country the political polarization is Left wing and Right wing. Assume now that a first poll of voter preferences for the four candidates on a small sample yielded the following results in Table 1 (a) (the estimates are in the form of probability intervals to account for the margin of error).

Assume now that a second poll on a much larger sample and where the question is no longer Which candidate are you going to vote for? but Do you prefer a left wing candidate or a right wing one? To simplify, we assume that candidates C1 and C2 are classified in the left wing and the other two in the right wing. Also, the estimates (see Table 1 (b)) are given in the form of probability intervals to take into account the margin of error.

It fully makes sense in this case to update the initial distribution (results of the first poll) with new information (results of the second poll) as this latter is more confident since it is carried out on a much larger sample. It is important to note that the initial information to update is an interval-based probability distribution P and the new input uncertain is also an interval-based probability distribution Pnew over a partition of the set of candidates. This update task is fully in the spirit of Jeffrey's rule (the new inputs are uncertain information bearing on a partition of Ω and the aim is to give priority to the new inputs). In this example, the task is not a simple belief merging but aims at giving priority to new inputs as in belief revision tasks. This is exactly in line with Jeffrey's rule in the standard probabilistic setting. But this latter handles only point-wise probability distributions and not interval-based ones. There is to the best of our knowledge no counterparts to Jeffrey's rule in the interval-based setting.

4 Updating Credal Sets with Uncertain Inputs

Before addressing updating probability intervals with uncertain inputs, let us first focus on updating credal sets with uncertain inputs using Jeffrey's rule. The idea is to use Jeffrey's rule to update every distribution p from the prior credal set K with every distribution pnew from the new input credal set Knew. In order to apply Jeffrey's rule on any prior distribution p fromK, we assume that ∀p∈K, ∀λi∈λ, p(λi)>0.

This section answers two fundamental questions: i) does updating a credal set with another credal result in a credal set and ii) can this update be done by manipulating only the vertices of the credal sets as in the case of conditioning with hard evidence. The following are the first main results of this paper (proofs are provided as supplementary material):

Proposition 1. Let K be the closed convex set to update. Let pnew be a single probability distribution over the partition λ and encoding the new information. Let K′ be such that

Then K′ is a convex credal set.

In Proposition 1, p⊕pnew denotes conditioning a pointwise probability distribution p with new inputs encoded in the form of a probability distribution pnew over a partition of Ω using Jeffrey's rule. This result states that using Jeffrey's rule to update each member of a convex credal set K with the same input distribution pnew results in a convex credal set K′ . Hence, we generalize the result that conditioning a credal set with a hard evidence gives a convex credal set.

Proposition 2. Let K be the closed convex set to update and let p∈K be a single probability distribution. Let Knew be a credal set over the partition λ and encoding the new information at hand. Let K′ be such that

Then K′ is a convex credal set.

Proposition 2 states that updating using Jeffrey's rule a single probability distribution p over Ω with each member of credal set Knew over a partition λ of Ω results in a convex credal set. Let us now generalize to the case where both K and Knew are arbitrary convex sets.

Proposition 3. Let K be the closed convex set to update and Knew be a closed convex set over the partition λ on Ω encoding the new information. Let

Then K′ is a convex credal set.

Proposition 3 states that using Jeffrey's rule to update each member of a prior credal set K with each member of credal set Knew results in a convex credal set K′ .

The following proposition states that the extreme points of the updated credal set K′ correspond to the updated set of extreme points of K with the new input using Jeffrey's rule.

Proposition 4. Let K be the closed convex set to update and let ext(K) be its set of extreme points. Let pnew be a single probability distribution over the partition λ and encoding the new information. Let K′ be the updated credal set following Proposition 1. Then

is the set of extreme points of K′ .

Lemma 1. Let K be the closed convex set to update and let ext(K) be its set of extreme points. Let pnew be a single probability distribution over the partition λ and encoding the new information. Let K′ be the updated credal set following Proposition 1. Then

In fact, given that from Proposition 1 K′ is convex (namely, it contains every convex combination of its extreme points) and the fact that CH(ext(K′ )) is by definition equal to all the convex combinations of the finite set ext(K′ ) computed following Proposition 4 then K′ can be recovered using only such extreme points.

Proposition 5 and Lemma 2 generalize conditioning credal sets based on extreme points to the case where the new input is also a credal set.

Proposition 5. Let K be the closed convex set to update and Knew be a closed convex set over the partition λ encoding the new information. Then

This means that an extreme point of K′ is necessarily a combination using Jeffrey's rule of an extreme point of K with an extreme point of Knew as illustrated in Example 1. But it is not true that every combination of p⊕pnew such that p∈ext(K) and pnew∈ext(Knew) is an extreme point of K′ . This is due to the union operation of convex sets. Indeed, in the case where the union of convex sets is convex, the extreme points of the resulting convex set (here ext(K′ )) is included in the union of sets of extreme points of the starting sets.

Lemma 2. Let K be the closed convex set to update and let ext(K) be its set of extreme points. Let pnew be a single probability distribution over the partition λ over Ω and encoding the new information. Let K′ be the updated credal set following Proposition 3. Then

Up to now, we showed that updating a credal set K with another uncertain input in the form of a credal set Knew over a partition of Ω results in a credal set K′ and amounts to updating the extreme points of K with those of Knew using Jeffrey's rule. Let us now use such findings to update prior probability intervals P with new uncertain inputs also in the form of probability intervals Pnew.

5 Updating Probability Intervals with Uncertain Inputs

Let us first place Jeffrey's conditioning rule principles in the context of probability intervals then provide update methods complying with such principles.

Let P be the IPD encoding the prior beliefs. Let Pnew be the IPD encoding the new information in hand. Pnew is of the form ((λ1, [l1, u1]),..,(λn, [ln, un])). This notation means that Pnew(λi)=[li, ui]. As in Jeffrey's rule, the set λ={λ1,..,λn} is a partition of Ω and we assume that the events λi are somewhat possible in the prior beliefs P (namely, we assume that ∀λi∈λ, P(λi)>0). The properties to satisfy stated in terms of interval-based probabilities are:

• Success principle (IP1) : It ensures that in the updated IPD P', the new information is fully accepted. Namely,

This principle enforces posterior intervals to be equal to the input intervals Pnew(λi).

• Probability Kinematics principle (IP2) : The objective here is to ensure that the intervals of P are modified as little as possible to accept the new information while respecting the probability kinematics principle in order to avoid affecting non relevant information.

Obviously, in the case of IPDs where lower bounds coincide with upper bounds (namely, if the initial belief set consists in a point-wise distribution over Ω and the new inputs are a point-wise distribution over the partition λ, the principles IP1 and IP2 collapse to P1 and P2 of Jeffrey's rule of Section 2.2. The success principle IP1 may be questionable but it may be a desired property in some applications such as in [Skulj, 2006]. In order to keep in Jeffrey's rule line, we just rephrase P1 in the context of probability intervals.

Now given an IPD P encoding the current information and new information Pnew, there are basically two possible ways to update P with Pnew: a credal-set based method applying at the semantic level and an interval-based one manipulating directly the bounds of the IPDs. In this paper, we rely on the former for robust conditioning while the latter is used for Dempster and geometric conditionings.

5.1 Updating Probability Intervals via Robust Conditioning on the Underlying Credal Sets

Our objective here is to update a belief set consisting of a prior IPD P with new inputs Pnew also provided in the form of an IPD over a partition λ of Ω. The belief update here consists in updating the credal set K underlying P (containing all the models of P) by the credal set Knew underlying Pnew using Jeffrey's rule. Indeed, one direct way to update a set of probability measures is to apply Jeffrey's rule on each member of the set where the new input is a single probability measure over the partition λ of Ω.

Following Lemma 2, we can define the update operation using only the extreme points of K and Knew, namely update each p∈ext(K) with each pnew∈ext(Knew) using Jeffrey's rule then recover the credal set K′ using the convex hull operator. Once K′ computed, the IPD P ′ is computed as lower and upper bounds from K′ . Hence, the credal-based update method is defined as follows:

Definition 2. Let P be IPD to update and Pnew be the new input IPD over a partition λ of Ω. Let K′ be the updated credal set computed according to Lemma 2 on K and Knew underlying respectively P and Pnew. P ′ is an IPD on Ω such that ∀ωi∈Ω,

Example 1. Let us assume in this example that the current beliefs about a given problem over two binary variables A and B are given by the IPD P(AB). In Table 2, we have the marginal distribution of A (namely, P(A)), the one of B (namely, P(B)) and the conditional distribution of A given B (namely, P(A|B)).

Assume now that we have new uncertain inputs given in probability distribution Pnew(B) as follows:

In order to update P to absorb Pnew using Definition 2, we update K with Knew using Lemma 2. Note that K has two extreme points p1=(.70, .05, .1, .15) and p2=(.50, .25, .1, .15) and Knew has also two extreme points, namely pnew1 =(.7, .3) and pnew2 =(.8, .2).

p1 will be updated into p′1=(.65, .05, .12, .18) and p′′ 1 =(.75, .05, .08, .12) and p2 will be updated into p′2=(.47, .23, .12, .18) and p′′ 2 =(.53, .27, .08, .12). Hence K′=CH({p′1 , p′′ 1 , p′2 , p′′ 2 }).

The updated distribution is given in P ′ of Table 3.

Table 2 and 3 show that the new input beliefs Pnew(B) are fully accepted in the posterior IPD P ′ (see the marginal distribution P ′ (B) computed from the updated distribution P ′ (AB)). Moreover, one can also check that P (A|B)=P ′ (A|B) ∀ai∈DA, ∀bi∈DB.

It is obvious that in case the IPDs P and Pnew underlying credal sets K and Knew each consisting of only one single probability distribution then updating P with Pnew following Definition 2 is equivalent to updating using Jeffrey's rule.

Lemma 3. If ∀ω∈Ω, P(ω)=P(ω) and ∀λi∈λ, P new (λi)=Pnew(λi) then the posterior distribution P ′ computed following Definition 2 amounts to using Jeffrey's rule to update the unique point-wise distribution p∈K underlying P with pnew∈Knew underlying Pnew.

In the general case, Proposition 6 states that updating using Definition 2 ensures that principles IP1 and IP2 are satisfied.

Proposition 6. Let P be IPD to update. Let the new information be the IPD Pnew over the partition λ of Ω. Let P ′ be the posterior IPD computed from P and Pnew following Definition 2. Then P ′ satisfies IP1 and IP2.

5.2 Alternatives to Robust Conditioning

Robust conditioning of probability intervals based on updating at the credal set level suffers from some drawbacks. For instance, it manipulates extreme points of credal sets underlying the IPDs while the number of such extreme points for an IPD with n states can be up to n! [Wallner, 2007]. More over, it requires that the events λi must be somewhat possible in the prior beliefs (namely, ∀λi∈λ, P(λi)>0) which may be seen as a strong constraint. The alternative then is to update directly the bounds of the intervals of the IPD to accommodate the input Pnew and use conditionings that do not require such strong assumptions. For instance, Dempster conditioning [Shafer, 1976] directly manipulates the bounds of the prior IPD P to condition on a new evidence ψ⊆Ω and it is defined as long as P(ψ)>0. It is defined as follows:

The lower bound can be easily obtained by duality (namely, P (φ||ψ)=1-P (φC ||ψ)=1- P (φC ∩ψ) P(ψ) . Here φC denotes the complement of φ in Ω. Proposition 7 extends Jeffrey's rule to probability intervals using Dempster conditioning.

Proposition 7. Let P be the IPD to update. Let the new information be the IPD Pnew on a partition λ of Ω. Let P ′ be the posterior IPD computed from P and Pnew as follows: ∀φ⊆Ω,

Then P ′ satisfies principles IP1-IP2.

Another common definition of conditioning of probability intervals is the one of geometric conditioning [Suppes and Zanotti, 1977] defined as follows:

The upper bound is obtained by duality P (φ|Gψ)=1 - P (φC |Gψ)=1- P (φC ∩ψ)

Proposition 8. Let P be the IPD to update. Let the new input be the IPD Pnew on a partition λ of Ω. Let P ′ be the posterior IPD computed from P and Pnew as follows: ∀φ⊆Ω,

Then P ′ satisfies principles IP1-IP2.

It is easy to check that in case where ∀ω∈Ω, P(ω)=P(ω) and ∀λi∈λ, P new (λi)=Pnew(λi) then updating following Propositions 7 and 8 collapses to updating using Jeffrey's rule in the standard setting (see Equation 8).

6 RelatedWork and Discussions

Jeffrey's rule generalizes the standard probabilistic conditioning to the case where the inputs are uncertain. This conditioning rule has been studied in many uncertainty settings such as possibility theory [Dubois and Prade, 1997] and DempsterShafer theory [Smets, 1993; Ma et al., 2011]. In [Benferhat et al., 2010], it is claimed that this rule can successfully recover most of belief revision rules such as natural and drastic belief revision. In [Skulj, 2006], the author use Jeffrey's rule to update a single probability distribution in order to obtain the desired neighborhood of events of interest expressed only in terms of interval probabilities. In [Yue and Liu, 2008], the authors dealt with updating imprecise knowledge in the framework of probabilistic logic programming. This work is mostly dealing with revising probabilistic logic programs and the proposed extension coincides with Jeffrey's rule and Bayesian conditioning only when the updated probabilistic logic program induces a single probability distribution. In [Marchetti and Antonucci, 2018], the authors propose a family of generalized adjustment operators tailored to update convex sets of probability measures with inconsistent piece of evidence. In case where the imprecise knowledge is compactly encoded by means of belief graphical models called credal networks [Cozman, 2000], there is only one work [da Rocha et al., 2008] dealing with updating a credal network with soft evidence. Note that the new information here is not a set of probability intervals but consists in likelihood ratios that can be cast into a single point-wise probability distribution. The authors in [Ma and Liu, 2011] deal with belief merging and focus on the influence of the strengths of inputs. The unique operator complying with the proposed postulates was proved to be a merging operator.

Updating sets of probability measures is not a new topic [Grove and Halpern, 1998; Levi, 1980; Walley, 1991; Tabia, 2018]. However, most of this work update sets of probability measures with hard evidence while the focus of the current work is updating sets of probability measures with new inputs both expressed by means of probability intervals. There are essentially two types of generalizations of Jeffrey's rule in the literature. The first one concerns rather generalizations or counterparts of this conditioning rule in some uncertainty theories such as belief functions [Smets, 1993] or possibility theory [Dubois and Prade, 1997] (note that such settings do not generalize the one of probability intervals and credal sets.). The second type of generalizations concerns rather the relaxation of the requirements of Jeffrey's rule. For example, in [Smets, 1993] it is no longer necessary that the new inputs be a partition of the set of possible states. Moreover, in [Smets, 1993; Wagner, 1992] the authors deal with the generalization of the conditionings (including Dempster and the geometric ones) of belief functions where both the prior information and new inputs are encoded by means of basic probability assignments over 2Ω (the powerset of Ω).

Regarding iterative revision, it is well-known that Jeffrey's rule is not commutative (since the new inputs are fully accepted, then updating first with (λi,[li, ui]) then with (λi,[l′i , u′i ]) will be different from updating first with

(λi,[l′i , u′i ]) followed by updating with ((λi,[li, ui])). Among the questions still open, there is that of the uniqueness of the proposed extensions (the paper only answers the question of the existence of extensions) as well as their optimality in terms of minimizing the belief change. As mentioned earlier, the objective of probability kinematics principle is to ensure some kind of minimal change. In the standard probabilistic setting, Jeffrey's rule was shown to provide the optimal solution in the sense of a distance measure between a prior distribution p and the posterior one p′ [Chan and Darwiche, 2005]. One can directly extend such a distance measure to credal sets as follows :

Proposition 9. Let K and K′ be two credal sets over the same states space Ω. Let

where

Then D is a distance measure.

The distance measure D combines Hausdorff distance (measuring distances between sets) with a distance for pointwise probability distributions specifically designed to bound belief change yielded by Jeffrey's rule in the standard probabilistic stetting [Chan and Darwiche, 2005]. Then there remains to show that updating a prior credal set K with new inputs in the form of credal set Knew following Lemma 2 guarantees that the posterior credal set K′ is optimal in the sense of distance D(K,K′ ) of Proposition 9. These two questions of optimality and uniqueness of the solution are part of the avenues for future work.

Another important open question concerns certain strong requirements of Jeffrey's conditioning in particular that the new information relates only to a partition of the set of possible states and the one requiring that the events λi∈λ be somewhat possible in the prior beliefs. We have proposed to use Dempster conditioning for this purpose but there are other tracks and other conditionings that address this problem such as the conditioning based on adjustment [Marchetti and Antonucci, 2018]. This latter is supposed to absorb even new inconsistent inputs (for instance in case of updating the probabilities of an event λi which could be impossible in the prior belief set in the case where P(λi)=0). In addition to these open questions, other avenues of future work will concern computational complexity and study of extensions of Jeffrey's rule with Pearl method of virtual evidence [Pearl, 1988] in the context of imprecise belief graphical models [Cozman, 2000]. Another avenue will be extending Jeffrey's rule to the case where the probabilistic beliefs are compactly encoded by probabilistic constraints as in conditional logic programs.

Acknowledgements

This research has received support from the ANR CROQUIS project, grant ANR-21-CE23-0004 of the French research funding agency ANR.