Introduction

Reasoning about exceptions in ontologies: a skeptical preferential approach (Extended Abstract)

DISIT

Introduction

Reasoning about exceptions in ontologies is nowadays one of the challenges the description logics community is facing, a challenge which is at the very roots of the development of non-monotonic reasoning in the 80s. Many non-monotonic extensions of Description Logics (DLs) have been developed incorporating non-monotonic features from most of the non-monotonic formalisms in the literature [ 1, 10, 12, 19, 5, 4, 7, 24, 11, 3, 20, 6, 18, 15, 16 ], or defining new constructions and semantics such as in [ 2 ].

The abstract describes a preferential approach for dealing with exceptions in description logics [ 14 ], where a typicality operator is used to select the typical (or most preferred) instances of a concept. This approach, as well as the preferential approach in [ 5 ], has been developed along the lines of the preferential semantics introduced by Kraus, Lehmann and Magidor [ 21, 22 ].

We focus on the rational closure for DLs [ 7, 9, 6, 16 ] and, in particular, on the construction developed in [ 16 ], which is semantically characterized by minimal preferential models. While the rational closure provides a simple and efficient approach for reasoning with exceptions, exploiting polynomial reductions to standard DLs [ 13 ], the rational closure does not allow an independent handling of the inheritance of different defeasible properties of concepts so that, if a subclass of C is exceptional for a given aspect, it is exceptional tout court and does not inherit any of the typical properties of C.

To cope with this problem Lehmann [ 23 ] introduced the notion of the lexicographic closure, which was extended to DLs by Casini and Straccia [ 8 ], while in [ 17 ] Gliozzi proposed a semantic approach in which models are equipped with several preference relations. The lexicographic closure allows for stronger inferences with respect to rational closure, computing the defeasible consequences in the lexicographic closure may require to compute several alternative bases [ 23 ](namely, consistent sets of defeasible inclusions which are maximal with respect to some specificity ordering).

In this extendedabstract we propose an alternative notion of closure, the skeptical closure, which can be regarded as a skeptical variant of the lexicographic closure. It is a refinement of rational closure which allows for stronger inferences, but it is weaker than the lexicographic closure and its computation does not require to generate all the alternative maximally consistent bases. The construction is based on the idea of building a single base, i.e. a single maximal consistent set of defeasible inclusions, starting with the defeasible inclusions with highest rank and progressively adding less specific inclusions, if consistent, but excluding the defeasible inclusions which produce a conflict at a certain stage without considering alternative consistent bases. 2

The rational closure

We briefly recall the logic ALC + TR which is at the basis of a rational closure construction proposed in [ 16 ] for ALC. The idea underlying ALC + TR is that of extending the standard ALC with concepts of the form T(C), whose intuitive meaning is that T(C) selects the typical instances of a concept C, to distinguish between the properties that hold for all instances of concept C (C ⊑ D), and those that only hold for the typical such instances (T(C) ⊑ D). The ALC + TR language is defined as follows: CR := A | ⊤ | ⊥ | ¬CR | CR ⊓ CR | CR ⊔ CR | ∀R.CR | ∃R.CR, and CL := CR | T(CR), where A is a concept name and R a role name. A KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusions CL ⊑ CR. ABox contains a finite set of assertions of the form CR(a) and aRb, for a, b individual names. The semantics of ALC + TR is defined in terms of rational models: ordinary models of ALC are equipped with a preference relation < on the domain, whose intuitive meaning is to compare the “typicality” of domain elements: x < y means that x is more typical than y. The instances of T(C) are the instances of concept C that are minimal with respect to <. We refer to [ 16 ] for a detailed description of the semantics and we denote by |=ALC+TR entailment in ALC + TR.

In [ 16 ] the rational closure construction has been defined for ALC + TR, extending to DLs the notion of rational closure introduced by Lehmann and Magidor [ 22 ]. The definition is based on the notion of exceptionality. Roughly speaking T(C) ⊑ D holds in the rational closure of K if C is less exceptional than C ⊓ ¬D. We shortly recall this construction of the rational closure of a TBox and we refer to [ 16 ] for full details. Definition 1 (Exceptionality of concepts and inclusions). Let E be a TBox and C a concept. C is exceptional for E if and only if E |=ALC+TR T(⊤) ⊑ ¬C. An inclusion T(C) ⊑ D is exceptional for E if C is exceptional for E. The set of inclusions in TBox which are exceptional for E will be denoted by E (E).

