Syntactic Computation of Hybrid Possibilistic Conditioning under Uncertain Inputs

1 Introduction

In possibility theory, in presence of a new sure piece of information, there are two different ways to define the conditioning depending on how possibility degrees are interpreted: either we fully use the numerical unit interval [0,1] or we only use a relative total preordering induced by the unit interval [0,1]. This distinction leads to two different frameworks called quantitative (or product-based) framework and qualitative (or min-based) framework.

A possibilistic counterpart of Jeffrey's rule for cases where new information is uncertain has been proposed and used in [Dubois and Prade, 1997; 1993]. In [Benferhat et al., 2011], an analysis of the uniqueness and the existence of the solution has been performed.

At the syntactic level, when the input is a single weighted formula (φ, a), such a form of revision comes down to adding φ to a knowledge base Σ at the prescribed level a. What makes the problem difficult is that the knowledge base must be modified so that the added formula, φ, maintains its prescribed priority, a, that is, it is neither implicitly inhibited by higher-priority formulas that contradict it, nor pushed to higher priority levels by formulas that imply it. A first step towards an efficient way for doing this when the input is a single weighted formula has been proposed in [Benferhat et al., 2002].

Andrea G. B. Tettamanzi Universit´e de Nice Sophia Antipolis, Lab. I3S, France andrea.tettamanzi@unice.fr

Most possibilistic-based revision approaches are based on homogeneous operators for conditioning (the same operator is used to revise the possibility distribution on the models of all elements of the input). However, since the conditioning of the models of each component of the inputs proceeds independently of and in parallel with the conditioning of the models of the other components, one might as well decide to use different operators on different components, as proposed in [Benferhat et al., 2012] in a belief-revision setting, thus obtaining a family of several hybrid operators.

The ability to perform hybrid revision might prove useful, for example, in fault diagnosis, where possibly conflicting information from different sensors, requiring different treatments, must be combined simultaneously.

Despite the important role played by possibilistic Jeffrey's rule in belief revision (e.g. [Dubois et al., 1998; Benferhat et al., 2010a]), no syntactic equivalent to the possibilistic counterpart of Jeffrey's rule has been given yet in the literature, where the input consists of more than a single weighted formula. Here, we bridge this gap, by proposing a syntactic characterization of a set of basic operations that may be applied on possibility distributions. These operations will be used to define a syntactic computation of hybrid conditioning that revises possibilistic knowledge bases. Our approach generalizes possibilistic counterparts of Jeffrey's rule of conditioning in the sense that different forms of conditioning may be applied on different components of the input.

Performing conditioning at the syntactic level has clear advantages, since performing revision at the semantic level has a higher computational cost, as the cardinality of the set of interpretations grows exponentially with the number of propositional atoms, and even impossible if the language adopted has an infinite number of interpretations (consider, e.g., FirstOrder Logic or expressive Description Logics).

The paper is organized as follows: after recalling the main notions of possibilistic logic in Section 2 and presenting the two different types of conditioning in possibility theory in Section 3, Section 4 introduces the concept of generalized conditioning operators. Section 5 presents a set of basic elementary operations on possibility distributions which are then used in Section 6 to define syntactic computations of hybrid conditioning. Section 7 concludes the paper.

2 Possibilistic Logic: A refresher

Let us consider a finite set of propositional variables V and a propositional language PLV built from V ∪ {⊤,⊥} and the connectives ∧, ∨, ¬,→,↔ in the usual way. Formulas, i.e., elements of PLV are denoted by Greek letters.

Let Ω be the finite set of interpretations on V . We denote by [φ] the set of models of φ.

2.1 Possibility Distributions and Possibility Measures

A possibility distribution is a mapping from the set of interpretations Ω to the interval [0,1]. A possibility distribution π represents the available knowledge about what the real world is. By convention, π(ω) = 1 means that it is totally possible for ω to be the real world, 1 > π(ω) > 0 means that ω is only somehow possible, while π(ω) = 0 means that ω is certainly not the real world. When π(ω1) > π(ω2), ω1 is a preferred candidate to ω2 for being the real state of the world. π is said to be normalized if ∃ω ∈ Ω, such that π(ω) = 1.

