On the Compilation of Stratified Belief Bases under Linear and Possibilistic Logic Policies

1 Introduction

Integrating pieces of information coming from different, possibly conflicting sources may lead to reason with inconsistent formulae. In this case, classical inference can not be used to exploit the given belief base, since from an inconsistent base every formula can be inferred (ex falso quodlibet sequitur principle).

Many approaches have been proposed in order to reason under inconsistency without trivialization. While some of them consist in weakening the inference relation such as paraconsistant logics, others weaken the available beliefs like the well-known coherence based-approaches [Rescher and Manor, 1970].

Coherence-based approaches can be characterized by the two following steps: i) give up some formulas of the inconsistent belief base Σ in order to restore its consistency; this operation results into one or several consistent subbases of Σ; and ii) use classical entailment on these consistent subbases to define plausible conclusions from the knowledge base Σ. When priorities attached to pieces of knowledge are available, the task of coping with inconsistency is simplified, because priorities give information about how to solve conflicts.

Examples of prioritized coherence approaches which select one consistent subbase are the possibilistic logic approach [Dubois et al., 1994], Williams' adjustment ap-

Habiba Drias

Institut National d'Informatique BP 68M Oued Smar 16309 Algiers. Algeria.

h drias@ini.dz

proach [Williams, 1995], and linear order approach [Nebel, 1994]. Examples of approaches which use several consistent subbases are Rescher's notion of acceptable subbases [Rescher, 1976], Brewka's preferred sub-theories [Brewka, 1989] and the lexicographical system [Benferhat et al., 1993; Lehmann, 1995].

In this paper, we mainly focus on the linear order and on possibilistic logic policies. Given a stratified belief base Σ = (S1, . . . , Sk) (S1 contains the most prioritized formulas, while the stratum Sk contains the least prioritized formulas), possibilistic logic only takes into account the first i consistent strata, and stops when inconsistency is met. Nebel [Nebel, 1994] has elaborated a less liberal way to select one consistent subbase. When inconsistency occurs at some strata k, we give up the whole stratum (concerned by inconsistency), but we continue to add strata with lower certainty if consistency is preserved.

From a practical point of view, reasoning under inconsistency is a hard problem [Nebel, 1998]. Indeed, deciding the inference from a stratified belief base with respect to the possibilistic policy is a Δp2 [O(log n)]-complete problem while deciding the inference from it with respect to the linear order policy is Δp2 -complete.

To address this problem, one can use knowledge compilation. Knowledge compilation is a key direction of research in Artificial Intelligence [Selman and H.Kautz, 1996; Cadoli and Donini, 1997; Darwiche and Marquis, 2002]. It consists in preprocessing off-line the knowledge base in order to make the inference from it easier on-line.

A key issue, in possibilistic logic, is how to determine the level of uncertainty associated with formulas that can be derived from an inconsistent knowledge base. Another important issue is how to compute "possibilistic conditioning". Namely, like in possibilistic networks, given some evidence, often provided in the form of a conjunction of literals (a term), we need to evaluate the impact of this evidence on the certainty degrees of variables or more generally of formulas of knowledge bases.

In this paper, we propose an efficient way to compile stratified belief bases with respect to the linear order and possibilistic logic policies. In order to support possibilistic conditioning and the computation of weights associated with concluded formulas, we need to keep track and encode the weights associated with formulas. This is obtained by adding new variables, as it has been previously done in some existingworks [Darwiche andMarquis, 2004; Coste-Marquis and Marquis, 2004; Benferhat and Prade, 2005].

The main advantage of our approach is the resulting extra compilation cost which is very low. Indeed, the number of additional variables needed for compiling stratified knowledge bases under linear order and possibilistic policy, is only equal to the number of strata in the belief base. In [Benferhat and Prade, 2006] a compilation method has been proposed to compile possibilistic bases (and not linear order policy). However, this approach needs to add binary clauses and is based on the idea of forgetting variables which limits the target compilation languages that can be exploited. Moreover, it does not support possibilistic conditioning.

The remainder of the paper is organized as follows. Section 2 introduces stratified belief bases and the corresponding inference relations w.r.t the linear order and possibilistic logic policies. We also define how to associate weights to the inferred conclusions and the notion of possibilistic conditioning. After a brief background on knowledge compilation in Section 3, we describe our compilation method in the case of linear order policy in Section 4. In Section 5, we adapt this method to compile possibilistic knowledge bases. We also, show how to handle weighted possibilistic inference relation and possibilistic conditioning. Section 6 provides some comparative studies and concludes the paper.

2 Stratified Belief Bases

We consider a finite propositional language denoted by L. |= denotes classical consequence relation. Greek letters Φ, Ψ, . . . represent formulas. ⊤ and ⊥ denote the constants true and false respectively.

A stratified belief base is a set of formulae equipped with a total pre-order. Formally:

Definition 1 A stratified belief base (SBB for short)Σ is a finite sequence (S1, . . . , Sk) where Si (i = 1, . . . , k) is a stratum containing propositional formulas having the same priority level i and which are more reliable than formulas of the stratum Sj for j > i.

According to coherence-based approaches, the inference from a stratified belief base is considered as a two step process consisting first in generating some preferred consistent subbases of Σ and then using classical inference from some of them depending on the entailment principle used.

Many policies for the selection of subbases can be considered, especially the possibilistic policy [Dubois et al., 1994], the linear order policy [Nebel, 1994], the inclusion preference policy [Brewka, 1989] and the lexicographical policy [Benferhat et al., 1993]. Among them, we focus on the possibilistic and the linear order policies.

The idea of the possibilistic logic policy is to start with formulas having the highest priority level and to propagate as many prioritized formulas as possible while maintaining consistency. We stop at the first priority level where we meet inconsistency and the formulas at this level and below are ignored. Formally:

Definition 2 Let Σ = (S1, . . . , Sk) be a SBB. The set ΣPO of all the preferred subbases of Σ w.r.t the possibilistic policy is the singleton {⋃s-1 i=1 Si}, where s is the smallest index s.t. ⋃si=1 Si is inconsistent. If Σ is consistent, then ΣPO = Σ.

As to the linear order policy which keeps more information, it does not stop at the first level where it meets inconsistency: when an inconsistency is encountered, the current stratum is dropped, and the process moves to the next stratum and so on. Formally:

Definition 3 Let Σ = (S1, . . . , Sk) be a SBB. The set ΣLO of all the preferred subbases of Σ w.r.t the linear order policy is the singleton {⋃ki=1 S ′ i }, where S ′ i is defined by S ′ i = Si if Si ∪ ⋃i-1 j=1 S ′j is consistent, ∅ otherwise.

Example 1 Let Σ = (S1, S2, S3, S4) be such that:

S1 = {a ∨ b}

S3 = {¬b, d ∨ e}

S4 = {b ∨ d, e}.

• S1∪S2 is consistent whereas S1∪S2∪S3 is not. According to the possibilistic policy, we stop at the first stratum where we meet inconsistency thus ΣPO = S1 ∪ S2 = {a ∨ b, ¬a, c}.
• As for the linear order policy, we delete S3 and continue the treatment with the other strata. S1 ∪ S2 ∪ S4 is consistent so ΣLO = S1 ∪S2 ∪S4 = {a∨b, ¬a, c, b∨d, e}.

Definition 4 Let Σ = (S1, . . . , Sk) be a SBB and Ψ a formula.

• Ψ is a consequence of Σ w.r.t the possibilistic policy, denoted by Σ |=PO Ψ, iff ΣPO |= Ψ.
• Ψ is a consequence of Σ w.r.t the linear order policy, denoted by Σ |=LO Ψ, iff ΣLO |= Ψ.

Example 2 Let us consider again the stratified belief base Σ given in Example 1. For the first inference relation, we have for instance, Σ |=PO b. As to the second one, we have for example Σ |=LO e.

It is easy to see that |=LO goes beyond |=PO, namely for each propositional formula Ψ, if Σ |=PO Ψ then Σ |=LO Ψ.

A key issue in possibilistic logic is how to compute the certainty degree associated with inferred formulas:

Definition 5 Let Σ = (S1, . . . , Sk) be a stratified belief base and Ψ be a formula. Ψ is a weighted consequence of Σ to a degree i, denoted by Σ |=we (Ψ, i), iff:

