# conditional_independence_for_iterated_belief_revision__98bcf8af.pdf

Conditional Independence for Iterated Belief Revision

Gabriele Kern-Isberner1 , Jesse Heyninck1,3,4 and Christoph Beierle2

1TU Dortmund, Germany 2Fern Universit at in Hagen, Germany 3Vrije Universiteit Brussel, Belgium 4University of Cape Town and CAIR, South-Africa gabriele.kern-isberner@cs.tu-dortmund.de, jesse.heyninck@tu-dortmund.de, christoph.beierle@fernuni-hagen.de

Conditional independence is a crucial concept for efficient probabilistic reasoning. For symbolic and qualitative reasoning, however, it has played only a minor role. Recently, Lynn, Delgrande, and Peppas have considered conditional independence in terms of syntactic multivalued dependencies. In this paper, we define conditional independence as a semantic property of epistemic states and present axioms for iterated belief revision operators to obey conditional independence in general. We show that c-revisions for ranking functions satisfy these axioms, and exploit the relevance of these results for iterated belief revision in general.

1 Introduction

Over the last decades, conditional independence was shown to be a crucial concept supporting adequate modelling and efficient reasoning in probabilistics. For example, in medical diagnosis, symptoms are often assumed to be conditionally independent given the disease [Pearl, 1988]. It is the fundamental concept underlying network-based reasoning in probabilistics, which has been arguably one of the most important factors in the rise of contemporary artificial intelligence. Even though many reasoning tasks on the basis of probabilistic information have a high worst-case complexity due to their semantic nature, network-based models allow an efficient computation for many concrete instances of these reasoning tasks thanks to local reasoning techniques. On the other hand, for the modelling of intelligent agents, it is important to give a formal account of the dynamics of knowledge and belief. This is done in the field of belief change. Traditionally, researchers have been mainly interested in studying the dynamics of sets of propositional formulas (so-called AGM theory, based on [Alchourr on et al., 1985]). One of the drawbacks of this perspective is that such formal models do not give an account of iterated belief revision, i.e. of how to revise a previously revised set of formulas. It became clear that for iterated revision, information about the state of mind of an agent that goes beyond the merely

Contact Author

propositional level is needed. Such information can be represented by epistemic states, and iterated belief revision can then be viewed as the revision of these epistemic states. In the AGM framework, total preorders over propositional interpretations that represent the respective (im)plausibility of these interpretations, provide the basic semantic structures for iterated revision [Darwiche and Pearl, 1997]. In this paper, we present a concept of conditional independence for total preorders that provides a novel axiomatic foundation for iterated belief revision, allowing for local reasoning in the revised epistemic state. The basic idea of such axioms is simple: If we have conditional independence in the prior epistemic state, and the new information is compatible with that, then we also should have conditional independence in the posterior epistemic state. The challenge is to define conditional independence for total preorders that is, on the one hand, compatible with (iterated) AGM revision, and, on the other hand, shows basic characteristics of probabilistic conditional independence. However, conditional independence in probabilistics makes heavy use of the rich arithmetic properties of probabilities which are not available for total preorders. Spohn s ranking functions [Spohn, 1988; Spohn, 2012] are a good mediator between these different semantic frameworks. We use the notion of conditional independence for ranking functions to fully elaborate our approach to conditional independence in belief revision by providing c-revisions [Kern-Isberner and Huvermann, 2017] as a proof of concept. Moreover, we show how many of the features of that framework can be made relevant also for total preorders, and hence for iterated revision in general. This paper is organized as follows: In the next section, we compile basics on propositional logic, total preoders and ranking functions, and iterated AGM belief revision. In Section 3, we recall related work on conditional independence which is relevant to this paper. Then Section 4 presents our approach to conditional independence for total preorders, and Section 5 makes it usable for iterated revision. Section 6 concludes and puts out future work.

2 Formal Preliminaries Propositional Logic. Let L be a finitely generated propositional language over an alphabet Σ with atoms a, b, c, . . ., and with formulas A, B, C, . . .. For conciseness of notation, we will omit the logical and-connector, writing AB instead

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

