Probabilistic Reasoning with Inconsistent Beliefs Using Inconsistency Measures

1 Introduction

Many branches in artificial intelligence deal with reasoning under uncertainty and inconsistency, e. g., default reasoning [Reiter, 1980], paraconsistent logics [B´eziau et al., 2007], belief dynamics [Hansson, 2001], computational argumentation [Bench-Capon and Dunne, 2007] and probabilistic reasoning [Nilsson, 1986]. Inconsistencies arise easily in many applications, e. g., when several experts share their knowledge in order to solve a problem [Konieczny and Perez, 2011].

We consider the scenario that our knowledge is both uncertain and inconsistent. As a simple example, consider two experts, the one arguing that the price of a stock will probably rise, the other arguing that the price will probably fall. Even though uncertain, taken together both statements are inconsistent. How can a rational agent incorporate both beliefs simultaneously?

To represent uncertain knowledge, we use an extension of classical probabilistic logic [Nilsson, 1986] and consider probabilistic conditionals (ψ | φ)[d] that encode uncertain rules 'if φ then ψ with probability d' [Benferhat et al., 1999; Kern-Isberner, 2001]. Inconsistencies occur in this framework when multiple conditionals cannot be satisfied jointly by a probability function. To deal with inconsistencies, we generalize the probabilistic entailment problem [Jaumard et al., 1991; Lukasiewicz, 1999] to inconsistent knowledge bases by using inconsistency measures [Grant and Hunter, 2013b]. An inconsistency measure I is a function that maps a knowledge base to a non-negative real number such that larger values indicate larger inconsistency. For probabilistic

Matthias Thimm

University of Koblenz-Landau, Germany thimm@uni-koblenz.de

conditional logic, several inconsistency measures have been proposed, see, e. g. [Thimm, 2013; Picado-Mui˜no, 2011]. We apply the family of minimal violation measures from [Potyka, 2014] since they allow us to extend the classical notion of models of a probabilistic knowledge base to inconsistent ones. Intuitively, the generalized models are those probability functions that minimally violate the knowledge base [Potyka and Thimm, 2014]. We incorporate integrity constraints and study a family of generalized entailment problems for probabilistic knowledge bases. More specifically, the contributions of this work are as follows:

1. We introduce the computational problem of generalized entailment with integrity constraints in probabilistic logics and thus provide an approach to reasoning with inconsistent probabilistic knowledge (Section 3).
2. We analyse the behaviour of our approach by showing that it satisfies several rationality postulates (Section 4),
3. We show how to solve the generalized entailment problem and that this is computationally not harder than solving the classical probabilistic entailment problem for consistent knowledge bases (Section 5).

We explain the necessary basics in Section 2, discuss related work in Section 6, and conclude in Section 7.

2 Preliminaries

We consider a propositional language L(At) built up over a finite set of propositional variables At in the usual way. For φ, ψ ∈ L(At) we abbreviate φ ∧ ψ by φψ and ¬φ by φ.

A possible world assigns a truth value to each a ∈ At. Let Ω(At) denote the set of all possible worlds. ω ∈ Ω(At) satisfies an atom a ∈ At, denoted by ω |= a, if and only if ω(a) = true. |= is extended to complex formulas in L(At) in the usual way. Formulas ψ, φ ∈ L(At) are equivalent, denoted by φ ≡ ψ, if and only if ω |= φ whenever ω |= ψ for every ω ∈ Ω(At) and vice versa.

We build up a probabilistic language (L(At) |L(At))pr containing a probabilistic conditional (ψ | φ)[d] for all φ, ψ ∈ L(At) and d ∈ [0, 1]. Intuitively, (ψ | φ)[d] says that if φ is true then ψ is also true with probability d (see below). If φ is tautological, φ ≡ ⊤, we abbreviate (ψ | φ)[d] by (ψ)[d].

A knowledge base K is an ordered finite subset of (L(At) | L(At))pr . We impose an ordering on the conditionals in a knowledge base only for technical convenience. The order can be arbitrary and has no further meaning other than to enumerate the conditionals of a knowledge base in an unambiguous way.