a) S1 ∪ . . . ∪ Si is consistent; b) S1 ∪ . . . ∪Si |=Ψ; c) ∄j < i : S1 ∪ . . . ∪Sj |=Ψ.

Lastly, in possibilistic logic we are also interested in computing possibilistic conditioning. Namely,

Definition 6 Let e be a consistent term. Then Ψ is a conclusion of conditioning Σ by e to a rank i iff Σ ∪ S0 = {e} |=we (Ψ, i), where S0 is a new and high important stratum.

Possibilistic conditioning inference is an important concept in possibilistic theory. It is, to some extent, the logical counterpart of possibilistic propagation algorithms in possibilistic networks.

Following [Nebel, 1998; Lang, 2000], deciding the possibilistic inference is Δp2 [O(log n)]-complete : it needs at most log2 n calls to SAT solver. As for the linear order one, it is more expensive from a computational point of view. Indeed, deciding it is a Δp2 -complete which means that it can be decided in polynomial time using NP oracles [Nebel, 1994]. We refer the reader to [Papadimitriou, 1994] for more details about computational complexity.

3 Knowledge Compilation

The key motivation of Knowledge compilation is that a knowledge base is not modified very often, and the same base is used to answer many queries (see [Cadoli and Donini, 1997] for a survey). So, the idea of knowledge compilation is to split query answering into two phases:

• first, the knowledge base is preprocessed to obtain an appropriate data structure. Such a phase is called off-line reasoning.
• the second phase which is called on-line reasoning, consists in answering queries using the data structure generated during the first phase.

A target compilation language is a class of formulas which is tractable for clause deduction at least. Stated otherwise, it is a language which permits at least achieving clausal deduction in polynomial time.

Initially, the well-known prime implicates language (PI for short) was the target compilation language on which most of the compilation methods focus. Recently, Darwiche and Marquis have considered in [Darwiche and Marquis, 2002] other target compilation languages. These languages are special cases of the NNF ( Normal Negation Form) language obtained by imposing some properties. A NNF formula is a formula constructed with literals using only the conjunction and disjunction operators. As to the properties, one can list decomposability, determinism, smoothness, decision, order, etc.

The resulting target compilation languages are DNF, DNNF, d-DNNF, sd-DNNF, FBDD, OBDD, OBDD<, MODS, PI and IP. Additionally, they are compared in terms of their spacial efficiency via the succinctness criteria and also in terms of the set of logical queries and transformations they support in polynomial time.

With the exception of PI, DNNF is the most succinct among all target compilation languages. In fact, it is known that PI is not more succinct than DNNF, but it is unknown whether DNNF is more succinct than PI. A sentence in DNNF (for Decomposable NNF) is a NNF sentence satisfying the decomposability property: for each conjunction C in the sentence, the conjuncts of C do not share variables [Darwiche, 2001].

4 Compiling Stratified Belief Bases under the Linear Order Policy

A classical way to compile a SBB under the linear order (resp. possibilistic logic) policy consists first in generating the preferred consistent subbase with respect to this policy. This step comes down to solve a ΔP2 -complete (resp. Δp2 [O(log n)]- complete) problem. Then we compile the resulting (classical) base into a target compilation language. We stress here that such an effort can not be exploited for handling the possibilistic logic policy. Namely, such approach is not appropriate to compute weighted possibilistic conclusions and possibilistic conditioning.

Our method relies on a propositional encoding of the SBB by adding new variables which the number is equal to the number of its strata. Then we proceed to compiling this propositional encoding into a target compilation language and then generating in polynomial time the base that corresponds to the linear order policy or even to the possibilistic one. The additional variables will be deleted from the final result.

4.1 Propositional Encoding of a Stratified Belief Base

Let Σ = (S1, . . . , Sn) be a SBB. The first step in our compilation method consists in encoding the given base into a classical propositional base denoted by KΣ. This encoding takes advantage of the one recently proposed in [Benferhat and Prade, 2005] for handling an extension of possibilistic logic.