Given a TBox, it is possible to define a sequence of non increasing subsets of TBox ordered according to the exceptionality of the elements E0 ⊇ E1 ⊇ E2 . . . by letting E0 = TBox and, for i > 0, Ei = E (Ei−1) ∪ {C ⊑ D ∈ TBox s.t. T does not occurr in C}. Observe that, being KB finite, there is an n ≥ 0 such that, for all m > n, Em = En or Em = ∅. A concept C has rank i (denoted rank (C) = i) for TBox, iff i is the least natural number for which C is not exceptional for Ei. If C is exceptional for all Ei then rank (C) = ∞ (C has no rank). Rational closure builds on this notion of exceptionality: Definition 2 (Rational closure of TBox). Let KB = (TBox, ABox) be a DL knowledge base. The rational closure of TBox is defined as: TBox = {T(C) ⊑ D | either rank (C) < rank (C ⊓ ¬D) or rank (C) = ∞} ∪ {C ⊑ D | KB |=ALC+TR C ⊑ D}, where C and D are ALC concepts.

Exploiting the fact that entailment in ALC + TR can be polynomially encoded into entailment in ALC, it is easy to see that deciding if an inclusion T(C) ⊑ D belongs to the rational closure of TBox is a problem in EXPTIME [ 16 ].

Example 1. Let K = {T(Student ) ⊑ ¬Pay Taxes, T(WStudent ) ⊑ Pay Taxes, T(Student ) ⊑ Young, WStudent ⊑ Student } be a knowledge base stating that typical students do not pay taxes, but typical working students (which are students) do pay taxes and that typical students are young. It is possible to see that E0 = {T(Student ) ⊑ ¬Pay Taxes , T(Student ) ⊑ Young , WStudent ⊑ Student }, E1 = {T(WStudent ) ⊑ Pay Taxes , WStudent ⊑ Student} and that the defeasible inclusions T(Student ⊓ Italian ) ⊑ ¬Pay Taxes and T(WStudent ⊓ Italian ) ⊑ Pay Taxes both belong, as expected, to the rational closure of K , as being Italian is irrelevant with respect to being or not a typical student. However, we cannot conclude that T(Student ) ⊑ Y oung: concept WStudent is exceptional w.r.t. Student concerning the property of paying taxes and, hence, it does not inherit any defeasible property of Student .

In the example above the rational closure is too weak to infer that typical working students, as typical student, are young. The lexicographic closure [ 23 ] strengthens the rational closure and allows to conclude that typical working students are young. The property of typical students of being toung is inherited by working students, as it is consistent with all the other (strict or defeasible) properties of working students. 3

From the lexicographic to the skeptical closure

Given a concept B, one wants to identify the defeasible properties of the B-elements. Assume that the rational closure of the knowledge base K has already been constructed and that k is the rank of concept B in the rational closure. The typical B elements are clearly compatible with all the defeasible inclusions in Ek, but they might satisfy further defeasible inclusions with lower ranks, i.e. those included in E0, E1, . . . , Ek−1. In general, there may be alternative maximal sets of defeasible inclusions compatible with B, among which one would prefer those that maximize the number of defeasible inclusions with higher rank. This is indeed what is done by the lexicographic closure [ 23 ], which considers alternative maximally preferred sets of defaults called ”bases”, which, roughly speaking, maximize the number of defaults of higher ranks with respect to those lower ranks (degree of seriousness), and where situations which violate a number of defaults with a certain rank are considered to be less plausible than situations which violates a lower number of defaults with the same rank. In general, there may be exponentially many alternative sets of defeasible inclusions (bases) which are maximal and consistent for a given concept, and the lexicographic closure has to consider all of them to check if a defeasible inclusion is accepted. Instead, in the following, we aim at defining a construction which skeptically builds a single set of defeasible inclusions compatible with B.

Let SB be the set of typicality inclusions T(C) ⊑ D in K which are individually compatible with B (with respect to Ek), that is

SB = {T(C) ⊑ D ∈ TBox | Ek ∪ {T(C) ⊑ D} 6|=ALC+TR T(⊤) ⊑ ¬B}. Clearly, although each defeasible inclusion in SB is compatible with B, it might be the case that overall set SB is not compatible with B, i.e., Ek ∪SB |=ALC+TR T(⊤) ⊑ ¬B.

