# using_conditional_independence_for_belief_revision__897d16a3.pdf

Using Conditional Independence for Belief Revision

Matthew James Lynn,1 James P. Delgrande,1 Pavlos Peppas2

1Simon Fraser University, Canada 2University of Patras, Greece mlynn@cs.sfu.ca, jim@cs.sfu.ca, pavlos@upatras.gr

We present an approach to incorporating qualitative assertions of conditional irrelevance into belief revision, in order to address the limitations of existing work which considers only unconditional irrelevance. These assertions serve to enforce the requirement of minimal change to existing beliefs, while also suggesting a route to reducing the computational cost of belief revision by excluding irrelevant beliefs from consideration. In our approach, a knowledge engineer specifies a collection of multivalued dependencies that encode domain-dependent assertions of conditional irrelevance in the knowledge base. We consider these as capturing properties of the underlying domain which should be taken into account during belief revision. We introduce two related notions of what it means for a multivalued dependency to be taken into account by a belief revision operator: partial and full compliance. We provide characterisations of partially and fully compliant belief revision operators in terms of semantic conditions on their associated faithful rankings. Using these characterisations, we show that the constraints for partially and fully compliant belief revision operators are compatible with the AGM postulates. Finally, we compare our approach to existing work on unconditional irrelevance in belief revision.

1 Introduction

Belief revision is concerned with the situation in which an agent is confronted with a new fact to incorporate into its belief set. If the new fact is inconsistent with the current belief set, the challenge is to revise these beliefs so that as many of the current beliefs as possible are retained while incorporating the new fact and maintaining consistency. This process is formalised as a belief revision operator which takes a current knowledge base K and a formula for revision φ and produces a revised knowledge base K φ. In order to formalise the requirement that revision should result in a minimal change to existing beliefs, a number of authors have turned to irrelevance, suggesting that those beliefs irrelevant to the formula for revision should remain unchanged (Gardenfors 1990). This also has the potential advantage of opening a pathway to more efficient belief revision operators, by being able to exclude irrelevant beliefs from the revision process. However, so far, these notions of

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

irrelevance have been extremely strict, considering beliefs as irrelevant only when there is no connection, however indirect, between them. To see the issue, consider the following situation: an agent is informed that refrigerators require power, power is generated in the local area by wind turbines, and wind turbines kill birds. It would seem that information about birds would be independent of information concerning refrigerators; however, this is not the case, given the link between refrigerators and birds mediated by wind turbines. Consequently, existing approaches would consider refrigerators relevant to birds. However, when revising our beliefs about birds there would seem to be no reason for our beliefs about refrigerators to change. Hence, it seems we need a more nuanced and less restrictive notion of irrelevance. This situation has a parallel in probability theory. In practice, random variables are rarely independent. However, they are frequently conditionally independent. As a result, Bayesian networks have been developed to exploit conditional independence properties, thereby overcoming the otherwise seemingly-intractable complexity of probabilistic inference (Pearl 2014). In this paper we take a suitable analogue of conditional independence for determining which beliefs may be considered irrelevant to others in a given context. We then apply this notion to belief revision, and we study those revision operators which comply with this formulation of conditional independence. Our approach is given in terms of the Katsuno-Mendelzon approach for belief revision. In our approach, we assume that conditional independence is a property of the underlying domain, and we consequently assume that a knowledge engineer has provided a collection of such conditional independence assertions. These assertions can then be taken into account in the belief revision process. To this end, we study two related notions of what it means for a belief revision operator to take into account conditional independencies. We provide postulates that characterise conditional independence in revision, and which generalise previous approaches to (non-conditional, absolute) independence. Furthermore, we provide representation results, giving conditions on faithful rankings which correspond to the sets of postulates characterising conditional independence in revision. The next section covers background material: we first

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

present useful definitions and notation, after which we give background material on belief revision, including existing approaches to independence in belief revision, along with conceptions of conditional independence in logic. Section 3 shows that multivalued dependencies can be used to represent background knowledge of conditional irrelevance, and introduces the classes of partially compliant and fully compliant belief revision operators which take these into account. In Section 4 we provide representation results for partially and fully compliant belief revision operators in terms of semantic conditions on faithful rankings. Finally, Section 5 discusses related work, and future work, after which we have a brief conclusion.

