Weakening Conflicting Information for Iterated Revision and Knowledge Integration
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 109-117.
© 2001 International Joint Conferences on Artificial Intelligence
Abstract
The ability to handle exceptions, to perform iterated belief revision and to integrate information from multiple sources are essential skills for an intelligent agent. These important skills are related in the sense that they all rely on resolving inconsistent information. We develop a novel and useful strategy for conflict resolution, and compare and contrast it with existing strategies. Ideally the process of conflict resolution should conform with the principle of Minimal Change and should result in the minimal loss of information. Our approach to minimizing the loss of information is to weaken information involved in conflicts rather than completely removing it. We implemented and tested the relative performance of our new strategy in three different ways. We show that it retains more information than the existing Maxi-Adjustment strategy at no extra computational cost. Surprisingly, we are able to demonstrate that it provides a computationally effective compilation of the lexicographical strategy, a strategy which is known to have desirable theoretical properties.
- [Alchourrón et al., 1985] C. E. Alchourrón, P. Gärdenfors and D. Makinson On the logic of theory change: Partial meet contrac- tion and revision functions. Journal of symbolic logic, 50:510- 530, 1985.
- [Benferhat et al., 1993] S. Benferhat, C. Cayrol, D. Dubois, J. Lang, H. Prade. Inconsistency management and prioritized syntax-based entailment. Proc. IJCAI, France, 640-645. IJCAI
- [Dubois et al., 1994] D. Dubois, J. Lang, H. Prade. Possibilistic logic. Handbook of Logic in AI and Log. Prog., (3), 439-513.
- [Lau et al., 2000] R. Lau, A.H.M. ter Hofstede, P.D. Bruza and K.F. Wong. Belief Revision and Possibilistic Logic for Adaptive In- formation Filtering Agents. Proc. IEEE (ICTAI), Canada, 19-26.
- [Lehmann, 1995] D. Lehmann. Another perspective on default rea- soning. Annals of Mathematics and Artif. Intel., 15, 61-82.
- [Spohn, 1988] W. Spohn. Ordinal conditional functions: A dy- namic theory of epistemic states. In: Causation in Decision, Belief Change and Statistic,(2), Reidel, Dordrecht, 105-134.
- [Williams, 1994] M. A. Williams. Transmutations of knowledge systems. Proc. KR'94, 619-629.
- [Williams, 1996] M. A. Williams. A practical approach to belief revision: reason-based change. Proc. KR'96, 412-421.
- [Williams, 1998] M. A. Williams. Applications of Belief Revision. in Transactions and Change in Logic Databases, LNAI 1472, 285-314, Springer Verlag.
- [Williams and Sims, 2000] M. A. Williams and A. Sims SATEN: An object-oriented web-based revision and extraction en- gine. Proc. of the Int. Workshop on Nonmonotonic Rea- soning (NMR' 2000). Online Computer Science Abstract http://arxiv.org/abs/cs.AI/0003059/ Link
- [Wong and Lau, 2000] O. Wong and R. Lau Possibilistic Reasoning for Intelligent Payment Agents. Proc. of the 2 nd Workshop on AI in Electronic Commerce (AIEC' 2000), 1-13.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Information modeling and management is a fundamental activity of intelligent systems. Intelligent systems require robust and sophisticated information management capabilities such as exception handling, iterated revision and the integration of information. In this paper we develop a novel and useful strategy for conflict resolution which can be applied to exception handling, iterated revision, and information integration. Throughout we assume that the available information is given as ordered knowledge bases, i.e. a ranking of information as logical sentences. Solving conflicts in our context means computing a consistent knowledge base. One well known system that can deal with conflicts in knowledge bases is the so-called Adjustment procedure [Williams, 1994]. In essence, Adjustment propagates as many highly ranked formulas as possible, and ignores information at and below the highest rank where an inconsistency is found. The main advantage of this system is its computational efficiency. For example, it only needs at most Log2n calls to a SAT solver to build the consistent knowledge base where n is the number of ranks in the knowledge base. The obvious disadvantage of Adjustment, however, is that it can remove more formulae than is necessary to restore the consistency of the knowledge base if the independence of information is not made explicit. In order to overcome this shortcoming another strategy called Maxi-Adjustment was introduced [Williams, 1996] and implemented [Williams and Sims, 2000]. Maxi-Adjustment has proved to be a useful strategy for real world applications e.g. software engineering [Williams, 1998], information filtering [Lau et al., 2000] and intelligent payment systems [Wong and Lau, 2000]. The main idea of Maxi-Adjustment is to solve conflicts at each rank of priority in the knowledge base. This is done, incremently, starting from the information with highest rank. When inconsistency is encountered in the knowledge base, then all formulas in the rank responsible for the conflicts are removed. The other formulas are kept, and the process continues to the next rank.
Clearly Maxi-Adjustment keeps more information than Adjustment, since it does not stop at the first rank where inconsistency is met. Even though Maxi-Adjustment propagates more information than Adjustment, one can still argue that Maxi-Adjustment removes too much information because it adopts a sceptical approach to the way it removes the conflict sets at each rank.
The purpose of this paper is to describe a significant improvement to Maxi-Adjustment. We call this system Disjunctive Maxi-Adjustment, and denote it by DMA. The idea is similar to Maxi-Adjustment, except that information is weakened instead of being removed when conflicts are detected. So instead of removing all formulas involved in conflicts, as it is done in Maxi-Adjustment, DMA takes their disjunctions pairwise. If the result is consistent, then we move to the next rank. If the result is still inconsistent, then we replace the formulas in conflicts by all possible disjunctions involving 3 formulas in the conflict sets and again if the result is consistent we move to the next layer, and if it is inconsistent we consider disjunctions of size 4, 5, etc. The only case where all formulas responsible for conflicts are removed is when the disjunction of all these formulas is inconsistent with the higher priority information.
This paper focuses on the DMA strategy from the theoretical and experimental perspectives. In particular,
- We show that DMA is equivalent to the well known
lexicographical strategy [Benferhat et al., 1993; Lehmann, 1995]. More precisely, we show that for an inconsistent base K if δDMA(K) is the classical base obtained using DMA, and δLex(K) is the set of all lexicographically maximal consistent subbases of K, then:
- It is well known that computing conflicts is a hard task, and we are able to show that DMA works even if the conflicts are not explicitly computed. For this, we propose an alternative, but equivalent, approach to DMA called whole-DMA where disjunctions are built on the whole stratum when we meet inconsistency instead of only on the conflicts.
- We also propose another equivalent alternative to DMA called iterative-DMA where instead of considering disjunctions of size (3,4, etc) on the initial set of conflicts, we only compute disjunctions of size 2 but on new sets of conflicts.
- Lastly, we compare these different implementations of DMA experimently, and contrast their applicability.
2 Ordered information in Spohn's OCF framework
We consider a finite propositional language denoted by L. Let Ω be the set of interpretations. ⊢ denotes the classical consequence relation, Greek letters φ, ψ, ... represent formulas. We use Spohn's ordinal conditional function [Spohn, 1988] framework, which is also known as the Kappa function framework.
At the semantic level, the basic notion of Spohn's ordinal conditional function framework is a distribution called an OCF, denoted by κ, which is a mapping from Ω to N, such that ∃ω, κ(ω) = 0. N is the set of natural numbers. κ(ω) can be viewed as the degree of impossibility of ω.
By convention, κ(ω) = 0 means that nothing prevents ω from being the real world, and κ(ω) = +∞ means that ω is certainly not the real world 1 . The lower κ(ω) is, the more expected it is, i.e. if κ(ω) < κ(ω′ ) then ω is said to be more plausible than ω′ .
In practice, OCF distributions over all possible worlds are not available, however a ranked knowledge base provides a compact representation of an OCF distribution [Williams, 1994]. Since we will be working with ranked knowledge bases throughout, we define a knowledge base to be ranked. In particular, a knowledge base is a set of weighted formulas of the form K = {(φi, ki) : i = 1, . . . , n} where φi is a classical formula and ki is a positive number representing the level of priority of φi. The higher ki, the more important the formula φi .
Given K, we can generate a unique OCF distribution, denoted by κK, such that all the interpretations satisfying all the formulae in K will have the lowest value, namely 0, and the other interpretations will be ranked with respect to the highest formulae that they falsify. Namely:
1 Note that the notion of impossible worlds (+∞) does not exist in original works of Spohn.
Definition 1 ∀ω ∈ Ω,
Then, given κK associated with a knowledge base K, the models of K are the interpretations ω s.t. κK(ω) = 0.
3 Adjustment andMaxi-Adjustment
3.1 Stratified vs ranked knowledge base
We have seen that ranked information is represented by means of knowledge bases of the form K = {(φi, ki) : i = 1, . . . , n}. We sometimes also represent this base K in a stratified form as follows: K = {S1, . . . , Sn} where Si (i = 1, . . . , n) contains classical formulas of K having the same rank and which are more reliable than formulas of Sj for j > i. So the lower the stratum, the higher the rank.
In this representation, subbases are also stratified. That is, if A is a subbase of K = {S1, . . . , Sn}, then A = {A1, . . . ,An} such that Aj ⊆ Sj, j = 1, . . . , n.
(Aj may be empty).
Conversely, we can represent a stratified base K = {S1, . . . , Sn} using a weighted knowledge base by associating formulas of each strata Si to the same rank ki. These ranks should be such that k1>. . .>kn.
Let us now introduce the notion of conflicts and kernel which will prove useful in the subsequent discussion:
Definition 2 Let K = {S1, . . . , Sn} be a stratified base. A conflict in K, denoted by C, is a subbase of K such that:
- C ⊢⊥ (inconsistency),
- ∀φ, φ ∈ C, C - {φ} ⊬⊥ (minimality).
Definition 3 Let C be the set of all possible conflicts in K. We define the kernel of K, denoted by kernel(K), as the set of formulas of K which are involved in at least one conflict in C i.e., kernel(K) is the union of all conflicts in K.
Formulas in K which are not involved in any conflict in K are called free formulas.
3.2 The problem
Our aim in this paper is to address the problem of identifying conflicts for the purposes of drawing plausible inferences from inconsistent knowledge bases, iterated revision and information integration. Our technique for resolving conflicts can be used: (i) to build a transmutation for iterated belief revision [Williams, 1994] where the new information can be incorporated into any rank, and (ii) for theory extraction [Williams and Sims, 2000] which provides a natural and puissant mechanism for merging conflicting information. Without loss of generality we focus on a particular case of revision where some new information ϕ is added to some ranked knowledge base K. Namely, given a knowledge base K, and a new formula ϕ we compute δ(K ∪ {(ϕ,+∞)}), the classical (not stratified) consistent subbase of K ∪ {(ϕ,+∞)}. Then, ψ is said to be a plausible consequence of K ∪ {(ϕ,+∞)} iff δ(K ∪ {(ϕ,+∞)}) ⊢ ψ. In the rest of this paper we simply write Kϕ instead of K ∪ {(ϕ, +∞)}. In a stratified form we write {S0, S1, . . . , Sn} where S0 = {ϕ}. We briefly recall two important methods to compute δ(K ∪ {(ϕ,+∞)}): Adjustment and Maxi-Adjustment. We will illustrate them using a simple example. We point the reader to [Williams, 1994; 1996] for more details.
3.3 Adjustment
From a syntactical point of view, the idea of Adjustment is to start with formulas having the highest rank in Kϕ and to add as many prioritized formulas as possible while maintaining consistency. We stop at the highest rank (or the lowest stratum) where we meet inconsistency called the inconsistency rank of Kϕ, denoted by Inc(Kϕ).
Note that a more efficient binary search based algorithm which only needs Log2n consistency checks has been developed and implemented 2 [Williams and Sims, 2000]. The selected base will be denoted by δA(Kϕ). Note that the process of selecting the consistent base using the Adjustment for new pieces of information placed in the highest rank is identical to that used in possibilistic logic [Dubois et al., 1994].
One can easily see that this is not a completely satisfactory way to deal with the inconsistency since formulas with rank lower than Inc(Kϕ) are ignored even if they are consistent with the selected base.
A formula ψ is said to be an Adjustment consequence of Kϕ, denoted by Kϕ ⊢A ψ, if δA(Kϕ) ⊢ ψ. One important property of Adjustment is that it is semantically well defined. More precisely, we have the following soundness and completeness result: Kϕ ⊢A ψ iff ∀ω ∈ Pref(κKϕ ), ω |= ψ, where Pref(κKϕ ) is the set of interpretations which satisfy ϕ and have minimal rank in the OCF distribution κKϕ given by Definition 1.
Example 1 Let K = {S1, S2, S3} be such that S1 = {(¬a ∨ ¬b ∨ c, 3), (¬d ∨ c, 3), (¬e ∨ c, 3)}, S2 = {(d, 2), (e, 2), (f, 2), (¬f ∨ ¬g ∨ c, 2)} and S3 = {(a, 1), (b, 1), (g, 1), (h, 1)}. Let ϕ = ¬c. First, we have δA(K¬c) = {¬c}. There is no conflict in δA(K¬c) ∪ S1 then δA(K¬c) ← {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c}. Now, S2 contradicts δA(K¬c) due to the conflicts {d, ¬d ∨ c, ¬c} and {e, ¬e ∨ c, ¬c}. Then, we do not add the stratum S2 and the computation of δA(K¬c) is achieved, and we get δA(K¬c) = {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c}. Note that δA(K¬c) ̸⊢ h, even if h is not involved in any conflict in K¬c.
3.4 Maxi-Adjustment
Maxi-Adjustment [Williams, 1996] was developed to address the problem of discarding too much information for applications like software engineering [Williams, 1998] and information filtering [Lau et al., 2000].
2 http://cafe.newcastle.edu.au/systems/saten.html
The idea in Maxi-Adjustment also involves selecting one consistent subbase from K denoted by δMA(Kϕ). The difference is that it does not stop at the first rank where it meets inconsistency. Moreover, conflicts are solved rank by rank. We start from the first rank and take the formulas of S1 which do not belong to any conflict in {ϕ} ∪ S1. Let S′1 be the set of these formulas. Then, we move to the next rank and add all formulas which are not involved in any conflict in S′1 ∪S2, and so on. It is clear that Maxi-Adjustment keeps more formulas than the Adjustment.
Example 1(using Maxi-Adjustment)
First, we have δMA(K¬c) = {¬c}.
There is no conflict in δMA(K¬c) ∪ S1 then
δMA(K¬c) ← {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c}. Now, S2 contradicts δMA(K¬c) due to the conflicts {d, ¬d ∨ c, ¬c} and {e, ¬e ∨ c, ¬c}. Then, we do not add the clauses from S2 involved in these conflicts: δMA(K¬c) ← δMA(K¬c) ∪ {f, ¬f ∨ ¬g ∨ c}.
Now, S3 contradicts δMA(K¬c) due to the conflicts {a, b, ¬a ∨ ¬b ∨ c, ¬c} and {f, g, ¬f ∨ ¬g ∨ c, ¬c}. Since all the clauses, except h, from the stratum S3 are involved in one conflict, we only add h to δMA(K¬c). Finally, we get: δMA(K¬c) = {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c, f, ¬f ∨ ¬g ∨ c, h}. Note that δMA(K¬c) ⊢ h.
4 Disjunctive Maxi-Adjustment
Although Maxi-Adjustment retains more information than Adjustment, it can still be argued that it is too cavalier in the way it solves the conflicts.
In this section, we propose a new strategy which is a significant improvement of Maxi-Adjustment. The computation of the consistent base is essentially the same as in Maxi-Adjustment, the only difference is when we meet an inconsistency at some rank, instead of removing all the formulas involved in the conflicts at this rank we weaken them, by replacing them by their pairwise disjunctions. If the result is consistent then we move to the next rank, else we replace these formulas by their possible disjunctions of size 3. If the result is consistent then we move to the next rank, else we add the disjunctions of size 4 of these formulas, and so on. We summarize this process in Algorithm 1:
Notation: dk(C) is the set of all possible disjunctions of size k between formulas of C. If k >|C | then dk(C) = ∅.
Example 1 (using DMA)
First, we have KB = {¬c}.
There is no conflict in KB ∪S1 then
KB ← {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c}.
Now, S2 contradicts KB due to the conflicts {d, ¬d ∨ c, ¬c} and {e, ¬e ∨ c, ¬c}. We do not add the clauses from S2 involved in these conflicts: KB ← KB ∪ {f, ¬f ∨ ¬g ∨ c}. Now we create all the possible disjunctions of size 2 with C = {d, e}: d2(C) = {d ∨ e}. Since KB ∪ d2(C) is inconsistent, and we cannot create larger disjunctions, we do not add anything from S2 to KB.
Algorithm 1: DMA(K, ϕ)
Data: a stratified knowledge base K = {S1, . . . , Sn} ; a new sure formula: ϕ ; Result: a consistent subbase δDMA(Kϕ) beginKB ← {ϕ} ;
for i ← 1 to n do if KB ∪ Si is consistent then KB ← KB ∪ Si else Let C be the subset of Si in kernel of KB∪Si; KB ← KB ∪ {φ : φ ∈ Si and φ ̸∈ C}; k ← 2 ; while k ≤ |C| and KB∪dk(C) is inconsistent do k ← k + 1; if k ≤ |C| then KB ←KB ∪ dk(C) ; return KB end
Please note at this rank, we do not add more information than Maxi-Adjustment.
Now, S3 contradicts KB due to the conflicts {a, b, ¬a ∨ ¬b ∨ c, ¬c} and {f, g, ¬f ∨ ¬g ∨ c, ¬c}. h is not involved in any conflict. Then, KB ← KB ∪ {h}.
We now create all the possible pairwise disjunctions with C = {a, b, g}: d2(C) = {a ∨ b, a ∨ g, b ∨ g}. Since KB ∪ d2(C) is inconsistent, we create d3(C) = {a ∨ b ∨ g}. Since KB ∪ d3(C) is consistent, we add d3(C) to KB and the algorithm stops.
which is equivalent to {¬c, ¬a ∨ ¬b, ¬d, ¬e, f, ¬g, h, a ∨ b}. DMA keeps more information from the last stratum than Maxi-Adjustment does.
Definition 4 A formula ψ is said to be a DMA consequence of K and ϕ, denoted by Kϕ ⊢DMA ψ, if it is inferred from δDMA(Kϕ). Namely, Kϕ ⊢DMA ψ iff δDMA(Kϕ) ⊢ ψ.
5 Two other implementations of DMA
In the previous section we have shown a way to compute δDMA(Kϕ) using the computation of the kernel. In this section, we propose two alternative ways to compute δDMA(Kϕ). The first approach, called whole-DMA(K,ϕ), does not compute the kernel. The main motivation for this alternative is that computing the kernel is in general hard. For the second approach, called iterative-DMA(K,ϕ), when inconsistency is (again) met after weakening the kernel, then rather than weakening the original kernel by considering its disjunctions of size 3, we only weaken the newly computed kernel obtained by considering disjunctions of size 2. The motivation of this approach is to reduce the size of added (disjunctions) formulas.
5.1 Whole Disjunctive Maxi-Adjustment
We propose a slightly modified version of the DMA algorithm. The idea is that when KB∪Si is inconsistent, instead of considering all possible disjunctions of size j of elements of Si which are in kernel(KB∪Si), we consider all possible disjunctions of size j of Si without computing a kernel. This is justified by the following proposition:
Proposition 1 Let KB ∪ S be inconsistent. Let C be the subset of S in kernel(KB ∪ S), and F = S - C be the set of remaining formulas. Let dj(C) (resp. dj(S)) be the set of all possible disjunctions of size j from C (resp. S). Then,
Proof (sketch)
Let us assume that dj-1(S) ∪ KB is inconsistent, and show that dj (S) ∪ KB ≡ dj (C) ∪ KB ∪ F .
It is clear that dj(C) ⊆ dj(S). Hence it is enough to show that KB ∪ dj (S) ⊢ F .
Let A be a conflict of KB ∪ dj-1(S), and {ψ1, . . . , ψn} be a subset of A in dj-1(S). Let ϕ ∈ F .
Then {ϕ ∨ ψ1, . . . , ϕ ∨ ψn} ⊆ dj(S), with ψi ̸= ϕ since ϕ ̸∈ A (because ϕ is free).
Now since KB ∪ A is inconsistent then KB ⊢ ¬ψ1 ∨ · · · ∨ ¬ψn. Applying successive resolutions between {ϕ ∨ ψ1, . . . , ϕ ∨ ψn} and ¬ψ1 ∨ · · · ∨ ¬ψn leads to entail ϕ.
Hence there is no need to consider disjunctions containing free formulas since they will be subsumed. x3
With the help of this proposition, the "else" block in the DMA algorithm is replaced by
elsek ← 2 while KB ∪ dk(Si) is inconsistent and k ≤| Si | do k ← k + 1 if k ≤|Si | then KB ← KB ∪ dk(Si)
to obtain the whole DMA algorithm.
Example 1 (using whole DMA)
First, we have KB = {¬c}.
S1 is consistent with KB. Then, KB ← KB ∪ S1. Now, S2 contradicts KB. We compute all possible pairwise disjunctions with S2. d2(S2) = {d ∨ e, d ∨ f, d ∨ ¬f ∨ ¬g ∨ c, e ∨ f, e ∨ ¬f ∨ ¬g ∨ c}.
Since, KB ∪ S2 is inconsistent, we compute all possible disjunctions of size 3 between formulas of S2. We get d3(S2) = {d∨e∨f, d∨e∨¬f ∨¬g ∨c} which is consistent with KB. Then, KB ← KB ∪ d3(S2).
Now, S3 is inconsistent with KB. We compute all possible pairwise disjunctions with S3. d2(S3) = {a ∨ b, a ∨ g, a ∨ h, b∨g, b∨h, g ∨h} which is still inconsistent with KB. We have d3(S3) = {a ∨ b ∨ g, a ∨ b ∨ h, b ∨ g ∨ h, a ∨ g ∨ h} which is consistent with KB, then KB ← KB ∪ d3(S3). Hence, δWDMA(K¬c) = {¬c, ¬a∨¬b∨c, ¬d∨c, ¬e∨ c, d∨ e∨f, d∨e∨¬f ∨¬g∨c, a∨b∨g, a∨b∨h, b∨g∨h, a∨g∨h} which is equivalent to {¬c, ¬a ∨ ¬b, ¬d, ¬e, f, ¬g, a ∨ b, h}.
Then, it is equivalent to δDMA(K¬c).
5.2 Iterative Disjunctive Maxi-Adjustment
The idea of this alternative implementation of DMA is as follows: let Si be inconsistent with KB. Let C and F be the kernel and the remaining formulas of Si.
Now assume that KB∪F ∪d2(C) is still inconsistent. Then rather than weakening C again by considering disjunctions of size 3, we only weaken those formulas in d2(C) which are still responsible for conflicts. Namely, we split d2(C) into C′ and F ′ which respectively represent the kernel and remaining formulas of d2(C). Then instead of taking KB ∪ F ∪ d3(C) as in DMA, we take KB ∪ F ∪ F ′ ∪ d2(C′ ). The algorithm becomes:
Algorithm 2: IDMA(K, ϕ)
Data: a stratified knowledge base K = {S1, . . . , Sn} ; a new sure formula: ϕ
Result: a consistent subbase δIDMA(Kϕ)
beginKB ← {ϕ}, i ← 1; while i ≤ n do if KB ∪Si is consistent then KB ←KB ∪Si ; i ← i +1 ; else Let C ⊆ Si be in kernel(KB ∪ Si) ; Si ← {φ : φ ∈ Si and φ ̸∈ C} ; if | C |= 1 then i ← i + 1 else Si ← Si ∪ d2(C) ; return KB end
Proposition 2 Let KB ∪ F ∪ di(C) be inconsistent. Then, KB ∪ F ∪ di(C) ≡ KB ∪ F ∪ F ′ ∪ d2(C′ ), where F ′ and C′ are kernels from di(C).
The proof is a corollary of Prop. 1 and the following lemma:
Lemma 1 Let A be a set of formulas. Let B = di(A) and C = di+1(A) be the set of all possible disjunctions of A of size i and i + 1 respectively. Then, C = d2(B).
This lemma means that taking all disjunctions of size i, then reconsidering all disjunctions of size 2 again on the result is the same as considering all disjunctions of size i + 1.
Example 1 (using iterative DMA)
First, we have KB = {¬c}.
There is no conflict in KB ∪ S1. Then, KB ← KB ∪ S1. S2 is inconsistent with KB due to the conflicts {¬c, ¬d∨c, d} and {¬c, ¬e ∨ c, e}. We add {f, ¬f ∨ ¬g ∨ c} to KB. The disjunction d ∨ e is still inconsistent with KB, then we move to S3.
S3 contradicts KB due to the conflicts {a, b, ¬a∨¬b∨c, ¬c} and {f, g, ¬f ∨¬g ∨ c, ¬c}. h is not involved in any conflict. Then, KB ← KB ∪ {h}.
We now create all the possible pairwise disjunctions with C = {a, b, g}: d2(C) = {a ∨ b, a ∨ g, b ∨ g}.
KB∪d2(C) is inconsistent due to the conflict {¬c, ¬a∨¬b∨ c, f, ¬f ∨¬g ∨c, a∨g, b∨g}. a∨b in d2(C) is not involved in the conflict, then KB ←KB ∪ {a ∨ b}.
Now, we take the pairwise disjunctions with C = {a ∨ g, b ∨ g}. d2(C) = {a ∨ b ∨ g}. KB ∪ d2(C) is consistent. However, there is no need to add a ∨ b ∨ g to KB since a ∨ b already belongs to KB. Hence, δIDMA(K¬c) = {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c, f, ¬f ∨ ¬g ∨ c, a ∨ b, h} which is equivalent to {¬c, ¬a ∨ ¬b, ¬d, ¬e, f, ¬g, a ∨ b, h}. Hence, it is equivalent to δDMA(K¬c).
6 DMA: Compilation of lexicographical inferences
The aim of this section is to show that DMA is a compilation of the lexicographical system, hence it satisfies the AGM postulates [Alchourr´on et al., 1985]. First let us recall the lexicographical inference.
6.1 Lexicographical inference
The lexicographical system [Benferhat et al., 1993; Lehmann, 1995] is a coherence-based approach where an inconsistent knowledge base is replaced by a set of maximally preferred consistent subbases. The preference relation between subbases is defined as follows:
Definition 5 Let A = {A1, . . . ,An} and B = {B1, . . . , Bn} be two consistent subbases of K.
A is said to be lexicographically preferred to B, denoted by A >Lex B, iff
Let δLex(Kϕ) denotes the set of all lexicographically preferred subbases of Kϕ, those which are maximal w.r.t. >Lex. Then, the lexicographical inference is defined by:
Definition 6 A formula ψ is said to be a lexicographical consequence of Kϕ, denoted by Kϕ ⊢Lex ψ, if it is a classical consequence of all the elements of δLex(Kϕ), namely
Example 1 (continued)
We have δLex(K¬c) = {A, B} where A = {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c, f, ¬f ∨ ¬g ∨ c, a, h} and B = {¬c, ¬a ∨ ¬b ∨ c, ¬d ∨ c, ¬e ∨ c, f, ¬f ∨ ¬g ∨ c, b, h}. For example, we have
K¬c ⊢Lex a ∨ b since A ⊢ a ∨ b and B ⊢ a ∨ b.
6.2 Basic steps of the compilation
The aim of this section is to show that DMA is equivalent to the lexicographical system. DMA offers a clear advantage over the lexicographical system because it obviates the need to explicitly compute δLex(Kϕ) which may be exponential in size. Formally, we will show the following equivalence:
Note that δDMA(Kϕ) is a classical consistent base.
Example 1 (continued)
Let us first show that applying the lexicographical system on K¬c gives the same results as applying DMA on K¬c. Indeed, K¬c ⊢Lex ψ iff A ⊢ ψ and B ⊢ ψ iff A ∨ B ⊢ ψ iff {¬c, ¬a ∨ ¬b, ¬d, ¬e, f, ¬g, a ∨ b, h} ⊢ ψ (after removing subsumed formulas in A∨B) iff δDMA(K¬c) ⊢ ψ iff K¬c ⊢DMA ψ.
To show (1) we follow the following steps: Step 1: we construct a new base K′ from K s.t.
Namely, applying lexicographical system on Kϕ is equivalent to applying Adjustment to K′ϕ.
Step 2: in the second step we show that
Namely, applying Adjustment to K′ϕ is equivalent to applying DMA to Kϕ.
Step 1: Constructing K′
In order to show the proof of (2), we need to rewrite the lexicographical system at the semantic level, which is immediate:
Definition 7 Let K = {S1, . . . , Sn}. Let ω and ω′ be two interpretations, and Aω, Aω′ be the subbases composed of all formulas of K satisfied by ω and ω′ respectively.
Then, ω is said to be lexicographically preferred to ω′ w.r.t. K, denoted by ω >Lex,K ω′ , iff Aω >Lex Aω′ (using Definition 5).
Proposition 3 Let δLex(K) be the set of lexicographical preferred consistent subbases of K.
Let Aω be the set of formulas in K satisfied by ω. Then, i. If ω is minimal w.r.t. >Lex,K then Aω ∈ δLex(K) ii. ∀A ∈ δLex(K), ∃ω |= A s.t. ω is minimal w.r.t. >Lex,K.
Using Prop. 3, at the semantic level, (2) is equivalent to:
where κK′ϕ is the OCF associated to K′ϕ obtained from Definition 1.
Let us now show how to construct K′ from K such that it satisfies (4). For this, we use two intuitive ideas.
The first idea is that Adjustment is insensitive to the number of equally reliable formulas falsified while lexicographical system is not (i.e. cardinality of conflict sets). Assume that we have a base K = {(φ, i), (ψ, i)} which contains two formulas with a same rank. Then, the rank (using Def. 1) associated with an interpretation ω falsifying one formula has a same rank as an interpretation falsifying two formulas. However, if we use the lexicographical system, an interpretation falsifying one formula is preferred to an interpretation falsifying two formulas. Now one can check that if we construct a knowledge base K′ = {(φ, i), (ψ, i), (φ ∨ ψ, 2i)} from K by adding the disjunction φ ∨ ψ with a higher rank, then equation (4) is satisfied. So the first idea is to add disjunctions with the rank equal to the sum of ranks of formulas composing the disjunctions.
The second idea is related to the notion of compensation. To illustrate this idea, let us now consider K = {S1, S2} such that S1 = {φ1} and S2 = {φ2, φ3, φ4}. The intuition behind this example is to show that ranks associated with the formulas should satisfy some constraints in order to recover the lexicographical inference. Indeed, let us for instance associate the rank 2 with φ1, and the rank 1 with φ2, φ3, φ4. Let ω and ω′ be two interpretations such that Aω = {{φ1}, {}} and Aω′ = {{}, {φ2, φ3, φ4}}. Aω means that ω satisfies all formulas of S1 but falsifies all formulas of S2. Aω′ means that ω′ satisfies all the formulas of S2 but falsifies all the formulas of S1. Following the suggestion of the first idea, let us add all possible disjunctions. We obtain:
K′ = {{(φ1∨φ2∨φ3∨φ4, 5)}; {(φ1∨φ3∨φ4, 4); (φ1∨φ2∨ φ4, 4); (φ1 ∨ φ2 ∨ φ3, 4)}; {(φ1 ∨ φ2, 3); (φ1 ∨ φ3, 3); (φ1 ∨ φ4, 3); (φ2 ∨φ3 ∨φ4, 3)}; {(φ1, 2); (φ2 ∨φ3, 2); (φ2 ∨φ4, 2); (φ3 ∨ φ4, 2)}; {(φ2, 1); (φ3, 1); (φ4, 1)}}.
We can easily check that κK′ (ω) = 3 and κK′ (ω′ ) = 2 while Aω >Lex,K Aω′ . This is due to the fact that the disjunction φ2 ∨ φ3 ∨ φ4 has a rank higher than φ1. Hence, there is a compensation effect. So, in order to recover the lexicographical order, φ1 must have a rank strictly greater than the rank of φ2 ∨φ3 ∨φ4. A way to do this is to significantly differentiate the different ranks associated with strata. For this, we associate to each formula (φij, ki) ∈ Si the rank N ki where N is very large. N should be s.t. ∀i, N ki > Σj>iN kj . Such an N always exists. It means that the rank given to a stratum must be greater than the sum of all the ranks of the less reliable strata.
Following these two ideas, K′ is formally constructed as follows:
Let K = {S1, . . . , Sn}, and ϕ a new sure information:
- We define a new base B:
- B = {(φij , N ki ) : i = 1, n and φij ∈ Si}.
- K′ = {(Dj(B), aj)} where Dj(B) is the set of all possible disjunctions of size j between formulas of B, and aj is the sum of ranks of formulas in Dj(B).
Then we have:
Proposition 4 K′ϕ ⊢A ψ iff Kϕ ⊢Lex ψ.
The following proposition shows that the base K′ constructed in Step 1 allows us to recover the lexicographical system.
Proposition 5 Let K = {S1, . . . , Sn} be a stratified base, and ϕ be a sure formula. Let K′ be a base constructed in Step 1. Then,
Due to the lack of space, we skip the proof of Prop. 5 and illustrate its main ideas by an example. The idea is to simplify the computation of δA(K′ϕ) until recovering δDMA(Kϕ).
Example 2 Let K = {S1, S2} where S1 = {¬a ∨ ¬b ∨ c} and S2 = {a, b, g}. Let ϕ = ¬c.
First it can be checked that
δDMA(K¬c) = {¬c, ¬a ∨ ¬b ∨ c, a ∨ b, g}.
Let N be a large number. Using Step 1, we have:
B = {(¬a ∨ ¬b ∨ c, N 2 ), (a, N), (b, N), (g, N)}.
The base K′ obtained from Step 1 (after removing tautologies): K′ = {(¬a ∨ ¬b ∨ c ∨ g,N 2 + N), (¬a ∨ ¬b ∨ c, N 2 ), (a ∨ b ∨ g, 3N), (a ∨ b, 2N), (a ∨ g, 2N), (b ∨ g, 2N), (a, N), (b, N), (g, N)}.
Since we apply Adjustment on K′¬c , the first idea is to ignore formulas in K′¬c under the inconsistency level (see Section 3.3). We can check that Inc(K′¬c ) = N. Then, δA(K′¬c ) is the classical base (obtained by ignoring the ranks) associated with {(¬c, +∞), (¬a ∨ ¬b ∨ c ∨ g, N 2 +N ), (¬a ∨ ¬b ∨ c, N 2 ), (a∨b∨g, 3N), (a∨b, 2N), (a∨g, 2N), (b∨g, 2N)}. The second idea is that subsumed disjunctions are not added. In this example, since ¬a ∨ ¬b ∨ c and a ∨ b, a ∨ g, b ∨ g will belong to δA(K′¬c ) then there is no need to keep the disjunctions ¬a ∨ ¬b ∨ c ∨ g and a ∨ b ∨ g.
Lastly, the other disjunctions can be refined. Since C = {¬c, ¬a ∨ ¬b ∨ c, a, b} is inconsistent, then all disjunctions constructed from g and this conflict C are reduced to g.
Therefore, we have δA(K′¬c ) ≡ {¬c, ¬a ∨ ¬b ∨ c, a ∨ b, g} which is equivalent to δDMA(K¬c).
7 Experimental results
We now present some experimental results which illustrate the different behaviour of each strategy. We used a propositional logic implementation of the strategies 3 . We chose 8 inconsistent bases at random from the DIMACS challenge (aim-50-no) containing 50 variables each and 80 clauses for the first 4, 100 clauses for the others. Then we stratified the bases with 20 clauses per strata, keeping the clauses in their original order. It appeared that each time the conflicts were discovered and weaken in the second strata, no more appeared in the remaining strata. The following table gives the number of clauses in the second strata after applying a given strategy. WDMA (resp. IDMA) stands for whole-DMA (resp. iterative DMA).
| #clauses | t1 | t2 | t3 | t4 | t5 | t6 | t7 | t8 |
|---|---|---|---|---|---|---|---|---|
| Adj. | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| MA | 17 | 7 | 8 | 18 | 13 | 7 | 10 | 17 |
| DMA | 17 | 54 | 49 | 18 | 21 | 60 | 35 | 18 |
| WDMA | 168 | 149 | 153 | 161 | 161 | 155 | 152 | 160 |
| IDMA | 17 | 54 | 49 | 18 | 21 | 60 | 35 | 18 |
There are no differences between DMA and IDMA because on these examples consistency was either restored using d2(C) (t2,t3,t5,t6,t7) or all the clauses involved in a conflict have to were removed. Whole-DMA clearly hides the information contained in the knowledge base by generating a large number of clauses but timewise its fast. Let us now take a look at the time spent computing each strategy.
| time (s) | t1 | t2 | t3 | t4 | t5 | t6 | t7 | t8 |
|---|---|---|---|---|---|---|---|---|
| Adj. | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| MA | 137 | 0.6 | 2.0 | 332 | 6.1 | 0.3 | 1.2 | 304 |
| DMA | 136 | 0.6 | 2.1 | 329 | 6.2 | 0.3 | 1.2 | 302 |
| WDMA | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 |
| IDMA | 139 | 0.6 | 2.1 | 329 | 6.0 | 0.3 | 1.2 | 306 |
These results can be interpreted as follows: computing the set of clauses involved in conflicts (kernel) is costly, so all methods relying on this information will require small KB's to revise. This can be achieved for instance using modular KB's, a common practice in knowledge engineering.
Interestingly, since the three DMA approaches we introduced are logically equivalent, we can propose one way to efficiently compute the DMA policy: whole DMA, only based on satisfiability testing. This method can be used for instance if the knowledge base is hidden to the final user, and that only the queries are important. On the other hand, if the knowledge base itself is important for the user, such that the revised base must be as "close" as possible to the original one, an IDMA approach should be used (only necessary information will be weakened), but a computational cost must be paid. DMA is a tradeoff between these two policies.
3 ADS: http://cafe.newcastle.edu.au/daniel/ADS/
8 Conclusion
We introduced a new family of computationally effective strategies for conflict resolution which can be used for exception handling, iterated belief revision and merging information frommultiple sources. The most important feature of our strategy is that it relies on weakening conflicting information rather than removing conflicts completely, and hence is retains at least as much, and in most cases more, information than all other known strategies. Furthermore, it achieves this higher retention of information at no extra computational cost. We compared and contrasted three implementations of our new strategy with existing ones from a theoretical standpoint and by measuring their relative performance. We were also able to show the surprising result that the DMA policy provides a compilation of the lexicographical system which is known to have desirable theoretical properties. DMA offers the clear advantage of obviating the need to explicitly compute the set of all preferred subbases which can be hard. Another pleasing result is that the DMA strategy can be implemented as whole-DMA where the need to explicitly compute the culprits responsible for the conflicts is not required.
@inproceedings{ijcai2001p15,
title = {Weakening Conflicting Information for Iterated Revision and Knowledge Integration},
author = {Benferhat, Salem and Kaci, Souhila and Le Berre, Daniel and Williams, Mary-Anne},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bernhard Nebel},
pages = {109--117},
year = {2001},
url = {https://ijcai.org/proceedings/2001/15},
}
TY - CPAPER TI - Weakening Conflicting Information for Iterated Revision and Knowledge Integration AU - Benferhat, Salem AU - Kaci, Souhila AU - Le Berre, Daniel AU - Williams, Mary-Anne T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 109 EP - 117 UR - https://ijcai.org/proceedings/2001/15 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: