On the Expressivity of Inconsistency Measures (Extended Abstract)

1 Introduction

Inconsistency measurement is about the quantitative assessment of the severity of inconsistencies in knowledge bases. Consider the following two knowledge bases K1 and K2 formalised in propositional logic:

Both knowledge bases are classically inconsistent as for K1 we have {a, ¬a ∧ ¬b} |=⊥ and for K2 we have, e. g., {a, ¬a} |=⊥. These inconsistencies render the whole knowledge bases useless for reasoning if one wants to use classical reasoning techniques. In order to make the knowledge bases useful again, one can either rely on non-monotonic/paraconsistent reasoning techniques [Makinson, 2005; Priest, 1979] or one revises the knowledge bases appropriately to make them consistent [Hansson, 2001]. Looking at the knowledge bases K1 and K2 one can observe that the severity of their inconsistency is different. In K1, only two out of four formulas (a and ¬a ∧ ¬b) are "participating" in making K1 inconsistent while for K2 all formulas contribute to its inconsistency. Furthermore, for K1 only two propositions (a and b) are conflicting and using e. g. paraconsistent reasoning one could still infer meaningful statements about c and d. For K2

∗This paper is an extended abstract of an article in the Artificial Intelligence Journal [Thimm, 2016a].

no such statement can be made. This leads to the assessment that K2 should be regarded more inconsistent than K1.

Inconsistency measures can be used to analyse inconsistencies and to provide insights on how to repair them. An inconsistency measure I is a function on knowledge bases, such that the larger the value I(K) the more severe the inconsistency in K. A lot of different approaches of inconsistency measures have been proposed, mostly for classical propositional logic [Hunter and Konieczny, 2004; 2008; 2010; Ma et al., 2009; Mu et al., 2011; Xiao and Ma, 2012; Grant and Hunter, 2011; 2013; McAreavey et al., 2014; Jabbour et al., 2014], but also for classical first-order logic [Grant and Hunter, 2008], description logics [Ma et al., 2007; Zhou et al., 2009], default logics [Doder et al., 2010], and probabilistic and other weighted logics [Ma et al., 2012; Thimm, 2013; Potyka, 2014]. Due to this plethora of inconsistency measures it is hard to determine which measure to use for an application and which measure is meaningful. Rationality postulates have been proposed that address the issue of assessing the quality of a measure-see e. g. [Hunter and Konieczny, 2006; Mu et al., 2011]-but many of these properties have been criticised to address only a specific point of view, see [Besnard, 2014] for a recent discussion on this topic.

In this paper, we take a different perspective on the evaluation of inconsistency measures by considering a quantitative analysis of their expressivity, that is, we study howmany different (inconsistent) knowledge bases can be distinguished by a given inconsistency measure. By the term expressivity we here refer to the property of a semantical concepthere, an inconsistency measure-and its capability to distinguish syntactical constructs-here, knowledge bases-, similarly as it has been done for the analysis of expressivity of semantics for other logical languages, see e. g. skepticism relations for formal argumentation [Baroni and Giacomin, 2008]. Our analysis is meant to complement the study on rationality postulates and is, of course, not meaningful on its own as the compliance of measures with the basic intuitions behind inconsistency measures can only be assessed by rationality postulates. However, we introduce expressivity of inconsistency measures as an additional method to evaluate their quality. In particular, we propose four different expressivity characteristics that quantify the relation between the number of different values of an inconsistency measure wrt.

different notions of the size of the knowledge base, such as number of formulas or number of propositions. We conduct a thorough comparative analysis of different inconsistency measures from the literature [Hunter and Konieczny, 2008; 2010; Grant and Hunter, 2011; Knight, 2002; Thimm, 2016b; Grant and Hunter, 2013; Mu et al., 2011; Jabbour and Raddaoui, 2013; Xiao and Ma, 2012; Doder et al., 2010] and classify these measures in a hierarchy of expressivity. In our study, we made several interesting observations, such as the relation between the measure IMI [Grant and Hunter, 2011] and Sperner families [Sperner, 1928] and of the measure IMI C [Grant and Hunter, 2011] with profiles of Boolean functions. One of our results is that the distance-based measure I Σ dalal from [Grant and Hunter, 2013] has maximal expressivity along all considered characteristics.