Semantics are given to probabilistic conditionals by probability functions over Ω(At), which are denoted by P(At). The probability of a formula φ ∈ L(At) with respect to P ∈ P(At) is defined by P(φ) = ∑ω|=φ P(ω). As usual in this context, P satisfies a probabilistic conditional (ψ | φ)[d], denoted by P |=pr (ψ | φ)[d], if and only if P(ψφ) = dP(φ) [Nilsson, 1986; Paris, 1994]. A probability function P satisfies a knowledge base K (or is a model of K), denoted by P |=pr K, if and only if P |=pr c for every c ∈ K. Let Mod(K) ⊆ P(At) be the set of models of K. If Mod(K) = ∅ then K is called inconsistent.

Broadly speaking, there are two main approaches to reason with probabilistic logics. First, we can consider the whole set of models Mod(K) of K and use it to derive probability intervals for given formulas [Nilsson, 1986; Jaumard et al., 1991]. Second, we can search for a best model P ∗ ∈ Mod(K) with respect to some common sense rationales and use P ∗ to compute the probabilities directly [Nilsson, 1986; Paris, 1994; Kern-Isberner, 2001]. However, if K is inconsistent, there is no way to infer reasonable information with these approaches because there exists no model at all.

Inconsistency measures help analyzing inconsistent knowledge bases by assigning nonnegative values to knowledge bases that quantify the degree of inconsistency, see, e. g., [Knight, 2002; Hunter and Konieczny, 2010; Thimm, 2013]. The family of minimal violation measures is defined by measuring the violation of the equations defined by the probabilistic satisfaction relation [Potyka, 2014]. To understand how, note that the condition P(ψφ) = dP(φ) is a linear constraint over P. With a slight abuse of notation, let us identify P with a probability vector (P(ω1) . . . P(ωn)), n = |Ω(At)|; and for a formula F, let the indicator function 1{F}(ω) map to 1 iff ω |= F and to 0 otherwise. Then we can rewrite P(ψφ) = dP(φ) in vector notation as acP = 0, where ac is the transpose of the vector

see also [Nilsson, 1986; Jaumard et al., 1991]. Now given a knowledge base K, we associate K with the (m × n)-matrix

The linear equation system AKx = 0 can be solved by a probability vector P if and only if K is consistent, see also [Nilsson, 1986; Jaumard et al., 1991]. The minimal violation value I pΠ(K) of K with respect to the minimal violation measure I pΠ is the solution of the following optimization problem

where ‖.‖p denotes the p-norm defined by ‖x‖p = p√∑ni=1 |xi|p for p ≥ 1. Well-known special cases are the 1-norm ‖x‖1 = ∑ni=1 |xi|, the Euclidean norm ‖x‖2 = 2√∑ni=1 x2i and the limit for p → ∞, the maximum norm ‖x‖∞ = max{|xi| | 1 ≤ i ≤ n}.

Note that the constraints of (1) guarantee that each feasible solution is a probability vector. By definiteness of norms, it holds I pΠ(K) = 0 iff there is a P such that AKP = 0, i. e., iff K is consistent. As K becomes 'more' inconsistent, I pΠ(K) increases continuously, see [Potyka, 2014] for the details and further properties.

The probability functions minimizing (1) can be regarded to be as close as possible to a model of K in the sense that they minimally violate the corresponding equation system. In fact, if K is consistent, they correspond to the models of K and are therefore called generalized models of K [Potyka and Thimm, 2014]. More formally, the set of generalized models is defined as follows:

In [Potyka and Thimm, 2014] generalized maximum entropy reasoning is considered. That is, among all generalized models one selects the one maximizing entropy. The generalized maximum entropy model can be used to repair the knowledge base or to compute probabilities for arbitrary formulas. This approach has some nice properties and can be computed by convex programming techniques [Potyka and Thimm, 2014].

3 Generalized Entailment with Integrity Constraints

We will now focus on generalizing the second major approach to reason with consistent knowledge, namely reasoning with all models. This problem is usually called the probabilistic entailment problem [Jaumard et al., 1991].