A possibility distribution π induces two mappings grading respectively the possibility and the certainty of a formula:

• The possibility measure Π(φ) = max{π(ω) : ω |= φ} which evaluates to what extent φ is consistent with the available knowledge expressed by π.
• The necessity measure: N(φ) = 1-Π(¬φ) which evaluates to what extent φ is entailed by the knowledge expressed by π.

2.2 Possibilistic Knowledge Bases

A possibilistic knowledge base is a finite set of weighted formulas Σ = {(φi, ai), i = 1, . . . , n}, where ai is understood as a lower bound of the degree of necessity N(φi) (i.e., N(φi) ≥ ai). Formulas with ai = 0 are not explicitly represented in the knowledge base, i.e., only knowledge which is somewhat accepted by the agent is explicitly represented. The higher the weight, the more certain the formula.

Definition 1 Let Σ be a possibilistic base, and a∈[0,1]. We call the a-cut of Σ (resp. strict a-cut), denoted by Σ≥a (resp. Σ>a), the set of classical formulas in Σ having a certainty degree at least equal to (resp. strictly greater than) a.

A possibilistic knowledge base Σ is said to be consistent if the classical knowledge base, obtained by forgetting the weights, is classically consistent. Each inconsistent possibilistic base is associated with a level of inconsistency in the following way:

Definition 2 Let Σ be a possibilistic knowledge base. The inconsistency degree of Σ is: Inc(Σ) = max{a : Σ≥a ≡ ⊥}, with max(∅) = 0.

2.3 From Syntactic to Semantic Representation

Possibilistic knowledge bases are compact representations of possibility distributions. Given a possibilistic knowledge base Σ, we can generate a possibility distribution from Σ by associating to each interpretation, its level of compatibility with the agent's knowledge, namely with Σ, as explained in [Dubois et al., 1994].

Definition 3 : The least specific possibility distribution associated to knowledge base Σ is defined, for all ω ∈ Ω, by:

Example 1 Let Σ = {(q, 0.3), (q ∨ r, 0.5)}. Then:

The two interpretations qr and q¬r are the preferred ones since they are the only ones which are consistent with Σ, and ¬qr is preferred to ¬q¬r, since the highest knowledge falsified by ¬qr (i.e. (q, 0.3)) is less certain than the highest knowledge falsified by ¬q¬r (i.e., (q ∨ r, 0.5)).

The possibility distribution πΣ is not necessarily normal; it is normal iff Σ is consistent.

3 Conditioning in Possibility Theory

3.1 Conditioning under Certain Input

Two different types of conditioning [Dubois and Prade, 1998] have been defined in possibility theory for revising a possibility distribution π by a new and certain formula φ (when Π(φ) > 0):

• In an ordinal setting, we have:

This is the definition of minimum-based conditioning.

• In a numerical setting, we get:

This is the definition of product-based conditioning, which is also known as Dempster rule of conditioning [Shafer, 1976].

These two definitions of conditioning satisfy an equation of the form ∀ω, π(ω) = π(ω | φ)✸Π(φ), which is similar to Bayesian conditioning, where ✸ is the minimum or the product, respectively. The rule based on the product is much closer to genuine Bayesian conditioning than the qualitative conditioning defined from the minimum which is purely based on the comparison of levels. Besides, when Π(φ) = 0, π(ω |m φ) = π(ω |· φ) = 1, ∀ω, by convention (see also [Coletti and Vantaggi, 2009] for an analysis of this particular case in a coherent possibility theory setting).

3.2 Conditioning under Uncertain Input

Jeffrey's rule [Jeffrey, 1965] allows revising a probability distribution p into p′ given the uncertainty bearing on a set of mutually exclusive and exhaustive events µ = {(λi, ai), i = 1, . . . , n}. In [Dubois and Prade, 1997] a possibilistic counterpart of Jeffrey's rule has been defined. Given the initial beliefs encoded by a possibility distribution π and the uncertainty bearing on an exhaustive and mutually exclusive set of events λi in the form of (λi, ai) such that Π′ (λi) = ai, then the revised possibility distribution π′ according to Jeffrey's rule must satisfy the following conditions:

