PEAR: a Tool for Reasoning About Scenarios and Probabilities in Description Logics of Typicality

Abstract

In this work we describe PEAR, a tool for reasoning about prototypical properties in an extension of Description Logics of typicality with probabilities and scenarios. PEAR implements a non-monotonic procedure for the logic ALC + TPR, a recently introduced extension of the logic of typicality ALC +TR by inclusions of the form T(C) vp D, where p is a real number between 0 and 1 capturing the intuition that \all the typical Cs are Ds, and the probability that a C is not a D is 1 p". In this logic, di erent scenarios are considered by taking into account several extension of the ABox, containing only some typicality assumptions about individuals. Each scenario has a probability depending on those equipping typicality inclusions, then entailment can be restricted to scenarios whose probabilities belong to a given and xed range. PEAR is implemented in Python, it computes all scenarios of a knowledge base and it allows the user to check the probability of a query by exploiting a translation into standard ALC.

-

Non-monotonic extensions of Description Logics (from now on, DLs for short) have been actively investigated since the early 90s [1{6], in order to tackle the well known problem of allowing one to represent and reason about prototypical properties and defeasible inheritance. A simple but powerful non-monotonic extension of DLs is proposed in [ 7 ]: in this approach, typical properties can be directly speci ed by means of a \typicality" operator: a TBox, in addition to standard inclusions C v D, representing that \all Cs are also Ds", can contain inclusions of the form T(C) v D to represent that \typical Cs are also Ds". The Description Logic so obtained is called ALC + TR and, as a di erence with standard DLs, one can consistently express exceptions and reason about defeasible inheritance as well. For instance, a knowledge base can consistently contain the inclusions (1) HummingBird v Bird , (2) T(Bird ) v :BackwardsFlier and (3) T(HummingBird ) v BackwardsFlier , expressing that, normally, birds are not able to y backwards, however hummingbirds are exceptional birds that, typically, are able to y backwards. The key point of the logic ALC + TR relies on the fact that the semantics of the T operator is strongly related to axioms and rules of rational entailment as introduced in [ 8 ], widely considered as the core properties of non-monotonic reasoning. As a consequence, T inherits wellestablished properties like speci city : in the example, if one knows that Petey is a typical hummingbird, then the logic ALC + TR allows one to infer that it ies backwards, giving preference to the most speci c information of being a hummingbird with respect to being a bird.

The main drawback of the logic ALC + TR it that it is too weak: indeed, although the operator T is non-monotonic (T(C) v E does not imply T(C u D) v E), the logic ALC + TR is monotonic [ 9, 10 ], namely, if F is entailed from a knowledge base KB, then F is also entailed from any KB' KB. As a consequence, unless a KB contains explicit assumptions about typicality of individuals, there is no way of inferring defeasible properties about them: in the above example, if KB only contains that Petey is a hummingbird (HummingBird (petey )), it is not possible to conclude that it ies backwards: this would be possible only if the stronger information that Petey is a typical hummingbird (T(HummingBird )(petey )) belongs to (or can be inferred from) KB. In order to tackle this problem, in [ 9, 11 ] the authors have strengthened the semantics of the logic ALC + TR by means of a minimal model semantics, corresponding to a notion of rational closure as de ned in [ 8 ] for propositional logic. Intuitively, the idea is to restrict reasoning to (canonical) models that maximize typical instances of a concept when consistent with the knowledge base. As a consequence, in the resulting logic ALC + TRRaCl , if one knows that Petey is a hummingbird, one can nonmonotonically assume that it is also a typical one if this is consistent, and therefore that it is able to y backwards. From a semantic point of view, the logic ALC + TRRaCl is based on a preference relation among ALC + TR models and a notion of minimal entailment restricted to models that are minimal with respect to such preference relation.

The logic ALC + TRRaCl imposes to consider all typicality assumptions that are consistent with a KB. In other words, in absence of explicit contradictory information, the logic ALC +TRRaCl leads to assume that there are no exceptions: this seems to be too strong in several application domains, especially in situations characterized by a high number of individuals that are all considered as typical ones, whereas it could be useful to reason about scenarios exhibiting exceptional ones. To this aim, in [ 12 ] we have introduced a further extension of the logic of typicality called ALC +TPR, which extends ALC by means of typicality inclusions equipped by probabilities of the form T(C) vp D, where p 2 (0; 1), whose intuitive meaning is that \normally, Cs are Ds and the probability of having exceptional Cs { not being Ds { is 1 p". All the typical instances of the concept C are also instances of the concept D, but we have the opportunity of expressing a degree about the fact that a C element is not also a D element, i.e. it is an exceptional C element. This allows us to rank di erent typicality inclusions, for instance we can have that T(TeenAger ) v0:6 In uencerFollower as well as that T(TeenAger ) v0:9 9play :VideoGame, capturing the intuition that both following an in uencer and playing video games are typical properties of teenagers, and we also want to express that the probability of having exceptional teenagers not following any in uencer is higher than the one of nding ones not playing video games, by ranking the two properties with probabilities 0:6 and 0:9, respectively.

In this work we introduce PEAR, a preliminary implementation of the reasoning mechanism for the logic ALC + TPR described in [ 12 ]. PEAR, standing for Probability of Exceptions and typicAlity Reasoner, computes di erent syntactic extensions of an ABox containing only some of the \plausible" typicality assertions that can be entailed from the KB in the non-monotonic logic ALC + TRRaCl : each extension represents a scenario having a speci c probability. Then, PEAR allows one to check whether a query is non-monotonically entailed from the knowledge base, either by selecting the scenarios where it holds or by restricting the attention to extensions whose probabilities belong to a given and xed range, as well as to compute the probability of a query as the sum of the probabilities of scenarios from which it is entailed. This allows one to reason about scenarios that are not necessarily the most probable and are, in some sense, surprising. The decision procedure computed by PEAR is ExpTime complete, therefore we retain the same complexity of the underlying standard ALC. 2

Preferential Description Logics

Let us rst quickly recall the main notions about the Description Logic of typicality ALC + TR introduced in [ 7, 13, 9 ]. The logic ALC + TR is obtained by adding to standard ALC the typicality operator T [ 7 ]. The intuitive idea is that T(C) selects the typical instances of a concept C. We can therefore distinguish between the properties that hold for all instances of concept C (C v D), and those that only hold for the normal or typical instances of C (T(C) v D). From a semantic point of view, we refer to rational models [ 9 ]: a model M is any structure h I ; <; :I i where I is the domain, < is an irre exive, transitive, well-founded and modular (for all x; y; z in I , if x < y then either x < z or z < y) relation over I . In this respect, x < y means that x is \more normal" than y, and that the typical members of a concept C are the minimal elements of C with respect to this relation. An element x 2 I is a typical instance of some concept C if x 2 CI and there is no C-element in I more typical than x. In detail, :I is the extension function that maps each concept C to CI I , and each role R to RI I I . For concepts of ALC, CI is de ned as usual. For the T operator, let M in<(CI ) = fx 2 CI j @y 2 CI s.t. y < xg, we de ne (T(C))I = M in<(CI ).

A model M can be equivalently de ned by postulating the existence of a function kM : I 7 ! N, where kM assigns a nite rank to each domain element: the rank function kM and < can be de ned from each other by stating that x < y if and only if kM(x) < kM(y). Given standard de nitions of satis ability of a KB in a model, we de ne a notion of entailment in ALC + TR. Given a query F (either an inclusion C v D or an assertion C(a) or an assertion of the form R(a; b)), we say that F is entailed from a KB if F holds in all ALC + TR models satisfying KB.

As already mentioned in the Introduction, even if the T operator itself is nonmonotonic, the logic ALC + TR is monotonic. In order to perform useful nonmonotonic inferences, in [ 9 ] the authors have strengthened the above semantics by restricting entailment to a class of minimal models. Intuitively, the idea is to restrict entailment to models that minimize the untypical instances of a concept. The resulting logic is called ALC + TRRaCl and it corresponds to a notion of rational closure on top of ALC + TR. Such a notion is a natural extension of the rational closure construction provided in [ 8 ] for the propositional logic. The non-monotonic semantics of ALC + TRRaCl relies on minimal rational models that minimize the rank of domain elements. Informally, given two models of KB, one in which a given domain element x has rank 2 (because for instance z < y < x), and another in which it has rank 1 (because only y < x), we prefer the latter, as in this model the element x is assumed to be \more typical" than in the former. Query entailment is then restricted to minimal canonical models. The intuition is that a canonical model contains all the individuals that enjoy properties that are consistent with KB. A model M is a minimal canonical model of KB if it satis es KB, it is minimal and it is canonical1. A query F is minimally entailed from a KB if it holds in all minimal canonical models of KB. In order to ascribe typical properties to individuals, the notion of rational closure is further extended to the ABox. In [ 9 ] it is shown that query entailment in ALC + TRRaCl is in ExpTime. 3

The Logic ALC + TPR In this section we recall the logic ALC + TPR, extending the DLs of typicality with probabilities and scenarios. Here, typicality inclusion are equipped with a probability/degree of not having exceptions for it, and have the form

T(C) vp D; whose meaning is \typical Cs are also Ds, and the probability of having exceptional Cs not being Ds is 1 p".

De nition 1. We consider an alphabet of concept names C, of role names R, and of individual constants O. Given A 2 C and R 2 R, we de ne:

C := A j > j ? j :C j C u C j C t C j 8R:C j 9R:C An ALC + TPR knowledge base is a pair (T ; A). T contains axioms of the form either C v C or T(C) vp C, where p 2 R; p 2 (0; 1). A contains assertions of the form either C(a) or R(a; b), where a; b 2 O.

Given an inclusion T(C) vp D, the higher the probability p, the less the probability of having exceptional Cs not being also Ds. In this respect, the probability p is a real number included in the open interval (0; 1): the probability 1 is not allowed, in the sense that an inclusion T(C) v1 D would correspond to a strict 1 In Theorem 10 in [ 9 ] the authors have shown that for any consistent KB there exists a nite minimal canonical model of KB. inclusion C v D (all Cs are Ds). Given another inclusion T(C0) vp0 D0, with p0 < p, we assume that this inclusion is less \strict" than the other one, i.e. the probability of having exceptional C0s is higher than the one of having exceptional Cs with respect to properties D0 and D, respectively.

Given a KB, we de ne the nite set Tip of concepts occurring in the scope of the typicality operator, i.e. Tip = fC j T(C) vp D 2 KBg. Given an individual a explicitly named in the ABox, we de ne the set of typicality assumptions T(C)(a) that can be minimally entailed from KB in the non-monotonic logic ALC + TRRaCl , with C 2 Tip. We then consider an ordered set TipA of pairs (a; C) of all possible assumptions T(C)(a), for all concepts C 2 Tip and all individual constants a in the ABox. We then de ne the ordered multiset PA = m [p1; p2; : : : ; pn]; respecting the order imposed on TipA, where pi = Q pij for all j=1 T(Ci) vpi1 D1; T(Ci) vpi2 D2; : : : ; T(Ci) vpim Dm in T : The ordered multiset PA is a tuple of the form [p1; p2; : : : ; pn], where pi is the probability of the assumption T(C)(a), such that (a; C) 2 TipA at position i. pi is the product of all the probabilities pij of inclusions T(C) vpij D in the TBox.

Following the basic idea underlying surprising scenarios outlined in [ 14 ], we consider di erent extensions Afi of the ABox and we equip them with a probability Pi. Starting from PA = [p1; p2; : : : ; pn], the rst step is to build all alternative tuples where 0 is used in place of some pi to represent that the corresponding typicality assertion T(C)(a) is no longer assumed. We then de ne the notion of extension of the ABox corresponding to a string so obtained: in this way, the extension corresponding to PA contain all the available typicality assumptions; in the other extensions, some typicality assumptions are discarded, thus 0 is used in place of the corresponding pi. The probability of an extension Afi corresponding to a string PAi = [pi1; pi2; : : : ; pin] is de ned as the product of probabilities pij when pij 6= 0, i.e. the probability of the corresponding typicality assumption when this is selected for the extension, and 1 pj when pij = 0, i.e. the corresponding typicality assumption is discarded, that is to say the extension contains an exception to the inclusion. It is easy to observe that we obtain a probability distribution over extensions of A.

Non-monotonic entailment of a query F in the Description Logic ALC + TPR is de ned as follows: (i) if F is a TBox inclusion C v D, then it is entailed from KB if it is minimally entailed from KB0 in the non-monotonic ALC + TRRaCl , where KB0 is obtained from KB by removing probabilities of exceptions, i.e. by replacing each typicality inclusion T(C) vp D with T(C) v D; (ii) if F is an ABox fact C(a), then it is entailed from KB if it is entailed in the monotonic ALC + TR from scenarios extending KB with Ai. Furthermore, one can consider a notion of entailment restricted to scenarios whose probabilities belong to a given range and, similarly to [ 15 ], a notion of probability of the entailment of a query C(a), as the sum of the probabilities of all extensions from which C(a) is so entailed. In [ 12 ] it is shown that entailment in ALC + TPR is ExpTime-complete as for standard ALC.

Design of PEAR

In this section we introduce PEAR (Probability of Exceptions and typicAlity Reasoner), a Python implementation of the reasoning services provided by the logic ALC + TPR. PEAR makes use of the library owlready2 2 that allows one to rely on the services of e cient DL reasoners, e.g. the HermiT reasoner. PEAR exploits the translation of an ALC + TR knowledge base into standard ALC introduced in [ 9 ] and described later in this section. The current version of the system PEAR, along with the les for the examples presented in this paper, are available at http://di.unito.it/pear.

The system PEAR implements a non-monotonic procedure whose aim is to compute extensions A of the ABox and corresponding alternative scenarios having di erent probabilities described in the previous section. Given an ALC + TPR KB=(T ; A) and a query F , PEAR computes the following four steps: 1. compute the set Tipa of all typicality assumptions that are minimally entailed from the knowledge base in the non-monotonic logic ALC +TRRaCl ; 2. compute all possible Afi extensions of the ABox and compute their probabilities; 3. select the extensions whose probabilities belong to a given range hp; qi; 4. check whether the query F is entailed from all the selected extensions in the monotonic logic ALC +TR. Step 1 is based on reasoning in the non-monotonic logic ALC +TRRaCl : in this case, PEAR computes the rational closure of an ALC + TR knowledge base by means of the algorithm introduced in [ 9 ], which is sound and complete with respect to the minimal model semantics recalled in Section 2. Step 4 is based on reasoning in the monotonic logic ALC + TR: to this aim, the procedure relies on a polynomial encoding of ALC + TR into ALC introduced in [ 16 ], which exploits the de nition of T in terms of a Godel-Lob modality 2 as follows: T(C) is de ned as C u 2:C where the accessibility relation of the modality 2 is the preference relation < in ALC + TR models. Let KB=(T ; A) be a knowledge base where A does not contain positive typicality assertions on individuals of the form T(C)(a). The encoding KB'=(T 0; A0) of KB in ALC is de ned as follows. First of all, we let A0 = ;. Then, for each A v B 2 T , not containing T, we introduce A v B in T 0. For each T(A) occurring in T , we introduce a new atomic concept Box :A and, for each inclusion T(A) vp B 2 T , we add to T 0 the inclusion A u Box :A v B. In order to capture the properties of the 2 modality, a new role R is introduced to represent the relation < in preferential models, and the following inclusions are introduced in T 0: (i) Box :A v 8R:(:A u Box :A) and (ii) :Box :A v 9R:(A u Box :A). Inclusion (i) accounts for the transitivity of <, whereas inclusion (ii) accounts for the well-foundedness, namely the fact that if an element is not a typical A element then there must be a typical A element preferred to it. For the encoding of the inclusions, if Cl v Cr is not a typicality inclusion, then Cl0 = Cl and Cr0 = Cr; if Cl v Cr is a typicality inclusion T(A) v Cr, then Cl0 = A u Box :A and Cr0 = Cr. The size of KB' is polynomial in the size of the KB. The same for Cl0 and C0 , assuming the size of Cl and Cr r be polynomial in the size of KB. As an example, let the TBox contain: 2 https://pythonhosted.org/Owlready2/

Text file

gives information to computed by

manage order of execution computed by Auxiliary file

Reasoning and query files manage information by

The system PEAR comprises eleven Python les, whose behaviour and dependencies are summarized in Figure 4. In particular, the following modules represent the core components of the tool: { OntologyManager.py, whose aim is to manage the knowledge base implementing the above translation into standard ALC; { IncreasedOntology.py, whose objectives are to generate all scenarios and to compute their probabilities; { ReasoningOnScenarios.py, which is devoted to check entailment of a query (QueryInput.py) by exploiting reasoning services provided by HermiT. Let us explain the functioning of PEAR by an example inspired by [ 12 ]. Let a KB be a knowledge base in ALC + TPR, where the TBox is as follows: PokemonCardPlayer v CardPlayer T(CardPlayer ) v0:85 :YoungPerson T(PokemonCardPlayer ) v0:7 YoungPerson T(Student ) v0:6 YoungPerson T(Student ) v0:8 InstagramUser (1) (2) (3) (4) (5) whereas the ABox is fPokemonCardPlayer (lollo); Student (thomas)g. PEAR rst computes the set of typicality assumptions entailed from ALC + TRRaCl , namely (a) T(PokemonCardPlayer )(lollo) and (b) T(Student )(thomas). Then, PEAR generates the following four di erent scenarios: 1. neither (a) nor (b) are assumed: the probability is (1 0:7) (1 (0:6 0:8)) = 0:156, but PEAR is not able to conclude anything about Lollo and Thomas; 2. (a) is assumed, whereas (b) is not: this scenario, having a probability 0:7 (1 (0:6 0:8)) = 0:364, allows PEAR to conclude YoungPerson(lollo); 3. (b) is assumed, whereas (a) is not: this scenario has probability (1 0:7) (0:6 0:8) = 0:144, and PEAR only concludes YoungPerson(thomas) and InstagramUser (thomas); 4. both (a) and (b) are assumed: in this scenario, whose probability is 0:7 (0:6 0:8) = 0:336. In this scenario, PEAR concludes that both Lollo and Thomas are young persons and that Thomas is an Instagram user. PEAR can also evaluates the probability of a query as the sum of the probabilities of scenarios where such a query holds. In the example, PEAR evaluates the probability that Lollo is a young person as the sum of the probabilities of scenarios (2) and (4), and it is therefore 0:336 + 0:364 = 0:7. Similarly, the probability that Thomas is an Instagram user is 0:336 + 0:144 = 0:48. Some pictures of the execution of PEAR in this example are provided in Figure 4.

5 Related Works and Conclusions

In this work we have introduced PEAR, a tool for reasoning in the non-monotonic Description Logic ALC + TPR, which extends the logic of typicality by means of probabilities equipping typicality inclusions. In this setting, T(C) vp D is intended as \normally, Cs are Ds and we have a probability of 1 p of having exceptional Cs not being Ds". From a knowledge representation point of view, as a di erence from ALC + TRRaCl , the logic ALC + TPR allows one to distinguish among typicality inclusions by means of their probabilities: given two typical properties of a given concept, one can formalize the fact that the probability of having exceptional elements is di erent for the two properties/inclusions. Probabilities of exceptions are then used in order to reason about plausible scenarios, obtained by selecting only some typicality assumptions and whose probabilities belong to a given and xed range. PEAR is implemented in Python and it provides a decision procedure for reasoning in the Description Logic ALC + TPR, which turns out to be in ExpTime as in the underlying standard ALC.

An extension of DLs of typicality with probabilities is presented in [ 17 ], however probabilities are intended as degrees of belief as in the DISPONTE semantics [ 15 ].

PEAR represents a preliminary attempt to implement reasoning services for the logic ALC + TPR. We plan to provide a more mature version, by investigating the applicability of techniques introduced in [ 18, 19 ] in order to improve the e ciency of the system.

References

1. Bonatti , P.A. , Lutz , C. , Wolter , F. : The Complexity of Circumscription in DLs . Journal of Arti cial Intelligence Research (JAIR) 35 ( 2009 ) 717 { 773

2. Baader , F. , Hollunder , B. : Priorities on defaults with prerequisites, and their application in treating speci city in terminological default logic . JAR 15 ( 1 ) ( 1995 ) 41 { 68

3. Donini , F.M. , Nardi , D. , Rosati , R.: Description logics of minimal knowledge and negation as failure . ACM Transactions on Computational Logics (ToCL) 3 ( 2 ) ( 2002 ) 177 { 225

4. Casini , G. , Straccia , U. : Rational closure for defeasible description logics . In: Proc. of JELIA 2010 . Volume 6341 of LNAI ., Springer ( 2010 ) 77 { 90

5. Casini , G. , Straccia , U. : Defeasible Inheritance-Based Description Logics . Journal of Arti cial Intelligence Research (JAIR) 48 ( 2013 ) 415 { 473

6. Bonatti , P.A. , Faella , M. , Petrova , I. , Sauro , L.: A new semantics for overriding in description logics . Arti cial Intelligence 222 ( 2015 ) 1 { 48

7. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : ALC+T: a preferential extension of description logics . Fundamenta Informaticae 96 ( 2009 ) 341 { 372

8. Lehmann , D. , Magidor , M. : What does a conditional knowledge base entail? Arti cial Intelligence 55 ( 1 ) ( 1992 ) 1 { 60

9. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Semantic characterization of Rational Closure: from Propositional Logic to Description Logics . Artif. Intelligence 226 ( 2015 ) 1 { 33

10. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Minimal model semantics and rational closure in description logics . In Eiter, T., Glimm , B. , Kazakov , Y. , Krotzsch, M., eds.: Informal Proceedings of the 26th International Workshop on Description Logics. Volume 1014 of CEUR Workshop Proceedings., CEUR-WS.org ( 2013 ) 168 { 180

11. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Minimal model semantics and rational closure in description logics . In: Informal Proceedings of Description Logics 2013. Volume 1014 of CEUR Workshop Proceedings., CEUR-WS.org ( 2013 ) 168 { 180

12. Pozzato , G.: Typicalities and probabilities of exceptions in nonmotonic Description Logics . International Journal of Approximate Reasoning 107 ( 2019 ) 81 { 100

13. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : A NonMonotonic Description Logic for Reasoning About Typicality . Arti cial Intelligence 195 ( 2013 ) 165 { 202

14. Pozzato , G.L. : Reasoning about surprising scenarios in description logics of typicality . In: Advances in Arti cial Intelligence: AI*IA 2016 . Volume 10037 of LNAI . ( 2016 ) 1 { 15

15. Riguzzi , F. , Bellodi , E. , Lamma , E. , Zese , R. : Probabilistic description logics under the distribution semantics . Semantic Web 6 ( 5 ) ( 2015 ) 477 { 501

16. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L. : Rational closure in SHIQ . In: Proc. of Description Logics 2014. Volume 1193 of CEUR Workshop Proceedings., CEUR-WS.org ( 2014 ) 543 { 555

17. Lieto , A. , Pozzato , G.L.: A description logic of typicality for conceptual combination . In: Proc. of ISMIS 2018 . Volume 11177 of LNAI ., Springer ( 2018 ) 189 { 199

18. Alberti , M. , Bellodi , E. , Cota , G. , Riguzzi , F. , Zese , R. : cplint on SWISH: probabilistic logical inference with a web browser . Intelligenza Arti ciale 11(1) ( 2017 ) 47 { 64

19. Bellodi , E. , Lamma , E. , Riguzzi , F. , Zese , R. , Cota , G.: A web system for reasoning with probabilistic OWL . Journal of Software: Practice and Experience 47 ( 1 ) ( 2017 ) 125 { 142