2 Background Material 2.1 Preliminaries and Notation Let V = {p, q, r, . . . } be a finite set of propositional variables, arbitrary subsets of which are denoted by X, Y , and Z. We sometimes juxtapose these subsets to represent unions, e.g. XY = X Y . The relative complement V X will be denoted by X. Every subset X of V induces a propositional language L(X) consisting of formulae constructed from the elements of X by applying the propositional connectives , , , and . We write L for the entire propositional language L(V ). Lower case Greek letters φ, ψ, γ, . . . will be used to range over formulae in a propositional language, with K playing a special role of a formula thought of as representing the knowledge base of an agent. Also associated to every subset X of V is the set ΩX of functions v : X {T, F} referred to as models or possible worlds over X. We will freely think of these possible worlds as either these functions, or as conjunctions of the literals satisfied by them. Hence, for us, {x 7 T, y 7 F} is the same thing as x y. Given a possible word u over V alongside a subset X of V , we write u X for the reduct of u to a possible world over X, that is the unique function u X : X {T, F} agreeing with u on X. When φ is a formula we write [φ] for the set of models over V satisfying φ, so that [φ] ΩV . We write φ ψ to indicate [φ] [ψ], and φ ψ to indicate [φ] = [ψ]. We write V (φ) for the minimal set of propositional variables for which there exists a formula ψ logically equivalent to φ containing only occurrences of variables in V (φ), for instance V (q (p p)) = {q}.

2.2 Projections of a Propositional Formula In order to speak about components of a knowledge base K expressed in various subvocabularies we will introduce the following analogue of the projection operator from the relational algebra (Abiteboul, Hull, and Vianu 1995). Definition 2.1. If φ is a propositional formula, and X V , then the projection φX of φ onto X is defined up to logical equivalence as the formula φX such that [φX] = {u ΩV | v [φ], v X = u X}. Example 2.1. The projection of (p q) (q r) onto {p, q} is (p q), whereas the projection of (p q) (q r) onto {q, r} is (q r).

Regarding a set of possible worlds as tuples in a relation, it follows that φX defines the set of worlds resulting from projecting this relation onto the attributes in X, then taking the Cartesian product of this with all possible interpretations of the remaining variables. This operator also appears as the notion of a uniform interpolant, a model-theoretic reduct (Hodges 1993), or as the dual of a forgetting operator1 (Delgrande 2017). For our purposes, we will rely on the following property of projections: Theorem 2.1. If φ ψ and V (ψ) X then φ φX and φX ψ.

2.3 Revision Operators and Faithful Rankings A belief revision operator, as formalised by Alchourron, G ardenfors, and Makinson (1985), is a binary function which maps a belief set K and a formula φ and produces a revised belief set K φ in a manner satisfying the AGM postulates. These postulates attempt to capture the requirement that K φ must include φ alongside as many beliefs from K as possible, while maintaining consistency. In other words, K φ results from a minimal change to the existing belief set K which results in φ being believed. Note that belief revision captures an agent revising its beliefs about the present state of affairs, whereas updating its beliefs when the state of the world changes is the subject of belief update operators, cf. (Katsuno and Mendelzon 1991a) or (Peppas 2008). In our setting of a finite vocabulary, we can simplify matters by working instead with the Katsuno-Mendelzon approach wherein the belief sets K and K φ are represented as single formulas, and the AGM postulates are rephrased in the following manner (Katsuno and Mendelzon 1991b). Definition 2.2. A binary function : L L L is a belief revision operator if it satisfies the following Katsuno Mendelzon postulates: R1. K ψ ψ; R2. If K φ is satisfiable then K φ K φ; R3. If φ is satisfiable then K φ is satisfiable; R4. If K1 K2 and φ1 φ2 then K1 φ1 K2 φ2; R5. (K φ) ψ K (φ ψ); R6. If (K φ) ψ is satisfiable then K (φ ψ) (K φ) ψ. It is worthwhile noting that some authors only require a belief revision operator to satisfy the basic postulates (R1) through to (R4), and refer to (R5) and (R6) as the supplementary postulates. Katsuno and Mendelzon (1991b) show that belief revision operators satisfying (R1) through to (R6) can be characterised as determining K φ by selecting those worlds in [φ] which are minimally implausible with respect to a ranking on worlds. To this end, they introduce binary relations K on worlds referred to as faithful rankings wherein u K v means that v is at least as implausible as u from the perspective of an agent knowing only K. Definition 2.3. A faithful ranking for K is a binary relation K on possible worlds which satisfies the following properties:

1In the sense that φY forget(φ, V Y ).

1. w K w and w K w implies w K w . 2. Either w K w or w K w. 3. w K w for all w if and only if w |= K. A family of faithful rankings { K}K such that K1 K2 implies K1 = K2 is called a faithful assignment. If W is a set of possible worlds and is a faithful ranking, we write min(W, ) for the set of worlds in W which are minimal under . That is to say, x min(W, ) if and only if x W and x y for all y W. Theorem 2.2 (Katsuno and Mendelzon, 1991b). A binary function : L L L is a belief revision operator if and only if there exists a faithful assignment { K}K where for every K it follows that [K φ] = min([φ], K).