Property 1 (Input preservation condition) ∀λi, Π′ (λi) = ai. Property 2 (Conditioning preservation condition) ∀λi ⊂ Ω, ∀φ ⊆ Ω, Π′ (φ|λi) = Π(φ|λi).

Property 1 states that, after the revision operation, the a posteriori possibility of each event λi must be equal to ai (namely, Π′ (λi) = ai). Hence, this way for specifying the uncertainty relative to the uncertain evidence expresses the fact that the uncertain evidence is seen as a constraint or an effect once the new evidence is accepted [Chan and Darwiche, 2005]. Property 2 states that the conditional possibility of any event φ given any uncertain event λi remains the same in the original and the revised distributions.

In [Dubois and Prade, 1997], two possibilistic counterparts of Jeffrey's rules have been defined. More precisely, revising with µ can be achieved using the following definition:

where ✸ is either the minimum or the product, depending on whether conditioning is based on the product or the minimum operator. From the above definitions, it is clear that the new ranking on models of φ is simply obtained using conditioning with a sure input. Note that, if ✸ = product, both Properties 1 and 2 are satisfied. When ✸ = min, instead, only Property 1 is satisfied [Benferhat et al., 2011].

4 Generalized Conditioning Operators

We now define a family of generalized conditioning operators that take an uncertain input of the form µ = {(λi, ai, ✸i), i = 1, . . . , n}, where the propositional formulas λi induce a partition 1 of the set of interpretations, ai is the possibility of formula λi, and ✸i indicates the conditioning operator to be applied to the models of λi.

Hybrid conditioning with uncertain input µ = {(λi, ai,✸i), i = 1, . . . , n} proceeds to parallel changes on each models of λi. Here, the (λi, ai,✸i)'s are interpreted as constraints to be satisfied by the revised possibility distribution, namely, the revised possibility distribution denoted π(· |h µ) should be such that, for all i, Π(λi |h µ) = ai.

Definition 4 Let π be a possibility distribution. Let µ = {(λi, ai,✸i), i = 1, . . . , n} be an uncertain input, with max(ai) = 1. We assume that ∀λi,Π(λi) > 0. We define hybrid conditioning of π by µ, denoted by π(· |h µ) as follows: ∀λi ∈ µ and ∀ω |= λi,

• if ✸i =min,

The symbol ✸i indicates the way hybrid conditioning should be defined. Hybrid here is given the sense that models of λi and λj, with i ̸= j, may use different forms of conditioning. For instance, models of λi may be revised with minbased conditioning, whereas models of λj are revised with product-based conditioning.

1 In fact, this restriction may be relaxed by weakening Property 1 so that ∀λi, Π′ (λi) ≤ ai (ai's may reflect a reliability of the sources). This corresponds to a different view of conditioning than the one we adopt here.

One can check that Property 1 (Section 3.2) is satisfied whatever the ✸i used. Property 2 (Section 3.2), however, is only satisfied when ∀i, ✸i = product-based conditioning. When at least one of the ✸i is min-based conditioning, one may reuse the same counterexamples provided in [Benferhat et al., 2011].

Clearly, hybrid conditioning generalizes possibilistic Jeffrey's rule of conditioning where all λi are revised using the same form of conditioning; with respect to this, the symbols ✸i may be regarded as parameters that indicate the way the models of λi should be revised. Standard homogeneous conditioning (recalled in Section 3) is obtained as a special case when ✸i = ✸j for all i, j. Likewise, the hybrid belief change operators studied in [Benferhat et al., 2012] are obtained as special cases when µ = {(λ, 1, ✸1), (¬λ, a, ✸2)}, where ✸1 ̸= ✸2.

Example 2 Let us consider the possibility distribution πΣ of Example 1 and let us revise it for the uncertain input µ = {(q ∧ r, 0.8, min), (q ∧ ¬r, 0.4, min), (¬q, 1, ·)}.

Definition 4 yields the new possibility degree associated with each interpretation ω ∈ Ω:

• Interpretation qr is the only model of q∧r, hence we get π(qr |h µ) = 0.8 (first item of Definition 4).
• Interpretation q¬r is the only model of q ∧ ¬r, hence we get π(q¬r |h µ) = 0.4 (again using the first item of Definition 4).
• Interpretation ¬qr is one of the models of ¬q. We have from πΣ of Example 1 Π(¬q) = 0.7. Using item 2 of Definition 4, we get π(¬qr |h µ) = 0.7 0.7 · 1 = 1.
• Interpretation ¬q¬r is one of the models of ¬q. We have from πΣ of Example 1 Π(¬q) = 0.7. Using item 2 of Definition 4, we get π(¬q¬r |h µ) = 0.5 0.7 · 1 = 0.7143.

Hence, computing π(ω |h µ) according to Definition 4 yields:

One might wonder whether the same effect could not be obtained by first applying the min-based conditioning on an input µmin consisting of only the triples with ✸i = min and then applying the product-based conditioning on an input µproduct consisting of only the triples with ✸i = product. The problem is that neither µmin nor µproduct would be a partition; they would have to be completed by arbitrarily setting the possibility degree of the remaining models, thus yielding, in general, a different result.

5 Elementary Operations on Possibility Distributions

We now introduce a set of elementary operations on possibility distributions, summarized in Table 1, which will be used to characterize hybrid conditioning under uncertain input. For each elementary operation given in Table 1 we will later provide its syntactic counterpart when possibility distributions are compactly represented by possibilistic knowledge bases. This will help us define the syntactic computation of hybrid possibilistic conditioning.

Unnormalized conditioning simply declares countermodels of φ as impossible while preserving initial possibility degrees of models of φ. It is called unnormalized because max{πφ(ω) : ω ∈ Ω} may be different of 1.

• a-Discounting decreases the possibility degrees of some (or all) interpretations. The degree a ∈ [0, 1] can be viewed as a reliability degree of the source that provides the possibility distribution. There are two different ways to discount a possibility distribution:
• (Proportional a-discounting) either we proportionally shift down all interpretations, namely we replacie a possibility degree π(ω) of each interpretation ω by a · π(ω), or
• (Threshold a-discounting) we shift down only interpretations that are greater than a. Namely, Threshold a-discounting consists of viewing the degree a as threshold, where any interpretation having a possibility degree greater than a should be discounted to a.
• a-Enhancing is the dual operation to a-discounting. It increases the possibility degrees of some or all interpretations. The degree a here means that all possible events have at least a degree equal to a. Again, there are two different ways to enhance a possibility distribution:
• Proportional a-enhancing, which replaces a possibility degree π(ω) of each interpretation ω by max{1, π(ω)/a} with the constraint that π(ω)/a ≤ 1 (here, it is assumed that a > 0).
• Threshold a-enhancing, which leaves π unchanged if there exists at least an interpretation having a degree greater than a. Otherwise, it only enhances the best interpretations to a.

5.1 Characterizing Hybrid Conditioning

We begin by observing that Definition 4 may be viewed as a set of parallel changes to an initial possibility distribution induced by each element of the input:

Definition 5 Let π be a possibility distribution. Let µ = {(λi, ai,✸i), i = 1, . . . , n} be an uncertain input. Let us define, for each (λi, ai,✸i), a possibility distribution πλi as follows: ∀ω ∈ Ω,

where ✸i is either a minimum or a product operator.

The following proposition shows that hybrid conditioning with uncertain input µ can be viewed as a disjunctive combination of possibility distributions associated with each element of µ:

Proposition 1 Let µ = {(λi, ai,✸i), i = 1, . . . , n} be an uncertain input. Let πλi be a possibility distribution given by Definition 5. Then, ∀ω ∈ Ω, π(ω |h µ) = max(λi,ai,✸i)∈µ πλi (ω), where π(· |h µ) is given in Definition 4.

Example 4 One can easily check that, in Example 3,

where π(ω |h µ) was computed in Example 2.

The following two propositions give the characterisation of πλi using elementary operations. The two cases considered in Definition 4 are handled separately.

Proposition 2 Let π be an initial possibility distribution. Let (λi, ai,✸i) be an element of the input µ, where ✸i = min. We denote by π′ the result of modifying π using successively the following three steps :

1. apply unnormalized conditioning of π on λi;
2. apply threshold ai-discounting;
3. apply best ai-enhancing;

Then, ∀ω ∈ Ω, π′ (ω) = πλi (ω), where πλi is a possibility distribution given by Definition 5.

Intuitively, when ✸i = min, applying subnormalized conditioning allows to declare all countermodels of λi as impossible. Of course, they may be declared as possible by other πλj 's, with j ̸= i (recall that πλj 's are combined using the maximum operation; see Proposition 1). In a case where Π(λi) ≥ ai, applying ai-threshold discounting yields Πλi (λi) = ai. In this case, applying best-ai-enhancing has no effect. Clearly, we recover the first item of Definition 4. the semantic definition of hybrid conditioning. Now, in a case where Π(λi) < ai, applying ai-threshold discounting has no effect, since no model in [λi] has a degree greater than ai. However, applying best-ai-enhancing allows to promote the best models of λi to have a possibility degree equal to ai. Again, we recover the first item of Definition 4.