When compatible with B, SB is the unique maximal basis with respect to the seriousness ordering [ 23 ]. Let δ(Ei) denote the set of defeasible inclusions in Ei. When SB is not compatible with B, we cannot use the defeasible inclusions in SB to derive conclusions about typical B elements. In this case, we can either use just the defeasible inclusions in Ek, as in the rational closure, or we can additionally use all the defeasible inclusions in SkB−1 ∈ δ(Ek−1), with rank k − 1, provided they are compatible with B and Ek and, possibly, we can add all the defeasible inclusions in SkB−2 ∈ δ(Ek−2) (with rank k − 2) provided they are compatible with B, Ek and SkB−1, and so on for lower ranks. This leads to the construction below. For each rank j of the rational closure construction, let SjB be a set of the defeasible inclusions in Ej as follows: SjB = {T(C) ⊑ D ∈ δ(Ej ) | Ek ∪ SkB−1 ∪ SkB−2 ∪ . . . ∪ SjB+1 ∪ {T(C) ⊑ D} 6|=ALC+TR T(⊤) ⊑ ¬B} Informally, SjB is the set of the defeasible inclusions with rank j, which are not (individually) overridden by defeasible inclusions with higher ranks (from j + 1 to k). Definition 3. Let B be a concept such that rank (B) = k. We define the skeptical closure Ssk,B of B as follows: Ssk,B = Ek ∪ SkB−1 ∪ SkB−2 ∪ . . . ∪ ShB, where h is the least integer j such that 0 ≤ j ≤ k − 1 and Ek ∪ SkB−1 ∪ SkB−2 ∪ . . . ∪ SjB 6|=ALC+TR T(⊤) ⊑ ¬B, if such a j exists; Ssk,B = Ek, otherwise.

Intuitively, Ssk,B contains, for each rank j, all the defeasible inclusions having rank j which are compatible with B and with the more specific defeasible inclusions (with rank > j). As ShB−1 is not included in the skeptical closure, Ek ∪ SkB−1 ∪ SkB−2 ∪ . . . ∪ Sh ∪ ShB−1 |=ALC+TR T(⊤) ⊑ ¬B i.e., the set ShB−1 contains conflicting defeasible inclusions which are not overridden by more specific ones. The inclusions in ShB−1 (and, similarly, all the defeasible inclusions with rank lower than h − 1) are not added to the skeptical closure of B. Let us now define when a defeasible inclusion is derivable from the skeptical closure of a TBox.

Definition 4. Let T(B) ⊑ D be a query and let k = rank (B) be the rank of concept B in the rational closure. T(B) ⊑ D is derivable from the skeptical closure of TBox if Ssk,B |=ALC+TR T(⊤) ⊑ (¬B ⊔ D).

The identification of the defeasible inclusions in Ssk,B requires a number of entailment checks which is linear in the number of defeasible inclusions in TBox. In Example 1 the inclusion T(WStudent ) ⊑ Young is derivable from the skeptical closure of TBox, as WStudent has rank 1 and inclusion T(Student ) ⊑ Young in E0 is compatible with WStudent . No other inclusions in δ(E0) are compatible with E1. Instead, the inclusion T(WStudent ) ⊑ Young is not derivable from the skeptical closure of the KB K ′ = {T(Student ) ⊑ ¬Pay Taxes, T(Worker ) ⊑ Pay Taxes, T(Student ) ⊑ Young, WStudent ⊑ Student ⊓ Worker }. as S0WStudent is not compatible with WStudent (w.r.t. E1), due to the conflicting defaults concerning tax payment for Worker and Student (both with rank 0). Hence, the defeasible property that typical students are young is not inherited by typical working students.

Notice that, the property that typical working students are young is accepted in the lexicographic closure of K′, as there are two bases (the one including T(Student ) ⊑ ¬Pay Taxes and the other T(Worker ) ⊑ Pay Taxes), both containing T(Student ) ⊑ Young. The skeptical closure is indeed weaker than the lexicographic closure. Also, while in the logic DLN [ 2 ], given the knowledge base K′, the concept WStudent has an inconsistent prototype, in the skeptical closure one cannot conclude that T(WStudent ) ⊑ ⊥ and, using the terminology in [ 2 ], the conflict is “silently removed”. In this respect, the skeptical closure appears to be weaker than DLN , although it shares with DLN (and with lexicographic closure) a notion of overriding. Detailed comparisons and the study of the semantics underlying the skeptical closure will be subject of future work.

Baader and B. Hollunder. Priorities on defaults with prerequisites, and their application in treating specificity in terminological default logic . J. Autom. Reasoning , 15 ( 1 ): 41 - 68 , 1995 .

P. A.

Bonatti ,

Faella , I. Petrova , and

Sauro . A new semantics for overriding in description logics . Artif . Intell., 222 : 1 - 48 , 2015 .

