Preference-Based Inconsistency Management in Multi-Context Systems (Extended Abstract)

1 Introduction

Multi-Context Systems (MCS) are an approach to share information between individual knowledge bases, called emphcontexts, which exchange information using special rules, called bridge rules. The semantics of the whole system then emerges from the local semantics of the constituent knowledge bases. Practical applications of MCS are defeasible reasoning in ambient intelligence [Bikakis and Antoniou, 2010], cooperation in distributed information systems [Caire and Bikakis, 2011], and the METIS system for maritime situation awareness support [Velikova et al., 2014].

MCS are rooted in the work of McCarthy [1993] and enjoyed a rich development (cf. [Giunchiglia and Serafini, 1994; Ghidini and Giunchiglia, 2001; Roelofsen and Serafini, 2005; Brewka et al., 2007; Serafini and Homola, 2012; Bikakis and Antoniou, 2010; Brewka et al., 2011]). For generality, this work is based on MCS with heterogeneous contexts and nonmonotonic information exchange [Brewka and Eiter, 2007].

As the contexts of an MCS are typically autonomous and host knowledge bases that are inherited legacy systems, information exchange may lead to inconsistency; which means

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Eiter and Weinzierl, 2017]. This extended abstract has been supported by the Academy of Finland, project 251170 and the Austrian Science Fund (FWF) project P27730. Initial research was funded byWWTF, grant ICT08-020.

r1: (2 : hyperglycemia) ← (1 : hyperglycemia).

r2: (2 : allow anim insulin) ←not (1 : allergic anim insulin).

r3: (3 : bill anim insulin) ← (2 : give anim insulin).

r4: (3 : bill human insulin) ← (2 : give human insulin).

r5: (3 : insurance B) ← (1 : insurance B).

Figure 1: Hospital MCS M = (C1, C2, C3) and its bridge rules.

that the MCS has no global model (called equilibrium); thus, the whole MCS becomes useless. The notion of diagnosis can be used to repair an inconsistent MCS [Eiter et al., 2010; 2014] and it indicates bridge rules that must be modified in order to restore consistency. But the modified information exchange may have serious consequences.

Example 1. Consider an MCS M employed in a hospital, which interconnects three systems: (1) a patient database with information about illnesses, insurance companies, and potential allergies of patients; (2) an expert system suggesting proper medications for illnesses; and (3) a system billing the insurance company of patients for the administered treatments. The system is shown in Figure 1 together with its bridge rules r1 to r5; for illustration we assume that there is only one patient. Bridge rule r1 states that the medication context C2 knows that the patient has hyperglycemia if the patient database C1 believes so; bridge rule r2 states that C2 is allowed to administer animal insulin if an allergy to animal insulin is not present in the patient database. The other bridge rules inform the billing system C3 about the patient's insurer (r3) and what insulin was administered (r4 and r5). The expert system only recommends treatments to which patients are not allergic to and the billing system only allows administered treatments that are covered by the insurance companies. Suppose now that the patient's illness requires insulin and she/he is allergic to animal insulin. If the insurer of the patient only pays for animal insulin, the only allowed treatment is rejected by the billing system and M is inconsistent. To repair M, consider its set of minimal diagnoses:

D±m(M) = {({r1} , ∅), ({r4} , ∅), ({r5} , ∅), (∅, {r2})}, where ({r1} , ∅) indicates to remove r1, which means the illness of the patient is ignored; ({r4} , ∅) removes r4, hence the (correct) medication is not billed; ({r5} , ∅) ignores the insurer, likely billing it for some medication it will not pay; (∅, {r2}) indicates to make the bridge rule r2 condition-free, i.e., remove all conditions from r2 and by that add the allowance to administer animal insulin although the patient is allergic to it; this may threaten the health of the patient. No diagnosis is clearly the best, and depending on one's preferences one diagnosis may be better than another.