A similar result holds for product-based conditioning:

Proposition 3 Let π be an initial possibility distribution. Let (λi, ai,✸i) be an element of the input µ, where ✸i = product. We denote by π′ the result of modifying π using successively the following three steps :

1. apply unnormalized conditioning of π on λi;
2. apply proportional ai-discounting;
3. apply proportional Π(λi)-enhancing.

Then, ∀ω ∈ Ω, π′ (ω) = πλi (ω), where πλi is a possibility distribution given by Definition 5.

6 Syntactic Hybrid Conditioning

The following diagram summarizes the aim of this section:

The syntactic computation of hybrid conditioning is decomposed in three steps:

1. Provide the syntactic counterpart of each elementary operation on possibility distributions given in Table 1.
2. Provide the syntactic counterpart of each πλi associated to each element (λi, ai,✸i) of the input.
3. Use the syntactic counterpart of Propositions 1, 2, and 3 to give syntactic counterpart of hybrid conditioning.

6.1 Syntactic Elementary Operations

We now provide the syntactic counterparts of the elementary operations on possibility distributions given in Table 1.

Such syntactic characterizations are obtained in polynomial size of original bases. The results of this section will be used to define the syntactic counterpart of hybrid possibilistic conditioning under uncertain inputs given by Definition 4.

Table 2 summarizes these syntactic elementary operations, where Σ is a possibilistic knowledge base, πΣ is its associated possibility distribution according to Definition 3, φ is a propositional formula, and h(πΣ) = 1 - max{b : Σ>b is consistent}.

The following proposition establishes the equivalence between the operations of Table 2 and those of Table 1.

Proposition 4 Let Σ be a possibilistic knowledge and πΣ its associated possibility distribution. Let πE and ΣE be a result of modifying π and Σ using an elementary operation E given in Tables 1 and 2 respectively. Then, ∀ω ∈ Ω, we have:

where πΣE is the possibility distribution associated with ΣE.

For lack of space, we only give the proof of proportional a-discounting and threshold a-discounting.

• The proof of the syntactic counterpart of proportional adiscounting is as follows. Let ω be an interpretation.

• = a · πΣ(ω).
• To see the proof of threshold a-discounting, let us first decompose Σ into two subbases:

Let ω be an interpretation. Assume that ω is a model of all formulas of Σ1. Then it is easy to check that πΣ(ω) ≥ a and hence TD(πΣ(ω), a) = a by definition of Threshold a-discounting. Besides, using Definition 3, we also have πΣTD(a) (ω) = a (since ω trivially falsifies (⊥, 1 - a)), hence πΣTD(a) (ω) = TD(πΣ(ω), a).

Similarly, if ω falsifies some formulas of Σ1, then clearly πΣ(ω) = πΣ1 (ω) ≤ a hence by definition of Threshold a-discounting we have TD(πΣ(ω), a) = πΣ(ω). Besides one can easily check that πΣTD(a) (ω) = πΣ1 (ω). Hence, again we have πΣTD(a) (ω) = TD(πΣ(ω), a).

6.2 Putting It All Together

We are now able to show how hybrid conditioning is performed (syntactically) on a possibilistic knowledge base.