We give necessary preliminaries in Section 2. In Section 3 we present four different expressivity characteristics and evaluate the considered inconsistency measures wrt. these characteristics. We conclude in Section 4. All inconsistency measures discussed in this paper have been implemented and an online interface to try out these measures is available 1 .

2 Preliminaries

Let At be some fixed propositional signature, i. e., a (possibly infinite) set of propositions, and let L(At) be the corresponding propositional language constructed using the usual connectives ∧ (and), ∨ (or), and ¬ (negation).

Definition 1. A knowledge base K is a finite set of formulas K ⊆ L(At). Let K be the set of all knowledge bases.

If X is a formula or a set of formulas we write At(X) to denote the set of propositions appearing in X. Semantics to a propositional language is given by interpretations and an interpretation ω on At is a function ω : At → {true, false}. Let Ω(At) denote the set of all interpretations for At. An interpretation ω satisfies (or is a model of) a proposition a ∈ At, denoted by ω |= a, if and only if ω(a) = true. The satisfaction relation |= is extended to formulas in the usual way.

For Φ ⊆ L(At) we also define ω |= Φ if and only if ω |= φ for every φ ∈ Φ. Define furthermore the set of models Mod(X) = {ω ∈ Ω(At) | ω |= X} for every formula or set of formulas X. If Mod(X) = ∅ we also write X |=⊥ and say that X is inconsistent.

Let R∞≥0 be the set of non-negative real values including ∞. Inconsistency measures are functions I : K → R∞≥0 that aim at assessing the severity of the inconsistency in a knowledge base K, cf. [Grant and Hunter, 2011]. The basic idea is that the larger the inconsistency in K the larger the value I(K) and I(K) = 0 if and only if K is consistent. However, inconsistency is a concept that is not easily quantified and there have been a couple of proposals for inconsistency measures so far, in particular for classical propositional logic, see e. g. [Besnard, 2014; McAreavey et al., 2014; Jabbour et al., 2014; Hunter et al., 2014] for some recent works. We selected 15 inconsistency measures from the literature in order to conduct our analysis on expressivity, taken from [Hunter and Konieczny, 2008; 2010; Grant and Hunter, 2011; Knight, 2002; Thimm, 2016b; Grant and Hunter, 2013; Mu et al., 2011; Xiao and Ma, 2012; Doder et al., 2010]. We only give the formal definitions of two of those, see [Thimm, 2016a] for the remaining definitions.

1 http://tweetyproject.org/w/incmes/

The drastic measure Id is usually considered as a baseline approach for inconsistency measurement.

Definition 2. The drastic inconsistency measure Id : K → R∞≥0 is defined as

for K ∈ K.

A more fine-grained approach can be devised by taking minimal inconsistent subsets into account. A set M ⊆ K is called minimal inconsistent subset (MI) of K if M |=⊥ and there is no M ′ ⊂ M with M ′ |=⊥. Let MI(K) be the set of all MIs of K.

Definition 3. TheMI-inconsistencymeasure IMI : K→R∞≥0 is defined as

for K ∈ K.

Example 4. Consider the knowledge bases K1 and K2 from

Here we have

Therefore we obtain IMI(K1) = 1 and IMI(K2) = 2.

3 Expressivity Characteristics

In the literature, inconsistency measures are usually analytically evaluated on a set of rationality postulates. 2 Some basic example postulates given in [Hunter and Konieczny, 2006] are the following (let I be any inconsistency measure)

Consistency I(K) = 0 if and only if K is consistent

Monotony if K ⊆ K′ then I(K) ≤ I(K′ )

