Qualitative Relevance and Independence: A Roadmap

1. Introduction

It has been known for some time that the AGM revision theory (named from Alchourr6n, Gardenfors and Makinson; see Gardenfors ( 1988) ), and the preferential approach to non monotonic reasoning are two sides of the same coin. In recent years we have shown that this tight link could be explained in the setting of possibility theory, using set­ functions satisfying the single axiom fi(A v B) = max(O(A), fi(B)), together with qualitative conditioning. The contribution of this paper is to show that there is a "third side" of the coin, viz. qualitative independence. The notion of epistemic independence naturally arises in the framework of reasoning under uncertainty and belief change. Most prominently, probabilistic conditional independence (between variables) plays a key role in Bayesian nets. More recently several authors (Delgrande and Pelletier, 1994; Benferhat et al., 1994; Dubois et al., 1994) have advocated the interest of qualitative independence notions for nonmonotonic reasoning. Gardenfors ( 1990) and Farinas del Cerro and Herzig (1996) have investigated the complementary notion ofrelevance in relation to belief change. The aim of the paper is to provide an exhaustive typology of the forms that independence and relevance can assume in the setting of an ordinal approach to uncertainty, like the one underlying major belief change and nonmonotonic inference theories.

In the paper, A, B, C, ... stand for events belonging to a Boolean algebra of subsets of a set W. T and F are propositional constants denoting the true and false events respectively. Let us assume that our representation framework enables us to distinguish between three states of cognitive attitudes regarding C: i) Cis an accepted belief, ii) ...,c is an accepted belief (i.e., C is refuted), iii) neither C nor -,c is accepted (i.e., total ignorance about C). Hence C and ...,c cannot be held as accepted beliefs simultaneously. Intuitively, an event C is said to be independent of another event A when one's opinion about C is not affected by learning A.

Any definition of independence or relevance in such a setting can be expressed in terms of five basic notions corresponding to the possible effects of learning A on the belief status of C (Table 1). As already said an important distinction has to be made between propositions C that are a priori believed and those which are a priori ignored. Independence may then refer either to the Jack of influence of A on a believed proposition C that remains accepted (line I), or on the contrary, to the lack of influence of A on an ignored proposition that remains ignored (line 5). We shall speak of "qualitative independence" in the former case, and of "uninformativeness" in the latter.

Relevance then may mean either that A negatively affects an agent's belief in C, or that A makes the agent start to believe C. This covers three situations: C was an accepted belief and upon learning A, C becomes ignored (line 2), or refuted (rejected) (line 3); if C was previously ignored, C may become accepted when learning A (line 4). In the follo­ wing we reserve the name "qualitative relevance" for the first two cases, keeping the third one apart since the belief change then takes the opposite direction. It can be checked that all the other situations can be obtained from these 5 cases changing C into ...,c, or exchanging C and A.

What are the properties of such independence and relevance notions? Can they be characterized in a precise way? How are they related to theories of uncertainty? It is the purpose of this paper to answer these questions. In particular, it turns out that these notions are generally non­ symmetric and sensitive to negation. However, they can be preserved via conjunction or disjunction, and this behavior is the one that was found natural by philosophers of probability such as Keynes or Gardenfors. It is also worth noticing that due to the ternary structure of states of belief, it cannot be expected that independence and relevance be complementary notions.

For the sake of brevity, proofs of propositions are omitted. Moreover, definitions of independence and relevance are not given here with respect to a given context. However, the extension to ternary relations ("A is relevant/independent w.r.t. to C, given evidence E") is straightforward, and used in Section 5.

2. Relevance and Independence

2.1. The Probabilistic Framework

Suppose that a cognitive state is represented by means of a probability-like set-function. The standard definition of probabilistic independence is in terms of invariance with respect to conditioning: C is independent of A iff Prob(C I A) = Prob(C). It follows from the axioms of probability theory that independence then satisfies:

(symmetry) If C is independent of A then A is independent of C.

(negation) · If C is independent of A then C is independent

of ·A.

(truth) A and T are independent.

Probabilistic independence has been criticized quite early by several authors such as Keynes: its symmetry, and the lack of properties with respect to conjunction and disjunction have been found debatable in an epistemic perspective. Following Keynes, Gardenfors ( 1978) has discussed conjunction criteria for dependence and independence.