Let Σ be a possibilistic knowledge base and π be its associated possibility distribution. Proposition 1 suggests that, in order to compute the possibilistic knowledge base Σµ associated with π(· |h µ), it is enough to first compute the possibilistic knowledge bases associated with each πλi , then apply the syntactic counterpart of the disjunctive combination mode given in Proposition 5.

The syntactic counterpart of the disjunction of two possibility distributions, using maximum operator, has been studied in [Benferhat et al., 2010b]:

Proposition 5 Let Σ1 and Σ2 be two possibilistic bases. Let π1 and π2 be their associated possibility distributions. Then Σ∨ = {(φi ∨ ψj,min{ai, bj}) : (φi, ai) ∈ Σ1, (ψj, bj) ∈ Σ2} is associated with the disjunctive combination π∨ of π1 and π2.

It is obvious that the disjunctive combination mode is associative and commutative, which means that these combination modes can be extended to more than two possibilistic knowledge bases. In terms of complexity in space, the way Σ∨ is defined suggests that its size is the product of the sizes of Σ1 and Σ2. In fact, we can provide a linear representation of Σ∨ by introducing one new variable per possibilistic knowledge base. More precisely, let A1 and A2 be two new propositional symbols that are associated with Σ1 and Σ2 respectively. Then, we redefine the syntactic counterpart of disjunctive combination modes [Benferhat et al., 2010b] as

Of course, this way of defining the disjunctive counterpart is more compact than the one given in Proposition 5, since the size of Σ′∨ is polynomial w.r.t. the sizes of Σ1 and Σ2. It is easy to show that πΣ∨ (ω) = πΣ′∨ (ω), where the interpretation ω does not contain the new symbols A1 and A2.

To sum up, to compute the syntactic conditioning of a possibilistic base Σ under uncertain input µ = {(λi, ai, ✸i)}, we first compute each Σλi using the syntactic elementary operations, then we take their disjunction.

Example 5 Let us continue with Example 2: recall that we are to revise knowledge base Σ = {(q, 0.3), (q ∨ r, 0.5)} of Example 1 for the uncertain input µ = {(q∧r, 0.8, min), (q∧ ¬r, 0.4, min), (¬q, 1, ·)}. Now, we compute Σµ as follows:

1. Compute the unnormalized conditional bases Σλi U :

1. Compute the discounted bases:

1. Compute the enhanced bases:

1. Compute the disjunctive combination of the three enhanced bases: we begin by computing

because (q ∧ ¬r) ∨ q ∨ r = q ∨ r and (q ∧ ¬r) ∨ q = ¬q∨¬r; finally, we compute the disjunctive combination of the result with Σq∧r TE(0.8) in tabular form as follows:

which, after simplification, yields

It is now easy to verify that πΣµ , the possibility distribution corresponding to Σµ, is identical to π(ω |h µ) as computed in Example 2.

7 Conclusion

We have studied syntactic computations of a new form of possibilistic conditioning where both min-based and productbased conditioning can be used for revising possibility distributions under uncertain inputs. Our hybrid conditioning extends the possibilistic counterparts of Jeffrey's rule [Dubois and Prade, 1993], heterogeneous conditioning [Benferhat et al., 2012], and standard min-based and product-based conditioning [Dubois and Prade, 1998] in presence of a sure piece of information. We then proposed a syntactic characterization of a set of basic operations that may be applied on possibility distributions. These operations were then used to define a syntactic computation of hybrid conditioning that revises possibilistic knowledge bases. An important result is that the computational complexity is the same as the one of standard min-based and product-based conditioning. Hence, we enriched the definitions of possibilistic conditioning without extra computational cost. These results are very important for belief revision. Indeed, in [Benferhat et al., 2010b] it has been proved, at the semantic level, that many revision approaches (such as adjustment [Williams, 1994], natural belief revision [Boutilier, 1993], drastic belief revision [Nayak, 1994], and/or revision of an epistemic state by another epistemic state) can be captured using possibilistic Jeffrey's rule. Syntactic counterparts of all these major revision operations studied in [Benferhat et al., 2010b] can now have their syntactic counterparts using results of this paper.

Acknowledgments

This work has received support from the Agence Nationale de la Recherche, ASPIQ project reference ANR-12-BS02-0003.