In fact, for each stratum Si, we will introduce a new propositional variable Ai. Intuitively, Ai means something like "the situation is Ai- abnormal". Hence, for each formula Φij from the stratum Si will correspond the propositional formula Φij ∨Ai which can be read as "Φij is true or the situation is Ai-abnormal".

In this paper, (Φij ∨ Ai) will be used as an encoding of the fact that the certainty degree or the priority rank of Φij is Ai. The use of abnormal predicates have been used in several non-monotonic formalisms, e.g., [McCarthy, 1980].

Definition 7 Let Σ = (S1, . . . , Sk) be a SBB. The propositional encoding associated with Σ, denoted by KΣ, is the propositional knowledge base defined by:

We note that generally, the number of strata in a SBB is very low. Hence, the cost of the propositional encoding we propose here is very low too.

Example 3 Let us consider again the SBB Σ given in Example 1. Let A1, A2, A3 and A4 be four propositional variables associated with strata S1, S2, S3 and S4 respectively. Using the above definition, the propositional knowledge base associated with Σ is:

4.2 Conditioning

We review in this section, the operation of conditioning which will be useful for our approach.

Definition 8 The conditioning of a propositional formula Ψ on a consistent term (a conjunction of literals)γ, denoted by CD(Ψ, γ), is the formula obtained from Ψ by substituting every literal of γ in Ψ by ⊤ if it is consistent with γ, by ⊥ otherwise.

Example 4 For instance we have:

• The conditioning of the formula Ψ = (¬a∧¬b)∨(b∧c) on the term γ = ¬a ∧ c, CD(Ψ, γ), gives (⊤ ∧ ¬b) ∨ (b ∧ ⊤).
• Conditioning the same formula on the term a ∧ ¬b, CD(Ψ, a ∧ ¬b) gives (⊥ ∧ ⊤) ∨ (⊥ ∧ c).

Following [Darwiche and Marquis, 2002], for any target compilation language C considered in [Darwiche and Marquis, 2002], C satisfies conditioning. This means that given a formula Ψ from C and any consistent term γ, we can construct in polytime a formula which belongs to C and is equivalent to CD(Ψ, γ).

Remark 1 In the following, in CD(Ψ, γ), γ is always a literal (an atom or a negated atom).

4.3 Compiling Linear Based Knowledge Bases

Given a stratified belief base Σ, we define its compilation with respect to a given target compilation language C as shown by the following definition:

Definition 9 Let Σ = (S1, . . . , Sk) be a stratified belief base and KΣ be its propositional encoding using Definition 7. Let C be any target compilation language. The compilation of Σ w.r.t. C, denoted by CompCΣ , is the compilation of KΣ into C, i.e., C(KΣ).

We propose now the following algorithm which provides an efficient way to generate ΣLO using CompCΣ and conditioning:

Algorithm 1: Computing ΣLO Data: CompCΣ Result: The compilation of ΣLO Begin K ← CompCΣ ; for i ← 1 to k do if K |= Ai thenK ←CD(K,Ai); else K ← CD(K, ¬Ai ); end return K; end

Proposition 1 The propositional knowledge base returned by Algorithm 1 is equivalent to ΣLO given by Definition 3.

Proposition 1 shows the equivalence of the knowledge base returned by the Algorithm 1 and ΣLO. Let us briefly explain the algorithm. It proceeds stratum per stratum and generates progressively the compiled base w.r.t. the linear order policy. The test in step 3 checks whether the stratum Si is inconsistent (with previously accepted beliefs). If it is the case, then all formulas of such stratum are ignored by replacing Ai ∨Φij by ⊤∨Φij , which is equivalent to a tautology. If it is not the case, theΦij are retained sinceAi∨Φij is replaced by⊥∨Φij which is equivalent to Φij.

Let us illustrate the above algorithmwith the following example:

Example 5 Let Σ = (S1, S2, S3) be such that S1 = {¬a ∨ b, a} S2 = {¬b, c} and S3 = {¬b ∨ ¬d}. It is easy to check that:

Let A1,A2 and A3 be three propositional variables associated with S1, S2 and S3 respectively.