(CCD.e) If C depends on A, and C depends on B, and A 1\ B:;:. F, then C depends on A 1\ B

(CCI .e ) If C is independent of A, and C is independent of B then Cis independent of A 1\ B.

Later, Gardenfors (1990) has proposed that the concept of relevance should satisfy four minimal requirements (up to a fifth axiom, superfluous in our representational setting, stating that relevance is syntax-independent):

Rl: A is relevant for C iff C is not independent of A

R2: If A is relevant for C then ·A is relevant for C

R3: T is independent of C

R4: If Cis contingent(= neither T nor F) then Cis relevant for C. ·

These postulates equate relevance with dependence (i.e., the complement of independence), and insist on negation insensitivity (so that F is not relevant for C). Gardenfors (1978) shows that under Rl-R4, CCI.e + CCD.e leads to trivialization in the probabilistic framework.

An alternative attitude is, rather than rejecting CCD .e, to accept regularities w.r.t. conjunction and disjunctions (such as CCD .e and CCI.e) and drop RI and R2. Namely, we shall object to negation insensitivity in some contexts, and we shall question the postulate that there is no middle way between relevance and independence. We shall choose a representation framework where the three cognitive attitudes (acceptance, rejection and ignorance) can be distinguished, viz. qualitative possibility theory, an ordinal setting for representing uncertainty in a way that directly extends classicai logic with levels of acceptance. This framework has strong connections with belief change (Dubois and Prade, 1991) and ordering-based nonmonotonic reasoning (Gardenfors and Makinson, 1994; Benferhat et al., 1992).

2.2. The Possibilistic Framework

In this section, we briefly recall the notions of possibility measure and distribution (Zadeh, 1978) and of conditional possibility (Dubois and Prade, 1988). Possibility theory provides a simple uncertainty representation setting where ordinal information about events derives from a complete transitive ordering of elementary events (the interpretations of a language). Dual rankings of events (or formulas) are induced in terms of possibility and certainty.

A function IT from a set of events into any finite totally ordered set L (with top 1 and bottom 0) is a possibility measure if it satisfies the following decomposability axiom: fl(A v B) = max(fl(A), fl(B)). This axiom enables an ordering on events to be recovered from an ordering of elementary events.. The quantity N(A) = I - fl(·A) is called the necessity of A, and represents a level of certainty (or acceptance) of A. 1 - O is just a notation for the order­ reversing function on L (if L = { 1 = ,.e 1 > .t2 > ... >,.en= 0}, 1 - (.t i) = .tn+I-i 'rJ i). In can be checked that min(N(A), N(·A)) = 0; A is said to be accepted iff N(A) > N(·A), or equivalently N(A) > 0. And we have the reasonable axiom of acceptance saying that if A is accepted and so is B, then A 1\ B is accepted too, since N(A 1\ B) = min(N(A), N(B)) holds. If A is not accepted (N(A) = 0), it does not entail that it is rejected (N(·A) > 0). This makes it clear that possibility theory can express the three possible attitudes that we want to distinguish.

Every possibility measure can be viewed as an encoding of a comparative possibility relation on events "~"defined by A ~ B if and only if fl(A) ~ fl(B) (Dubois and Prade, 1991). As shown in (Farinas del Cerro and Herzig, 1991, Hajek et al., 1994; Boutilier, 1994 ), such a notion of comparative possibility is equivalent to that in (Lewis, 1973).

Conditional possibility can be defined similarly to conditional probability, changing the Bayes identity P(A 1\ C) = P ( C I A) · P(A) into a more qualitative counterpart:

The use of minimum is justified by the ordinal nature of the possibility scale. The conditional possibility fl(C I A) is then defined as the maximal solution of the above equation. This choice of the maximal solution is due to the principle of minimal specificity which urges to select the least informative or committed possibility measure, i.e., the one which allows each event to have the greatest possibility level:

By duality the conditional necessity is N(...,C I A) = I - nee I A) . Hence

The following notable property expresses that C is accepted in context A iff A 1\ C is more plausible than A 1\ -,C:

Note that if neA 1\ C)> neA 1\ ...,q then N(C I A)= N(...,A v C)= 1 - neA 1\ ...,q ~ 1 - nc...,q = N(C). Hence if N(C) > 0, the situation N(C) > N(C I A) > 0 (attenuation of acceptance) may never happen. So the input information A either confirms C or totally destroys our confidence in it. This is typical of the ordinal conditioning.

2.3. A Typology

It is tempting to define independence via conditioning in possibility theory, in a way similar to probability theory, namely to define C as independent of A when the (conditional) measure of C given A . is equal to the unconditional measure of C. We can define independence either as nee I A) = ncq or as N(C I A) = N(C). If nee I A) = nCC) < I then we are in the situation where C is plausibly rejected (since nc...,q = 1 > nCC)) . It means that learning that A is true does not affect the plausible rejection of C. This expresses the negative statement that rejecting C is independent of A. It suggests to use N(C I A) = N(C) in order to express the positive statement that A is independent of (the level of acceptance of) C. It turns out that this notion of independence is not uniform because it expresses the disjunction of two distinct forms of irrelevance:

The two situations (i) and (ii) correspond to (almost) reversed orderings of interpretations. Case (i) corresponds to the situation where N(C I A) = N(C) = 0, that is, C is either ignored or rejected both a priori and in the context A, which is again a composite situation. Now, in possibility theory, the full knowledge about C is expressed by the pair (N(C), N(...,C)) and it covers the three situations where C is accepted, rejected or unknown. This leads to recognize three situations of independence in the absolute form:

• absolute independence of C vis-a-vis A
• N(C I A)= N(C) > 0 (hence N(...,C I A)= N(...,C) = 0)
• absolute independence of ...,c vis-a-vis A
• N(...,C I A)= N(...,C) > 0 (hence N(C I A)= N(C) = 0) - uninformativeness