P. A.

Bonatti ,

Faella , and

Sauro . Defeasible inclusions in low-complexity dls . J. Artif. Intell. Res. (JAIR) , 42 : 719 - 764 , 2011 .

P. A.

Bonatti , Carsten Lutz, and

Frank

Wolter . The Complexity of Circumscription in DLs . Journal of Artificial Intelligence Research (JAIR) , 35 : 717 - 773 , 2009 .

Britz ,

Heidema , and T. Meyer. Semantic preferential subsumption . KR 2008 , pages 476 - 484 , Sidney, Australia, September 2008 . AAAI Press.

Casini , T. Meyer,

I. J.

Varzinczak , , and

Moodley . Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox . DL 2013, CEUR , vol. 1014 , pp. 600 - 615 .

Casini and

Straccia . Rational Closure for Defeasible Description Logics . JELIA 2010 , volume 6341 of LNCS , pages 77 - 90 , Helsinki, Finland, September 2010 . Springer.

Casini and

Straccia . Lexicographic Closure for Defeasible Description Logics . In Proc. of Australasian Ontology Workshop , vol. 969 , pages 28 - 39 , 2012 .

Casini and

Straccia . Defeasible inheritance-based description logics . Journal of Artificial Intelligence Research (JAIR) , 48 : 415 - 473 , 2013 .

10. F. M. Donini , D.

Nardi , and R.

Rosati . Description logics of minimal knowledge and negation as failure . ACM Transactions on Computational Logic (ToCL) , 3 ( 2 ): 177 - 225 , 2002 .

11. T. Eiter, G. Ianni,

Lukasiewicz , and

Schindlauer . Well-founded semantics for description logic programs in the semantic web . ACM Trans. Comput. Log. , 12 ( 2 ): 11 , 2011 .

12. T. Eiter, G. Ianni,

Lukasiewicz ,

Schindlauer , and

Tompits . Combining answer set programming with description logics for the semantic web . Artif . Intell., 172 ( 12 -13): 1495 - 1539 , 2008 .

13.

Giordano and

Gliozzi . Encoding a preferential extension of the description logic SROIQ into SROIQ . In Proc. ISMIS 2015 , volume 9384 of LNCS , pages 248 - 258 . Springer, 2015 .

14. L. Giordano , V.

Gliozzi , N.

Olivetti , and G. L.

Pozzato . Preferential Description Logics. of LPAR 2007 , volume 4790 of LNAI , pages 257 - 272 , Yerevan, Armenia, October 2007 .

15. L. Giordano , V.

Gliozzi , N.

Olivetti , and G. L.

Pozzato . A NonMonotonic Description Logic for Reasoning About Typicality . Artificial Intelligence , 195 : 165 - 202 , 2013 .

16. L. Giordano , V.

Gliozzi , N.

Olivetti , and G. L.

Pozzato . Semantic characterization of rational closure: from propositional logic to description logics . Artif . Intell., 226 : 1 - 33 , 2015 .

17.

Gliozzi . A strengthening of rational closure in DLs: reasoning about multiple aspects . DL 2016 , CoRR abs/1604.00301, April 22- 25 , 2016 ,

Cape

Town .

18. G. Gottlob,

Hernich ,

Kupke , and

Lukasiewicz . Stable model semantics for guarded existential rules and description logics . In Proc. KR 2014 , 2014 .

19.

Ke and

Sattler . Next Steps for Description Logics of Minimal Knowledge and Negation as Failure . In F. Baader,

Lutz , and B. Motik, editors, DL 2008, CEUR Workshop Proceedings , volume 353 , Dresden, Germany, May 2008 . CEUR-WS.org .

20. M. Knorr , P.

Hitzler , and F.

Maier . Reconciling owl and non-monotonic rules for the semantic web . In ECAI 2012, page 474479 , 2012 .

21.

Kraus ,

Lehmann , and

Magidor . Nonmonotonic reasoning, preferential models and cumulative logics . Artificial Intelligence , 44 ( 1-2 ): 167 - 207 , 1990 .

22.

D. J.

Lehmann and

Magidor . What does a conditional knowledge base entail? Artificial Intelligence , 55 ( 1 ): 1 - 60 , 1992 .

23.

D. J.

Lehmann . Another perspective on default reasoning . Ann. Math. Artif. Intell., 15 ( 1 ): 61 - 82 , 1995 .

24.

Motik and

Rosati . Reconciling Description Logics and rules . J. ACM , 57 ( 5 ), 2010 .