Satisfaction of the property consistency ensures that all consistent knowledge bases receive a minimal inconsistency value and every inconsistent knowledge base receives a positive inconsistency value (we already implicitly required satisfaction of this postulate in the definition of an inconsistency measure). The postulate monotony states that the value of inconsistency can only increase when adding new information. Independence states that removing "harmless" formulas from a knowledge base does not change the value of inconsistency. Besides these three postulates a series of other postulates have been proposed in the literature, see [Thimm, 2016c] for a recent survey. However, some of these postulates are disputed as each of them usually covers only a single aspect of inconsistency, such as independence, which focuses on the role of minimal inconsistent subsets. An excellent discussion on the rationality of various postulates for inconsistency measures can be found in [Besnard, 2014]. Besides Besnard, several other authors have also criticised the rationality of individual postulates-discussions can be found in almost all papers cited before-and so there is some disagreement on which postulates are meaningful and which are not. One the one hand this calls for more work on rationality postulates and, on the other hand, it also suggests to investigate additional means for comparison. In the following, we propose a novel quantitative approach to evaluate and compare inconsistency measures that aims at complementing the existing approach of rationality postulates.

2 Some few works also consider empirical evaluation on computational performance and accuracy of algorithms approximating existing inconsistency measures, see e. g. [Ma et al., 2009; McAreavey et al., 2014; Thimm, 2016b]

The drastic inconsistency measure Id is usually considered as a very naive baseline approach for inconsistency measurement. Surprisingly, this measure already satisfies many rationality postulates such as consistency, monotony, and independence (the proofs are straightforward). What sets it apart from other more sophisticated inconsistency measures is that it cannot differentiate between different inconsistent knowledge bases. However, this demand is exactly what inconsistency measures are supposed to satisfy. While the qualitative behaviour of inconsistency measures is being discussed quite deeply using rationality postulates, their quantitative properties in terms of expressivity have been almost neglected so far. 3 With expressivity of inconsistency measures we here mean the number of different values an inconsistency measure can attain. We investigate the expressivity of inconsistency measures along four different dimensions of subclasses of knowledge bases.

Definition 5. Let φ be a formula. The length l(φ) of φ is recursively defined as

Definition 6. Define the following subclasses of the set of all knowledge bases K:

3 Some few rationality postulates such as Attenuation [Mu et al., 2011] are addressing this issue only in some very limited form and from a particular point of view.

In other words, Kv (n) is the set of all knowledge bases that mention at most n different propositions, Kf (n) is the set of all knowledge bases that contain at most n formulas, Kl (n) is the set of all knowledge bases that contain only formulas with maximal length n, and Kp (n) is the set of all knowledge bases that contain only formulas that mention at most n different propositions each. The motivation for considering these particular subclasses of knowledge bases is that each of them considers a different aspect of the size of a knowledge base. As a syntactical object, a knowledge base is a set of formulas, and both the number of formulas (considered by the class Kf (n)) and the length of each formula (Kl (n)) are the essential parameters that define its size. From a semantical point of view, the number of propositions appearing in each formula (Kp (n)) and in the complete knowledge base (Kv (n)) define the scope of the knowledge. Larger numbers for both of them also indicate larger scope and thus greater size. Inconsistency measures should adhere to the size of the knowledge base in terms of their expressivity. For example, the number of possible inconsistency values of a particular measure should not decrease when moving from a set Kv (n) to set Kv (n′ ) with n′ > n, as knowledge bases with n′ formulas should provide a larger variety in terms of inconsistency as knowledge bases of size n. Indeed, this property is true for all considered measures as Kv (n) ⊆ Kv (n′ ) (the same holds for all classes above).

The aim of our expressivity analysis is to investigate the number of different values that a specific inconsistency measure can attain on different subclasses of knowledge bases. We formalise this idea using expressivity characteristics as follows.

Definition 7. Let I be an inconsistency measure and n > 0. Let α ∈ {v, f, l, p}. The α-characteristic C α(I, n) of I wrt. n is defined as