2.4 Relevance in Belief Revision Although the general consensus is that a belief revision operator must satisfy the KM postulates, these postulates place few constraints on the behaviour of belief revision operators. For instance, they fail to rule out the belief revision operator defined by setting K φ = K φ if K φ is consistent and K φ = φ otherwise2. This is in tension with the objective of belief revision to preserve as many of the original beliefs as possible. In (Parikh 1999) the issue of minimal change is addressed via considering an additional postulate asserting that whenever the knowledge base is divisible into two unrelated components, then revision by a formula pertaining to only one of those components should leave the other component unchanged. For a KM belief revision operator , Parikh s postulate can be expressed as follows:

P If K K1 K2 where V (K1) X1, V (K2) X2, X1 X2 = , and φ is such that V (φ) X1 then

K φ (K1 φ) K2

where is a belief revision operator for the language X1.

The statement of Parikh s postulate admits a weak reading wherein varies as a function of K, as well as a strong reading wherein is fixed. In order to clarify this situation, Peppas et al. (2004) introduced the postulate (P1) corresponding to the weak reading of (P), and the postulate (P2) which in combination with (P1) corresponds to the strong reading of (P). We state these as follows in the KM setting:

P1. If V (K1) V (K2) = and V (φ) V (K1) then

((K1 K2) φ)V (K2) K2.

P2. If V (K1) V (K2) = and V (φ) V (K1) then

((K1 K2) φ)V (K1) (K1 φ)V (K1).

If we interpret a syntax-splitting K K1 K2 with V (K1) V (K2) = as meaning that the beliefs represented by K1 and K2 are irrelevant, then we obtain the following intuitive readings for (P1) and (P2). The postulate (P1) requires that when revising K by a formula φ whose vocabulary is disjoint from K2, then only the part of K relevant to

2Consider the rankings K where u K v for all u, v [K].

φ may be modified during revision, and hence K2 is left unchanged. The postulate (P2) further requires that K2 cannot influence the changes made to K1 in any way. Parikh (1999) only shows Parikh s postulate is consistent with the basic postulates for belief revision. Using these clarified postulates, Peppas et al. (2015) develop a characterisation of those belief operators satisfying (P1) and (P2), and show that Dalal s belief revision operator satisfies both the basic and supplementary KM postulates as well as (P1) and (P2). Subsequent work has extended these results to epistemic states (Kern-Isberner and Brewka 2017), to belief contraction operators (Haldimann, Kern-Isberner, and Beierle 2020), to epistemic entrenchments and selection functions (Aravanis, Peppas, and Williams 2019), and to preferential entailment relations (Kern-Isberner, Beierle, and Brewka 2020). Rather than considering belief revision operators that satisfy (P1), Delgrande and Peppas (2018) consider belief revision operators which satisfy an analogue of Parikh s postulate for only certain theories and a subset of possible syntax splittings. The idea is that the knowledge engineer will specify a number of irrelevance assertions, which are expressions of the form σ Y 3 which intuitively state that whenever a knowledge base entails the formula σ then beliefs over Y must be treated as irrelevant to beliefs over Y , and belief revision operators will be required to comply with these assertions in the following sense: Definition 2.4. A belief revision operator complies with σ Y at K when either K σ or for every consistent φ with V (φ) Y the following postulate is satisfied: R If K φ then K φ (K φ)Y KY . For a belief revision operator induced from a faithful assignment { K}K, Delgrande and Peppas (2018) show that complying with σ Y is equivalent to stating that, for every K entailing σ, the following postulates are satisfied: S1. If u Y = v Y , K u Y , and KY u then u K v; S2. If u Y = v Y , K u Y , KY u, and KY v then u <K v;

2.5 Conditional Independence Parikh s postulate, and the majority of approaches descending from it, suffers from the limitation that the knowledge base must be able to be split into disjoint components in order for the postulate to apply. This limitation is already noted in (Chopra and Parikh 2000) which attempts to overcome this limitation by introducing the notion of a belief structure, which splits a knowledge base into a number of compartments which may overlap in vocabulary. However this compartmentalisation is fixed which can lead to information being lost. This situation has an analogue in probability theory, where unconditional independence is a powerful but rarely applicable assumption. Rather, it is conditional independence which arises most frequently, and in fact has become

3For the reader familiar with multivalued dependencies, the similarity of this notation was a deliberate choice in (Delgrande and Peppas 2018).