The goal of this work is to develop a machinery for automatic identification of preferred diagnoses and pruning unwanted ones, in order to only require from a human operator to select from a reduced set (of most preferred diagnoses) the best diagnosis manually. What constitutes a preferred or best diagnosis cannot be decided in general since it will be different for each MCS and depends on the environment into which an MCS is embedded. In the above example, the health of patients may be paramount, alternatively billing may be of highest importance from an economic prespective.

Automatic selection of preferred diagnoses according to some preference requires in turn a formalism for expressing and evaluating preferences, like e.g. ceteris paribus preferences [Doyle et al., 1991], CP-nets [Boutilier et al., 2004; Domshlak et al., 2001; Goldsmith et al., 2008], or utility functions [Von Neumann and Morgenstern, 1944]. As there is no one-fits-all preference formalism our approach is based on the idea that a user-customized preference on diagnoses, specified in a formalism chosen by the user, can be seen as a knowledge-base or context of an MCS. We enable such a context to "see" the diagnoses of the MCS and provide extended notions to select the most preferred diagnoses based on the observations and preferences expressed by this context.

This paper gives a quick overview of our main contributions: 1. two basic methods for preference-based selection of diagnoses, 2. a meta-reasoning transformation to enable that a context observes diagnoses applied to an MCS, 3. extended notions of diagnosis for the selection of preferred diagnoses, and 4. computational complexity results on these notions.

2 Preliminaries

To capture all kinds of knowledge-representation formalisms, MCS use the concept of an abstract "logic", which is a triple L = (KB,BS,ACC) where KB is the set of knowledge bases ("inputs"), BS is the set of possible belief sets ("outputs"), and ACC : KB → 2BS is a function assigning each knowledge base a set of acceptable belief sets ("semantics"). This captures classical logic, ontologies, logic programs, etc.

Information exchange is specified using bridge rules, which are similar to rules in logic programming, of form:

Intuitively such a bridge rule reads: if all beliefs p1, . . . , pi are present at contexts c1, . . . , ci, respectively, and beliefs pi+1, . . . , pm are not present at ci+1, . . . , cm, respectively, then the knowledge-base formula s is added to context k.

A Multi-Context System M = (C1, . . . ,Cn) consists of contexts Ci = (Li, kbi, bri), 1 ≤ i ≤ n, where (i) Li = (KBi,BSi,ACCi) is an abstract logic, (ii) kbi ∈ KBi is a knowledge base, and (iii) bri is a set of bridge rules. By br(M) = ⋃ni=1 bri we denote the set of all bridge rules of M. The semantics of an MCS M = (C1, . . . , Cn) is defined over sequences S = (S1, . . . , Sn) of belief sets Si ∈ BSi, 1 ≤ i ≤ n called belief states. A bridge rule r is applicable in S, if for each positive body literal (j : p) holds p ∈ Sj, while for each (negative) not (j : p) holds p /∈ Sj . We denote by (k : s) ← ⊥ and (k : s) ← ⊤ bridge rules that are never and always applicable, respectively. A belief state S of M is an equilibrium if every belief set is locally accepted given applicable bridge rules. EQ(M) denotes the set of all equilibria; M is inconsistent if M has no equilibrium, i.e., EQ(M) = ∅.

For repairing (i.e., diagnosing) an inconsistent MCS, pairs (D1,D2) of sets of bridge rules are considered, such that if we deactivate the rules in D1 and add the rules in D2 in condition-free form, then the MCS admits an equilibrium. Formally, a diagnosis of M is a pair (D1,D2), D1,D2 ⊆ br(M), such that EQ(M[br(M) \ D1 ∪ cf (D2)]) ̸= ∅; D±(M) denotes the set of all diagnoses. A diagnosis indicates which bridge rules are assumed to require modification in order to obtain a consistent MCS, i.e., a diagnosis constitutes a way to repair an MCS. We call a pair D = (D1, D2) ∈ 2br(M) × 2br(M) a candidate diagnosis. By Occam's razor, one may consider preferable diagnoses to be the ones that require the least modifications, i.e., (subset-)minimal diagnoses. For a pairs A = (A1,A2) and B = (B1,B2) we say A ⊂ B iff A1 ⊆ B1, A2 ⊆ B2 and A ̸= B. Then, a diagnosis D ∈ D±(M) is (pointwise) subset minimal, if no D′ ⊂ D is in D±(M). Furthermore, D±m(M) denotes all such D.