of A B, and overlining formulas will indicate negation, i.e. A means A. Let Ωdenote the set of possible worlds over L; Ωwill be taken here simply as the set of all propositional interpretations over L. ω |= A means that the propositional formula A L holds in the possible world ω Ω; then ω is called a model of A, and the set of all models of A is denoted by Mod(A). For propositions A, B L, A |= B holds iff Mod(A) Mod(B), as usual. For a proposition A L, Cn(A) = {B L | A |= B} is the set of consequences of A in L. By slight abuse of notation, we will use ω both for the model and the corresponding conjunction of all positive or negated atoms. This will allow us to use ω both as an interpretation and a proposition, which will ease notation a lot. Since ω |= A means the same for both readings of ω, no confusion will arise. For subsets Θ of Σ, let L(Θ) denote the propositional language defined by Θ, with associated set of interpretations Ω(Θ). Note that while each sentence of L(Θ) can also be considered as a sentence of L, the interpretations ωΘ Ω(Θ) are not elements of Ω(Σ) if Θ = Σ. But each interpretation ω Ωcan be written uniquely in the form ω = ωΘωΣ\Θ with concatenated ωΘ Ω(Θ) and ωΣ\Θ Ω(Σ \ Θ). Here, ωΘ is called the reduct of ω to Θ [Delgrande, 2017]. If Ω Ω is a subset of models, then Ω |Θ = {ωΘ|ω Ω } Ω(Θ) restricts Ω to a subset of Ω(Θ). In the following, we will often consider the case that Σ is the union of three disjoint subsignatures Σ1, Σ2, Σ3, i.e., Σ = Σ1 Σ2 Σ3 where Σi Σj = for i = j, and denotes the exclusive union. Then we write ωi instead of ωΣi for the reducts to ease notation, i.e., in this case, each ω Ωcan be written in the form ω = ω1ω2ω3 with ωi Ω(Σi), i {1, 2, 3}. For Θ Σ and A L(Σ), with AΘ L(Θ), called the reduct of A to Θ, we denote any formula with Mod(AΘ) = {ωΘ | ω Mod(A)}. Note that AΘ is uniquely defined up to logical equivalence. For instance, for Σ = Σ1 Σ2 Σ3 and A L(Σ), we get AΣi L(Σi) for i {1, 2, 3}, and, e.g., AΣ1 Σ3 L(Σ1 Σ3). Just like ωΘ with ω Ω(Σ), we will consider AΘ also as a sentence in L(Σ) and thus having models over the larger signature Σ; using this view, AΘ is called the projection of A onto Θ in [Lynn et al., 2022]. Instead of AΣi Σj, we will often just write AΣi,Σj.

TPOs and OCFs. Total preorders (TPO) over possible worlds are total, reflexive, and transitive relations over Ω. As usual, ω ω iff ω ω and not ω ω, and ω Ψ ω iff both ω ω and ω ω. Such TPOs can be lifted to total preorders on the set of propositions via A B iff there is a (minimal) ω Mod(A) such that ω ω for all ω Mod(B). If Ω Ω, then min (Ω ) = {ω Ω | ω ω for all ω Ω } denotes the set of -minimal models in Ω . If Ω = Ω, then we simply write min( ) instead of min (Ω). If A L, then min (A) = min (Mod(A)). The minimal models of a TPO form its associated belief set: Bel ( ) = T (min( )), where T (Ω ) denotes the set of formulas which are true in all elements of Ω Ω. I.e., the agent believes exactly the propositions that are valid in all most plausible models. With K L, we denote the core of Bel ( ), i.e., the unique (up to logical equivalence) formula that respresents Bel ( ), in the sense that Bel ( ) = Cn(K ).

For Θ Σ, any TPO on Ω(Σ) induces uniquely a marginalized TPO |Θ on Ω(Θ) by