a central component of modern probabilistic modelling and inference. Inspired by probability theory, Darwiche (1997) introduces a notion of conditional logical independence together with a number of equivalent characterisations tailored for different reasoning problems. We will adopt the following definition, adapted from (Lang and Marquis 1998) and (Lang, Liberatore, and Marquis 2002).

Definition 2.5. If X, Y1, and Y2 are pairwise disjoint subsets of V and K is a propositional formula over V then Y1 and Y2 are conditionally independent given X modulo K when for any world u and formulae φ1 and φ2 with V (φ1) Y1 and V (φ2) Y2 such that K u X φ1 φ2 either K u X φ1 or K u X φ2.

Example 2.2. The sets {p} and {r} are conditionally independent given {q} modulo K := (p q) (q r). This follows from Lemma 3.1 below. To verify this for a specific case, let u be an arbitrary possible world and consider that K u{q} p r. Either u(q) = F in which case K u{q} p, or u(q) = T in which case K u{q} r, as required.

Taking inspiration instead from database theory, we can regard the worlds satisfying a propositional formula K as constituting a database table wherein the attributes are the propositional variables in V . Then, we may consider the notion of a multivalued dependency:

Definition 2.6. A propositional formula K satisfies the multivalued dependency X Y if and only if

Example 2.3. The formula K = (p q) (q r) (q r s) satisfies the multivalued dependencies {q} {p} and {q} {r, s}.

In the next section we show that multivalued dependencies, Darwiche s conditional logical independence, and Parikh s syntax-splittings are deeply interconnected.

3 Compliance with Multivalued Dependencies Delgrande and Peppas (2018) point out that Parikh s (1999) approach has a number of drawbacks: it assumes that irrelevance is completely determined by the current beliefs of an agent, it assumes that every syntax-splitting must be taken into account during belief revision, and it assumes that beliefs must be expressed over disjoint vocabularies in order to qualify as irrelevant. They argue that irrelevance is a domain-dependent phenomena, and represent this knowledge of the domain as a collection of irrelevance assertions which a belief revision operator is then required to comply with. This addresses the first and second drawback, but it leaves the issue of Parikh s original postulate considering only unconditional independence, which is an unrealistically strong condition to expect to hold often. Consider even a seemingly clear situation, such as a knowledge base containing knowledge about birds and knowledge about refrigerators. These topics would seem to

be independent. However, suppose we have that refrigerators require power, power is generated in the local area by wind turbines, and wind turbines often kill birds. Now, the ability to split the knowledge base is gone. However, we can observe that if the only link between birds and refrigerators passes through the language of wind turbines, then when revising knowledge about birds, our knowledge concerning refrigerators is not impacted, provided that our knowledge of wind turbines is unaffected. In our approach, the knowledge engineer will represent their understanding of conditional irrelevance between components of the knowledge base as a collection of multivalued dependencies. The intuitive interpretation being that a multivalued dependency X Y is satisfied when the only connections between knowledge over Y and knowledge over Y pass through X. In other words, were an agent given complete information about X, its beliefs about Y and Y would be independent. In our example scenario, knowledge about turbines comprises the only connection between birds and refrigerators, so the knowledge engineer would represent this via the multivalued dependencies Turbine V ocabulary Bird V ocabulary and Turbine V ocabulary Refrigerator V ocabulary. When a knowledge base K satisfies X Y , it follows that K KXY KY . In the case X = , the equivalence K KXY KY amounts to a syntax-splitting as used by (Parikh 1999). Using Craig s (1957) Interpolation Theorem, we can show the following equivalence between multivalued dependencies, Darwiche s logical conditional independence, and a generalisation of Parikh s syntax-splittings. Lemma 3.1 (Splitting Criterion). If Y1, Y2, and X are pairwise disjoint sets of propositional variables then for any propositional formulae K1 and K2 such that V (K1) Y1X and V (K2) Y2X it follows that Y1 and Y2 are independent given X modulo K1 K2.

Proof Sketch. Using K1 K2 u X φ1 φ2 derive K1 u X φ1 φ2 K2 u X. Apply Craig s Interpolation Theorem to get an interpolant over X, and observe u X must satisfy the interpolant or its negation.

The Splitting Criterion can be regarded as a special case of Darwiche s results on structured databases, which are graphs similar to Bayesian networks whose vertices are labelled by components of a knowledge base in such a way that conditional independencies may be read directly off the graph itself (Darwiche 1997; Darwiche and Pearl 1994). Lemma 3.2 (Projection Criterion). Given a propositional formula K and disjoint sets Y1, Y2, and X of propositional variables, it follows that Y1 and Y2 are independent given X modulo K if and only if KY1X KY2X KY1Y2X holds. Combining the Splitting and Projection Criteria, we arrive at the following result: Theorem 3.1. If X and Y are disjoint subsets of V and K is a propositional formula, then the following are equivalent: 1. There exists K1 and K2 with V (K1) XY and V (K2) Y such that K K1 K2. 2. K satisfies X Y . 3. Y and V (XY ) are independent given X modulo K.