3 Preferences

In the literature two forms of preference prevail: (1) filters, which consider a single outcome (i.e., a diagnosis) and discard it if it fails some condition; (2) (binary) preferences, which compare two outcomes and decide which is better. In the spirit of MCS we also want this approach to be open to any kind of formalism for specifying filters or preferences.

A filter can be seen as hard constraints on diagnosis candidates; for generality, a filter basically is a Boolean function.

Definition 1. A diagnosis filter for an MCS M with bridge rules br(M) is a function f : 2br(M) × 2br(M) → {0, 1}, and the set of filtered diagnoses is:

In general, a preference on diagnoses is just a binary order relation; to avoid counter-intuitive results, we require preferences to be transitive. Since virtually every other preference formalism yields an order relation, we introduce it as such.

Definition 2. A preference order over diagnoses for an MCS M is a transitive and reflexive binary relation ⪯ on 2br(M) × 2br(M) ; for D,D′ ∈ 2br(M) × 2br(M) we say that D is preferred to D′ if D ⪯D′ .

Using ⪯ we define what constitutes a most preferred diagnosis. Intuitively, such a diagnosis incurs a minimal set of modifications and no other diagnosis is strictly more preferred. We first introduce ⪯-preferred diagnoses, which are those diagnoses such that no other diagnosis is strictly more preferred. The most preferred diagnoses then are the subsetminimal ones from the set of ⪯-preferred diagnoses.

Definition 3. A diagnosis D ∈ D±(M) of an MCS M is called ⪯-preferred if for all D′ ∈ 2br(M) ×2br(M) with D′ ≺ D it holds that D′ /∈ D±(M). D is minimal ⪯-preferred if D is subset-minimal among all ⪯-preferred diagnoses. The set of all ⪯-preferred diagnoses is denoted by D± ⪯ (M) and the set of all minimal ⪯-preferred by D±m,⪯(M).

We do not require ⪯ to be acyclic and by relying on ≺ (the irreflexive and anti-symmetric version of ⪯) we consider all diagnoses in a cycle to be equally preferred.

4 Meta-Reasoning for Diagnosis

In order to realize filters and preference orders inside an MCS, some context must be able to reason on the diagnoses of the MCS. We achieve this based on the following insights. (A) If the rules of a context, say context Cn+1, are of certain form, it knows exactly whether some rules have been removed or made condition-free by a diagnosis and it can then exhibit this knowledge as beliefs.

Rule (1) is always firing, so if a diagnosis removes it, the knowledge not removedr is no longer present (provided it is not obtained in any other way). If a diagnosis makes this rule condition-free, it has no effect since it already is, i.e., its body is ⊤. For rule (2) it is exactly the other way round: it never fires so removing it has no consequences but if it is made condition-free, then the knowledge uncondr will be present.

(B) We can simulate with beliefs of an equilibrium the effects to a bridge rule of the modification by a diagnosis, i.e., if certain beliefs are present, the rule either stops firing or fires unconditionally. For example, let r be the bridge rule (3 : c) ← (1 : a), not (2 : b). and consider these bridge rules:

Rule (3) behaves like r as long as context n+1 does not believe removedr and it behaves as removed otherwise (i.e., it does not derive c for context 3). Similarly, rule (4) behaves like r being condition-free if n+1 believes uncondr. Replacing r by (3) and (4) thus enables simulation of a diagnosis.

By (A), a context can observe (parts) of a diagnosis and by (B), it can exhibit this observation as beliefs to other contexts whose rules then behave as being modified by the diagnosis. We can use this to establish a 1-1 correspondence between (effects of) diagnoses on an MCS M and (effects of) diagnoses on an extended MCS M ′ where diagnoses are observed by an observation context Cn+1. To also ensure that bridge rules like (3) and (4) are not modified in a diagnosis, we introduce the notion of a diagnosis excluding protected rules.