KΣ = {¬a∨ b ∨A1, a∨A1, ¬b ∨A2, c ∨A2, ¬b ∨¬d∨A3}. Let C = DNNF so let us compute CompDNNF Σ , we get : K = CompDNNF Σ = DNNF(KΣ) = (¬b ∧ A1 ∧ (c ∨ A2)) ∨ (b ∧ A2 ∧ (a ∨ A1) ∧ (¬d ∨ A3)).

• At the first iteration, we have K ⊭ A1 so K ← CD(K, ¬A1) = b ∧ A2 ∧ a ∧ (¬d ∨ A3)
• At the second iteration, K |= A2 implies that K ← CD(K, A2) = b ∧ a ∧ (¬d ∨ A3)
• At the third iteration, we have K ⊭ A3 thus K ← CD(K, ¬A3) = b ∧ a ∧ ¬d.

One can easily check that K is equivalent to ΣLO.

Proposition 2 Algorithm 1 is achieved in polynomial time in the size of CompCΣ . Moreover, the propositional base returned by Algorithm 1 belongs to the target compilation language C.

The corresponding proof is as follows. For all target compilation language C, C satisfies conditioning [Darwiche and Marquis, 2002]. This means that CD(K,Ai) (or CD(K, ¬Ai)) can be achieved in polynomial time and K still belongs to C. In addition, since Ai is a clause, the deduction test K |= Ai can be achieved in polynomial time. □

Since ΣLO belongs to a target compilation language, the inference from a stratified belief base Σ interpreted under the linear order policy falls from Δp2 down to P when queries are in a CNF form.

It is important to note that the cost induced here is only the one of the computation of CompCΣ , i.e., the cost of the compilation of the propositional base KΣ into the language C. The choice of the target compilation language is determined only via its concision. Hence, DNNF may be more interesting than the other languages in this case.

5 Computing Possibilistic Conclusions and Possibilistic Conditioning

5.1 Computing Possibilistic Inference

Compiling possibilistic knowledge bases has been recently achieved in [Benferhat and Prade, 2006]. In this section, we propose an alternative approach which offers several advantages with respect to the existing ones (see related works section). Contrary to the approach proposed in [Benferhat and Prade, 2006], our approach does not add binary clauses. Moreover, our approach is flexible since it supports all target compilation languages. Lastly, our approach allows the computation of possibilistic conditioning.

In fact, we suggest deriving another algorithm from Algorithm 1 where once we meet an inconsistency for the first time, we suppress the current stratum responsible of the inconsistency but also all the remaining strata.

Algorithm 2 : Computing ΣPO Data: CompCΣ Result: The compilation of ΣPO Begin K ← CompCΣ ; i ←1 ; while K ⊭ Ai and i ≤ k do K ← CD(K, ¬Ai); i ← i + 1; end while i ≤ k do K ← CD(K, Ai); i ← i + 1; end return K; end

Proposition 3 The propositional knowledge returned by the Algorithm 2 is equivalent to ΣPO given by Definition 2 and belongs to C. Also, Algorithm 2 runs in polynomial time.

Example 6 Let us consider again the SBB Σ given in Example 5. We can easily check that: ΣPO = {¬a ∨ b, a}. CompDNNF Σ = (¬b∧A1 ∧(c∨A2))∨(b∧A2 ∧(a∨A1)∧ (¬d ∨ A3)). Until the second iteration, namely until meeting an inconsistency, the process is the same as the linear order policy so K = b∧a∧(¬d∨A3). From here, all the remaining strata are ignored thus K ← CD(K, A3) = b∧a. Again one can easily check that K is equivalent to ΣPO.

5.2 CompilingWeighted Consequences and Possibilistic Conditioning

With a simple adaptation, one can still exploit CompCΣ in order to decide the weighted possibilistic inference relation in polynomial time as shown by the following algorithm:

Algorithm 3 : Computing weighted conclusions Data: CompCΣ , a CNF formula Ψ Result: a degree associated with Ψ Begin K ← CompCΣ ; is consequence← false; i ←1 ; while K ⊭ Ai and i ≤ k and is consequence = false do K ← CD(K, ¬Ai); if (K |= Ψ) then is consequence← true; else i ← i + 1; end if is consequence = true thenΨ is a consequence of Σ with a degree i