Given a consistent knowledge base K and a query (ψ | φ), φ, ψ ∈ L(At), the probabilistic entailment problem is to find a tight probability interval [l, u] such that P(ψ | φ) ∈ [l, u] for all P ∈ Mod(K) with P(φ) > 0 [Jaumard et al., 1991; Lukasiewicz, 1999]. 'Tight' means that the probability interval cannot be further decreased without violating the condition [Lukasiewicz, 1999]. This condition is important for otherwise the interval [0, 1] always yields a feasible and completely non-informative solution. We denote the classical probabilistic entailment relation by |=c , i. e., if [l, u] is the corresponding tight probability interval, we write K |=c (ψ | φ)[l, u]. If there is no P ∈ Mod(K) with P(φ) > 0, we follow [Lukasiewicz, 1999] and let l = 1, u = 0.

By replacing Mod(K), with the generalized models GModp (K), the generalized entailment problem can be defined. The lower and upper bounds l and u can be obtained by solving the two optimization problems

where opt stands for min and max, respectively. We want to consider a slightly more general problem. In addition to our knowledge base K, which might be inconsistent, we consider a second knowledge base IC which is assumed to be consistent. The conditionals in IC are called integrity constraints. To begin with, we generalize some basic concepts.

Definition 1 (Minimal Violation Measures with Integrity Constraints). The minimal violation value I p IC (K) of K with respect to the minimal violation measure I p IC with integrity constraints IC is the solution of the optimization problem

Definition 2 (Generalized Models with Integrity Constraints). The set of probability functions minimizing (3) is called the set of generalized models of K with respect to the integrity constraints IC and is denoted by GModpIC (K), that is,

Proposition 1. Let IC be a set of integrity constraints.

1. If IC = ∅, then I p IC = I pΠ and GModpIC (K) = GModp (K) for all knowledge bases K.
2. GModpIC (K) is always non-empty, compact and convex.
3. If K∪ IC is consistent, GModpIC (K) =Mod(K∪ IC).

Proof sketch. 1. follows immediately from the fact that Mod(∅) = P(At) and the definitions. 2. and 3. follow exactly like the corresponding properties of GModp (K) obtained in [Potyka, 2014] and [Potyka and Thimm, 2014].

Now we can define the generalized entailment problem with integrity constraints.

Definition 3 (Generalized entailment problem with integrity constraints). Given a knowledge base K, integrity constraints IC and a query (ψ | φ), φ, ψ ∈ L(At), the generalized entailment problem with integrity constraints is to solve

where opt stands for min and max respectively.

We denote the generalized entailment relation by |=pIC , i. e., if l and u are the lower and upper bounds obtained from (4), we write K |=pIC (ψ | φ)[l, u]. As before, if there is no P ∈ GModpIC (K) with P(φ) > 0, we let l = 1, u = 0.

Before looking at this problem in more detail, we consider some examples to illustrate that generalized entailment can yield reasonable results even if K is inconsistent. By reasonable we mean that the generalized entailment results can be regarded as merging contradictory opinions. The way in which the opinions are merged depends on the selected pnorm. How should we choose p? Intuitively, p = 1 takes the violation of all opinions into account without regarding how strong a single opinion is violated. On the other extreme, p = ∞ takes only the maximal violation of a single opinion into account and ignores the overall violation of all opinions. p = 2 yields a good balance between both extremes.

Example 1. Suppose we have some experts with different opinions on the probability of some event A, say, that the price of a stock rises. We consider the knowledge bases K1 = 〈(A)[0], (A)[1]〉, K2 = 〈(A)[0.1], (A)[0.8]〉, K3 = 〈(A)[0.1], (A)[0.8], (A)[0.7]〉, K4 = 〈(A)[0.1], (A)[0.8], (A)[0.9]〉, K5 = 〈(A)[0.1], (A)[0.8], (A)[0.8]〉, In K1 both experts are completely convinced of their opinion. In K2 both experts choose a more conservative formulation and in K3, K4 and K5 we have a third expert who also thinks that A is rather likely. We do not need any integrity constraints and set IC = ∅. Table 1 shows generalized entailment results for the query (A) and p = 1, 2, ∞.

For p = 1, we get most conservative results. For two experts, the whole interval between both opinions is possible. If we add a third expert, the results corresponds to the median of the experts' opinions. As p increases, larger violations are penalized more heavily and we end up with point probabilities somewhere between the experts' opinions. Finally, for p = ∞, only the maximal violation counts and so there is no difference between K2, K3 and K5 since the extreme opinions are represented by probabilities 0.1 and 0.8 in each case.