ωΘ 1 |Θ ωΘ 2 iff ωΘ 1 ωΘ 2 . (1) Note that on the right hand side of the iff condition above ωΘ 1 , ωΘ 2 are considered as propositions in L(Ω), hence ωΘ 1 ωΘ 2 is well defined [Kern-Isberner and Brewka, 2017]. Ordinal conditional functions (OCFs), (also called ranking functions) κ : Ω N { } with κ 1(0) = , were introduced (in a more general form) first by [Spohn, 1988]. They express degrees of plausibility of propositional formulas A by specifying degrees of disbeliefs of their negations A. More formally, we have κ(A) := min{κ(ω) | ω |= A}. Note that also OCFs κ induce total preorders on Ωvia ω1 κ ω2 iff κ(ω1) κ(ω2). Analogously to TPOs, Bel (κ) = T ({ω | κ(ω) = 0} is the set of beliefs of an OCF κ. An OCF κ is called convex if it does not have empty layers, i.e., if κ 1(i) = implies κ 1(j) = for all j < i. The marginalization of κ on Θ Σ, denoted by κ|Θ, is defined by κ|Θ(ωΘ) = κ(ωΘ) for any ωΘ Ω(Θ). OCFs can also be conditionalized with respect to propositional formulas: for any A L with κ(A) < , κ|A is an OCF on the models of A defined by κ|A(ω) = κ(ω) κ(A). Note that the marginalization for TPOs and OCFs as given above are special cases of the forgetful functor Mod(σ) from Σ-models to Θ-models in [Beierle and Kern-Isberner, 2012] where Θ Σ and σ : Θ Σ is the inclusion from Θ to Σ. Revision of Beliefs and Epistemic States. The following theorem that generalizes results from [Katsuno and Mendelzon, 1991] is fundamental to (iterated) AGM belief revision [Alchourr on et al., 1985]. In particular, it reveals that total preorders are the basic semantic structures that are needed for iterated belief revision. Theorem 1 ([Darwiche and Pearl, 1997]). A revision operator that assigns a posterior epistemic state Ψ A to a prior state Ψ and a proposition A is an AGM revision operator for epistemic states iff there exists a total preorder Ψ for an epistemic state Ψ with associated belief set K = Bel (Ψ), such that for any proposition A it holds that K A = Bel (Ψ A) = T (min(Ψ, A)). (2) This theorem also allows us to use the same symbol for revisions of belief sets and revision of epistemic states, where implicitly the validity of (2) is presupposed. C-revisions provide a highly general framework for revising OCFs (as specific implementations of total preorders) by (sets of) conditionals resp. propositions. For the purposes of this paper it will be sufficient to recall c-revisions by a single proposition [Kern-Isberner and Huvermann, 2017]. Definition 1 (Propositional c-revisions for OCFs). Let κ be an OCF specifying a prior epistemic state, and let A L. A (propositional) c-revision of κ by A is given by the OCF

κ A(ω) = κ(A) + κ(ω) + η if ω |= A, 0 otherwise (3)

with an integer η satisfying η > κ(A) κ(A). κ(A) in (3) is a normalization factor, and η > κ(A) κ(A) ensures κ A |= A. Each c-revision is an iterated revision in the sense of [Darwiche and Pearl, 1997].

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

3 Related Work on Conditional Independence Conditional independence is the crucial ingredient to make computations efficient in probabilistic networks [Pearl, 1988]. Thanks to the close relationship between rankings and probabilities, there is a straightforward adaptation of conditional independence for OCFs [Spohn, 2012, Chapter 7]. Definition 2. Let Σ1 Σ2 Σ3 Σ and let κ be an OCF. Σ2, Σ3 are conditionally independent given Σ1 with respect to κ, in symbols Σ2

κ Σ3|Σ1, if for all ω1 Ω(Σ1), ω2 Ω(Σ2), and ω3 Ω(Σ3), κ(ω2|ω1ω3) = κ(ω2|ω1) holds. As for probabilities, conditional independence for OCFs expresses that information on Σ3 is redundant for Σ2 if full information on Σ1 is available and used. The following lemma is straightforward and helpful for technical proofs. Lemma 1. Let Σ1, Σ2, Σ3 be disjoint subsignatures of Σ, let κ be an OCF. Then Σ2, Σ3 are conditionally independent given Σ1 with respect to κ iff for all ω1 Ω(Σ1), ω2 Ω(Σ2), and ω3 Ω(Σ3), we have κ(ω1ω2ω3) = κ(ω1ω2) + κ(ω1ω3) κ(ω1). As in probabilistics, conditional independence with respect to an OCF κ generalizes κ-independence, as defined in [Kern Isberner and Huvermann, 2017; Kern-Isberner and Brewka, 2017]; more precisely, Σ1, Σ2 are κ-independent iff they are conditionally independent given the empty set. Conditional independence with respect to databases resp. propositional formulas have been considered in [Darwiche, 1997; Lang and Marquis, 1998; Lang et al., 2002; Lynn et al., 2022]. We recall the definition of [Lynn et al., 2022] here. Definition 3 ([Lynn et al., 2022]). Let K L be a propositional formula. Let Σ1 Σ2 Σ3 Σ. Σ2, Σ3 are conditionally independent given Σ1 modulo K if for all ω Ω, for all A2 L(Σ2), A3 L(Σ3) such that K ω1 |= A2 A3, we have K ω1 |= A2 or K ω1 |= A3. In their paper [Lynn et al., 2022], Lynn, Delgrande, and Peppas considered conditional independence for (basic) AGM revision on the level of belief sets via syntactical representations called multivalued dependencies, and consider TPO-based AGM revision operators that comply with such dependencies. Our approach to conditional independence is a semantic one directly for TPOs, and hence is applicable to (more general) iterated revision tasks. For a more detailed comparison with that work, please see Section 5.

4 Conditional Independence for TPOs The basic semantic structure for iterated belief revision are total preorders (TPOs) on possible worlds, according to the seminal works by Katsuno and Mendelzon [Katsuno and Mendelzon, 1991], and Darwiche and Pearl [Darwiche and Pearl, 1997]. We first present a semantic notion of conditional independence for total preorders. Definition 4. Let Σ1 Σ2 Σ3 Σ let be a TPO on Ω. Σ2, Σ3 are conditionally independent given Σ1 with respect to , in symbols Σ2

Σ3|Σ1, if for all ω1 Ω(Σ1), ω2 1, ω2 2 Ω(Σ2), and ω3 1, ω3 2 Ω(Σ3) holds that for all i, j {2, 3}, i = j,

ω1ωi 1ωj 1 ω1ωi 2ωj 1 iff ω1ωi 1 ω1ωi 2. (4)

Again, conditional independence expresses that in the context of given information from Σ1, information on Σj is irrelevant for the ordering of worlds on Σi. Practically speaking, ωj 1 can be cancelled out . We illustrate this by examples.

Example 1. Consider the following TPO over the signature Σ = {p, q, r}:

p qr, pqr pqr, pqr, pq r pqr, p q r pqr.

{r}|{p}. A witness of this is the fact that p q pq and p qr pqr and p qr pqr. Notice that {q}

{r}|{p} yet it does not hold that {q, p}

{r}| . To see this, it suffices to observe that p q pq (in view of p qr pqr) yet p q r pqr. Likewise, it does not hold that {p}

{r}|{q}. This can be seen by observing that p q pq yet p q r pq r.

The next example uses slightly increased signatures.

Example 2. Let Σ = Σ1 Σ2 Σ3 with Σ = {a, b, c, d}, Σ1 = {a, b}, Σ2 = {c}, Σ3 = {d}, and let be the TPO over Σ given by:

abcd, abcd, abcd abcd, abcd, abcd

abcd, abcd abcd, abcd, abcd, abcd

abcd, abcd, abcd abcd

For checking that Σ2, Σ3 are conditionally independent given Σ1 with respect to , we have to ensure that for all ω1 {ab, ab, ab, ab}, all ω2 1, ω2 2 {c, c}, and all ω3 1, ω3 2 {d, d} the condition in (4) holds. For ω1 = ab we get, e.g., abc abc and abcd abcd and abcd abcd, and furthermore abd abd and abcd abcd and abcd abcd. Checking also the remaining instances of (4) reveals that Σ2

Σ3|Σ1 holds.

This definition of conditional independence for TPOs is compatible with the definition for OCFs, in the sense that conditional independence with respect to an OCF κ implies conditional independence with respect to the corresponding TPO κ:

Proposition 1. Let Σ1 Σ2 Σ3 Σ, let κ be an OCF. Then Σ2

κ Σ3|Σ1 implies Σ2

Proof. Let Σ1 Σ2 Σ3 Σ, and let κ be an OCF such that Σ2

κ Σ3|Σ1 holds. For the proof of Σ2

κ Σ3|Σ1, we focus on Σ2, the proof for Σ3 is analogous. Let ω1 Ω(Σ1), ω2 1, ω2 2 Ω(Σ2), and ω3 Ω(Σ3). ω1ω2 1ω3 κ ω1ω2 2ω3 means κ(ω1ω2 1ω3) κ(ω1ω2 2ω3), which is equivalent to κ(ω2 1|ω1ω3) κ(ω2 2|ω1ω3). Because of Σ2

κ Σ3|Σ1, this is equivalent to κ(ω2 1|ω1) κ(ω2 2|ω1), and hence to κ(ω1ω2 1) κ(ω1ω2 2), i.e., ω1ω2 1 κ ω1ω2 2, which was to be shown.

The converse of Proposition 1, i.e., that Σ2

Σ3|Σ1 implies Σ2

κ Σ3|Σ1 for some κ with κ= , cannot be expected in general because TPOs are too weak to mimick the arithmetic features of OCFs faithfully. However, in some cases, we might indeed lift conditional independence with respect to TPOs to conditional independence with respect to suitable OCFs.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Proposition 2. Let Σ1 Σ2 Σ3 Σ, and let be a TPO on Ωsuch that Σ2

Σ3|Σ1 holds. Let κ be an OCF such that κ= . Furthermore presuppose that all conditional OCFs in the sets {κ|ω1ω3 | ω1 Ω(Σ1), ω3 Ω(Σ3)} and {κ|ω1 | ω1 Ω(Σ1)} are convex. Then we also have Σ2

Proof. We have to show that κ(ω2|ω1ω3) = κ(ω2|ω1) for all ω1 Ω(Σ1), ω2 Ω(Σ2), ω3 Ω(Σ3). Since all conditional OCFs κ|ω1ω3, κ|ω1 define convex OCFs on Ω(Σ2) and start with rank 0, this is equivalent to (κ(ω2 1|ω1ω3) κ(ω2 2|ω1ω3) iff κ(ω2 1|ω1) κ(ω2 2|ω1)), for all ω1 Ω(Σ1), ω2 1, ω2 2 Ω(Σ2), ω3 Ω(Σ3). But this is straightforward: we have κ(ω2 1|ω1ω3) κ(ω2 2|ω1ω3) iff κ(ω1ω2 1ω3) κ(ω1ω2 2ω3). Due to κ= , this means ω1ω2 1ω3 ω1ω2 2ω3. Because of Σ2

Σ3|Σ1, this is equivalent to ω1ω2 1 ω1ω2 2, and hence to κ(ω1ω2 1) κ(ω1ω2 2), i.e., to κ(ω2 1|ω1) κ(ω2 2|ω1). We illustrate this by continuing Example 1.

Example 3. The minimal OCF implementing the TPO from Example 1 is given by κ(p qr) = κ(pqr) = 0, κ(pqr) = κ(pqr) = κ(pq r) = 1, κ(pqr) = κ(p q r) = 2, κ(pqr) = 3. It is straightforward to check that all conditional OCFs κ|ω1ω3, κ|ω1 are convex (they all take on only the ranks 0 and 1), so we also have {q}

κ {r}|{p} according to Prop. 2 which can easily be verified.

Next, we show that conditional independence of total preorders is compatible with the notion of conditional independence modulo propositional formulas (see Definition 3):

Proposition 3. Let Σ1 Σ2 Σ3 Σ. If Σ2, Σ3 are conditionally independent given Σ1 with respect to , then Σ2, Σ3 are also conditionally independent given Σ1 modulo the core K .

The proof of this proposition is straightforward, but omitted due to lack of space. The following example illustrates Proposition 3.

Example 4. For Σ = Σ1 Σ2 Σ3 and as in Example 2 we have Σ2

Σ3|Σ1 and K abcd abc. For checking whether Σ2, Σ3 are conditionally independent given Σ1 modulo K , we have to consider all ω Ω, all A2 L(Σ2), and all A3 L(Σ3). If K ω1 or if any of A2, A3 is equivalent to or equivalent to , the conditional independence requirement holds trivially. Thus, we are left to check the requirement for ω {abcd, abcd, abcd}, A2 {c, c}, and A3 {d, d}. First, let ω = abcd and thus ω1 = ab. Since K ab abcd, we get K ω1 |= A2 A3 only for the three cases (i) A2 c and A3 d, (ii) A2 c and A3 d, or (iii) A2 c and A3 d. In each of these cases, K ω1 |= A2 or K ω1 |= A3 holds. Otherwise, let ω {abcd, abcd} and thus ω1 = ab in both cases. Since K ab abc, we get K ω1 |= A2 A3 only for the two cases (i) A2 c and A3 d, or (ii) A2 c and A3 d. In both cases, K ω1 |= A2 holds. In summary, we observe that Σ2, Σ3 are conditionally independent given Σ1 modulo K .

Among the most important properties of independence relations is that of being a (semi-)graphoid:

Definition 5 ([Pearl and Paz, 1985]). A ternary relation

| among subsets of some signature Σ is a semi-graphoid over Σ iff for all pairwise disjoint Σ1, Σ2, Σ3, Σ4 Σ the following properties hold:

Symmetry if Σ2

Σ3|Σ1 then Σ3

Decomposition if Σ2

Σ3 Σ4|Σ1 then Σ2

Weak Union if Σ2

Σ3 Σ4|Σ1 then Σ2

Contraction if Σ2

Σ3|Σ1 and Σ2

Σ4|Σ3 Σ1 then Σ2

| is a graphoid (over Σ), if the following additional property is satisfied::

Intersection If Σ2

Σ3|Σ1 Σ4 and Σ2

Σ4|Σ3 Σ1 then Σ2

Spohn already showed that conditional independence in OCFs is a graphoid [Spohn, 2012, Theorem 7.10]. Since TPOs cannot make use of any of the arithmetic features that ranking functions and probabilities rely on, we cannot expect a similarly strong result here. Nevertheless, we are able to prove some of these properties, at least in a weakened form:

Proposition 4. Let a TPO be given. Then conditional independence .

.|. over Σ satisfies symmetry, weak union, and the following variant of decomposition:

Symmetric decomposition if Σ2

Σ3 Σ4|Σ1 and Σ2 Σ4

Σ3|Σ1 then Σ2

The proof of this proposition is a lengthy technical exercise and left out due to lack of space. It is an open question whether conditional independence for TPOs is, in general, a graphoid. For OCFs, and hence also regarding the appertaining TPOs according to Proposition 1, ranking functions respecting specific conditional independence statements can be easily constructed under mild conditions of compatibility, as shown next:

Proposition 5. Let Σ = Σ1 Σ2 Σ3, let κ2, κ3 be OCFs defined over Σ1 Σ2 and Σ1 Σ3, respectively, such that κ2(ω1) = κ3(ω1) for all ω1 Ω(Σ1). Define κ over Σ via κ(ω) = κ2(ω1ω2) + κ3(ω1ω3) κ2(ω1). Then κ is an OCF such that Σ2

κ Σ3|Σ1 holds.

Proof. First, κ is an OCF, i.e., there are worlds ω with κ(ω) = 0. Due to the prerequisite κ2(ω1) = κ3(ω1) for all ω1 Ω(Σ1), κ2|Σ1, κ3|Σ1 are marginalized OCFs such that κ2|Σ1 = κ3|Σ1. So, there is ω1 0 Ω(Σ1) such that κ2(ω1 0) = κ3(ω1 0) = 0. Then there are ω2 0 Ω(Σ2) and ω3 0 Ω(Σ3) such that κ2(ω1 0ω2 0) = κ2(ω1 0) = 0 = κ3(ω1 0) = κ3(ω1 0ω3 0). For ω0 = ω1 0ω2 0ω3 0, we have κ(ω0) = κ2(ω1 0ω2 0) + κ3(ω1 0ω3 0) κ2(ω1 0) = 0. Furthermore, we simply have to show that κ(ω1ω2) = κ2(ω1ω2), κ(ω1ω3) = κ3(ω1ω3), and κ(ω1) = κ2(ω1)(= κ3(ω1)), then the statement is immediate from the definition of κ. We show the first statement, the others are anologous:

κ(ω1ω2) = min ω3 Ω(Σ3) κ(ω1ω2ω3)

= min ω3 Ω(Σ3)(κ2(ω1ω2) + κ3(ω1ω3) κ2(ω1))

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

ω12 κ2(ω12) κ2(ω1) | ω13 κ3(ω13) κ3(ω1)

abc 1 1 | abd 2 1 abc 2 | abd 1 abc 3 3 | abd 3 3 abc 4 | ab d 4 abc 1 0 | abd 0 0 abc 0 | abd 0 abc 2 2 | abd 2 2 abc 3 | ab d 3

Table 1: OCFs κ2, κ3 for Example 5

ω κ(ω) ω κ(ω) ω κ(ω) ω κ(ω)

abcd 2 abcd 1 abcd 3 abcd 2 abcd 3 abcd 4 abcd 4 abcd 5 abcd 1 abcd 1 abcd 0 abcd 0 abcd 2 abcd 3 abcd 3 abcd 4

Table 2: The constructed OCF κ for Example 5

= κ2(ω1ω2) + min ω3 (κ3(ω1ω3)) κ2(ω1)

= κ2(ω1ω2) + κ3(ω1) κ3(ω1) = κ2(ω1ω2).

We illustrate this construction by an example. Example 5. Let Σ = Σ1 Σ2 Σ3 with Σ = {a, b, c, d}, Σ1 = {a, b}, Σ2 = {c}, Σ3 = {d}. With ω12, ω13, we denote worlds from Ω(Σ1 Σ2) resp. Ω(Σ1 Σ3), where ω1 is their common part over Σ1. Let κ2, κ3 over Σ1 Σ2 resp. Σ1 Σ3 be defined as in Table 1. We can easily observe that the compatibility condition κ2(ω1) = κ3(ω1) is satisfied. The constructed OCF κ(ω) = κ2(ω1ω2) + κ3(ω1ω3) κ2(ω1) is shown in Table 2. We might also use this construction for TPOs that are sufficiently compatible. More precisely, suppose we have Σ = Σ1 Σ2 Σ3 and two TPOs 2, 3 on Σ1 Σ2 resp. Σ1 Σ3 are given such that we can associate with them suitable OCFs κ2, κ3 over the respective subsignatures satisfying κ2= 2, κ3= 3 and obeying the compatibility condition κ2(ω1) = κ3(ω1) for any ω1 Ω(Σ1). Then κ constructed as in Proposition 5 is an OCF, and Propositions 5 and 1 ensure that Σ2

κ Σ3|Σ1 holds. At this point, the reader might wonder where conditional independencies come from. There are at least three sources where a knowledge engineer might look for conditional independencies. The first is background knowledge about the domain that being modelled, not unlike Bayesian networks, which are often manually constructed on the basis of background assumptions about the domain being modelled. A second source of conditional independencies is combining a set of component OCFs over different (possibly overlapping) sub-signatures as outlined in Proposition 5. Thirdly, we plan to develop algorithms for the extraction of conditional independencies between sub-signatures, taking inspiration of the

learning of the structure of Bayesian networks [Pearl, 1988, Ch. 8].

5 Conditional Independence Axioms for Iterated Revision

The basic idea of axioms of conditional independence for iterated belief revision would be that conditional independencies should be respected under revision, as far as possible. This means that if a conditional independence prevails in the prior epistemic state, and the new information is compatible with this independence in the sense that it does not contain atoms from both conditionally independent sets (see also [Lynn et al., 2022]), then also the posterior epistemic state should show that same conditional independence.

(CItpo) Let be a revision operator for TPOs, let be a TPO over Ω. Let Σ = Σ1 Σ2 Σ3. If Σ2

Σ3|Σ1 and A L(Σ1 Σ2), then Σ2

(CIocf) Let be a revision operator for OCFs, let κ be an OCF over Ω. Let Σ = Σ1 Σ2 Σ3. If Σ2

κ Σ3|Σ1 and A L(Σ1 Σ2), then Σ2

Proposition 6. C-revisions satisfy (CIocf).

Proof Sketch. Let Σ = Σ1 Σ2 Σ3, and let κ be an OCF over Ωsuch that Σ2

κ Σ3|Σ1 holds. Let A L(Σ1 Σ2). We have to show that then Σ2

κ Σ3|Σ1 also holds, where κ = κ A is a c-revision of κ by A according to Definition 1. In other words, we have to show that κ (ω1ω2ω3) = κ (ω1ω2) + κ (ω1ω3) κ (ω1). We outline the proof of the case for ω |= A, the case for ω |= A is similar. The claim is shown by first deriving the following equalities: κ (ω) = κ(A) + κ(ω1ω2) + κ(ω1ω3) κ(ω1) (I), κ (ω1ω3) = κ(A) + min{κ(Aω1), κ(Aω1) + η} + κ(ω1ω3) κ(ω1) (II), and κ (ω1) = κ(A) + min{κ(Aω1), κ(Aω1)+η} (III). Combining (I), (II) and (III) then yields κ (ω1ω2ω3) = κ (ω1ω2) + κ (ω1ω3) κ (ω1) as desired.

We illustrate this result by an example.

Example 6. We have Σ = Σ1 Σ2 Σ3 with Σ = {a, b, c, d}, Σ1 = {a, b}, Σ2 = {c}, Σ3 = {d}, and κ is given by Table. 3 with Σ2

κ Σ3|Σ1 (see also Example 5) and Bel (κ) = Cn(abc), i.e., Kκ = abc. We revise by A = bc. We have κ(A) = 1, so any c-revision κ of κ by A has the form

κ A(ω) = 1 + κ(ω) + η if ω |= b c, 0 otherwise.

We illustrate this with κ and a generic c-revision κ with η > κ(A) κ(A) = 1 in Table 3. It is straightforward to verify that indeed, Σ2, Σ3 are also conditionally independent given Σ1 in κ . Choosing η = 2 yields an OCF κ whose induced TPO κ coincides with given in Example 2.

It is also interesting to note that in Example 6, all crevisions as shown in Table 3 with η > 2 would yield the same total preorder. This means that in spite of the numerical nature of OCFs, the purely qualitative result of the revision,

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

ω κ(ω) κ (ω) | ω κ(ω) κ (ω)

abcd 2 1 | abcd 1 0 abcd 1 0 | abcd 1 0 abcd 3 2 + η | abcd 0 1 + η abcd 2 1 + η | abcd 0 1 + η

abcd 3 2 + η | abcd 2 1 + η abcd 4 3 + η | abcd 3 2 + η abcd 4 3 + η | abcd 3 2 + η abcd 5 4 + η | abcd 4 3 + η

Table 3: The (revised) OCF κ for Example 6

ω κ(ω) κ (ω) | ω κ(ω) κ (ω)

pqr 1 0 | pqr 1 2 pqr 2 1 | pqr 3 4 pqr 0 1 | p qr 0 1 pq r 1 2 | p q r 2 3

Table 4: The (revised) OCF κ for Example 7

i.e., the TPO κ A, does not depend so much on the chosen impact factor η, but more on the qualitative structure in the prior epistemic state. Therefore, we can very well use the power of OCF-based c-revisions also for TPOs to obtain revisions that satisfy (CItpo), if suitable transformations into OCFs are possible. More precisely, if Σ2

Σ3|Σ1 holds in a TPO , and we can find an OCF κ with κ= and Σ2

κ Σ3|Σ1, then we can apply c-revisions to this κ such that also Σ2

κ Σ3|Σ1 holds, and via κ we obtain a revision of that satisfies (CItpo) thanks to Propositions 6 and 1. We illustrate this by continuing Examples 1 and 3. Example 7. The TPO from Example 1 is defined over the signature Σ = {p, q, r}, has the belief set Bel ( ) = Cn(qr), and satisfies {q}

{r}|{p}, i.e., Σ1 = {p}, Σ2 = {q}, Σ3 = {r}. We want to revise this TPO by A = pq L(Σ1 Σ2) with the help of c-revisions. The minimal OCF κ implementing this TPO has been computed in Example 3 and is shown in Table 4. According to Proposition 2 and Example 3, we have {q}

κ {r}|{p}, and revising κ by A via c-revisions yields κ = κ A with

κ A(ω)(ω) = 1 + κ(ω) + η if ω |= A, 0 otherwise

with η > 1 0. We choose η = 2 and obtain the revised κ shown in Table 4 satisfying {q}

κ {r}|{p} according to Proposition 6. Then a revision of by A can be defined via A = κ A and is given by = A : pqr pqr, pqr, p qr pq r, pqr p q r pqr Thanks to Proposition 1, we also have {q}

A {r}|{p}. Finally, we show some partial agreement with the results from the paper [Lynn et al., 2022] that focuses on propositional AGM revision; the proof is straightforward and left out due to lack of space.

Proposition 7. Let be a revision operator for TPOs, let Σ = Σ1 Σ2 Σ3. Let be a TPO over Ωsuch that Σ2

Σ3|Σ1 holds. Let A L(Σ1 Σ2) such that A KΣ1,Σ3 is consistent. If satisfies (CItpo), then KΣ1,Σ2 A KΣ1,Σ3 |= K A.

Note that full compliance of a (propositional) revision operator with a conditional independence statement modulo formulas in [Lynn et al., 2022] postulates KΣ1,Σ2 A KΣ1,Σ3 K A. This seems to be a bit too strong for iterated revision, as also Example 6 illustrates. Here we have Kκ abc and A = bc, so A KΣ1,Σ3 κ bc ab abc is consistent, and Σ2

κ Σ3|Σ1 and Σ2

κ Σ3|Σ1 imply conditional independence modulo the respective belief sets according to Prop. 3. But Kκ abcd abc, hence we only have KΣ1,Σ2 κ KΣ1,Σ3 κ (abc abc) ab abc |= Kκ , verifying Prop. 7.

6 Conclusion We presented a semantic approach to conditional independence for total preorders which are the basic structure for revision of epistemic states resp. iterated revision according to the AGM and Darwiche-Pearl frameworks [Alchourr on et al., 1985; Darwiche and Pearl, 1997]. We showed that this concept of conditional independence is compatible to respective notions for purely propositional frameworks, Spohn s ranking functions, and some of Pearl s basic characteristics of conditional independence coming from probabilistics. Moreover, we made precise by axioms what it means for an iterated revision operator to respect conditional independence, both for total preorders and ranking functions, which basically say that conditional independencies should be preserved under revision if the revision input does not violate it. We proposed c-revision operators [Kern-Isberner and Huvermann, 2017] as a proof of concept to satisfy these axioms. Therefore, for the framework of ranking functions, conditional independence in the revised epistemic state can be easily implemented via c-revisions: once we have conditional independence in the prior ranking function, any c-revision (with a suitable input) will preserve it. We also provided a constructive method to build up a prior ranking function from local ranking functions (on subsignatures) that satisfies a conditional independence statement, thereby bringing in ideas of local reasoning. Via the close relationships between total preorders and ranking functions, many of these results can be used for the purely qualitative framework of total preorders. This paper complements the work [Kern-Isberner and Brewka, 2017] that deals with independence over marginalizations, whereas this paper deals with independence over conditionalization. As part of our future work, we plan to elaborate on the construction of total preorders from local ones that are compatible with conditional independence statements, and we will extend our considerations to also include revisions by conditionals. Furthermore, we plan to take advantage of the notion of conditional independence to design efficient networkbased models for iterated revision, and to show how complexity of revision tasks can be reduced effectively in these models.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Acknowledgements The work of Jesse Heyninck was partially supported by Fonds Wetenschappelijk Onderzoek Vlaanderen (project G0B2221N).

References [Alchourr on et al., 1985] C.E. Alchourr on, P. G ardenfors, and D. Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50(2):510 530, 1985. [Beierle and Kern-Isberner, 2012] C. Beierle and G. Kern Isberner. Semantical investigations into nonmonotonic and probabilistic logics. Annals of Mathematics and Artificial Intelligence 65(2-3):123 158, 2012. [Darwiche and Pearl, 1997] A. Darwiche and J. Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89:1 29, 1997. [Darwiche, 1997] Adnan Darwiche. A logical notion of conditional independence: Properties and application. Artif. Intell., 97(1-2):45 82, 1997. [Delgrande, 2017] James P. Delgrande. A knowledge level account of forgetting. J. Artif. Intell. Res., 60:1165 1213, 2017. [Katsuno and Mendelzon, 1991] H. Katsuno and A. Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52:263 294, 1991. [Kern-Isberner and Brewka, 2017] Gabriele Kern-Isberner and Gerhard Brewka. Strong syntax splitting for iterated belief revision. In C. Sierra, editor, Proceedings International Joint Conference on Artificial Intelligence, IJCAI 2017, pages 1131 1137. ijcai.org, 2017. [Kern-Isberner and Huvermann, 2017] Gabriele Kern Isberner and Daniela Huvermann. What kind of independence do we need for multiple iterated belief change? J. Applied Logic, 22:91 119, 2017. [Lang and Marquis, 1998] J erˆome Lang and Pierre Marquis. Complexity results for independence and definability in propositional logic. In Anthony G. Cohn, Lenhart K. Schubert, and Stuart C. Shapiro, editors, Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR 98), Trento, Italy, June 2-5, 1998, pages 356 367. Morgan Kaufmann, 1998. [Lang et al., 2002] J erˆome Lang, Paolo Liberatore, and Pierre Marquis. Conditional independence in propositional logic. Artif. Intell., 141(1/2):79 121, 2002. [Lynn et al., 2022] Matthew J. Lynn, James P. Delgrande, and Pavlos Peppas. Using conditional independence for belief revision. In Proceedings AAAI-22, 2022. [Pearl and Paz, 1985] Judea Pearl and Azaria Paz. Graphoids: A graph-based logic for reasoning about relevance relations. University of California (Los Angeles). Computer Science Department, 1985. [Pearl, 1988] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, Ca., 1988.

[Spohn, 1988] W. Spohn. Ordinal conditional functions: a dynamic theory of epistemic states. In W.L. Harper and B. Skyrms, editors, Causation in Decision, Belief Change, and Statistics, II, pages 105 134. Kluwer Academic Publishers, 1988. [Spohn, 2012] Wolfgang Spohn. The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford University Press, 2012.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)