else Ψ is not a consequence of Σ end One can check that Σ |=we (Ψ, i) using Definition 5 if and only if Ψ is a consequence of Σ to a degree i using Algorithm 3.

Let us check if b is a possibilistic consequence of Σ and to what degree. We can check that Σ |=we (b, 2). Let A1, A2 and A3 be three propositional variables associated respectively with the three strata in the knowledge base. KΣ = {(¬a ∨ b ∨ A1), (a ∨ A2), (c ∨ A2), (¬b ∨ A3)}. Let i = 1 and C =

• At the first iteration, K ⊭ A1. So, K ←CD(K, ¬A1) ≡ (a∧b∧A3 ∧(c∨(¬c∧A2 )))∨(¬a∧A2 ∧(¬b∨(b∧A3 ))). K ⊭ b so i ← i + 1.
• At the second iteration, K ⊭ A2. So, K ←CD(K, ¬A2) ≡ a∧b∧A3 ∧c. K |= b so is consequence← true which stops the loop. We deduce then that b is a possibilistic consequence of Σ to degree 2.

Given a stratified belief base Σ that have been compiled in CompCΣ . We show how we can exploit such a compilation effort in order to support the corresponding possibilistic conditioning by a given observation e in polynomial time.

It is enough to substitute in Algorithm 3 the line

"while K ⊭ Ai and i ≤ k and is consequence = false"

by :

"while K ⊭ ¬e ∨ Ai and i ≤ k and is consequence = false".

Clearly, this adapted algorithm runs in polynomial time since K belongs to a target compilation language and since ¬a ∨Ai is a clause. We can also check that it captures possibilistic conditioning.

6 RelatedWorks and Conclusions

In this paper, we have proposed a method for compiling stratified belief bases with respect to the possibilistic and linear order policies. The cost of the proposed method is very low since the number of new variables that we introduce is equal to the number of the strata which is generally negligible compared to the number of formulas for instance. Furthermore, this method is qualified to be flexible since it permits to exploit efficiently all the existing propositional compilers. In addition, re-partitioning the stratified belief base by permuting some strata priority levels can be done efficiently without a re-compilation cost. However, we can not change the ranks of individual formulas unless we attach one variable per formula.

We have proposed a compilation of possibilistic logic knowledge bases that support weighted conclusions and possibilistic conditioning.

Our method can be favorably compared with other work concerned with compiling stratified belief bases. Note first that contrary to existing approaches, our method allows to compute weighted conclusion and possibilistic conditioning from an already compiled stratified belief base without a recompilation cost. Let us mention the method proposed by Cost-Marquis and Marquis in [Coste-Marquis and Marquis, 2004]. Like ours, it is flexible since it takes advantage of existing propositional knowledge bases compilation methods. On the other hand, this method is more general in the sense that it handles the two remaining preferred coherent subbases selection policies namely the lexicographic and inclusionpreference policies. However, the inherent cost is really expensive. In fact, they introduce a new propositional variable per formula. It is to note that this method was adapted in [Darwiche and Marquis, 2004] to compile weighted knowledge bases in the penalty logic framework.

This paper also brings several improvements regarding the compilation of possibilistic knowledge bases. In this context, a recent method has been introduced in [Benferhat and Prade, 2005]. At the encoding level, the latter uses additionally (k -1) binary clauses. Furthermore, it is based essentially on the use of forgetting variables and forgetting literals operations [Lang et al., 2003] which reduces the number of target compilation languages that can be efficiently exploited. Indeed, this method exploits only the target compilation languages DNNF, DNF, PI and MODS which means that it is less flexible than the ours. Note first that contrary to existing approaches, our method allows to compute weighted conclusion and possibilistic conditioning from an already compiled stratified belief base without a re-compilation cost.

A future work is to extend these works for handling possibilistic conditioning with uncertain input [Dubois and Prade, 1997]. Another future work is to exploit results of this paper in order to provide an alternative implementation of existing propagation algorithms (such as junction trees algorithms) for possibilistic networks.

Acknowledgments: This work is supported by the national project ANR Blanc MICRAC (Mod`eles informatiques et cognitifs du raisonnement causal).