Example 2. Let us consider the Nixon diamond. We believe that quakers (Q) are usually pacifists (P) while republicans (R) are usually not. However, we know that Nixon (N) was both a quaker and a republican. We do not doubt the existence of Nixon and therefore consider the integrity constraint IC = 〈(N)[1]〉. The remaining knowledge is represented as follows: K = 〈(P |Q)[0.9], (P |R)[0.1], (QR|N)[1]〉. Table 2 shows the generalized entailment results.

Again, p = 1 yields most conservative results. For p > 1, we maintain the knowledge that quakers are probably pacifists and that republicans are probably not.

Example 3. We consider a variant of Kyburg's Lottery Paradox [Kyburg, 1992] similar to [Knight, 2002]. There is a lottery and exactly one player will win. However, for a particular player p, we do not believe that p will win. We model the lottery paradox with k players by the knowledge base Kk = 〈(p1)[0], . . . , (pk)[0]〉, where pk expresses that player k will win. The fact that one player will win is represented as an integrity constraint, i. e., ICk = 〈(∨ki=1 pi)[1]〉. As the number of players goes to infinity, the degree of inconsistency of the knowledge base goes to 0. If we perform generalized entailment to compute the probability that a particular player will win, the probability is equal for each player. Table 3 shows the results for different k.

Since the knowledge base does not favor any player, we cannot conclude anything for p = 1. For p > 1, the probability that a player wins is uniformly distributed as one would expect under the given premises.

4 Analysis

Our proposal of the generalized entailment relation |=pIC aims at extending the classical entailment relation |=c to inconsistent knowledge bases. The examples at the end of the previous section suggest that generalized entailment results are also intuitive in the case of inconsistency. In the spirit of other non-classical reasoning approaches like, e. g., [Kraus et al., 1990], we will now propose a set of rationality postulates that each probabilistic entailment relation |=IC should satisfy that extends probabilistic entailment to inconsistent knowledge bases while maintaining integrity constraints IC.

Let ⊎ denote disjoint union, i. e., A = A1 ⊎ A2 means A = A1 ∪ A2 and A1 ∩ A2 = ∅. We consider the following postulates for a probabilistic entailment relation |=IC.

1. Consistency: If K∪ IC is consistent, then it holds (K∪ IC) |=c (ψ | φ)[l, u] iff K |=IC (ψ | φ)[l, u].
2. Integrity: For all (ψ | φ)[d] ∈ IC, it holds that either K |=IC (ψ | φ)[d, d] or K |=IC (φ)[0, 0].
3. Consistent Independence: Let At = At1 ⊎ At2 and let K = K1 ⊎ K2 such that Ki is a knowledge base over L(Ati), i = 1, 2. If Ki ∪ IC is consistent and (ψi | φi) is a query over L(Ati), then Ki ∪ IC |=c (ψi | φi)[l, u] holds in L(Ati) iff K |=IC (ψi | φi)[l, u] holds in L(At).
4. Independence: Let At = At1 ⊎ At2 and let K = K1 ⊎K2 such that Ki is a knowledge base over L(Ati), i = 1, 2. If (ψi | φi) is a query over L(Ati), then K |=IC (ψi | φi)[l, u] holds in L(At) if and only if Ki |=IC (ψi | φi)[l, u] holds in L(Ati).
5. Continuity: If K is 'close' to a consistent knowledge base K0 such that (K0 ∪ IC) |=c (ψ | φ)[l0, u0], (K0 ∪ IC) ̸|=c (φ)[0, 0] and K |=IC (ψ | φ)[l, u], then [l, u] is 'close' to [l0, u0].

Consistency states that the extended entailment relation should agree with probabilistic entailment if the given information is consistent. Integrity assures that all integrity constraints are either obeyed or not applicable at all (then K |=IC (ψ | φ)[1, 0]). Consistent Independence states that consistency remains true for subsets of the language if there is only consistent information about this subset. Independence states that knowledge about a subset of the language should not influence entailment results about the remaining language. In particular, this property can be exploited to decompose the extended entailment problem into two smaller problems. Continuity says that if K0 is consistent and does not classically entail P(φ) = 0, then minor changes in K0 shall not result in major changes in the entailed probability P(ψ | φ) even if K0 becomes inconsistent. Since the definition of closeness is very subtle in this context, it will be discussed later on in more detail. We have the following relationships between our postulates.