3.1 Partially Compliant Operators

Once a knowledge engineer has gathered a collection of multivalued dependencies to capture the conditional irrelevance properties of the domain, these are incorporated into the belief revision process by requiring that a belief revision operator comply with each of the multivalued dependencies. We introduce two notions of compliance, the first of which is partial compliance:

Definition 3.1. If X and Y are disjoint subsets of V then a belief revision operator partially complies with X Y if the following postulate holds:

PCR. If K is consistent and satisfies X Y , V (φ) Y , and φ is consistent then

K φ (K φ)XY KY .

In other words, any belief revision operator partially complying with X Y must, when revising a knowledge base satisfying X Y by a consistent formula over Y , leave the Y component of the knowledge base unchanged. Returning to our example, supposing our knowledge base K satisfies Turbine V ocabulary Bird V ocabulary and we revise by some formula φ in the bird vocabulary, we would have that knowledge over Bird V ocabulary is preserved. In particular, as Refrigerator V ocabulary Bird V ocabulary, our beliefs concerning the relationship between turbines and refrigerators could not be changed during revision by any formula φ only referring to birds. As an immediate corollary of the Splitting Criterion, it follows that a belief revision operator partially complying with X Y must preserve the satisfaction of X Y when revising by a consistent formula over Y .

Theorem 3.2. If is a belief revision operator which partially complies with X Y , K satisfies X Y , and V (φ) Y then K φ satisfies X Y .

3.2 Fully Compliant Operators

Consider again an agent aware of wind turbines killing birds, and powering refrigerators, but with no knowledge directly linking birds and refrigerators. Suppose that this agent is given the new fact that birds have evolved a fear response to wind turbines, and are consequently no longer being killed by them. Revising by this new fact using a belief revision operator which partially complies with Turbine V ocabulary Bird V ocabulary may result in changes to the agent s beliefs about refrigerators, as the postulate (PCR) does not constrain belief revision by formulae involving Turbine V ocabulary. However, since the new knowledge is consistent with the fact that turbines power refrigerators, it seems that there is no reason why knowledge about refrigerators should be changed. This motivates us to consider a stronger notion of compliance which constrains revision by knowledge involving the shared vocabulary about wind turbines.

Definition 3.2. If X and Y are disjoint subsets of V then a belief revision operator fully complies with X Y if the following postulate holds:

CR. If K is consistent and satisfies X Y , V (φ) XY , and φ KY is consistent then

K φ (K φ)XY KY .

In other words, any belief revision operator fully complying with X Y must, when revising a knowledge base satisfying X Y by a formula over XY which is consistent with the Y component of the knowledge, leave the Y component of the knowledge base unchanged. With our running example, the belief that birds evade wind turbine is expressed over Bird V ocabulary Turbine V ocabulary, and consistent with the agent s beliefs over Bird V ocabulary, and thus revising by this new belief using a belief revision operator which fully complies with Turbine V ocabulary Bird V ocabulary will result in the beliefs about refrigerators being left unchanged. It follows from the Splitting Criterion that a belief revision operator fully complying with X Y must preserve the satisfaction of X Y in appropriate circumstances: Theorem 3.3. If is a belief revision operator which fully complies with X Y , K satisfies X Y , V (φ) XY , and φ KY is consistent then K φ satisfies X Y . Requiring that a belief revision operator fully comply with X Y is stronger than requiring that it partially comply with X Y , for the reason that (CR) applies to a broader class of formulae. Consequently, we obtain the following relationship between full and partial compliance: Theorem 3.4. If X and Y are disjoint subsets of V and is a belief revision operator which fully complies with X Y , then partially complies with X Y .

3.3 Sources of Multivalued Dependencies Our approach assumes that a knowledge engineer has specified a collection of multivalued dependencies as part of the domain knowledge, rather than these multivalued dependencies being automatically extracted from the initial knowledge base. This avoids requiring that a belief revision operator comply with spurious multivalued dependencies which just happen to hold. This also avoids the cost of having to determine all potential satisfied multivalued dependencies prior to revision, which is particularly important as checking whether a single multivalued dependency holds is known to be in Πp 2 (Lang, Liberatore, and Marquis 2002). This raises the question of how a knowledge engineer should select an appropriate collection of multivalued dependencies. This question, in the analogous setting of irrelevance assertions, is discussed in (Delgrande and Peppas 2018) which suggests a number of possible sources: knowledge about the domain (e.g. birds and refrigerators are unrelated), a causal theory, a Bayesian network, or some structural features of a knowledge base which the knowledge engineer deems essential. In our setting, we can make this a bit more precise. Using the notion of a symbolic causal network introduced by Darwiche and Pearl (1994), it follows from (Darwiche 1997) that conditional independence properties can be read off directly from these networks just as they are for Bayesian networks in probability theory (Pearl 2014). Any multivalued