The first (resp.: second) condition means that believing C (resp. : ...,q is not affected by A, while the third condition means that A does not inform about C. In the first (resp. : second) situation we shall say that believing C (resp.: ...,q is absolutely independent of A, where the term "absolute" refers to the stability of the level of acceptance, and the expression "believing C" indicates that C is an accepted a priori belief. The latter situation, which cannot be expressed in the probabilistic framework, means that in the presence of A, the piece of belief C, which was originally ignored, is still ignored. In this case, we shall speak of uninformativeness of A about C (or ...,c, equivalently), a notion that is negation-insensitive with respect to C. This is formalized by the following definitions: ·

Definition 1. Believing C is absolutely independent of A (noted A .L> C) iffN(C I A)= N(C) > 0.

Definition 2. A does not inform about C iff N(C I A) = N(C) = N(...,C I A)= N(...,C) = 0.

Now in order to investigate the opposite notions of relevance, simply taking the complement of the absolute independence or uninformativeness relation is not satisfactory. For instance the negation of "believing C is absolutely independent of A" is "either N(C) = 0, or N(C I A)'# N(C) > 0". But it is hard to see why N(C) = 0 alone would mean that A is relevant to C. So in the possibilistic framework, we must give up the idea that "relevance" is just the negation of "independence" . If we investigate relevance, we must keep the acceptance condition (N(C) > 0) and only negate the other equality condition. So A is said to be absolutely relevant to believing C iff N(C) > 0 but N(C I A) '# N(C). Again, this situation splits into three cases

In the first situation, learning A confirms C by increasing its level of acceptance. In the second case, learning A leads us to forget about C and we say that A cancels C. In the third case, the agent's belief in C is reversed: we say that A refutes C. (Remember that the missing case N(C) > N(C I A)> 0 (attenuation) cannot occur here.)

The two cases when A confirms C, and believing C is absolutely independent of A, are those where learning A neither cancels nor refutes the agent's a priori acceptance of C. In the purely ordinal case where levels of belief are represented in a relative fashion only, it is not really meaningful to distinguish confirmation from absolute independence. This argument is reinforced by the fact that attenuation of acceptance can only occur in a drastic way: namely if A confirms C, but B subsequently does not and on the contrary weakens our belief in C, then A 1\ B either cancels or refutes C. To sum it up, it means that there will not be any compensation effect between the confirmation of C by A and the subsequent negative effect of B. The latter will prevail in any case. So it is legitimate to consider the disjunction of the two cases when A neither cancels nor refutes C (in other words either A confirms C or believing C is absolutely independent to A) as expressing a single form of qualitative independence of C w.r.t. A. This leads to purely ordinal notions of relevance and independence:

Definition 3. Believing C is qualitatively independent of A (denoted A -:t> C) iff N(C) > 0 and N(C I A)> 0.

Definition 4. A is qualitatively relevant to believing C, denoted (A=> C), iff N(C) > 0 and N(C I A)= 0.

Hence A is qualitatively relevant for C iff A cancels or refutes our belief in C. Mind that relevance can but negatively affect beliefs. A last form of dependence is the one obtained when neither C nor ..,c is an accepted belief but C becomes accepted in the context where A is true. This is a form of direct relevance of A for C akin to causality, at least an epistemic form of it, since it means that A is a reason for starting to believe C.

Definition 5. A justifies C iff N(C) = N(..,C) = 0 and N(C I A) >0.

Figure 1 is the counterpart of Table I. It exhaustively summarizes the various cases of relevance and independence that can be expressed in an ordinal setting. (Dual cases can be expressed in terms of those which appear in the table, changing A into ..,A or C into -,C.) Figure 1 lays bare the fact that two distinct concepts of independence exist: uninformativeness, and a qualitative independence that expresses that an accepted belief C resists an input information A. The latter notion has absolute independence as a particular case.

Independence expresses a property of invariance (under conditioning) of the ordering of situations where C is true. This is similar to the case of probabilistic independence, that expresses numerical in variance under conditioning.

3. Properties and Representation Theorems

We now examine the properties of the above notions with respect to conjunction and disjunction. We shall first do it for the two notions of independence (Definitions 2 and 3) and three notions of "non-relevance" understood as the negations of each relevance notions (cancellation, refutation, justification). Then we also do it for these three relevance notions and the negation of the two independence notions. There are eight possible properties as follows , here formulated in terms of qualitative independence (-:t>) and its negation(=>, qualitative dependence).

In the above properties named XCYz, X stands for disjunction or conjunction, C for criterion, Y for independence or dependence and z stands for left or right. Whether or not a criterion holds for a given notion is listed in Table 2 below. Grey slots refer to the negation of the notion on the corresponding line.

All of the relations satisfy DCI.e, but the properties CCI.e and CCD .e are never satisfied and do not appear in the table. This apparent paradox will be explained in Section 4. In the case of uninformativeness and cancellation DCI.e is the only property that holds (formally, this is due to the prese.nce. of negations in the definition of the former). "Qualitative independence" and "uninformativeness" are the mo~t regular notions, due to their simple definition. Lastly, It can ~e proved that independence and relevance are related VIa negation as follows: If A => C then both ..,A -:t> C and C -:t> ..,A.

The above properties do not completely characterize the respective notions . It can be proved that q~alita~ive independence and qualitative relevance can be axtomattzed in such a way as to recover qualitative possibility theory. We have established the following results:

Theorem 1 (axiomatic equivalence of -:f.> with possibility theory). Let -:t> be any relation on events such that

• Qll T -:t> T (Tautologies do not undermine tautologies)
• QI2 if A -:t> C then A -:t> B v C (Right weakening)
• QI3 if T -:t> C then C -:t> C (If C is believed, then it cannot undermine itself)
• QI4 if A -:t> C then T -:t> C (If there is A that does not undermine C then C is a priori believed)
• QI5 A -:f.> -,A never holds
• QI6 if A -:t> C and B -:t> C then A v B -:t> C (left OR rule, i.e., DCI .e)

• QI7 if A v B -:1=> C then either A -:1=> C or A v B -:1=> -,A or both (similar to rational monotony)
• QI8 if A -:1=> B and A -:1=> C, then A -:1=> B A C (stability under conjunction for acceptance, i.e. , CCir)

and let N be any mapping from the set of events to [0,1] such that A -:1=> C iff N(C I A) ~ N(C) > 0. Then -:1=> is a qualitative independence relation iff N is a non-trivial necessity measure.

Lastly, it is possible to axiomatize qualitative relevance A z> C. Note that A z> Cis not equivalent to ..,(A -:1=> C), so that Glirdenfors' Rl does not hold. We have that A""> C iff ..,(A -:1=> C) and T -:1=> C. It is thus easy to see that A v C z> -,c iff TI(...,C) >TI(C) ~ TI(A). So the axiomatization of relevance does not follow immediately from that of independence.

Theorem 2 (axiomatic equivalence of z> with possibility theory). Let z> be any relation on events satisfying

QRl it does not hold that A z> A v C

QR2 F z> A iff A = T or there exists C such that -,A z> C

QR3 if A ::.> C and -,B ::.> B then A ::.> BA C

QR4 if ..,A ::.> C then -,A ::.> A

QR5 if A v B ::.> C then A ::.> C orB ::.> C (DCI.e)

QR6 if A v B ::.> A and A ::.> C then A v B ::.> C (restricted transitivity)

QR7 if A::.> B A C then A::.> BorA::.> C

(contraposed CCir)

and let N be any mapping from the set of events to L such that A z> C iff N(C I A) = 0 and N(C) > 0. Then ""> is a qualitative relevance relation iff N is a non-trivial necessity measure.

Although Glirdenfors' Rl does not hold, QRl is related to QII, QR3 to QI2, and Q15 is related to QR4. QR5-QR7 are contraposed forms of QI6-QI8. The contraposition of QI3-QI5 does not hold for z>.

4. Qualitative Independence and Belief Change

Several notions of independence and relevance studied above, among which qualitative independence, can be fully expressed in the framework of revision of propositional theories also called belief sets (Glirdenfors, 1988). Revising a belief set K by a sentence A means to add A to K and to restore consistency so as to keep A. Gardenfors (1990) proposes the following criterion for the revision of a belief set: If a belief state K is revised by a sentence A, then all sentences in K that are independent of the validity of A should be retained in the revised state of belief This seems to be a very natural requirement for belief revision operations, as well as a useful tool when it comes to implementing belief change operations. As noted by Glirdenfors, "a criterion of this kind cannot be given a technical formulation [ ... ] in a simple propositional language because the notion of relevance is not available in such a language." However the above criterion does make sense in the ordinal setting of possibility theory.

Given a belief set K, that is, a set of propositional formulas closed under deduction, and a revision operation *, K * A represents the result of revising K by a formula A. As stated in Glirdenfors ( 1988), if the reviSIOn operation satisfies the AGM postulates, then K and * can be represented equivalently by an epistemic entrenchment ordering, which in turn is nothing else than a qualitative necessity ordering (Dubois and Prade, 1991 ). Conversely, any qualitative necessity ordering leads to an AGM revision operation. Namely, given a necessity function N, the set K= {C, N(C) > 0} is a belief set that is, K is closed under conjunction and logical consequence. Moreover, it can be proved that the revision operation * can be defined in terms of possibility theory as follows: C e K * A is equivalent to N(C I A)> 0 (Dubois and Prade 1991). If we translate the various definitions of independence and relevance in terms of revision we get the following facts :

1. C is qualitatively independent of A (A -:1=> C) iff C e K and C E K * A
2. A cancels C iff C e K and C '"= K * A and -,c '"= K * A
3. A refutes C iff C e K and -,c e K * A
4. A is qualitatively relevant for C (A z> C) iff C e K and C'"= K*A
5. A justifies C iff C '"= K and C e K * A
6. A does not inform about C iff C '"= K, ...,c '"= K, ...,c '"= K * A and C '"= K *A.

Qualitative independence exactly expresses Glirdenfors' above requirement for independence-based revision.

The operation opposite to revision is contraction. Contracting a belief set K by a sentence A means to delete A from K, as well as those sentences that enable A to be derived so as to obtain a belief set K - A that does not contain A. The Harper Identity (Glirdenfors, 1988) defines contraction in terms of revision as follows: K- A= K n (K * -,A), i.e., first revise K to accept -,A and then keep only those formulas in K. Conversely K * A = Cn((K - -,A) u {A}), where Cn is the consequence operation. This is the Levi Identity whereby revising by A means deleting -,A first and then adding A. Companion definitions of qualitative independence and relevance relations 'i=C> and zc> can be associated to a contraction operation "-" via the following definition:

where A 'i=C> C reads: forgetting A does not affect the belief in C and A ::.c> C reads forgetting A destroys the belief in C. It is easy to check that Levi and Harper Identities can be written in terms of independence relations between events as follows:

Farinas del Cerro and Herzig ( 1996) have proved the equivalence between ::.c> satisfying QR1-QR7 (where A is changed into -,A) and AGM contraction operators.

Similarly, postulating the equivalence between -,A -:1=> C and C E K - A, it can be proved that axioms Qll-QI8 are equivalent to the AGM postulates. Indeed, with the Harper Identity, Cis qualitatively independent of A (A -:1=> C) when C e K and C e K- -,A (because K- -,A is K n K *A) . Due to the set inclusion of K - ..,A in K, this is just equivalent to C E K- -,A, which makes this independence notion parti-cularly simple: in fact, we are able to express that C E K by F -:t=> C. This permits to obtain a complete axiomatization of qualitative independence -:t=> by just rewriting the AGM postulates for contraction, turning A into -.A.

If A either cancels or refutes C then C E K and C ~ K * A. With the Harper Identity this is equivalent to C E K and C ~ K - -,A. This corresponds to a dependence notion proposed in (Farinas del Cerro and Herzig, 1996). If we had presented relevance and independence this way in terms of belief contractions instead of revisions, the properties CCD.e and CCI.e would have been fulfilled whenever the corresponding revision-based notion (via Levi or Harper Identity) satisfies DCI.e and DCD.e, respectively. In this way, we can recover the original Keynes-Gardenfors criteria (absent in Table 2).

5. Conclusion

We have established the equivalence between the statements "the agent's belief in C is independent of proposition A" (A -:t=> C) and "the agent still believes C if his belief set is revised by A". This notion of independence can be expressed in terms of possibilistic conditioning, thus laying bare the analogy with probabilistic independence.

This paper indicates that the notions of ordinal independence introduced here can be modelled as extra constraints on the ordering of interpretations of a language, and have the same expressive power as the AGM theory of belief revision. However the latter is in turn equivalent to the rational monotony approach to plausible inference (Lehmann and Magidor, 1992; Gardenfors and Makinson, 1994) and to possibility theory. Namely any AGM-Iike revision operation * on a belief set there corresponds to a possibility measure IT such that fiCA "B) > fiCA "-,B) iff B E K * A iff A fv B (A plausibly infers B). So, a revision operation generates a conditional knowledge base ~* = {A fv B: BE K *A}. The nice interaction between the basic laws of plausible inference (embedded in Lehmann's axiomatic framework), belief revision, and possibilistic independence, augmented with results of this paper, suggest that independence assumptions can be expressed by means of supplementary conditional assertions, provided that the above introduced independence notions are extended to conditional independence:

Qualitative conditional independence:

(A -:t=> C)0 iffN(C I D)> 0 and N(C I A" D)> 0.

So if a piece of knowledge comes under the form "C is independent of A in the context D", it can be expressed by the set of default rules { D fv C, A " D fv C}. Note that the corresponding conditional relevance (A :::> C)o (i.e., A refutes or cancels C in the context D) corresponds to the idea of Delgrande and Pelletier ( 1994) that A is relevant to a conditional assertion D fv C. However their definition is more specific than ours: it can be expressed in our terminology by "A refutes C in context DorA refutes ...,C in context D". They do not seem to consider the possibility of a mere cancellation of C.

Noticeably, the rational monotony axiom RM: D fv C implies D fv -,A or A" D fv C (underlying rational closure), does express a condition for conditional qualitative independence: In the context D, C is qualitatively independent of A as soon as -,A is not accepted in this context. These results are promising in the scope of exception-tolerant inference, because they suggest that conditional knowledge bases not delivering expected answers can be repaired by means of suitable conditional independence assumptions. It opens the road to a sound, feasible and computationally reasonable treatment of exception-tolerant plausible inference (Benferhat et al., 1996a, b) that can cope with most, if not all, counterexamples to rational closure.