=Paper=
{{Paper
|id=Vol-2214/paper7
|storemode=property
|title=On Probabilities of Exceptions in Description Logics of Typicality
|pdfUrl=https://ceur-ws.org/Vol-2214/paper7.pdf
|volume=Vol-2214
|authors=Gian Luca Pozzato
|dblpUrl=https://dblp.org/rec/conf/cilc/Pozzato18
}}
==On Probabilities of Exceptions in Description Logics of Typicality==
https://ceur-ws.org/Vol-2214/paper7.pdf
On Probabilities of Exceptions in
Description Logics of Typicality
Gian Luca Pozzato
Dipartimento di Informatica, Università di Torino, Italy
gianluca.pozzato@unito.it
Abstract. We describe a nonmonotonic procedure for preferential Description
Logics in order to reason about typicality by taking probabilities of exceptions
into account. We consider an extension, called ALC +TP R , of the logic of typical-
ity ALC + TR by inclusions of the form T(C) vp D, whose intuitive meaning
is that “typical Cs are Ds with a probability p”. We consider a notion of exten-
sion of an ABox containing only some typicality assertions, then we equip each
extension with a probability. We then restrict entailment of a query F to those
extensions whose probabilities belong to a given and fixed range. We propose a
decision procedure for reasoning in ALC + TP R and we exploit it to show that
entailment is E XP T IME-complete as for the underlying ALC.
1 Introduction
Description Logics [1], for short: DLs, represent one of the most important formalisms
of knowledge representation and are at the base of the languages for building ontologies
in the Semantic Web such as OWL. Standard Description Logics are not able to repre-
sent prototypical properties and to reason about defeasible inheritance. Recalling a well
known example coming from the literature of nonmonotonic reasoning, we can have a
TBox representing that birds fly (Bird v Fly), but that penguins are birds that do not
fly (Penguin v Bird and Penguin v ¬Fly). This knowledge base is consistent only if
there are no penguins. In order to tackle this problem, nonmonotonic extensions of De-
scription Logics have been actively investigated since the early 90s [2–8], allowing one
to represent prototypical properties of classes and to reason about defasible inheritance.
A simple but powerful nonmonotonic extension of DLs is proposed in [9]: in this
approach “typical” or “normal” properties can be directly specified by means of a “typ-
icality” operator T enriching the underlying DL, and a TBox can contain inclusions
of the form T(C) v D to represent that “typical Cs are also Ds” or “normally, Cs
have the property D”. The Description Logic so obtained is called ALC + TR and,
as a difference with standard DLs, one can consistently express exceptions and reason
about defeasible inheritance as well. For instance, a knowledge base can consistently
express that a typical activist of the Five Stars Movement is against fraudsters, however
he changes his mind if he also supports the so called “Government of changes” with
The League: as an example, a typical activist supporting the government is no longer
angry about the fact that the Italy’s supreme court has ruled that The League has re-
couped some 49 million of euros of public money received by the party’s former leader.
This can be formalized as follows:
T(FiveStarsActivist) v ∃against.Fraudsters
T(FiveStarsActivistuGovernmentOfChangeSupporter ) v ¬∃against.Fraudsters
The semantics of T is characterized by the properties of rational logic [10], recognized
as the core properties of nonmonotonic reasoning. As a consequence, T inherits well-
established properties like specificity: in the example, if one knows that Beppenito is a
typical Five Stars activist supporting the Government of Change, then the logic ALC +
TR allows us to infer that, normally, he is not against fraudsters, giving preference to
the most specific information.
The logic ALC + TR itself is too weak in several application domains. Indeed, al-
though the operator T is nonmonotonic (T(C) v E does not imply T(C u D) v E),
the logic ALC + TR is monotonic, in the sense that if the fact F follows from a given
knowledge base KB, then F also follows 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 contains the fact
that Gianpiercarloberto is a Five Stars activist, i.e. FiveStarsActivist(gianpiercarloberto)
belongs to KB, it is not possible to infer that he is against fraudsters. This would be
possible only if the stronger information that Gianpiercarloberto is a typical activist
T(FiveStarsActivist)(gianpiercarloberto) belongs to (or can be inferred from) KB.
In order to overwhelm this limit and perform useful inferences, in [11] the authors have
introduced a nonmonotonic extension of the logic ALC+TR based on a minimal model
semantics, corresponding to a notion of rational closure as defined in [10] for propo-
sitional logic. Intuitively, the idea is to restrict our consideration to (canonical) models
that maximize typical instances of a concept when consistent with the knowledge base.
The resulting logic, that we call ALC + TRaCl R , supports typicality assumptions, so that
if one knows that Gianpiercarloberto is a Five Stars activist, one can nonmonotonically
assume that he is also a typical Five Stars activist if this is consistent, and therefore that
he is against fraudsters. From a semantic point of view, the logic ALC + TRaCl R 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 + TRaCl R imposes to consider all typicality assumptions that are
consistent with a given KB. Following the above example about birds and penguins, if
the TBox further contains that, normally, birds have wings and have a small size, if it
is consistent to assume that Tweety and Kirby are typical birds, then the logic imposes
to infer that they both fly, have wings and have a small size. This seems to be too
strong in several application domains: it could be useful to reason about scenarios with
exceptional individuals, or one could need to assign different probabilities to typicality
inclusions. In the example, one could need to represent that the properties of flying,
having wings and having a small size are all typical properties of birds: however, it
could be needed to also describe that the probability of finding exceptional birds not
having wings is lower than the one of finding exceptional birds not having a small size.
In this work we describe a new an extension of ALC, called ALC+TPR , by means of
typicality inclusions equipped by probabilities of exceptionality of the form T(C) vp
D, where p ∈ (0, 1). The intuitive meaning is that “typical Cs are also Ds with a
probability p” or “normally, Cs are Ds and the probability of having exceptional Cs –
not being Ds – is 1 − p”. For instance, we can have
T(ItalianTeenAger ) v0.9 AppUser
T(ItalianTeenAger ) v0.6 ∃listenTo.Trap
whose intuitive meaning is that being users of apps for mobile devices and listening to
trap music are both typical properties of Italian teen agers, however the probability of
having exceptional teen agers not using apps is lower than the one of finding exceptional
teens not listening to trap music, in particular we have the evidence that the probability
of not having exceptions is 90% and 60%, respectively.
As a difference with DLs under the distributed semantics introduced in [12, 13],
where probabilistic axioms of the form p :: C v D are used to capture uncertainty in
order to represent that Cs are Ds with probability p, in the logic ALC + TPR we are able
to ascribe typical properties to concepts and to reason about probabilities of exceptions
to those typicalities. We define different extensions of an ABox containing only some
of the “plausible” typicality assertions: each extension represents a scenario having a
specific probability. Then, we provide a notion of nonmonotonic entailment restricted
to extensions whose probabilities belong to a given and fixed range, in order to reason
about scenarios that are not necessarily the most probable. We introduce a decision
procedure for checking entailment in ALC + TPR and we exploit it in order to show
that reasoning in ALC + TPR with probabilities of exceptions is E XP T IME complete,
therefore we retain the same complexity of the underlying standard ALC. This work
extends and revises the preliminary results presented in [14].
2 Preferential Description Logics
The logic ALC + TR is obtained by adding to standard ALC the typicality operator
T [9]. 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).
The semantics of the T operator can be formulated in terms of rational models:
Definition 1. A rational model M is any structure h∆I , <, .I i where: • ∆I is a non-
empty set of items called the domain; • < is an irreflexive, 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 ;
• .I is the extension function that maps each concept C to C I ⊆ ∆I , and each role
R to RI ⊆ ∆I × ∆I . For concepts of ALC, C I is defined as usual. For T, we have
(T(C))I = M in< (C I ).
The intuitive idea is as follows: the preference relation among domain elements
defines their level of exceptionality, namely x < y means that x is “more normal” than
y. Typical members of a concept C are the minimal elements of the extension C I of C
with respect to the preference relation <. An element x ∈ ∆I is a typical instance of
concept C if x ∈ C I and there is no C-element in ∆I more typical than x, i.e. there is
no z ∈ C I such that z < x.
A model M can be equivalently defined by postulating the existence of a function
kM : ∆I 7−→ N, where kM assigns a finite rank to each domain element:
Definition 2 (Rank of a domain element). Given a model M =h∆I , <, .I i, the rank
kM of a domain element x ∈ ∆I , is the length of the longest chain x0 < . . . < x from
x to a minimal x0 (i.e. such that there is no x0 such that x0 < x0 ).
kM and < can be defined from each other by letting x < y if and only if kM (x) <
kM (y).
Given standard definitions of satisfiability of a KB in a model, we define 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, written
KB |=ALC+TR F , if F holds in all ALC + TR models satisfying KB.
Even if the typicality operator T itself is nonmonotonic (i.e. T(C) v E does not
imply T(C u D) v E), what is inferred from a KB can still be inferred from any KB’
with KB ⊆ KB’, i.e. the logic ALC + TR is monotonic. In order to perform useful
nonmonotonic inferences, in [11] 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 + TRaCl R 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 [10] for the propositional logic.
The nonmonotonic semantics of ALC + TRaCl R relies on minimal rational models
that minimize the rank of domain elements of Definition 2 above. Intuitively, 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.
Formal definitions follow.
0 0
Definition 3 (Minimal models). Given M =h∆I , <, .I i and M0 = h∆I , <0 , .I i we
say that M is preferred to M0 , written M < M0 , if the following conditions hold:
0
– ∆I = ∆ I
0
– C I = C I for all concepts C
– for all x ∈ ∆I , it holds that kM (x) ≤ kM0 (x) whereas there exists y ∈ ∆I such
that kM (y) < kM0 (y).
Given a KB, we say that M is a minimal model of K with respect to < if it is a model
satisfying K and there is no M0 model satisfying K such that M0 < M.
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 consis-
tent with KB. A model M is a minimal canonical model of KB if it satisfies KB, it is
minimal and it is canonical. In [11], Theorem 10 shows that for any consistent KB there
exists a finite minimal canonical model of KB. A query F is minimally entailed from a
KB, written KB |=ALC+TRaCl F , if it holds in all minimal canonical models of KB. In
R
[11] it is shown that query entailment in ALC + TRaCl
R is in E XP T IME.
3 Dealing with Probabilities of Exceptions: the Logic ALC + TPR
We introduce a semantics that allows us to equip a typicality inclusion with the proba-
bility of not having exceptions for that, and then to reason about such inclusions. In the
resulting Description Logic, called ALC + TPR , a typicality inclusion has the form
T(C) vp D,
and its intuitive meaning is “normally, Cs are also Ds with probability p” or, in other
words, “typical Cs are also Ds, and the probability of having exceptional Cs not being
Ds is 1 − p”. We then define a nonmonotonic procedure whose aim is to describe al-
ternative completions of the ABox obtained by assuming typicality assertions about the
individuals explicitly named in the ABox: the basic idea is similar to the one proposed
in [9], where a completion of an ALC+T ABox is proposed in order to assume that ev-
ery individual constant of the ABox is a typical element of the most specific concept he
belongs to, if this is consistent with the knowledge base. An analogous approach is pro-
posed in [15], where different extensions of the ABox are introduced in order to define
plausible but surprising scenarios. Here we propose a similar, algorithmic construc-
tion in order to compute only some assumptions of typicality of individual constants,
in order to describe alternative scenarios having different probabilities: different exten-
sions/scenarios are obtained by considering different sets of typicality assumptions of
the form T(C)(a), where a occurs in the ABox.
Definition 4. We consider an alphabet of concept names C, of role names R, and of
individual constants O. Given A ∈ C and R ∈ R, we define:
C := A | > | ⊥ | ¬C | C u C | C t C | ∀R.C | ∃R.C
An ALC + TPR knowledge base is a pair (T , A). T contains axioms of the form either
(i) C v C or (ii) T(C) vp C, where p ∈ R, p ∈ (0, 1). A contains assertions of the
form either (i) C(a) or (ii) R(a, b), where a, b ∈ O.
Given an inclusion T(C) vp D, the higher the probability p the more the inclusion
is “exceptions-free” or, equivalently, the less is 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 in-
clusion T(C) v1 D (the probability of having exceptional Cs not being Ds is 0)
corresponds to a strict inclusion C v D (all Cs are Ds). Given another inclusion
T(C 0 ) vp0 D0 , with p0 < p, we assume that this inclusion is less “strict” than the
other one, i.e. the probability of having exceptional C 0 s is higher than the one of having
exceptional Cs with respect to properties D0 and D, respectively. Recalling the exam-
ple of the Introduction, where KB contains T(ItalianTeenAger ) v0.9 AppUser and
T(ItalianTeenAger ) v0.6 ∃listenTo.TrapMusic, we have that typical Italian teen
agers make use of apps for mobile devices, and that normally they also listen to trap
music; however, the second inclusion is less probable with respect to the first one: both
are properties of a prototypical Italian teen ager, however there is a higher probability
of finding exceptions of teens not listening to trap music with respect to the probability
of having Italian teen agers not using apps for mobile devices.
Before introducing formal definitions, we provide an example inspired to Example
1 in [15] in order to give an intuitive idea of what we mean for reasoning in ALC + TPR
with probabilities of exceptions. We will complete it with part 2 in Example 3.
Example 1 (Reasoning in ALC + TPR part 1). We aim at providing a formalization of
some information about illnesses and symptoms. Let KB = (T , A) where T is:
AtypicalDepressed v Depressed (1)
T(Depressed ) v0.85 ¬∃hasSymptom.MoodReactivity (2)
T(AtypicalDepressed ) v0.7 ∃hasSymptom.MoodReactivity (3)
T(ProstateCancerPatient) v0.6 ∃hasSymptom.MoodReactivity (4)
T(ProstateCancerPatient) v0.8 ∃hasSymptom.Nocturia (5)
The above TBox T represents that (2), normally, depressed people do not have mood
reactivity, namely the ability to feel better temporarily in response to positive life events.
On the contrary, (3) states that this is a typical symptom of a depression with atypical
features, known as atypical depression, that shares many of the typical symptoms of
depression but is characterized by improved mood in response to positive events. In-
clusion (1) intuitively represents that atypical depression is a kind of depression. Mood
reactivity, as well as nocturia, are also typical symptoms of prostatic cancer (inclusions
(4) and (5), respectively): more in detail, (4) says that we have a probability of 60% of
not having exceptional prostatic cancer patients with no mood swings, whereas (5) says
that the probability of not having exceptional prostatic cancer patients without nocturia
is 80% or, alternatively, probabilities of having exceptional prostatic cancer patients
with no mood swing and without nocturia are of the 40% and of the 20%, respectively.
Concerning TBox reasoning, as a first example, we have that in ALC + TPR we can
infer1 that, normally, depression in patients is not classified as Atypical depression:
T(Depressed ) v ¬AtypicalDepressed ,
and this is a wanted inference, since, in normal circumstances, members of a class do
not belong to a subclass containing exceptional individuals.
As another example, we have that
(6) T(Depressed u Spleenless) v ¬∃hasSymptom.MoodReactivity
follows from KB, and this is also a wanted inference, since undergoing spleen removal
is irrelevant with respect to mood reactivity as far as we know. This is a nonmonotonic
inference that does no longer follow if it is discovered that typical depressed people
without their spleen are subject to mood reactivity: given
T 0 = T ∪ {T(Depressed u Spleenless) v ∃hasSymptom.MoodReactivity},
we have that (6) does no longer follow from KB with T 0 in the logic ALC + TPR .
1
At this point of the presentation we only want to give an intuition of inferences characterizing
ALC + TP R . Technical details and definitions will be provided in Definition 8.
As for rational closure, the set of inclusions that are entailed from a ALC + TPR KB
is closed under the property known as rational monotonicity: for instance, from KB and
the fact that the inclusion representing that, normally, depressed people are not elder
(T(Depressed ) v ¬Elder ) is not entailed from KB in ALC + TPR , it follows that we
can infer the inclusion T(Depressed u Elder ) v ¬∃hasSymptom.MoodReactivity,
namely, a typical depressed and elder patient has not mood reactivity (the subconcept
Depressed u Elder inherits the typical properties of the concept Depressed ).
Concerning ABox reasoning, if we know that Jim is depressed, that is to say A =
{Depressed (jim)}, then we can infer that Jim has not mood swings with a probability
of 85%, since T(Depressed )(jim) is minimally entailed from KB in ALC + TRaCl R and
the inclusion (2) is equipped by a probability of 0.85. If we discover that Jim is an
atypical depressed, then ALC + TPR allows us to retract such inference, whereas the
fact that Jim has mood swings (∃hasSymptom.MoodReactivity(jim)) is entailed and
evaluated having probability of 70%. The same conclusions are also entailed in case we
discover that Jim is elder, i.e. Elder (jim) is added to the ABox, in detail:
– from (T , {Depressed (jim), Elder (jim)}), the logic ALC + TPR allows us to infer
¬∃hasSymptom.MoodReactivity(jim) with probability of 85%;
– from (T , {AtypicalDepressed (jim), Elder (jim)}), the logic ALC + TPR allows
us to infer ∃hasSymptom.MoodReactivity(jim) with probability of 70%.
It is worth noticing that it is possible to have knowledge bases containing inclusions of
the form T(C) vp D, where p ≤ 0.5 that, if wrongly interpreted, could be considered
as counter intuitive. For instance, the inclusion T(ItalianTeenAger ) v0.3 SportLover
could be wrongly interpreted as “normally, Italian teen agers do not love sport”. How-
ever, probabilities in ALC + TPR are not intended to express degrees of belief of the
inclusions they equip. In the example, even if its corresponding probability of excep-
tionality is low, the right interpretation of T(ItalianTeenAger ) v0.3 SportLover is
that loving sport is anyway a property of a prototypical Italian teen ager: as a difference
with T(ItalianTeenAger ) v0.9 AppUser , we essentially have that the probability of
finding exceptional Italian teen agers not loving sport is higher than the one of finding
exceptional ones not using apps, but both are typical properties of an Italian teen ager.
In case the ontology engineer needs to formalize that typical Italian teen agers do not
love sport, he just need to have T(ItalianTeenAger ) vp ¬SportLover in his KB with
a suitable p.
4 Extensions of ABox
Given a KB, we define the finite set Tip of concepts occurring in the scope of the
typicality operator, i.e. Tip = {C | T(C) vp D ∈ KB}. Given an individual a
explicitly named in the ABox, we define the set of typicality assumptions T(C)(a) that
can be minimally entailed from KB in the nonmonotonic logic ALC + TRaCl R , with C ∈
Tip. We then consider an ordered set TipA of pairs (a, C) of all possible assumptions
T(C)(a), for all concepts C ∈ Tip and all individual constants a in the ABox.
Definition 5 (Assumptions in ALC + TPR ). Given an ALC + TPR KB=(T , A), let T 0
be the set of inclusions of T without probabilities, namely
T 0 = {T(C) v D | T(C) vp D ∈ T } ∪ {C v D ∈ T }.
Given a finite set of concepts Tip, we define, for each individual name a occurring in
A: Tipa = {C ∈ Tip | (T 0 , A) |=ALC+TRaCl T(C)(a)}. We also define TipA =
R
{(a, C) | C ∈ Tipa and a occurs in A} and we impose an order on its elements:
TipA = [(a1 , C1 ), (a2 , C2 ), . . . , (an , Cn )]. Furthermore, we define the ordered multi-
set PA = [p1 , p2 , . . . , pn ], respecting the order imposed on TipA , where
m
Q
pi = pij for all T(Ci ) vpi1 D1 , T(Ci ) vpi2 D2 , . . . , T(Ci ) vpim Dm in T .
j=1
The ordered multiset PA is a tuple of the form [p1 , p2 , . . . , pn ], where pi is the probabil-
ity of the assumption T(C)(a), such that (a, C) ∈ TipA at position i. pi is the product
of all the probabilities pij of typicality inclusions T(C) vpij D in the TBox.
Following the basic idea underlying surprising scenarios outlined in [15], we con-
sider different extensions A fi of the ABox and we equip them with a probability Pi .
Starting from PA = [p1 , p2 , . . . , pn ], the first step is to build all alternative tuples
where 0 is used in place of some pi to represent that the corresponding typicality as-
sertion T(C)(a) is no longer assumed (Definition 6). Furthermore, we define the ex-
tension of the ABox corresponding to a string so obtained (Definition 7). In this way,
the highest probability is assigned to the extension of the ABox corresponding to PA ,
where all typicality assumptions are considered. The probability decreases in the other
extensions, where some typicality assumptions are discarded, thus 0 is used in place
of the corresponding pi . The probability of an extension A fi corresponding to a string
PAi = [pi1 , pi2 , . . . , pin ] is defined 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.
Definition 6 (Strings of possible assumptions S). Given a KB=(T , A), let the set
TipA and PA = [p1 , p2 , . . . , pn ] be as in Definition 5. We define the set S of all the
strings of possible assumptions with respect to KB as
S = {[s1 , s2 , . . . , sn ] | ∀i = 1, 2, . . . , n either si = pi or si = 0}
Definition 7 (Extension of ABox). Let KB=(T , A), PA = [p1, p2 , . . . , pn ] and TipA =
[(a1 , C1 ), (a2 , C2 ), . . . , (an , Cn )] as in Definition 5. Given a string of possible assump-
tions [s1 , s2 , . . . , sn ] ∈ S of Definition 6, we define the extension Ae of A with respect
to TipA and S asAe = {T(Ci )(ai ) | (ai , Ci ) ∈ TipA and si 6= 0}. We also define the
n
Q pi if si 6= 0
probability of Ae as PAe = χi where χi =
i=1 1 − pi if si = 0
It can be observed that, in ALC + TRaCl
R , the set of typicality assumptions that can
be inferred from a KB corresponds to the extension of A corresponding to the string
PA (no element is set to 0): all the typicality assertions of individuals occurring in the
ABox, that are consistent with the KB, are assumed. On the contrary, in ALC + TR ,
no typicality assumptions can be derived from a KB, and this corresponds to extending
A by the assertions corresponding to the string [0, 0, . . . , 0], i.e. by the empty set. It is
easy to observe that we obtain a probability distribution over extensions of A.
Example 2. Given a KB=(T , A), let the only typicality inclusions in T be {T(C) v0.6
D, T(E) v0.85 F }. Let a and b be the only individual constants occurring in A. Sup-
pose also that T(C)(a), T(C)(b), and T(E)(b) are entailed from KB in ALC + TRaClR .
We have that TipA = {(a, C), (b, C), (b, E)} and PA = [0.6, 0.6, 0.85]. All possible
strings, corresponding extensions of A and probabilities are shown in Table 1.
String Extension Probability
[0.6, 0.6, 0.85] A
f1 = {T(C)(a), T(C)(b), T(E)(b)} PA
g1
= 0.6 × 0.6 × 0.85 = 0.306
[0, 0, 0.85] A
f2 = {T(E)(b)} PA
g2
= (1 − 0.6) × (1 − 0.6) × 0.85 = 0.136
[0, 0.6, 0] A
f3 = {T(C)(b)} PA
g3
= (1 − 0.6) × 0.6 × (1 − 0.85) = 0.036
[0.6, 0, 0] A4 = {T(C)(a)}
f PA
g4
= 0.6 × (1 − 0.6) × (1 − 0.85) = 0.036
[0, 0.6, 0.85] A
f5 = {T(C)(b), T(E)(b)} PA
g5
= (1 − 0.6) × 0.6 × 0.85 = 0.204
[0.6, 0, 0.85] A
f6 = {T(C)(a), T(E)(b)} PA
g6
= 0.6 × (1 − 0.6) × 0.85 = 0.204
[0.6, 0.6, 0] A
f7 = {T(C)(a), T(C)(b)} PA
g7
= 0.6 × 0.6 × (1 − 0.85) = 0.054
[0, 0, 0] A
f8 = ∅ PA
g8
= (1−0.6)×(1−0.6)×(1−0.85) = 0.024
g + PA
PA
1
g + . . . + PA
2
g =
8
1
Table 1. Plausible extensions of the ABox of Example 2.
5 A Decision Procedure for Reasoning in ALC + TPR
Given KB and a query F , we distinguish two cases:
1. if F is an inclusion C v D, then it is entailed from KB if it is minimally entailed
from KB’ in the nonmonotonic ALC + TRaCl R , where KB’ 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;
2. if F is an ABox fact C(a), then it is entailed from KB if it is entailed in the mono-
tonic ALC + TR from the knowledge bases including the extensions of the ABox
of Definition 7. More in detail, we provide both (i) a notion of entailment restricted
to scenarios whose probabilities belong to a given range and (ii), similarly to [13],
a notion of probability of the entailment of a query C(a), as the sum of the proba-
bilities of all extensions from which C(a) is so entailed.
Here below are the formal definition of entailment of a query in the logic ALC+TPR .
We distinguish the case in which the query is a TBox inclusion from the one in which it
is an ABox assertion. Notice that, in the former case, probabilities do not play any role,
and, as already mentioned, entailment in ALC + TPR corresponds to entailment in the
nonmonotonic Description Logic ALC + TRaClR .
Definition 8 (Entailment in ALC + TPR ). Given a KB=(T , A), given Tip a set of
concepts, two real numbers p, q ∈ (0, 1], let E = {A
f1 , A fk } be the set of ex-
f2 , . . . , A
tensions of A of Definition 7 with respect to Tip, whose probabilities are such that
p ≤ P1 ≤ q, p ≤ P2 ≤ q, . . . , p ≤ Pk ≤ q. Let T 0 = {T(C) v D | T(C) vr
D ∈ T } ∪ {C v D ∈ T }. Given a query F , we say that F is entailed from KB in
hp,qi
ALC + TPR in range hp, qi, written KB |= P F , as follows:
ALC+TR
– if F is either an inclusion C v D or a typicality inclusion T(C) v D, if (T 0 , A)
|=ALC+TRaCl F ;
R
– if F is an ABox assertion C(a), where a ∈ O, if (T 0 , A ∪ A fi ) |=ALC+T F
R
for all Afi ∈ E. We also define the probability of the entailment of a query as
Pk
P(F ) = Pi .
i=1
Our decision procedure checks whether a query F is entailed from a given KB as in
Definition 8. We then exploit such decision procedure to show that the problem of
entailment in the logic ALC + TPR is in E XP T IME. This allows us to conclude that
reasoning about typicality and defeasible inheritance with probabilities of exceptions is
essentially inexpensive, in the sense that reasoning retains the same complexity class
of the underlying standard Description Logic ALC, which is known to be E XP T IME-
complete [1].
Given an ALC + TPR KB=(T , A) and a query F , we define a procedure computing
the following four steps:
1. compute the set Tipa of all typicality assumptions that are minimally entailed from
the knowledge base in the nonmonotonic logic ALC + TRaCl R ;
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 mono-
tonic logic ALC + TR .
Step 4 is based on reasoning in the monotonic logic ALC + TR : to this aim, the pro-
cedure relies on a polynomial encoding of ALC + TR into ALC introduced in [16].
Step 1 is based on reasoning in the nonmonotonic logic ALC + TRaClR : in this case, the
procedure computes the rational closure of an ALC + TR knowledge base by means of
the algorithm introduced in [11, 17]. Also the algorithm computing the rational closure
relies on reasoning in the monotonic logic ALC + TR , then on the above mentioned
polynomial encoding in ALC.
Let KB=(T , A) be an ALC + TPR knowledge base. Let T 0 be the set of inclusions
of T without probabilities of exceptions: T 0 = {T(C) v D | T(C) vr D ∈ T } ∪
{C v D ∈ T }, that the procedure will consider in order to reason in ALC + TR
and ALC + TRaClR for checking query entailment and finding all plausible typicality
assumptions, respectively. Other inputs of the procedure are the finite set of concepts
Tip, a query F , and two real numbers p, q ∈ (0, 1] describing a range of probabilities.
If F is C v D (where C could be T(C 0 )), we just need to check whether (T 0 , A)
|=ALC+TRaCl C v D in ALC + TRaCl R . If F is an ABox formula C(a), Algorithm 1
R
builds all possible scenarios, computes their probabilities and then checks whether KB
hp,qi
|= P F if F holds in all those scenarios having a probability between p and q.
ALC+TR
Algorithm 1 Entailment in ALC + TPR : KB |=hp,qi F
ALC+TP
R
0
1: procedure E NTAILMENT((T , A), T , F , Tip, p, q)
2: if F is of the form C v D then . If F is an inclusion, rely on ALC + TRaCl
R
0
3: return (T , A) |=ALC+TRaCl F
R
. Otherwise, F is an ABox assertion of the form C(a)
4: TipA ← ∅ . build the set S of possible assumptions
5: for each C ∈ Tip do
6: for each individual a ∈ A do . Reasoning in ALC + TRaClR
0
7: if (T , A) |=ALC+TRaCl T(C)(a) then TipA ← TipA ∪ {T(C)(a)}
R
8: PA ← ∅ . compute the probabilities of Definition 5 given T and TipA
9: for each C ∈ Tip do
10: ΠC ← 1
11: for each T(C) vp D ∈ T do ΠC ← ΠC × p
12: PA ← PA ∪ ΠC
13: S ← build strings of possible assumptions as in Definition 6 given TipA and PA
14: E ←∅ . build extensions of A
15: for each si ∈ S do
16: build the extension A
fi corresponding to si and compute P f as in Definition 7
Ai
17: if p ≤ P f ≤ q then E ← E ∪ A
Ai
fi . select extensions with probability in hp, qi
18: for each Afi ∈ E do . query entailment in ALC + TR
0
if (T , A ∪ Afi ) 6|=ALC+T F then return KB 6|=hp,qi
19: R P F
ALC+TR
hp,qi
20: return KB |= P F . F is entailed in all extensions
ALC+TR
We can exploit the procedure of Algorithm 1 to show that the problem of entail-
ment in the logic ALC + TPR is E XP T IME complete. This allows us to conclude that
reasoning about typicality and defeasible inheritance with probabilities of exceptions is
essentially inexpensive, since reasoning retains the same complexity class of the under-
lying standard ALC, which is known to be E XP T IME-complete [1].
Theorem 1 (Complexity of entailment). Given a KB in ALC + TPR , real numbers
p, q ∈ (0, 1] and a query F whose size is polynomial in the size of KB, the problem of
hp,qi
checking whether KB |= P F is E XP T IME -complete.
ALC+TR
Proof. (sketch, [14]) The algorithm checks, for each concept C ∈ Tip and for each
individual a whether T(C)(a) is minimally entailed from KB in nonmonotonic ALC +
TRaCl
R . Let n be the length of the string representing KB. By definition, the size of Tip
is O(n). There are O(n2 ) concepts T(C)(a), for each of them the algorithm relies on
reasoning in ALC + TRaCl R , which is in E XP T IME [11]. Building PA can be solved with
O(n2 ) operations. The algorithm considers all possible strings obtained by assuming
(or not) each typicality assumption T(C)(a) (they are O(n2 )) in order to compute the
set S of plausible extensions. For each si , we have either si = 0 or si 6= 0 , then
2 × 2 × . . . × 2 different strings, thus S has exponential size in n. Selecting extensions
whose probabilities PA fi are in the range [p, q] can be solved in E XP T IME , then the
algorithm relies on reasoning in monotonic ALC + TR , in order to check whether F is
entailed in selected extensions in E, whose size is O(2n ): we have O(2n ) calls to query
entailment in ALC + TR , which is E XP T IME-complete. 2
Let us now conclude Example 1 introduced in Section 3 in the light of the definitions
provided above.
Example 3 (Reasoning in ALC + TPR part 2). Suppose that the ABox is
A = {AtypicalDepressed (john), ProstateCancerPatient(greg)},
we can consider two typicality assumptions: (a) T(AtypicalDepressed )(john) and (b)
T(ProstateCancerPatient)(greg). We distinguish among four different extensions:
1. both (a) and (b) are assumed: in this scenario, whose probability is 0.7 × (0.6 ×
0.8) = 0.336, we conclude that both John and Greg have mood swings, and that
Greg has nocturia;
2. we assume (b) but not (a): this scenario has probability (1 − 0.7) × (0.6 × 0.8) =
0.144, and we can only conclude ∃hasSymptom.MoodReactivity(greg) and
∃hasSymptom.Nocturia(greg);
3. we assume (a) and not (b): this scenario, having a probability 0.7 × (1 − (0.6 ×
0.8)) = 0.364, allows us to conclude ∃hasSymptom.MoodReactivity(john);
4. neither (a) nor (b) is added to A: here the probability is (1 − 0.7) × (1 − (0.6 ×
0.8)) = 0.156, but we are not able to conclude anything about John and Greg.
The probability that John has mood swings is defined as the sum of the probabilities of
scenarios where such inference can be performed, namely scenarios (1) and (3), and it
is therefore 0.336 + 0.364 = 0.7. Similarly, the probability that Greg has nocturia and
mood swings is 0.336 + 0.144 = 0.48.
6 Conclusions
We have described the Description Logic ALC + TPR introduced in [14], which extends
the nonmonotonic Description Logic of typicality ALC + TRaCl R by means of probabil-
ities equipping typicality inclusions. Probabilities of exceptions are then used in order
to reason about plausible scenarios, obtained by selecting only some – i.e., not neces-
sarily all – typicality assumptions and whose probabilities belong to a given and fixed
range. We have also presented a decision procedure for reasoning in ALC +TPR , and we
have shown that such a procedure can be exploited in order to estimate the complexity
of the proposed logic, namely to show that reasoning in DLs with rational closure and
probabilities of exceptions remains in E XP T IME as in the underlying standard ALC.
The logic ALC +TPR , as well as the underlying ALC +TRaCl R , are based on the ratio-
nal closure, then they inherit its virtues, but also its weakness. It is well known that the
main advantage of the rational closure is related to its good computational properties.
However, rational closure is affected by the “all or nothing” behavior, in the sense that
it does not allow one to separately reason about the inheritance of different properties.
For instance, let us again recall the example in the Introduction: we have that typical
Italian teen agers make use of apps for mobile devices, and normally they also listen to
trap music. Furthermore, we can consistently express that, normally, convict Italian teen
agers do not make use of apps. As a consequence, they are recognized as untypical Ital-
ian teen agers, then no inheritance of typical properties is possible, for instance it is not
possible to infer that they listen to trap music. The problem also affects the definition of
scenarios in the logic ALC + TPR : if T(ItalianTeenAger )(simone) is a typicality as-
sumption to be considered in the construction of different scenarios (since it is entailed
in ALC + TRaClR from the knowledge base), then Simone inherits all the properties of
typical Italian teen agers. On the contrary, if T(ConvictItalianTeenAger )(simone)
is the typicality assertion to be considered for the scenarios generation, no inheritance
of typical Italian teen agers is possible for Simone. In order to solve this problem, a
strengthening of a rational closure-like algorithm with defeasible inheritance networks
has been studied by [18]. In [19] the author has proposed an alternative semantics by
considering models equipped with multiple preference relations, whence with multi-
ple “typicality” operators. In this variant, it should be possible to distinguish different
aspects of typicality/exceptionality and consequently to avoid the “all or nothing” be-
havior of rational closure with respect to property inheritance.
Several nonmonotonic extensions of DLs have been proposed in the literature in
order to reason about inheritance with exceptions, essentially based on the integration
of DLs with well established nonmonotonic reasoning mechanisms [2–4, 20, 5, 6, 8],
ranging from Reiter’s defaults to minimal knowledge and negation as failure (see [9,
8] for a detailed presentation). In none of them, probability of exceptions in concept
inclusions is taken into account, as far as we know.
Probabilistic extensions of DLs, allowing one to label inclusions (and facts) with
degrees representing probabilities, have been introduced in [12, 13]. In this approach,
called DISPONTE, the authors propose the integration of probabilistic information with
DLs based on the distribution semantics for probabilistic logic programs [21]. The basic
idea is to label inclusions of the TBox as well as facts of the ABox with a real number
between 0 and 1, representing their probabilities, assuming that each axiom is indepen-
dent from each others. The resulting knowledge base defines a probability distribution
over worlds: roughly speaking, a world is obtained by choosing, for each axiom of the
KB, whether it is considered as true of false. The distribution is further extended to
queries and the probability of the entailment of a query is obtained by marginalizing
the joint distribution of the query and the worlds. There are two main differences be-
tween the logic ALC + TPR proposed in this work and probabilistic DLs. On the one
hand, as already mentioned in the Introduction, in the logic ALC + TPR probabilities
are used in order to express different degrees of admissibility of exceptions with respect
to such typicality inclusions. Probabilities are then the basis of different scenarios built
by assuming – or not – that individuals are typical instances of a given concept. On
the contrary, in DISPONTE probabilities are used to capture a notion of uncertainty
about information of the KB, therefore an inclusion C v D having a very low proba-
bility p has a significantly different meaning with respect to an inclusion T(C) vp D,
representing anyway a typical property: normally, Cs are Ds, even if with a high prob-
ability of having exceptions to such typical inclusion. On the other hand, in ALC + TPR
probabilities are restricted to typicality inclusions only. On the contrary, in DISPONTE
probabilities can be associated to concept inclusions as well as to ABox facts.
In [15] a nonmonotonic procedure for reasoning about surprising scenarios in DLs
has been proposed. In this approach, the DL ALC + TR is extended by inclusions of
the form T(C) vd D, where d is a degree of expectedness. In this logic, cardinality
restrictions play a fundamental role in order to “filter” extended ABoxes and entailment
is restricted to minimal scenarios, determined by a partial order among such extended
ABoxes, whereas in our logic ALC + TPR , entailment is defined in terms of the proba-
bility of a given scenario and can be used to estimate the probability of a given query.
In future work we aim at extending the logic ALC + TPR to more expressive De-
scription Logics, such as those underlying the standard language for ontology engineer-
ing OWL. As a first step, in [16] the logic with the typicality operator and the rational
closure construction have been applied to the logic SHIQ.
References
1. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.: The Descrip-
tion Logic Handbook - Theory, Implementation, and Applications, 2nd edition. Cambridge
(2007)
2. Bonatti, P.A., Lutz, C., Wolter, F.: The Complexity of Circumscription in DLs. Journal of
Artificial Intelligence Research (JAIR) 35 (2009) 717–773
3. Baader, F., Hollunder, B.: Priorities on defaults with prerequisites, and their application in
treating specificity in terminological default logic. Journal of Automated Reasoning (JAR)
15(1) (1995) 41–68
4. 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
5. Casini, G., Straccia, U.: Rational closure for defeasible description logics. In Janhunen,
T., Niemelä, I., eds.: Logics in Artificial Intelligence - Proceedings of the12th European
Conference (JELIA 2010). Volume 6341 of Lecture Notes in Computer Science (LNCS).,
Springer (2010) 77–90
6. Casini, G., Straccia, U.: Defeasible Inheritance-Based Description Logics. Journal of Artifi-
cial Intelligence Research (JAIR) 48 (2013) 415–473
7. Straccia, U.: Default inheritance reasoning in hybrid kl-one-style logics. In: Proceedings of
the 13th International Joint Conference on Artificial Intelligence (IJCAI’93), Morgan Kauf-
mann (1993) 676–681
8. Bonatti, P.A., Faella, M., Petrova, I., Sauro, L.: A new semantics for overriding in description
logics. Artificial Intelligence 222 (2015) 1–48
9. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: ALC+T: a preferential extension of
description logics. Fundamenta Informaticae 96 (2009) 341–372
10. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artificial
Intelligence 55(1) (1992) 1–60
11. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Semantic characterization of Rational
Closure: from Propositional Logic to Description Logics. Artificial Intelligence 226 (2015)
1–33
12. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Reasoning with probabilistic ontologies. In
Yang, Q., Wooldridge, M., eds.: Proceedings of the Twenty-Fourth International Joint Con-
ference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015,
AAAI Press (2015) 4310–4316
13. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under the
distribution semantics. Semantic Web 6(5) (2015) 477–501
14. Pozzato, G.L.: Reasoning in description logics with typicalities and probabilities of ex-
ceptions. In Antonucci, A., Cholvy, L., Papini, O., eds.: Symbolic and Quantitative Ap-
proaches to Reasoning with Uncertainty - 14th European Conference, ECSQARU 2017,
Lugano, Switzerland, July 10-14, 2017, Proceedings. Volume 10369 of Lecture Notes in
Computer Science., Springer (2017) 409–420
15. Pozzato, G.L.: Reasoning about surprising scenarios in description logics of typicality. In
Adorni, G., Cagnoni, S., Gori, M., Maratea, M., eds.: Advances in Artificial Intelligence: Pro-
ceedings of the 15th International Conference of the Italian Association for Artificial Intel-
ligence. Volume 10037 of Lecture Notes in Artificial Intelligence LNAI., Genova, Springer
(November 2016) 1–15
16. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Rational closure in SHIQ. In: DL
2014, 27th International Workshop on Description Logics. Volume 1193 of CEUR Workshop
Proceedings., CEUR-WS.org (2014) 543–555
17. Giordano, L., Gliozzi, V., Pozzato, G.L., Renzulli, R.: An efficient reasoner for description
logics of typicality and rational closure. In Artale, A., Glimm, B., Kontchakov, R., eds.:
Proceedings of the 30th International Workshop on Description Logics, Montpellier, France,
July 18-21, 2017. Volume 1879 of CEUR Workshop Proceedings., CEUR-WS.org (2017)
18. Casini, G., Straccia, U.: Defeasible Inheritance-Based Description Logics. In Walsh, T.,
ed.: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI
2011), Barcelona, Spain, Morgan Kaufmann (July 2011) 813–818
19. Gliozzi, V.: Reasoning about Multiple Aspects in Rational Closure for DLs. In Adorni, G.,
Cagnoni, S., Gori, M., Maratea, M., eds.: Advances in Artificial Intelligence: Proceedings of
the 15th International Conference of the Italian Association for Artificial Intelligence. Vol-
ume 10037 of Lecture Notes in Artificial Intelligence LNAI., Genova, Springer (November
2016) 392–405
20. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A NonMonotonic Description Logic
for Reasoning About Typicality. Artificial Intelligence 195 (2013) 165 – 202
21. Sato, T.: A statistical learning method for logic programs with distribution semantics. In
Sterling, L., ed.: Logic Programming, Proc. of the 12th International Conference on Logic
Programming, MIT Press (1995) 715–729