Proposition 2.

1. Consistent Independence implies Consistency.
2. Consistency and Independence implies Consistent Independence.

Proof. 1 follows immediately by letting At2 = K2 = ∅. To prove 2, note that by Independence, generalized entailment w.r.t. K over L(At) is equivalent to generalized entailment w.r.t. K1 over L(At1). But since K1 is consistent, the claim follows with Consistency applied to K1 over L(At1).

Note that there are some interesting relationships to other properties. Consistent Independence implies Reflexivity [Kraus et al., 1990], i. e., if (ψ | φ)[p] is a satisfiable conditional and contains no atoms mentioned in K, then K ∪ {(ψ | φ)[p]} |=IC (ψ | φ)[p, p]. Independence implies Language Invariance [Paris, 1994], i. e., just adding additional atoms to the language does not change the entailment results.

Generalized entailment satisfies our first four desiderata.

Theorem 1. The generalized entailment relation |=pIC satisfies Consistency, Integrity, Consistent Independence and Independence.

Proof sketch. To prove consistency, note that Proposition 1, 3, implies that GModpIC (K) =Mod(K∪IC). But then (4) is just the definition of the probabilistic entailment problem.

Integrity follows from GModpIC (K) ⊆ Mod(IC).

By consistency and Proposition 2, Consistent Independence follows from Independence.

To prove Independence, show that for each probability function P over Ω(At) that satisfies K, there are corresponding probability function Pi over Ω(Ati) that satisfy Ki, i = 1, 2 and agree with P for all formulas from L(Ati) and vice versa. To get from P to Pi just marginalize. To get from P1 and P2 to P let P(ω) = P1(ω|At1 ) · P2(ω|At2 ). To meet space restriction, we leave out the details of the proof.

To prove continuity, we need a more precise notion of closeness of knowledge bases. However, using a too strong notion of closeness, continuity cannot be satisfied by any extended entailment relation that extends probabilistic entailment in a reasonable way, because even probabilistic entailment behaves discontinuously in some cases. Consider the following non-trivial example from [Paris, 1994] 1 .

Example 4. Consider a disease d, a symptom s and a possible complication c. Let K contain the conditionals (d | s)[0.75], (d | s)[0.25], (cd | s)[0.15], (c | ds)[0.6], (c | ds)[0.8] and (cd | s)[0.1]. K is consistent and, for instance, K |=c (s)[0, 1]. However, if we construct K′ from K by replacing (cd | s)[0.1] with (cd | s)[0.0999], we have K |=c (s)[0, 0]. Such discontinuities are connected to each conditional in K, see [Paris, 1994], p. 90, for more details.

To exclude such discontinuities, Paris defined convergence of knowledge bases as follows: (Ki) converges to K iff (Mod(Ki)) converges to Mod(K) with respect to the Blaschke metric. Roughly speaking, S1, S2 ⊆ Rn have Blaschke distance d, ‖S1, S2‖B = d, iff for every x1 ∈ S1, there is a x2 ∈ S2 such that ‖x1 - x2‖2 ≤ d and vice versa. By replacing the models with the generalized models in this notion of convergence, we obtain the following weak form of continuity for generalized entailment.

Theorem 2 (Weak Continuity). Let (Ki) be a sequence of knowledge bases such that (GModpIC (Ki)) converges to GModpIC (K) with respect to the Blaschke metric. If K ̸|=pIC (φ)[0, 0], K |=pIC (ψ | φ)[l, u] and Ki |=pIC (ψ | φ)[li, ui], then li and ui converge to l and u, respectively.

Proof sketch. For ease of notation, let G = GModpIC (K) and Gi = GModpIC (Ki). The claim follows from (A), where

(A) for all ϵ > 0 that are sufficiently small, there is a δ > 0 such that ‖G, Gi‖B < δ implies that for all P ∈ G (P ′ ∈ Gi) with P(φ) > 0 (P ′ (φ) > 0) there is a P ′ ∈ Gi (P ∈ G) such that |P (ψ | φ) - P ′ (ψ | φ)| < ϵ

