Abstract
In some application domains it is sometimes useful to reason about plausible but “not obvious” scenarios, excluding the most trivial ones. In this work we introduce nonmonotonic procedures for preferential Description Logics in order to reason about plausible but – in some sense – “surprising” scenarios. We consider an extension, called , of the nonmonotonic logic of typicality by inclusions of the form
Introduction
Nonmonotonic extensions of Description Logics (from now on, DLs for short) have been actively investigated since the early 90s [4–6, 28] in order to tackle the problem of representing prototypical properties of classes and to reason about defeasible inheritance. A simple but powerful nonmonotonic extension of DLs is proposed in [16–19, 21]:in this approach “typical” or “normal” properties can be directly specified by means of a “typicality” operator
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 “normally, a patient affected by depression is not able to react to positive life events”, whereas “mood reactivity (ability to feel better temporarily in response to positive life events) is a typical symptom of atypical depression” as follows:
AtypicalDepressed ⊑ Depressed
MoodReactivity
In the Description Logic standard models are extended by a function f which selects the typical/most normal instances of any concept C, i.e. the extension of
The logic itself is too weak in several application domains. Indeed, although the operator
The logic imposes to consider all typicality assumptions that are consistent with a given KB. This seems to be too strong in several application domains, in particular when the need arises of bounding the cardinality of the extension of a given concept, that is to say the number of domain elements being members of such a concept, as introduced in [1]. As a further example, consider the following KB, representing knowledge about toys and children preferences about them:
representing that, normally, action figures, tech toys and vehicles are toys appreciated by boys, whereas dollhouses are not (last inclusion). Suppose the assertional part of the KB contains the facts:
ActionFigure(techThor) (a)
TechToy(techThor) (b)
Vehicle(garagePlayset) (c)
ActionFigure(yoKaiJibanyan) (d)
Facts (a) and (b) state that the action figure of the Avengers titan hero Thor is also a tech toy, since it really speaks. Fact (c) means that a garage playset is classified in the “vehicle” category, whereas fact (d) states that we can consider the action figure of Yo-kai Watch’s Jibanyan. In the nonmonotonic logic we are able to infer the following facts:
and then that techThor, garagePlayset, and yoKaiJibanyan are all boys’ toys. This happens in because it is consistent to make the three assumptions above, that hold in all minimal models, however one should be interested in selecting only one toy (for instance, for a present), therefore considering three distinct scenarios that cannot be captured by as it is. One could think of extending the logic by means of cardinality restrictions, in the example by imposing that there is only one member of the extension of the concept BoysToy, however the resulting knowledge base would be inconsistent. Furthermore, it is sometimes useful to restrict reasoning to surprising scenarios, excluding “trivial” / “obvious” ones. For instance, in the above example about toys, one could be interested in selecting an appreciated boys’ toy, but not the most “obvious” one, in order to minimize the risk of duplication of birthday gifts. The ontology engineer could need to represent different degrees of typical properties: action figures and vehicles are both typical boys’ toys, however there are more exceptions of action figures not intended for boys only with respect to vehicles. In this respect, having the need of choosing only one present and of being not “trivial” in this choice, it could be useful to conclude that the action figure of Yo-kai Watch’s Jibanyan has to be preferred to a garage playset as well as to the “less unexpected” action figure of Thor. As another example, recently a great attention has been devoted to serendipitous search engines, that must be able to provide results that are “surprising, semantically cohesive, i.e. relevant to some information need of the user, or just interesting” [11]. In this sense, the scenario (among those satisfying cardinality restrictions) obtained by assuming the largest set of consistent typicality assumptions in corresponds to the most trivial one, whereas one could be interested in less expected ones, in which some typicality assumptions are discarded.
In this work we introduce the logic , which is based on the combination of two components. On the one hand, we allow one to express different degrees of expectedness of typicality inclusions, having the form
The plan of the paper is as follows. In Section 2 we recall Description Logics of typicality and , then in Section 3 we introduce the logic , allowing to express degrees of expectedness of typicality inclusions as well as cardinality restrictions, and to reason about surprising scenarios. In Section 4 we provide a decision procedure for checking query entailment in , then we exploit it to show that the complexity of reasoning in is in
This work is an extended and improved version of [25], whereas preliminary ideas have been outlined by considering an extension of the lightweight DL-Lite core for surprising scenarios in [24].
Preferential Description Logics
The monotonic logic
The logic is obtained by adding to standard the typicality operator
The semantics of the
(f
(f
(f
(f
(f
(f
The semantics of the
Given standard definitions of satisfiability of a KB in a model, we define a notion of entailment in . Given a query F (either an inclusion C ⊑ 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 , if F holds in all models satisfying KB.
The nonmonotonic logic
Even if the typicality operator
The nonmonotonic semantics of 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 is a minimal canonical model of KB if it satisfies KB, it is minimal and it is canonical
1
. A query F is minimally entailed from a KB, written KB , if it holds in all minimal canonical models of KB. In [21] it is shown that query entailment in is in
Between and : The logic
In this section we define an alternative semantics that allows us to express a degree of expectedness for the typicality inclusions and to limit the number of typicality assumptions in the ABox in order to obtain less predictable scenarios. The basic idea is similar to the one proposed in [16], where a completion of an +
The logic allows one to express cardinality restrictions in the TBox. More expressive DLs allow one to specify (un)qualified number restrictions, in order to specify the number of possible elements filling a given role R. As an example, number restrictions allow one to express that a student attends to 3 courses. Number restrictions are therefore “localized to the fillers of one particular role” [1], for instance we can have Student ⊑ = 3 Attends. Course as a restriction on the number of role fillers of the role Attends. However one could need to express global restrictions on the number of domain elements belonging to a given concept, for instance to express that in the whole domain there are exactly 3 courses. In DLs not allowing cardinality restrictions one can only express that every student must attend to three courses, but not that all must attend to the same ones. In the logic , cardinality restrictions on concepts are added to the TBox: they are assertions of the form either (≥ n C) or (≤ n C) or (= n C), where n is a positive integer and C is a concept, as proposed in [1]. This is formally defined in the next definition, where, given a set S, ♯S is the cardinality of S.
C : = A ∣ ⊤ ∣ ⊥ ∣ ¬ C ∣ C ⊓ C ∣ C ⊔ C ∣ ∀ R . C ∣ ∃ R . C
An
knowledge base is a pair (). contains axioms of the form: C ⊑ C; (⊙ n C), where ⊙ ∈ {= , ≤ , ≥} and .
contains assertions of the form C (a) and R (a, b), where .
Given an inclusion
It is known that axioms expressing cardinality restrictions are even more expressive than inclusions C ⊑ D or C ≐ D, the last one shortening for the pair of inclusions C ⊑ D and D ⊑ C (thus expressing that the concepts C and D have the same extensions, i.e. ). Indeed, C ≐ D means that the set of domain elements that are Cs but not Ds is empty, and viceversa (the set of domain elements that are Ds but not Cs is empty). This can be expressed by the following cardinality restriction: (= 0 ((C ⊓ ¬ D) ⊔ (¬ C ⊓ D))). The same for an inclusion of the form C ⊑ D, whose meaning is that every C element is also a D element, that can be expressed by (= 0 (C ⊓ ¬ D)) (the intersection of and the complement of is empty). Therefore, we could restrict our language to TBoxes only containing cardinality restrictions, however we have decided to consider the extended language of Definition 1 for the sake of readability.
Before introducing technical details and formal definitions (sections 3.1 and 3.2), we provide an example in order to give an intuitive idea of what we mean for reasoning about not obvious scenarios in the logic .
Depressed ⊑ Condition ProstateCancerPatient ⊑ Condition Bipolar ⊑ Condition AtypicalDepressed ⊑ Depressed (≥1 Condition) (≤2 Condition)
the last ones stating that we want to focus on at least one/at most two conditions determining patient’s symptoms. We have that
(*)
follows
2
from KB, and this is a wanted inference, since being affected by acromegaly, a rare syndrome that results when the anterior pituitary gland produces excess growth hormone, 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 also affected by acromegaly are subject to mood reactivity: given = , we have that the inclusion (*) does no longer follow from the KB with in the logic . As for rational closure, the set of facts/inclusions that are entailed from a KB is closed under the property known as rational monotonicity: for instance, from KB and the fact that
We have that is not entailed by KB, but KB is consistent. We are then interested in finding a diagnosis for Greg’s symptoms, that is to say a set of assertions such that follows from KB . The most trivial scenario suggests that Greg is affected by the bipolar disorder, i.e. , however this scenario is discarded in the logic : in this context, the condition that is taken into consideration is prostatic cancer, i.e.
One could object that no one would be interested in a medical diagnosis support system that discards the most likely explanation for a medical problem, however, as mentioned in the Introduction, the idea underlying the proposed approach is not to ignore the most expected explanation, rather to “go beyond” it in order to find (unexpected) alternative ones in case of a failure with the standard diagnosis. In other words: if the most likely explanation does not provide a solution, the logic tries to provide less obvious alternatives that could be taken into account for further investigations.
Extensions of ABox
Given a KB, we define the finite set of concepts occurring in the scope of the typicality operator, i.e. . These are the concepts whose atypical instances we want to minimize.
Given an individual a explicitly named in the ABox, we define the set of “plausible” typicality assumptions
We also define :
Intuitively, the ordered multiset is a tuple of the form [d1, d2, …, d
n
], where d
i
is the degree of expectedness of the assumption
In order to define alternative scenarios, where not all plausible assumptions are taken into account, we consider different extensions of the ABox and we introduce an order among them, allowing to range from unpredictable to trivial ones. Starting from , the first step is to build all alternative tuples where 0 is used in place of some d
i
to represent that the corresponding typicality assertion
let KB’ be the knowledge base obtained by replacing suppose that: KB’ KB’ KB’
We have that
- [0, 0, 2], corresponding to extending with the only assumption
- [0, 1, 0], corresponding to extending with the only assumption
- [1, 0, 0], corresponding to extending with the only assumption
- [0, 1, 2], corresponding to extending with the assumptions
- [1, 0, 2], corresponding to extending with the assumptions
- [1, 1, 0], corresponding to extending with the assumptions
- [0, 0, 0], corresponding to not extending (the set of typicality assumptions is empty).
Let us now introduce formal definitions for the above mentioned notions of string of assumptions and of extension of an ABox corresponding to a string.
∀i = 1, 2, …, n either s i = d i or s i = 0}
It can be observed that, in , the set of typicality assumptions that can be inferred from a KB corresponds to the extension of corresponding to the string (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 , no typicality assumptions can be derived from a KB, and this corresponds to extending by the assertions corresponding to the string [0, 0, …, 0], i.e. by the empty set.
Cardinality restrictions and perfect extensions
Let us now introduce models of the Description Logic taking cardinality restrictions into account, as well as the notion of eligible extension of the ABox as a set of typicality assumptions satisfying cardinality restrictions.
(TBox) an inclusion C ⊑ D if ; a typicality inclusion a cardinality restriction of the form (⊙ n C) if , where ⊙ ∈ {≤ , ≥ , =} and .
(ABox) an assertion of the form C (a) if ; an assertion of the form R (a, b) if .
Given a KB=(), we say that a model satisfies KB if it satisfies all the inclusions in and all the assertions in .
Intuitively, a string s whose elements are “lower” than the ones of another string r corresponds to a less trivial ABox. For instance, let us consider again the knowledge base of Example 2: given the strings s = [1, 1, 0] and r = [1, 0, 2], we have that s < r, because there exists a bijection {(1, 1), (0, 0), (1, 2)}. The assumptions
s1 = [2, 2, 0]
s2 = [2, 0, 0]
s3 = [0, 0, 2]
corresponding to the following extensions:
we have that the extensions and are not comparable, however is a proper subset of , which is more “obvious” than (indeed, s3 < s1). Therefore, we assume that the scenario represented by is weakly less trivial than the one represented by .
This is formally stated in next definition:
Given the above definitions, we can define a notion of entailment in . Intuitively, given a query F, we distinguish two cases: if F is a TBox inclusion C ⊑ D (even if it is a typicality inclusion, i.e. C has the for if F is an ABox fact C (a), we check whether F follows in the monotonic logic from a given KB, whose ABox is augmented with extensions that are minimal (perfect) as in Definition 9. We can reason either in a skeptical way, by asking that F is entailed if it follows in all KBs, obtained by considering each minimal extension of the ABox, or in a credulous way, by assuming that F is entailed if there exists at least one extension of the ABox allowing such inference.
This is stated in a rigorous manner by the following definitions:
if F is a TBox inclusion C ⊑ D, if it holds that KB ; if F is an ABox fact C (a), where , if () for all .
if F is a TBox inclusion C ⊑ D, if it holds that KB ; if F is an ABox fact C (a), where , if there exists such that () .
At a first glance, one could have the impression that the notions of rank in the semantics of , where elements with lowest rank are the most typical ones, and the semantics of expectedness of Definitions 7 and 9, where lower ranks correspond to more surprising scenarios, are in conflict. However, this is not the case: ranks in the semantics are introduced in order to define extensions of typicality concepts, and this is also considered in the expectation semantics to select plausible typicality assumptions. The rank among extensions is rather used in order to choose less trivial scenarios, to restrict the number of typicality assumptions to satisfy cardinality restrictions: the unexpectedness is the additional ingredient to select surprising scenarios by fixing cardinality restrictions, where all candidates try to maximize the typicality of individuals.
Let us conclude this section by recalling the example inspired by sports entertainment taken from [24].
(= 1 RoyalRumbleWinner) (T4)
the last one stating that there could be only one winner. Concerning typicality inclusions, we represent the facts that normally, a face wrestler wins the Royal Rumble match (T1), however this admits more exceptions with respect to the fact that, typically, an athlete whose victory has been predicted by wrestling web sites normally wins the Royal Rumble match (T3), which is in turn more surprising than the most “obvious” inclusion, namely that an athlete returning from an injury wins the Royal Rumble match (T2). Let the ABox be:
FaceWrestler(dean)
Returning(seth)
FaceWrestler(roman)
Predicted(roman)
In the logic , we can infer that Dean is the winner of the Royal Rumble match:
KB
KB
since there is only one perfect extension. Let . By Definition 2 above, we have that: , , {Returning}. Furthermore, consider in this order. Concerning the degrees of expectedness, we have . As mentioned, in the minimal model semantics forces all the consistent typicality assumptions, namely we are considering an ABox extended with the following facts:
corresponding (in the sense of Definition 4) to the multiset [1, 1, 2, 3]. However, in we obtain that Dean, Roman and Seth are all winners, against the fact that we want to have only one winner: the extension corresponding to [1, 1, 2, 3] is indeed not eligible in the sense of Definition 6. In order to find only one winner and to obtain a non-trivial outcome of the match, we consider the set of all possible strings of typicality assumptions (Definition 3). The only eligible extensions of the ABox are:
, by [0, 0, 0, 3]
, by [0, 0, 2, 0]
, by [1, 0, 0, 0]
, by [0, 1, 0, 0]
We have that and are less trivial than , because [1, 0, 0, 0] < [0, 1, 2, 0] and [0, 1, 0, 0] < [0, 1, 2, 0]. Furthermore, and are less trivial than (again, [1, 0, 0, 0] < [0, 0, 0, 3] and [0, 1, 0, 0] < [0, 0, 0, 3]). Moreover, and are less trivial than (again, [1, 0, 0, 0] < [0, 0, 0, 2] and [0, 1, 0, 0] < [0, 0, 0, 2]). The strings [1, 0, 0, 0] and [0, 1, 0, 0] are not comparable, however is weakly less trivial than , since and [1, 0, 0, 0] < [0, 1, 2, 0]. This allows one to conclude that is minimal (the perfect extension) and to suggest that Dean has to be chosen as the winner of the Royal Rumble match.
A decision procedure for
In this section we describe a decision procedure for reasoning in the logic . We consider skeptical and credulous entailment. In both cases, we exploit the decision procedure to show that the problem of entailment in the logic is in
The procedure performs the following steps: compute the set of all typicality assumptions that are minimally entailed from the KB in the nonmonotonic logic ; compute all possible extensions of the ABox and select perfect extensions; check whether the query F is entailed from at least one extension/all the extensions of KB in the monotonic logic plus cardinality restrictions.
Step 3 is based on reasoning in the monotonic logic : to this aim, the procedure relies on a polynomial encoding of into introduced in [20] and then on reasoning with cardinality restrictions. Step 1 is based on reasoning in the nonmonotonic logic : in this case, the procedure computes the rational closure of an knowledge base by means of the algorithm introduced in [21], which is sound and complete with respect to the minimal model semantics recalled in Section 2.2. Also the algorithm computing the rational closure relies on reasoning in the monotonic logic , then on the above mentioned polynomial encoding in . We assume unary encoding of numbers in cardinality restrictions in order to exploit the results in [29], namely that reasoning in , extending with qualified number restrictions, is
Reasoning in
In order to reason in , in [20] the authors provide the following polynomial encoding in standard of KB
4
. The idea on which the encoding is based exploits the definition of the typicality operator
Let KB=() be a knowledge base where does not contain positive typicality assertions on individuals of the form
In order to capture the properties of the □ modality, a new role R is introduced to represent the relation < in preferential models, and the following inclusions are introduced in :
Box¬A ⊑ ∀ R. (¬A ⊓ Box¬A)
¬Box¬A ⊑ ∃ R . (A ⊓ Box¬A)
The first inclusion accounts for the transitivity of <. The second inclusion 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 C
l
⊑ C
r
is not a typicality inclusion, then and ; if C
l
⊑ C
r
is a typicality inclusion
The size of KB’ is polynomial in the size of the KB. The same for and , assuming the size of C l and C r be polynomial in the size of KB.
Given the above encoding, in [20] it is shown that (we write KB to mean that F holds in all models of KB): KB if and only if KB’
and, as a consequence, that the problem of deciding entailment in is in
Reasoning in
We have mentioned that the semantics of the logic corresponds to the rational closure of an knowledge base introduced in [21]. Here we recall this machinery, essentially an extension to of the definition of rational closure introduced by Lehmann and Magidor in [23] for the propositional case. We first consider the rational closure with respect to the TBox, in which essentially we only consider which inclusions belong to the rational closure of KB. Next we will consider rational closure with respect to the ABox, in which we consider the individuals explicitly named in the ABox itself.
Similarly to the rational closure for propositional logic in [23], we introduce a sequence of knowledge bases, starting from the initial one, KB, in order to iteratively use exceptionality in the construction of the rational closure. At each step, in order to reason about the following exceptional subset of KB, we remove the inclusions
(as a consequence of the next Definition 14, these are the Bs such that rank (B) = i - 1).
Clearly , while Observe that, being KB finite, there is a least n ≥ 0 such that, for all or . We take as the last element of the sequence of knowledge bases starting from KB.
Informally, for the definition of , if (i.e., a is a typical B-element), and B has rank i - 1,then, for all the inclusions
Consider the least n ≥ 0 such that, for all or . Then from the above definition it follows that if a concept C has a rank, its highest possible value is n. The notion of rank of a formula allows one to define the rational closure of a knowledge base KB with respect to the TBox.
Let us now consider the rational closure of the ABox as defined in [21]:
Given a rank assignment k
j
we define: for each a
i
: s.t. let for all just calculated for all a1, …, a
m
in We say that k
j
is consistent with () if: if , then k
j
(a
i
) = rank(C); is consistent in ; We say that k
j
is minimal and consistent with () if k
j
is consistent with () and there is no k
i
consistent with () s.t. for all a
i
, k
i
(a
i
) ≤ k
j
(a
i
) and for some b, k
i
(b) < k
j
(b). The rational closure of () is the set of all assertions derivable in from for all minimal consistent rank assignments k
j
: .
In [21] it is shown that, given a knowledge base KB=(), the semantics based on rational models of Section 2.2 is equivalent with the above notion of rational closure of KB, namely: given an inclusion C ⊑ D, KB if and only if given an ABox fact C (a), KB if and only if .
Moreover, it is shown that the problem of deciding whether is in
1:
2: ▹ build the set of possible assumptions
3:
4:
5:
6: build the ordered multiset of avg degrees of Definition 2 given and
7: build strings of possible assumptions as in Definition 3 given and
8: ▹build plausible extensions of
9:
10: build the extension corresponding to d i
11:
12: ▹select eligible extensions checking cardinality restrictions
13:
14:
15:
16:
17:
18:
19: ▹select perfect extensions
20:
21:
22:
23:
1:
2: ▹build the set of possible assumptions
3:
4:
5:
6: build the ordered multiset of avg degrees of Definition 2 given and
7: build strings of possible assumptions as in Definition 3 given and
8: ▹build plausible extensions of
9:
10: build the extension corresponding to d i
11:
12: ▹select eligible extensions checking cardinality restrictions
13:
14:
15:
16:
17:
18:
19: ▹select perfect extensions
20:
21:
22:
23:
Reasoning in : the whole procedure
Let KB=() be an knowledge base, where is a set of cardinality restrictions and does not contain cardinality restrictions. Let be the set of inclusions of without the degrees of expectedness: , that the procedure will take into account in order to reason in and for checking query entailment and finding all plausible typicality assumptions, respectively. Other inputs of the procedure are a finite set of concepts and a query F. If F is an inclusion C ⊑ D (even with typicality, i.e. C has the form
By exploiting the procedures described by Algorithms 1 and 2, we can estimate the complexity of reasoning in the logic :
lines 2-5: the algorithm checks, for each concept and for each individual name a of the ABox whether line 6: the algorithm builds the ordered multiset of Definition 2: obviously, this operation consists in computing the average of the degrees of expectedness of the inclusions , which are O (n), for each , again O (n). Therefore, this problem can be solved with O (n2) operations, i.e. in polynomial time; line 7: the algorithm builds the set of possible assumptions (Definition 3). We have to consider all possible strings obtained by assuming (or not) each typicality assumption lines 8-11: the algorithm builds the extensions of the ABox corresponding to strings of , again an exponential number of extensions (O (2
n
2
)); lines 12-15: the algorithm checks, for each extension of the ABox, whether it satisfies cardinality constraints in : therefore, the algorithm makes O (2
n
2
) calls to a procedure checking the satisfiability of a knowledge base in plus cardinality restrictions, that is in lines 17-18: the algorithm compares each pair of strings (d
i
, d
j
) of possible assumptions, in order to check whether d
i
< d
j
and, therefore, conclude that the extension is more surprising than . To this aim, we consider the following procedure. First, elements (integers) of d
i
and d
j
are ordered, and since they are O (n2), this can be done in O (n2logn2) steps. Call and the ordered strings. Then, we proceed as follows: an index k is used to scan elements in and ; at each step, if (integer in position k of ) is ≤ of , then k is incremented in order to index the subsequent integer in and , otherwise the procedure answers that . If the scan of k is completed, and all integers of the strings have been considered, the procedure answers that . The procedure requires O (n2) steps, and since there are O (2
n
2
) strings in , these operations are performed in line 19: the algorithm builds the set of perfect extensions, that is to say extensions of the ABox that are minimal with respect to the relation < introduced in line 18 by the algorithm. The algorithm checks, for each extension , whether it is minimal: to this aim, for each , the algorithm checks whether , and this can be done in constant time (we could think of implementing the relation < introduced in step 18 by means of a bi-dimensional array, therefore this operation corresponds to a direct access to raw i and column j of such array). For each extension (and they are O (2
n
)) the algorithm considers all the other O (2
n
) extensions, therefore, since 2
n
× 2
n
= 22n, this step can be solved in steps 20-23: the algorithm relies on reasoning in monotonic plus cardinality restrictions in order to check whether the query F is entailed in all perfect extensions in . Since the size of is O (2
n
), we have O (2
n
) call to query entailment in , which is an
We obtain the same result for credulous reasoning:
Since reasoning in the underlying standard is
Reasoning about Scenarios “in the middle”
The approach described in the previous sections could be extended in order to take also into account all the extensions of the ABox satisfying cardinality restrictions, that is to say the eligible extensions of Definition 6. The idea is to reason about all plausible scenarios, each one equipped with a degree of expectedness, representing a sort of probability, allowing the user to choose the one he considers more adequate for his application, ranging from the most trivial scenario to the most surprising one.
We iteratively define sets of extensions representing scenarios “in the middle”: intuitively, at each step, we consider the extensions of ABox that are minimal w.r.t. the weak preference among extensions of ABox in Definition 8. At the next step, only remaining eligible extensions are considered, and so on. This is formally stated as follows:
we let , where is the set of eligible extensions that are minimal as in Definition 9; while is not empty, let be the extensions in that are minimal with respect to the order relation of Definition 8.
Definition 17 describes a sequence of sets of eligible extensions with a degree of expectedness i associated to each one. We can formally define what we mean for reasoning in more or less surprising scenarios:
1:
2: … lines 2–18 as in Algorithm 1 …
19: ▹select perfect extensions (degree 0)
20: j ← 0
21:
22:
23:
24: j ← j + 1
25: ▹select the extensions at degree i
26:
27:
28:
29:
Since it computes all the extensions of an ABox, Algorithm 1 can be slightly modified in order to compute the sets of extensions in order to reason in plausible scenarios with a given degree of expectedness, according to Definition 18. Algorithm 3 shows the complete procedure for skeptical reasoning, that can be exploited in order to show that also reasoning about scenarios “in the middle” is
26:
27:
28:
29:
1:
2: … lines 2–18 as in Algorithm 1 …
19: ▹select perfect extensions (degree 0)
20: j ← 0
21:
22:
23:
24: j ← j + 1
25:
26: i ← n
27:
28:
29: i ← i + 1
30:
31:
32:
33:
It is easy to observe that reasoning in perfect extensions, corresponding to the most “surprising” scenarios, as in Definitions 10 and 11, is an instance of entailment at degree i, namely checking whether a query F is entailed in perfect extensions corresponds to checking whether F is entailed at degree i = 0 with respect to entailment inDefinition 18.
A further generalization of the reasoning procedure allows us also to define (credulous and skeptical) entailment in combinations of plausible scenarios. As an example, one could be interested in reasoning in all scenarios such that i < k for a given and fixed k. As a general case, we define a notion of entailment restricted to scenarios with degrees of expectations between n and m, as in the followingdefinition:
The resulting procedure is formally stated by Algorithm 3k, and such a procedure again allows us to show that the complexity of reasoning in the logic remains
Related works
The need for representing prototypical properties and to reason about inheritance with exceptions in DLs has motivated the study of nonmonotonic extensions of DLs. Several nonmonotonic extensions of DLs have been proposed in the literature, essentially based on the integration of DLs with well established nonmonotonic reasoning mechanisms. Here we focus on the approaches that can be considered more similar to the peculiarities of the logic introduced in this work, whereas we refer to [16, 19] for a detailed discussion about other extensions of DLs for defeasible inheritance. We consider: approaches allowing degrees/priorities among TBox inclusions; probabilistic extensions of DLs, allowing to label inclusions (and facts) with degrees representing probabilities.
In [3] an extension of DL with Reiter’s default logic is proposed. Being based on a minimal models mechanism, our approach is strongly related to the one based on circumscription 5 [6–8, 10] and to the semantics proposed in [5], where defeasible inclusions are allowed besides classical concept inclusions. The problem of conflicting defaults and of priorities among inclusions has been studied since seminal works in the context of inheritance networks [12]. In the field of nonmonotonic extensions of DLs, in order to overcome the problem of modeling inheritance with exceptions, extensions of DLs with prioritized defaults have been studied in [4, 28], whereas priorities among defeasible inclusions are allowed in [5].
In the logic , degrees of expectedness are not intended to represent priorities among inclusions, since dealing with conflicting inclusions is provided for free by the preferential semantics of the typicality operator which allows one to give preference to the most specific information, without the need of any additional machinery. As a further example, if TBox is:
SumoWrestler ⊑ Athlete
and the ABox is {Athlete (chad)}, then the fact ¬Fat (chad) is entailed in the logic , whereas it is no longer entailed if we add to the ABox the fact SumoWrestler(chad), from which the fact Fat(chad) is rather entailed. It is easy to observe that the degree of expectedness in the two inclusions does not play any role in this, as a difference with priorities on defaults of the above mentioned approaches.
The use of positive integers for expressing degrees of expectedness in the logic is only a way of formalizing a partial order among typicality inclusions, however all properties expressed by typicality inclusions of the form
The extension of DLs highlighted in this work suggests a relation with probabilistic Description Logics under the distribution semantics [26]. In this approach, called DISPONTE, the authors propose the integration of probabilistic information with DLs based on the distribution semantics for probabilistic logic programs [27]. 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 independent 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 a query is obtained by marginalizing the joint distribution of the query and the worlds.
As an example, consider the following variant of the knowledge base inspired by the people and pets ontology in [26]:
0.3 : : ∃ hasAnimal . Pet ⊑ NatureLover (1)
0.6 : : Cat ⊑ Pet (2)
0.9 : : Cat (tom) (3)
hasAnimal(kevin, tom) (4)
The inclusion (1) expresses that individuals that own a pet are nature lovers with a 30% probability, whereas (2) is used to state that cats are pets with probability 60%. The ABox fact (3) represents that Tom is a cat with probability 90%. Inclusions (1), (2) and (3) are probabilistic axioms, whereas (4) is a certain axiom, that must always hold. The KB has the following eight possible worlds:
{((1), 0), ((2), 0), ((3), 0)}
{((1), 0), ((2), 0), ((3), 1)}
{((1), 0), ((2), 1), ((3), 0)}
{((1), 0), ((2), 1), ((3), 1)}
{((1), 1), ((2), 0), ((3), 0)}
{((1), 1), ((2), 0), ((3), 1)}
{((1), 1), ((2), 1), ((3), 0)}
{((1), 1), ((2), 1), ((3), 1)}
representing all possible combinations of considering/not considering each probabilistic axiom. For instance, the world {((1), 1), ((2), 0), ((3), 1)} represents the situation in which we have that (1) and (3) hold, i.e. ∃hasAnimal . Pet ⊑ NatureLover and Cat(tom), whereas (2) does not. The query
NatureLover(kevin)
is true only in the last world, i.e. having that (1), (2) and (3) are all true, whereas it is false in all the other ones. The probability of such a query is P (NatureLover (kevin)) =0.3 × 0.6 × 0.9 = 0.162.
To the best of our knowledge, the literature lacks a formalization of surprising scenarios in probabilistic formalizations of knowledge, however it is worth observing that a surprising scenario could be defined as a set of facts with a low probability, then one can think of restricting the attention to less probable outcomes corresponding, for instance, to worlds where corresponding probabilities are lower than a given threshold. However, as mentioned above, degrees in the logic are used in order to represent a level of expectedness in typicality inclusions, whereas in DISPONTE KBs we can express inclusions like (1) above that cannot express prototypical properties: in we would not have something like
Let us recall the example from sports entertainment at the end of Section 3: we can think of representing the typicality inclusions
with the following ones in the language of probabilistic DLs:
0.6: : FaceWrestler ⊑ RoyalRumbleWinner (a)
0.8: : Returning ⊑ RoyalRumbleWinner (b)
0.7: : Predicted ⊑ RoyalRumbleWinner (c)
The ABox facts
In the first case, we have that the predicted winner, Roman, wins the match, whereas in the second one the winner is the returning athlete Seth. In none of them, the most surprising outcome in which Dean wins the Royal Rumble match is taken into account. As an alternative, one can think of formalizing the initial TBox with certain axioms, as follows:
FaceWrestler ⊑ RoyalRumbleWinner
Returning ⊑ RoyalRumbleWinner
Predicted ⊑ RoyalRumbleWinner
and to capture degrees of expectedness with the following probabilistic ABox:
{((i), 1), ((ii), 0), ((iii), 0), ((iv), 0)}
{((i), 0), ((ii), 1), ((iii), 0), ((iv), 0)}
{((i), 0), ((ii), 0), ((iii), 1), ((iv), 0)}
(*) {((i), 0), ((ii), 1), ((iii), 1), ((iv), 0)}
{((i), 0), ((ii), 0), ((iii), 0), ((iv), 1)}
In the first world, Dean is the winner with a probability of 10%, whereas in the last one Seth is the winner with a probability of 30%. In all other worlds, Roman is the winner. It is worth noticing that, with this knowledge base, in order to reason about typicality we need to “weaken” certain facts of the ABox to probabilistic ones, losing the opportunity to reason about them with respect to other properties. For instance, if the TBox further contains FaceWrestler ⊑ KidsFavourite, then in the logic we are still able to infer that kids are fans of both Dean and Roman, since eligible extensions select only typicality assumptions: only one of them is a typical face wrestler, but both are face wrestlers, then obtaining support by the kids. On the contrary, in the DLs with DISPONTE semantics with the above formulation, Dean and Roman are face wrestlers with a certain probability, and this also affects the probabilities of being kids’ favourites or not.
Conclusions and future issues
In this work we have provided a nonmonotonic procedure for preferential Description Logics in order to reason about surprising scenarios in presence of cardinality restrictions on concepts. We have introduced the Description Logic of typicality , an extension of with a typicality operator
We have also described a procedure for reasoning in exploiting reasoning mechanisms in the logics and , the last one relying on a notion of rational closure for Description Logics. This procedure allowed us to show that entailment in is
The extension of DLs of typicality with cardinality restrictions is of its own interest, and one can think of considering cardinality restrictions not limited to plausible scenarios of the logic , but directly applied to the nonmonotonic semantics of . Furthermore, we aim at studying also cardinality restrictions on roles.
In future work we aim at extending this approach to more expressive Description Logics, in particular those underlying the standard language for ontology engineering OWL. As a first step, in [20] the logic with the typicality operator and the rational closure construction have been applied to the logic .
Footnotes
As mentioned, at this point of the presentation we only want to give an intuition of the inferences characterizing the logic . Formal definitions of nonmonotonic entailment in will be provided in Definitions 10 and 11.
Other aggregation functions could be used to define d i (e.g. maximum/minimum degree). We aim at studying the impact of this choice on the reasoning machinery in future research.