Definition 4. Given an MCS M with protected rules brP ⊆ br(M), a diagnosis excluding protected rules is a diagnosis (D1,D2) ∈ D±(M), where D1,D2 ⊆ br(M) \ brP . We denote the set of all such diagnoses by D±(M, brP ) and by D±m(M, brP ) the set of all minimal such diagnoses.

Consider a diagnosis filter f on diagnosis candidates of M, if Cn+1 observes all bridge rules of the original MCSM, then Cn+1 sees in M ′ whether a diagnosis candidate (D1,D2) of M is applied (assuming that only bridge rules of the form (3) and (4) are not protected). So, in principle, the logic inside Cn+1 could evaluate f(D1,D2) = t and in case of t = 0 context Cn+1 could become inconsistent. By that, all diagnoses excluding protected rules of M ′ are diagnoses passing the filter f. That is, we found a way to obtain filtered diagnoses and since we did not specify what logic is used inside Cn+1, any formalism deemed appropriate may be used.

For the meta-reasoning to serve as uniform foundation for filters and preferences, we introduce a property θ that describes the additional behavior of the context Cn+1. For preferences a set Kp of additional bridge rules at Cn+1 whose head beliefs are all distinct and whose bodies are ⊥, is required. Intuitively, Kp are additional bridge rules which may be forced by θ to become condition-free. By that, θ can (arbitrarily) map diagnosis candidates of M into diagnoses modifying Kp. So θ specifies how a diagnosis candidate maps into Kp. An (informal) definition of M mr(θ,Kp) is as follows.

Definition 5. Given an MCS M = (C1, . . . ,Cn), Kp, and θ : 2br(M) × 2br(M) × 2Kp , the MCS M mr(θ,Kp) = (C ′1 , . . . , C ′n , Cn+1) is a meta-reasoning encoding if:

(i) C ′ i equals Ci except that all its bridge rules are replaced with ones like in (3) and (4).

• (ii) Cn+1 = (Ln+1, kbn+1, brn+1) is a context such that:
• (a) the logic Ln+1 = (KBn+1,BSn+1,ACCn+1) is compatible with bridge rules in Kp and of form (1) and (2);
• (b) the bridge rules brn+1 are those in Kp and for each r ∈ br(M) a bridge rule of form (1) and of form (2); and
• (c) the knowledge base kbn+1 ∈ KBn+1 fulfills: for every set H of possible inputs by bridge rules, there is an acceptable belief set Sn+1 ∈ ACCn+1(kbn+1 ∪ H) iff Sn+1 exhibits the bridge rule modifications through beliefs removed r and uncondr, and θ holds for H.

The context Cn+1 is similar to an interface in programming, which defines certain properties but is open to an arbitrary implementation. In the next section we illustrate how θ and Kp can be used for preference realization.

5 Preference Realization

Since a preference order compares two diagnosis candidates, but meta-reasoning can only observe one diagnosis at a time, our solution is to clone the original MCS M such that we obtain an MCS 2M that contains two independent copies of M. Every diagnosis of 2M then is comprised of two diagnoses of M. Since the latter are independent of each other, applying the meta-reasoning encoding yields the MCS (2M)mr(θ,Kp) where the observation context sees two (independent) diagnoses of M and it may compare them, mapping the result of this comparison to Kp. The minimal ⪯-preferred diagnoses can then be selected from M ⪯ = (2M)mr(θ,Kp) using a slightly more involved diagnosis notion with prioritized bridge rules. Instead of defining the clone encoding here, we illustrate M ⪯ in Figure 2 for Example 1.

There are three types of bridge rules at the observation context C7: (i) bridge rules of the form di(rj), i ∈ {1, 2}, that encode two diagnoses for M, one per each clone, (ii) prioritized bridge rules of the forms ini(rj) and ini(rj), i ∈ {1, 2}, that encode the diagnosis of the first clone again, and (iii) the bridge rule tmax . The latter two types comprise the set Kp of the meta-reasoning transformation.