dependency obtained by this method will be non-spurious since it would arise from the causal structure of the domain, as given in the causal network. We believe further investigation of revision operators which comply with the entire structure of a symbolic causal network is worthwhile.

4 Representation via Faithful Rankings

Belief revision operators which partially, or fully, comply with a multivalued dependency can be characterised semantically in terms of conditions on their corresponding faithful rankings. Using these characterisations, we can construct compliant belief revision operators, and gain insight into the epistemic aspect of compliance.

4.1 Partially Compliant Revision Operators

Belief revision operators which partially comply which a multivalued dependency X Y can be represented via faithful assignments which partially respect X Y in the following sense:

Definition 4.1. A faithful assignment { K}K partially respects X Y if for every K either K does not satisfy X Y or K satisfies the following conditions:

PCS1. If u XY = v XY , K u Y , u [KY ], and v <K u then there exists w such that w Y = u Y and w <K v. PCS2. If KY v then there exists a world u [KY ] such that u Y = v Y and u <K v.

Condition (PCS1) states that when worlds u and v with u XY = v XY are ruled out by K on the basis of u Y , yet u is consistent with KY , then either u is at least as plausible as v or there is some world w with w Y = u Y strictly more plausible than both u and v. Condition (PCS2) further states that a possible world v inconsistent with KY is always less plausible than some possible world u satisfying KY , and furthermore such a u may be obtained from v by modifying only the variables in Y . This has the important consequence that whenever v is minimal in [v Y ] then v [KY ].

Theorem 4.1. If is a belief revision operator which partially complies with X Y , then there exists a faithful assignment { K}K which partially respects X Y , such that [K φ] = min([φ], K) for all K and φ.

Proof Sketch. Choose any faithful ranking via Theorem 2.2. Verify (PCS1) by considering K u Y , and (PCS2) by considering K v Y .

Theorem 4.2. If { K}K is a faithful assignment which partially respects X Y , then the binary function defined by [K φ] = min([φ], K) is a belief revision operator which partially complies with X Y .

Proof Sketch. Show (K φ)XY KY K φ using (PCS1), and K φ (K φ)XY KY using (PCS2).

4.2 Fully Compliant Revision Operators As with (PCR), the postulate (CR) can be characterised in terms of conditions (CS1), (CS2), and (CS3) on faithful rankings. The stronger nature of (CR) will result in (CS1) and (CS2) appearing much closer to the original conditions (S1) and (S2) introduced in (Delgrande and Peppas 2018).

Definition 4.2. A faithful assignment { K}K fully respects X Y if for every K either K does not satisfy X Y or K satisfies the following conditions:

CS1. If u XY = v XY , K u XY , and KY u then u K v. CS2. If u XY = v XY , K u XY , KY u, and KY v then u <K v. CS3. If K u XY , K v XY , and KY u XY and KY v XY then there exists w with w XY = u XY and w <K v.

Conditions (CS1) and (CS2) together state that for possible worlds u such that K u XY it follows that u is minimally implausible among those worlds in [u XY ] if and only if u [KY ]. Condition (CS3) is rather involved, but under the assumption of (CS1) it can be shown to be equivalent to the following (CS3 ) which states minimally implausible worlds consistent with KY are always strictly preferred to worlds inconsistent with KX:

Theorem 4.3. Assuming (CS1) holds, condition (CS3) is equivalent to the following (CS3 ) condition:

CS3 If u [KY ] and v [KX] then u <K v.

Demonstrating that a belief revision operator fully complying with X Y results in the conditions (CS1), (CS2), and (CS3) being satisfied for the corresponding faithful rankings proceeds along lines strongly reminiscent to Theorem 2 of (Delgrande and Peppas 2018).

Theorem 4.4. If is a belief revision operator which fully complies with X Y , then there exists a faithful assignment { K}K which fully respects X Y such that [K φ] = min([φ], K) for all K and φ.

Proof Sketch. Choose any faithful ranking via Theorem 2.2. Verify (CS1) and (CS2) by considering K u XY , and (CS3) by considering K (u XY v XY ).