We know from Real Analysis that ‖x‖1 ≤ √n ‖x‖2 for all x ∈ Rn . Note also that |P(F) - P ′ (F)| ≤ ‖P - P ′ ‖1 for all F ∈ L(At). Therefore, ‖G,Gi‖B < ϵ/√n implies that for all P ∈ G (P ′ ∈ Gi), there is a P ′ ∈ Gi (P ∈ G) with |P(F) -P ′ (F)| < ϵ. Since K ̸|=pIC (φ)[0, 0], there is a P ∈ G with P(φ) > 0. Hence, if δ < P(φ) 2√n , there is a P ′ ∈ Gi with P ′ (φ) > P(φ)/2 > 0. Hence, if δ is sufficiently small, both [l, u] and [li, ui] are non-trivial. Finally, check that for 0 < ϵ < 1 and δ < ϵ P(φ) 4√n (δ < ϵPi(φ) 4√n ), (A) holds.

Note that if (K ∪ IC) is consistent, Consistency implies that (K ∪ IC) ̸|=pIC (φ)[0, 0] and (K ∪ IC) |=c (ψ | φ)[l, u], so that li and ui converge to the probabilistic entailment result as demanded in Convergence.

5 Computational Aspects

We cannot expect to find highly efficient algorithms for the generalized entailment problem, since even the probabilistic satisfiability problem is NP-hard [Georgakopoulos et al.,

1 The example was originally proposed in P. Courtney, Doctoral thesis, Manchester University, Manchester, U.K., 1992.

1988]. However, it is interesting to ask how much more difficult is the generalized entailment problem as compared to the probabilistic entailment problem.

Our first goal is to show that the generalized entailment problem can be solved by linear programming techniques. To do so, we introduce a vector aF = (1{F}(ωj))1≤j≤n for each formula F. Note that aFP = P(F), see also [Nilsson, 1986; Jaumard et al., 1991]. We will also need the following lemma, which is a straightforward generalization of [Potyka and Thimm, 2014], Lemma 1.

Lemma 1. Let K be a knowledge base, let IC be a set of integrity constraints and let 1 < p < ∞. Let P ∈ GModpIC (K) be a generalized model and let x = AKP. Then it holds AKP ′ = x for all P ′ ∈ GModpIC (K) and we call x = xpK the violation vector of K.

Theorem 3. The generalized entailment problem with integrity constraints has a well-defined solution and (4) is equivalent to the following linear programs, where ϵp = I p IC (K), Rn+ denotes the non-negative real vectors and opt stands for min and max, respectively.

• For p = 1, (4) is equivalent to

• For 1 < p <∞, (4) is equivalent to

In particular, the linear programs are feasible if and only if there is a P ∈ GModpIC (K) with P (φ) > 0.

Proof sketch. To begin with, recall that GModpIC (K) ̸= ∅ is guaranteed. (4) can be rewritten as

To get rid of the non-linear constraint ‖AKx‖p = ϵp, we can apply Lemma 1 for 1 < p < ∞, to replace ‖AKx‖p = ϵp with AKP ′ = xpK. For p = 1 and p = ∞, we can exploit piecewise linearity to replace ‖AK x‖1 = ϵ1 with the constraints -y ≤ AK x ≤ y and ∑mi=1 yi = ϵ1, where y ∈ Rm; and to replace ‖AK x‖∞ = ϵ∞ with -ϵ∞ ≤ AK x ≤ ϵ∞.

To get rid of the non-linear objective, we can apply a result from [Charnes and Cooper, 1962], which is also used to solve the probabilistic entailment problem [Jaumard et al., 1991]. Basically, the feasible solutions are scaled such that aφ x = 1 holds. Then aψφ x aφ x equals aψφ x. This transformation does not change the optimal objective as the scaling factor cancels out in the fraction, see [Charnes and Cooper, 1962] for details.

Equivalence of the linear programs with (2) follows with the arguments sketched above and guarantees that all linear programs are feasible if and only if P(φ) > 0 for some P ∈ GModpIC (K). If there is some P ∈ GModpIC (K) with P(φ) > 0, existence of the solutions follows from the theory of linear programming.