The idea of the clone encodingM ⪯ is that tmax is used as a flag whether the diagnosis applied to clone 2 is preferred over the diagnosis applied to clone 1. Specifically, if the diagnosis of clone 2 is preferred over the diagnosis of clone 1, then tmax does not lead to an inconsistency, but in all other cases it does. This means, that every diagnosis of M ⪯ where the diagnosis of clone 1 is minimal ⪯-preferred must contain tmax . So θ can be readily given by: θ holds for H iff H corresponds to a candidate diagnosis (D1,D2) of clone 1 and a candidate diagnosis (D′1 ,D′2 ) of clone 2, and one of the following holds, where K(D1,D2) is the representation of (D1,D2) by prioritized bridge rules of the form ini(rj) and ini(rj), i ∈ {1, 2}, and Rp are all such rules in H:

• (D1, D2) = (D′1 , D′2 ) and Rp = K(D1, D2) ∪ {tmax }, or
• (D′1 ,D′2 ) ≺ (D1,D2) and Rp = K(D1,D2).

If for a given diagnosis of clone 1, there exists a more preferred diagnosis of clone 2, then there exists a diagnosis without tmax . Selecting a diagnosis modifying a minimal set of prioritized bridge rules thus selects a ⪯-preferred diagnosis.

Definition 6. Let M be an MCS with protected rules brP , and prioritized rules brH. A diagnosis D ∈ D±m(M, brP ) is prioritized-minimal if no D′ ∈ D±m(M, brP ) modifies a smaller set of prioritized bridge rules; D±(M, brP , brH) is the set of all prioritized-minimal diagnoses.

Below we denote by t(D1,D2) the candidate diagnosis in M ⪯ that directly corresponds to (D1,D2) of M. Then:

Theorem 1. Let M be an MCS and let ⪯ be a preference order on the diagnoses of M. Then (D1,D2) ∈ D±(M) is ⪯-preferred iff t(D1, D2) ∈ D±(M ⪯, brP , brH) holds.

Finally, selecting a diagnosis that modifies a minimal set of prioritized bridge rules and contains tmax corresponds to selecting a minimal ⪯-preferred diagnosis.

Definition 7. Let M be an MCS with protected rules brP and prioritized rules brH. A subset-minimal prioritized-minimal (mpm) diagnosis wrt. tmax is a diagnosis that is prioritizedminimal, contains tmax , and is subset-minimal (w.r.t. nonprioritized bridge rules) among all prioritized-minimal diagnoses that contain tmax . The set of all such diagnoses is denoted by D±m,tmax (M, brP , brH).

We show that the clone encoding is sound and complete.

Theorem 2. Let M be an MCS and let ⪯ be a preference order on diagnoses of M. Then (D1, D2) ∈ D±m,⪯(M) holds iff t(D1, D2) ∈ D±m,tmax (M ⪯, brP , brH) holds.

r1

6 Computational Complexity

We analyzed the computational complexity of each of the following decision problems for a given diagnosis candidate D of an MCS M with bridge rules br(M), protected rules brP and prioritized rules brH: MCSDPm, decide whether D ∈ D±m(M, brP ) holds; MCSDPH, decide whether D∈D±(M, brP , brH) holds; MCSDPHm,tmax , decide whether D ∈ D±m,tmax (M, brP , brH) holds; We also analyzed MCSDMPREF: given a preference order ⪯ decide whether D ∈ D±m,⪯(M), i.e., if D is minimal ⪯-preferred. The results are given in Table 1, where MCSDm is the complexity of deciding whether D ∈ D±m(M) holds (cf. [Eiter et al., 2014]). Notably, the problems for our extended notions of diagnosis do not have higher complexity than the basic notion, except for MCSDPHm,tmax . But we show that the underlying problem MCSDMPREF is hard for the same complexity class, thus our solution is worst-case optimal.

7 Conclusion

The full article [Eiter and Weinzierl, 2017] contains formal notions, much more details, examples, and many results omitted for this abstract, including another encoding for total preference orders, and an appendix with full proofs.