Theorem 4.5. If { K}K is a faithful assignment which fully respects X Y , then the binary function defined by [K φ] = min([φ], K) is a belief revision operator which fully complies with X Y .

Proof Sketch. Show (K φ)XY KY K φ using (CS1), and show K φ (K φ)XY KY using (CS2) and (CS3).

4.3 Existence of Fully Compliant Operators Using these representation results, we can demonstrate that partial and full compliance with X Y is compatible with the postulates for belief revision. As full compliance entails partial compliance, it suffices to show that for any multivalued dependency X Y there exists a belief revision operator which fully complies with X Y .

Theorem 4.6. If X and Y are disjoint then there exists a belief revision operator which fully complies with X Y .

Proof Sketch. Intuitively, given a multivalued dependency X Y one may construct a faithful assignment { K}K such that each ranking K arranges the worlds into three levels: the lowest level consisting of worlds satisfying K, the second level consisting of worlds satisfying KY but not K, and the third level consisting of worlds not satisfying KY . It follows that (CS1), (CS2), and (CS3) are satisfied by any such faithful ranking, and therefore the corresponding belief revision operator satisfies the AGM postulates and is fully compliant with X Y .

5 Discussion 5.1 Related Work The approach of (Delgrande and Peppas 2018) is closest to our work, which raises the question of whether the independence assertions studied there are related to the conditional independence assertions considered here. Clearly our multivalued dependencies have no mechanism for encoding the selective behaviour of the condition σ in an assertion σ Z unless σ is tautologous, in which case it becomes equivalent to the multivalued dependency Z. In the reverse direction, suppose a multivalued dependency X Y were encoded via an independence assertion σ Z. There are two natural-appearing approaches to consider: 1. If Z = Y then when revising K with K σ by φ with V (φ) Z = Y it would follow that K φ (K φ)Y KY . Hence, we would have K φ satisfies Y . This is far too strong, for this means that all beliefs relating X and Y have been lost in the revision process, whereas we know that (PCR) and (CR) would result in them having been preserved. 2. If Z = XY then when revising K with K σ by φ with V (φ) Z = XY it would follow that K φ (K φ)XY KXY . Hence, we would have K φ satisfies XY . This is again far too strong, for this means that all beliefs relating X and Y have been lost in the revision process, whereas we know that (PCR) and (CR) would result in them having been preserved. Neither of these are tenable, which suggests that conditional independence assertions cannot in general simulate the multivalued dependencies we consider in this work.

5.2 Future Work There are a number of opportunities for future work deriving from the above. One immediate observation is that although we demonstrate the classes of operators partially complying, or fully complying, with an arbitrary multivalued dependency are non-empty, we have not demonstrated that any reasonable-looking, natural belief revision operator reside within these classes. Hence, the question remains of finding interesting belief revision operators which satisfy our postulates. Another line of inquiry would be to ask how we can take advantage of partial or full compliance to reduce the

computational cost of belief revision. One possibility is to develop efficient representations for rankings analogous to Bayesian networks for probability distributions (Pearl 2014) or ranking functions (Spohn 2012), which use the ranking conditions (CS1), (CS2), and (CS3) to factor a ranking into smaller components. When a knowledge engineer specifies that a belief revision operator must comply with a large number of multivalued dependencies, the question of determining which multivalued dependencies constrain the operator in computing K φ becomes challenging: determining whether K satisfies X Y is shown to be co NP-complete in (Lang and Marquis 1998). This suggests that it would be valuable to adopt a special representation such as the symbolic causal networks introduced in (Darwiche and Pearl 1994), the structured databases of (Darwiche 1997), or perhaps an analogue of the B-structures in (Chopra and Parikh 2000). Investigating alternative notions of independence, such as the pathrelevance from (Makinson 2009), or the conditional independence for ranking functions in (Spohn 2012), also might reduce this cost. Finally, it would be interesting to investigate whether these postulates can be extended to nonmonotonic logics in a manner analogous to the extension of Parikh s syntax splitting paradigm in (Kern-Isberner, Beierle, and Brewka 2020).

6 Conclusion

The central challenge of belief revision is to efficiently and plausibly restore consistency to a knowledge base after incorporating a contradictory proposition, and in a manner which causes only minimal changes to existing beliefs. With the standard postulates for belief revision failing to rule out rather pathologically-destructive or bizarre operators, the problem of formalising this requirement of minimality remains an ongoing challenge. We believe that enforcing the requirement that irrelevant beliefs are unchanged is an important aspect of minimal change. In this work we have extended the previous work on unconditional independence in belief revision to accommodate conditional independence in the form of multivalued dependencies. We have introduced two notions by which a belief revision operator may comply with a multivalued dependency, and characterised these postulates in terms of conditions on faithful rankings. Further, we have endorsed the perspective of (Delgrande and Peppas 2018) that conditional independencies should be provided by the knowledge engineer, rather than read off of the knowledge base. This both avoids enforcing spurious conditional independencies, and means that our operators are not required to carry out the expensive task of checking for conditional independence themselves. Our hope is that these postulates will assist in identifying those belief revision operators which can be truly said to result in minimal changes to existing beliefs, and that these operators will admit computationally efficient implementations by merit of being able to limit the amount of work required to perform revisions.