Now let us look at the cost of solving the generalized entailment problem. Reasoning is usually a two-stage process. First, we test satisfiability, then we perform a reasoning algorithm. In our approach, the satisfiability phase is replaced with an inconsistency measuring phase. To compute minimal violation measures, we have to solve a linear program for p ∈ {1, ∞}, a quadratic program for p = 2 and a convex program for other p, see [Potyka, 2014] for details. Probabilistic satisfiability, probabilistic entailment and generalized entailment can be computed by linear programs. Expected costs when using standard algorithms are summarized in Table 4. For linear programs, we consider estimates proposed in [Matousek and G¨artner, 2007] for the Simplex algorithm. For quadratic and convex programs, we use estimates proposed in [Boyd and Vandenberghe, 2004] for interior-point methods. The cost is estimated with respect to the number of optimization variables n and the number of constraints m. Note that we have to introduce additional slack variables for linear programs whenever inequalities are present.

In practice, |Ω| is the dominating factor because it depends exponentially on the number of propositional variables |At| in our language. In contrast, |K| usually grows at most polynomially in |At|. In fact, whenever |K| > |Ω| the knowledge base is overdetermined in the sense that it either contains redundant information (AK does not have full rank) or it leaves no degrees of freedom (AKx has at most one solution). Taking this into account, we see that computing minimal violation measures for p = 1 and p = ∞ is asymptotically not harder than testing satisfiability. Similarly, performing generalized entailment, when the inconsistency values are known, is asymptotically not harder than performing probabilistic entailment. In fact, for 1 < p < ∞, we get basically the same cost because the violation constraints can be represented by linear equalities as explained in Lemma 1. To deal with larger instances of the generalized entailment problem, we can exploit Independence and apply column generation techniques to reduce the exponential influence of |At| on |Ω| [Hansen and Perron, 2008; Finger and De Bona, 2011; Cozman and Ianni, 2013].

6 RelatedWork

An overview of inconsistency measures for classical logics can be found in [Grant and Hunter, 2013b], an overview of measures for probabilistic logics in [Thimm, 2013]. The idea of generalized reasoning transfers primarily to approaches that measure inconsistency by a notion of distance from interpretations to actual models. An interesting family of such measures for classical logics has been proposed in [Grant and Hunter, 2013a]. The idea is to extend the models of single formulas in the knowledge base until the intersection for all formulas is non-empty. The resulting set can be understood as a classical notion of a set of generalized models and it is interesting to ask if reasonable generalized inference relations for classical logics can be derived. Note also that minimal violation measures have recently been generalized to languages allowing probability intervals [l, u], 0 ≤ l ≤ u ≤ 1 rather than point probabilities [d] and some properties have been strengthened in this framework [De Bona and Finger, 2014].

To deal with inconsistencies in classical logics, several approaches have been proposed. For instance, one can introduce new connectives, consider consistent subsets of the knowledge base or apply belief merging approaches [Konieczny et al., 2005; B´eziau et al., 2007; Konieczny and Perez, 2011]. For probabilistic logics, several revision, fusion and merging approaches have been considered, see, for instance, [KernIsberner and R¨odder, 2004; Weydert, 2011; Wilmers, 2015].

The idea of generalizing the notion of a probabilistic model has also been employed in [Daniel, 2009]. There, reasoning in inconsistent probabilistic knowledge is realized by a fuzzy notion of a model and this is used to generalize reasoning based on the principle of maximum entropy. However, the general probabilistic entailment problem and computational issues are not discussed in [Daniel, 2009].

7 Summary

We defined the generalized entailment problem with integrity constraints and showed that it satisfies several desirable properties. These properties seem to be reasonable desiderata for each approach that extends probabilistic entailment to inconsistent knowledge bases. Generalized entailment satisfies only a weak form of continuity, but this seems to be true for all reasonable extensions because of discontinuities that are inherent to the probabilistic entailment problem. Computationally, generalized entailment for p = 1,∞ is barely harder than performing a probabilistic satisfiability test and probabilistic entailment.

The approach proposed in this paper has been implemented in Java and is available as open source 2 .