In other words, C α(I, n) is the number of different inconsistency values I assigns to knowledge bases from Kα(n). Note that these characteristics are not always the same as the maximal value of an inconsistency measure on a specific set of knowledge bases, even if the codomain of the measure is the natural numbers. Indeed, it can be the case that intermediate values cannot be attained.

We now come to the main contribution of [Thimm, 2016a], which is a thorough study of the considered inconsistency measures in terms of our four proposed expressivity characteristics.

Theorem 8. The α-characteristics C α(I, n) (α ∈ {f, v, l, p}) for the inconsistency measures Id, IMI, IMI C , Iη, Ic, ILPm , Imc, Ip, Ihs, I Σ dalal , I max dalal , I hit dalal , IDf , Imv, and Inc are as shown in Table 1.

The complete proof of the above theorem can be found in [Thimm, 2016a].

Table 1 shows that the measure I Σ dalal has maximal expressivity wrt. all four expressivity characteristics (among the considered inconsistency measures) and, as expected, the drastic inconsistency measure Id is the least expressive one. One can also observe that for many measures the values of C v (I, n) and C f (I, n) are complementary, i. e., if a measure has a high value in C f it has small value in C v (consider e. g. Ic and Ip). This is due to the fact that many measures measure only a specific aspect of inconsistency and usually belong either to the MI-based family of inconsistency measures-which focus on using minimal inconsistent subsets for measuring-or the variable-based family-which focus on conflicting propositions-, cf. [Hunter and Konieczny, 2008]. Therefore, they are constrained in their expressivity if one of these dimensions is limited. For example, if the number of formulas in a knowledge base is restricted, so is the number of minimal inconsistent subsets.

∗ only for n > 1

∗∗ only for n > 3

†Φ(x) is the number of fractions in the Farey series of order x and can be defined as Φ(x) = |{k/l | l = 1, . . . , x, k = 0, . . . , l}|, see e. g. http://oeis.org/A005728

‡Ψ(n) is the number of profiles of monotone Boolean functions of n variables, see e. g. http://oeis.org/A220880

Remark 9. Note that [Thimm, 2016a] also considered the measure IPm [Jabbour and Raddaoui, 2013] and reported it to have maximal expressivity. However, the original publication [Jabbour and Raddaoui, 2013] falsely claimed that IPm satisfies the consistency postulate, which is usually deemed a necessary requirement for inconsistency measures. However, IPm does not comply with this basic property as e. g. for inconsistent KPm = {a, ¬(a ∧ a)}, IPm (KPm) = 0, cf. Definition 2, Proposition 2, and Section 3 in [Jabbour and Raddaoui, 2013]. Therefore, we omit discussing IPm in this paper.

4 Summary and Conclusion

We conducted a focused but extensive comparative analysis of inconsistency measures from the recent literature in terms of their expressivity. For that, we introduced 4 different expressivity characteristics and conducted an analytical evaluation of the considered measures wrt. these expressivity characteristics. Our findings also revealed some interesting relationships of inconsistency measures to, e. g., set theory and monotone Boolean functions, see [Thimm, 2016a] for a discussion. Finally, the measure I Σ dalal [Grant and Hunter, 2013] has been proven to be maximally expressive wrt. all our characteristics.

Expressivity characteristics provide a novel evaluation method for assessing the quality of inconsistency measures. It has to be noted, however, that high expressivity alone is not a sufficient criterion for doing this. It is straightforward to construct measures that exhibit maximal expressivity along all discussed dimensions, but fail to comply with the intuitions one expects from inconsistency measures. The use of rationality postulates-such as the ones presented and discussed in [Hunter and Konieczny, 2006; Mu et al., 2011; Besnard, 2014]-must still serve as first-level evaluation criterion. If measures satisfy the same (or a similar set of) rationality postulates, expressivity can be used to make further quality assessments.

To the best of our knowledge, our work is the most extensive comparative analysis of inconsistency measures so far. All inconsistency measures discussed in this paper have been implemented and an online interface to try out these measures is available 4 .

4 http://tweetyproject.org/w/incmes/