Acknowledgements

We would like to thank our reviewers for their insightful comments, as well as the Natural Sciences and Engineering Research Council of Canada for financial support.

Abiteboul, S.; Hull, R.; and Vianu, V. 1995. Foundations of Databases, volume 8. Addison-Wesley Reading. Alchourr on, C. E.; G ardenfors, P.; and Makinson, D. 1985. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. Journal of Symbolic Logic, 510 530. Aravanis, T.; Peppas, P.; and Williams, M.-A. 2019. Full Characterization of Parikh s Relevance-Sensitive Axiom for Belief Revision. Journal of Artificial Intelligence Research, 66: 765 792. Chopra, S.; and Parikh, R. 2000. Relevance sensitive belief structures. Annals of Mathematics and Artificial Intelligence, 28(1): 259 285. Craig, W. 1957. Three uses of the Herbrand-Gentzen Theorem in Relating Model Theory and Proof Theory. The Journal of Symbolic Logic, 22(3): 269 285. Darwiche, A. 1997. A Logical Notion of Conditional Independence: Properties and Applications. Artificial Intelligence, 97(1-2): 45 82. Darwiche, A.; and Pearl, J. 1994. Symbolic Causal Networks. In AAAI, 238 244. Delgrande, J.; and Peppas, P. 2018. Incorporating Relevance in Epistemic States in Belief Revision. In International Conference on Principles of Knowledge Representation and Reasoning. Delgrande, J. P. 2017. A Knowledge Level Account of Forgetting. Journal of Artificial Intelligence Research, 60: 1165 1213. Gardenfors, P. 1990. Belief Revision and Relevance. In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, 349 365. Philosophy of Science Association. Haldimann, J. P.; Kern-Isberner, G.; and Beierle, C. 2020. Syntax Splitting for Iterated Contractions. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 17, 465 475. Hodges, W. 1993. Model Theory. Cambridge University Press. Katsuno, H.; and Mendelzon, A. O. 1991a. On the Difference between Updating a Knowledge Base and Revising It. In Allen, J. F.; Fikes, R.; and Sandewall, E., eds., Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR 91). Cambridge, MA, USA, April 22-25, 1991, 387 394. Morgan Kaufmann. Katsuno, H.; and Mendelzon, A. O. 1991b. Propositional Knowledge Base Revision and Minimal Change. Artificial Intelligence, 52: 263 294.

Kern-Isberner, G.; Beierle, C.; and Brewka, G. 2020. Syntax Splitting= Relevance+ Independence: New Postulates for Nonmonotonic Reasoning from Conditional Belief Bases. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 17, 560 571. Kern-Isberner, G.; and Brewka, G. 2017. Strong Syntax Splitting for Iterated Belief Revision. In IJCAI, 1131 1137. Lang, J.; Liberatore, P.; and Marquis, P. 2002. Conditional Independence in Propositional Logic. Artificial Intelligence, 141(1-2): 79 121. Lang, J.; and Marquis, P. 1998. Complexity Results for Independence and Definability. In Proc. the 6th International Conference on Knowledge Representation and Reasoning, 356 367. Makinson, D. 2009. Propositional relevance through lettersharing. J. Appl. Log., 7(4): 377 387. Parikh, R. 1999. Beliefs, Belief Revision, and Splitting Languages. Logic, Language and Computation, 2(96): 266 268. Pearl, J. 2014. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Elsevier. Peppas, P. 2008. Belief revision. Foundations of Artificial Intelligence, 3: 317 359. Peppas, P.; Chopra, S.; and Foo, N. Y. 2004. Distance Semantics for Relevance-Sensitive Belief Revision. In Dubois, D.; Welty, C. A.; and Williams, M., eds., Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004), Whistler, Canada, June 2-5, 2004, 319 328. AAAI Press. Peppas, P.; Williams, M.-A.; Chopra, S.; and Foo, N. 2015. Relevance in Belief Revision. Artificial Intelligence, 229: 126 138. Spohn, W. 2012. The Laws of Belief: Ranking Theory and its Philosophical Applications. Oxford University Press.