The representation of defeasible information in Description Logics is a well-known issue and many formal approaches have been proposed. However, in these proposals, little attention has been devoted to studying their capabilities in capturing the interpretation of typicality and exceptions from an ontological and cognitive point of view. In this regard, we are developing a model of defeasible knowledge for description logics based on combining ideas from prototype theory, weighted description logic (aka 'tooth logic'), and earlier work on justifiable exceptions. This machinery is then used to determine exceptions in case of conflicting axioms. In this paper, we analyse this formalisation with respect to some interesting cases where the defeasible properties to which we may have exceptions are also present as features in prototype descriptions. The analysis will suggest that a new preference order, which considers what happens inside the models, may be best suited and we outline how this new preference order can be defined.
The study of defeasible reasoning and its modelling through non-monotonic logics has a long story
in Artificial Intelligence [
In the present paper, we build on that formalism by proposing a more elaborate preference relation
on models which is able to address some shortcomings of the previous formulation. Therefore, we firstly
describe the approach of [
In our approach, we distinguish two parts in the knowledge bases: the actual DL knowledge base, which represents the knowledge of interest and can contain defeasible axioms and information about features of individuals, and a separate set containing prototype definitions.
In this section we outline the syntax and semantics of such enriched KBs.
The following definitions are independent from the DL language used for representing the main knowledge base: we consider a fixed concept language ℒΣ based on a DL signature Σ with disjoint and non-empty sets NC of concept names, NR of role names, and NI of individual names. We identify a subset of the concept names as denoting prototype names by assuming a subset NP ⊆ NC. For simplicity, we call general concepts the concepts composed only of concepts in NC ∖ NP.
The features associated with prototypes together with the degree of their importance are given in prototype definitions .
Definition 1 (Positive prototype definition) . Let ∈ NP be a prototype name, let 1, . . . , be general concepts of ℒΣ and let = (1, . . . , ) ∈ Q be a weight vector of rational numbers, where for every ∈ {1, . . . , } we have > 0. Then, the expression
(1 : 1, . . . , : ) is called a (positive) prototype definition for .
Note that this definition of prototypes is similar to the definition of concepts by the tooth operator
defined in [
In the present work we are agnostic with respect to where the weights come from. However, in future
we plan to study sources for getting these weights as for example, learning models.
Moreover, we use here rational weights, which is suficient for practical purposes. Real numbers could
be allowed as well, but this would not substantially change the formal setup; this is also the case for the
related perceptron logic [
Another important remark is that, since some features could be mutually exclusive (e.g. the color of an apple can be red or green, but not both), prototype definitions should not be seen as denoting a “perfect individual”.
A final point on prototype definitions is that to allow for a direct comparison across scores of diferent
prototypes, these need to be normalised to a common value interval, possibly with a scoring function
that does not depend on the number of features defining diferent prototypes. In an initial proposal, we
simply constrained the weights of features to be in the [
In the knowledge part of the KB, we can use prototype names in DL axioms to describe properties of the members of such classes. Here we consider the case in which prototype names are only used as primitive concepts on the left-hand side of concept inclusions.
Definition 2 (Prototype axiom). A concept inclusion of the type ⊑ is a prototype axiom of ℒΣ if ∈ NP and is a general concept of ℒΣ.
Intuitively, these axioms are not absolute and can be “overridden” by prototype instances (cf. defeasible
axioms in [
As noted above, we consider knowledge bases which can contain prototype axioms and which are enriched with an accessory KB, the PBox providing prototype definitions. Formally: Definition 3 (Prototyped Knowledge Base, PKB). A prototyped knowledge base, PKB for short, in language ℒΣ is a triple K = ⟨ , , ⟩ where: – = ⊎ is a DL TBox consisting of concept inclusion axioms of the form ⊑ , and partitioned into the disjoint sets of prototype axioms and of general concept inclusions based on general concepts; – = ⊎ is a set of ABox assertions partitioned into the disjoint sets of prototype assertions (of the form () with ∈ NP and ∈ NI) and of assertions for general concepts and roles; – is a set of prototype definitions, exactly one for each prototype name ∈ NP appearing in the prototype TBox .
Remark. Note that a PKB ⟨ , , ∅⟩ can be seen as a standard DL knowledge base. Example 1. Consider the following prototyped knowledge base = ⟨ , , ⟩: = { Dog ⊑ Trusted, Wolf ⊑ ¬Trusted, Dog ⊑ hasLegs, Wolf ⊑ hasLegs }, = { Dog(balto), Wolf(balto), Dog(pluto), Wolf(alberto), Dog(cerberus), livesInWoods(balto), hasLegs(balto), isTamed(balto), hasCollar(pluto), hasLegs(pluto), isTamed(pluto), hasLegs(alberto), Hunts(alberto) ¬Trusted(cerberus)}, = { Wolf(livesInWoods : 10, hasLegs : 4, livesInPack : 8, Hunts : 11),
Dog(hasCollar : 33, livesInHouse : 22, hasLegs : 11, isTamed : 44) } Below we give a semantics for this kind of PKB which will entail and justify the conclusion that balto is a trusted dog which is a wolf, without being inconsistent, and that cerberus is an exceptional dog with respect to the property of dogs of being trusted. Note that in the case of the instances pluto and alberto no contradiction arises, thus we want that the axioms in are applied to them normally. Observe that the conflict regarding balto has the same structure of the so called Nixon diamond. ◇
The semantics of PKBs is based on standard interpretations for the underlying DL ℒΣ. In fact, interpretations of a PKB are DL interpretations for its knowledge base part.
Definition 4 (Interpretation). An interpretation ℐ is pair ⟨∆ ℐ , · ℐ ⟩ for signature Σ with a non-empty
domain, ∆ ℐ , ℐ ∈ ∆ ℐ for every ∈ NI, ℐ ⊆ ∆ ℐ for every ∈ NC, ℐ ⊆ ∆ ℐ × ∆ ℐ for every ∈ NR,
and where the extension of complex concepts is defined recursively as usual for language ℒΣ.
We are not giving a DL interpretation to the prototype definition expressions in , however, we need to
introduce additional semantic structure to manage exceptions to prototype axioms in , exploiting the
prototype definition expressions in . We consider the notion of axiom instantiation as defined in [
A clashing set for ⟨, ⟩ is a satisfiable set ⟨, ⟩ of ABox assertions s.t. ⟨, ⟩ ∪ { ()} is unsatisfiable.
1As in [
Intuitively, an exception assumption ⟨ ⊑ , ⟩ states that we assume that is an exception to the prototype axiom ⊑ in a given interpretation. Then, the fact that a clashing set ⟨ ⊑,⟩ for ⟨ ⊑ , ⟩ is derived by such an interpretation gives a “justification” of the validity of the assumption of overriding in terms of ABox assertions. This intuition is reflected in the definition of models: we first extend interpretations with a set of clashing assumptions.
Definition 6 ( -interpretation). A -interpretation is a structure ℐ = ⟨ℐ, ⟩ where ℐ is an interpretation and is a set of exception assumptions.
Then, -models for a PKB K are those -interpretations that verify “strict” axioms in and defeasibly apply prototype axioms in (excluding the exceptional instances in ).
Definition 7 ( -model). Given a PKB K, a -interpretation ℐ = ⟨ℐ, ⟩ is a -model for K (denoted ℐ |= K), if the following holds: (i) for every ∈ ∪ of ℒΣ, ℐ |= ; (ii) for every = ⊑ ∈ , if ⟨, ⟩ ∈/ , then ℐ |= ().
Two DL interpretations ℐ1 and ℐ2 are NI-congruent, if ℐ1 = ℐ2 holds for every ∈ NI. This extends to -interpretations ℐ = ⟨ℐ, ⟩ by considering interpretations ℐ.
Intuitively, we say that a -interpretation is justified if all of its exception assumptions have a clashing set that is verified by the interpretation.
Definition 8 (Justifications) . We say that ⟨, ⟩ ∈ is justified for a -model ℐ , if some clashing set ⟨, ⟩ exists such that, for every ℐ′ = ⟨ℐ′, ⟩ of K that is NI-congruent with ℐ , it holds that ℐ′ |= ⟨, ⟩.
A -model ℐ of a PKB K is justified , if every ⟨, ⟩ ∈ is justified in K.
We define the consequence from justified -models: K |= if ℐ |= for every justified -model ℐ of K.
Remark. Note that there can be more than one justified model, in particular for diferent valid combinations of exception assumptions and justifications. As will be shown in examples, this allows reasoning by cases: scores defined over prototype definitions’ values allow to define a preference over such cases.
The main intuition of prototype definitions is that each individual which is an instance of a prototype
is associated with a score which denotes the “degree of typicality” of the individual with respect to the
concept described by the prototype. As in [
Given the set of prototypes ∈ , a family of prototype score functions { } ∈ is composed by functions : NI → R for each prototype name ∈ such that every function of the family has range in a fixed interval [, ..., ] ∈ R.
Ideally, these families of functions can then be used to define preferences over models: diferent preference criteria can be defined, in particular, by using the results of score functions on the exceptional individuals in the exception assumptions’ sets of -interpretations.
In general, we define a preference on exception assumption sets as a partial order 1 > 2 on the sets for K. Given two -interpretations ℐ1 = ⟨ℐ1, 1⟩ and ℐ2 = ⟨ℐ2, 2⟩, we say that ℐ1 is preferred to ℐ2 (denoted ℐ1 > ℐ2 ) if 1 > 2.
Finally, we define the notion of PKB model as a minimal justified model for the PKB. Definition 9 (PKB model). An interpretation ℐ is a PKB model of K (denoted, ℐ |= K) if – K has some justified -model ℐ = ⟨ℐ, ⟩. – there exists no justified ℐ′ = ⟨ℐ′, ′⟩ that is preferred to ℐ .
The consequence from PKB models of K (denoted K |= ) characterizes the "preferred" consequences of the PKB, on the basis of the degree of typicality of instances.
A simple score function can be defined by considering the features that are inferable from the KB (in all justified models): Definition 10 ((Model independent) Prototype score). Given a prototype definition (1 : 1, ..., : ), we define the (model independent) score function score : NI → R for prototype as: score () =
∑︁ K |= ()
This measure, however, depends on the value interval over which the prototype weights have been defined: in order to compare the score of an individual with scores relative to other prototypes, this value needs to be normalized. We do so by computing the maximum score and minimum score for all prototypes.
The maximum score denotes the score of the maximum value of obtainable from the weights of consistent subset of features of . Formally, given a prototype definition (1 : 1, ..., : ), let be the set of sets ⊆ { 1, . . . , } s.t. ∪ K is consistent. Then: The minimal score denotes the sum of the weights for “unavoidable” features, namely those that are strictly implied by the membership to the prototype concept. Formally: = max( ∑︁ | ∈ )
∈ =
∑︁ K |= ⊑
() = () − −
A normalized score function can be derived from as:
Consider that with such normalisation we obtain a family of prototype score functions with range in
the same interval [
We can then define a simple preference using the model independent score defined above: we prefer justified -models where the exceptions appear on elements of the less scoring prototypes. Definition 11 (Preference SP). 1 > 2 if, for every ⟨ ⊑ , ⟩ ∈ 1 ∖ 2 such that there exists a ⟨ ⊑ , ⟩ ∈ 2 ∖ 1 with K ∪ {(), ()} unsatisfiable, it holds that () < (). The intuition behind the condition K ∪ {(), ()} unsatisfiable is that we want to make the comparison between the clashing assumptions that are directly in conflict.
Example 2. Considering the PKB reported in the example above, assume to have two PKB interpretations ℐ1 and ℐ2 associated respectively with the following two sets of clashing assumptions 1 = {⟨Wolf ⊑ ¬Trusted, balto⟩, ⟨Dog ⊑ Trusted, cerberus⟩} and
2 = {⟨Dog ⊑ Trusted, balto⟩, ⟨Dog ⊑ Trusted, cerberus⟩}.
We have now two -interpretations corresponding to ⟨ℐ1, 1⟩ and ⟨ℐ2, 2⟩. Assuming that they are also -models, we can check if the two are also justiifed . Since, the clashing assumptions have the following clashing sets, respectively {Wolf(balto), Trusted(balto), Dog(cerberus), ¬Trusted(cerberus)} for the clashing assumptions in 1 and {Dog(balto), ¬Trusted(balto), Dog(cerberus), ¬Trusted(cerberus)} for those in 2, they are both justified.
In order to decide which model is preferred, we need to compute the prototype scores for balto and for cerberus: we have score () = 14, score() = 55, score() = 11. Then we need to normalise them:
() = () = () = score() −
−
≈ 0, 4 score () − −
≈ 0, 3 score() − −
= 0 Consequently score () < score() and, since ⟨Dog ⊑ Trusted, cerberus⟩ is present in both 1 and 2 so it does not influence the preference order, then we can conclude that 1 > 2. This means that the preferred model, i.e. the PKB model, is ℐ1 where balto is an exception to Wolf ⊑ ¬Trusted and cerberus is an exception to Dog ⊑ Trusted. Consequently, it holds that K |= Trusted(balto) and K |= ¬Trusted(cerberus).
Moreover, we can note that for pluto and alberto we can standardly infer Trusted(pluto) and ¬Trusted(alberto). The reason is that the clashing assumptions are referred to specific individuals, and since there are no contradicting assertions for pluto and alberto, there are no clashing sets that justify their assumptions as exceptions. Therefore, axioms in apply to them standardly. ◇ Remark. For simplicity, we are assuming independence of scores across the features: for example, the weight of a feature hasWhiteTail is not dependent on the weight of a more general hasTail. Dependence across features and their impact on the evaluation of weights is indeed an interesting extension to our work and we plan to provide a characterization in our future work.
The preference relation defined above may be too coarse-grained with respect to some cases. For instance, consider the following example which is a modified version of the example considered above: Example 3. For the concepts Dog and Wolf we use here the letters and respectively and for Trusted we use T. Moreover, balto is here simplified to .
Now, we can imagine to have two new prototype axioms talking of house animals () and wild animals ( ), where the first are considered docile ( ), while the second not docile. So, we now have the four prototype axioms
⊑ T, ⊑ ¬T, ⊑ and ⊑ ¬; the individual causing the conflict because it is an instance of , , and :
(), (), () and (); and the four prototype descriptions, with the third one that includes T among its features: ( : 2, : 8), ( : 4, : 6), (T : 3, : 7) and ( : 8, : 2). where the features , , , , , , do not have a specific meaning. Moreover, we know that (), (), () and ().
From this KB we can see that we have four sets of justified exception assumptions, that is the sets of exception assumptions which have an associated clashing set: We can now compute the normalised typicality scores, which are respectively: Consequently, the order we have on sets of exception assumptions is: 1 = {⟨ ⊑ T⟩, >, ⟨ ⊑ , ⟩} 2 = {⟨ ⊑ T, ⟩, ⟨ ⊑ ¬, ⟩} 3 = {⟨ ⊑ ¬T, ⟩, ⟨ ⊑ , ⟩} 4 = {⟨ ⊑ ¬T, ⟩, ⟨ ⊑ ¬, ⟩} () = 0, 8; () = 0, 4; () = 0, 7; () = 0, 8.
3 2 from which, ℐ 3 results to be the preferred model.
We have two key observations regarding this example: first, T() is not considered in the computation of the scores because K ⊭ T(). In fact, in ℐ 1 and ℐ 2 we have ¬T().
Second, the fact that the preferred model is the one where T() and ¬() hold is counter-intuitive. The reason is that if we can conclude T() in a model, it should mean that we can add the weight associated with that feature in the prototype description of . Consequently, would result as a more typical than , and so we would like to conclude (). Consequently, the desired interpretation would be ◇ The problem derives from the use of consequence to define the score of individuals: while this assures a uniform score across the models, this score does not consider the satisfaction of features in the single interpretations. Thus, to deal with such cases, we can define a new preference order, which considers what holds inside the models and consequently can be called model-dependent.
The first step is to change the definition of prototype score in order to have a diferent score for each model: Definition 12 ((Model dependent) Prototype score). Given a prototype definition (1 : 1, ..., : ), we define the score function scoreℐ : NI → R for prototype and a justified model ℐ as: scoreℐ () =
∑︁ ℐ |= ()
We leave the other steps of the computation of the typicality score as they are, such that we will have a family of normalised score functions which now are relative to the -models they are in, making the score an intra-interpretations score. The idea is to measure the typicality of the individual according to the hypothetical situation we are considering, that is according to the hypotheses regarding what is exceptional and especially to what it is exceptional.
In fact, remember that a -model is a DL interpretation with an associated set of hypothetical exceptions. This would precisely address the problem arising in the case above, since if we are supposing that is exceptional with respect to ⊑ ¬T, we should assume T(). However, now the problem is how to compare the scores, which are dependent from interpretations, in a consistent and meaningful way with respect to the role that the comparison has in our system. This role is that of ordering those interpretations with the goal to find out which hypothetical exceptions are reasonably actual exceptions. In the first formalisation, we relied on comparing typicality scores that were independent from the diferent interpretations and hypotheses and so were, so to say, the outcome of the strict knowledge that is certain in all the interpretations. Therefore, the typicality scores could be compared consistently since they depended on the same knowledge.
Endorsing this intuition, also in the new preference order we can compare the scores that do not change across the interpretations. The reason is that, since they do not change it means that they are independent from the particular interpretation and so we are in the same position as in the modelindependent preference. From a formal perspective, this means that the computation of the typicality scores do not depend on other prototype axioms. Then, we can order the interpretations using the existing preference function slightly adjusted to consider only the scores that do not change across the models, individuating in this way the set of the local preferred models, that is those that are preferred with respect of only the strict knowledge. At this point, we can apply recursively the previous step, that is comparing the scores that do not change across these locally preferred models and order them according to the preference function we have, individuating the set of the new locally preferred models. We continue with this method iteratively until we remain with the set of globally preferred models.
Now we can give a more precise definition of this new preference order. Firstly, we need a definition of the scores we would consider: Definition 13 (Stable score). Given a set = {ℐ | ℐ is a justified -model}, score () is a stable score if ∀ℐ , ℐ ∈ score () = score ()
ℐ ℐ
Now, we can define the new preference mechanism by modifying the previous one with the addition of the constraint that we are comparing only the scores that are stable across all the justified -models. Definition 14 (Local Preference). 1 > 2 if, for every ⟨ ⊑ , ⟩ ∈ 1 ∖ 2 such that there exists a ⟨ ⊑ , ⟩ ∈ 2 ∖ 1 with K ∪ {(), ()} unsatisfiable and such that score () and score() are stable scores, it holds that () < ().
As before, a preferred justified -model is a justified -model that has no justified -model which is preferred to it: formally, a justified -model ℐ = ⟨ℐ, ⟩ is a locally preferred justified -model of K if there exists no justified ℐ ′ = ⟨ℐ′, ′⟩ that is preferred to ℐ . Therefore, we can define the set of these preferred models: Definition 15 (Set of locally preferred justified -models). We denote the set of locally preferred justified -models of a set of justified -models of K with ( ).
Note that ( ) ⊆ and so ( ) ∈ ( ), where ( ) stands for the power-set of .
Now we are ready to define the global preference between the models, thanks to an iterative application of the local preference: Definition 16 (Global Preference). Given the set ℳ of all the justified -models of K, consider the sequence of sets of models 0, ..., where ⊆ ℳ such that (i) 0 = ℳ; (ii) +1 = (); (iii) is the fixed point such that () = .
A justified -model ℐ is a globally preferred model of K if ℐ ∈ Proposition 1. The global preference construction above has a fixed point .
Proof. Assume that there is no fixed point. This can happen in two ways: either (i) there are infinitely many , or (ii) there is a loop such that + = where > 1.
Consider situation (i): we can notice that 0 ⊇ ⊇ +1 and so on ad infinitum since we never produce new justified -models, but we select among the elements of the ith-set those that are preferred and we use them to build the new ith+1-set. However, this selection depends only on the s of the justified -models, that we recall are sets of exception assumptions. Since the latter are defined on axioms and individual names in K, the exceptional assumptions are finite and consequently also the s. Therefore, there cannot be infinitely many justified -models.
Now, consider situation (ii). A loop would have a form like this: () = +1; (+1) = +2 = − 1 and (− 1) = .
Since ∀( ⊇ +1), ⊇ +1 ⊇ − 1 ⊇ . But this means that = +1 and this is inconsistent with the assumption.
By considering the globally preferred models as those preferred tout court for the Definition 9 of the PKB models, we now have a new preference order which allows to reach the desired conclusion in cases like those in Example 3 above. To illustrate that this is the case and how the new method works, we can apply the new preference to the example above: Example 4. Consider the knowledge base presented in Example 3, we have the same four exception assumptions 1, 2, 3 and 4. So, now we can start applying the new preference order: we have the elements of our set 0 = ℳ = {ℐ 1 , ℐ 2 , ℐ 3 , ℐ 4 }.
Then, we can compute the normalised typicality scores, but now each justified -model will have its set of typicality scores thanks to Definition 12, which are respectively: () () () () ℐ 1 0, 8 0, 4 0, 7 0, 8 ℐ 2 0, 8 0, 4 0, 7 0, 8 ℐ 3 0, 8 0, 4
1 0, 8 Now we can apply the new definition of preference, which will compare only the stable scores. In this case the stable score are () and (). Note that 3 and 4 assume that Balto is exceptional with respect to wolves being not trusted and the stable score with respect to the prototype is smaller than that of the prototype . Therefore, the locally preferred models are ℐ 3 and ℐ 4 , or, in other words, (0) = 1 = {ℐ 3 , ℐ 4 }
In the next step, we have to select the locally preferred justified -models, but in the new set 1. So, now, we compare also () and () which are stable normalised scores in 1 and we have 4 > 3. Therefore, (1) = 2 = {ℐ 4 }.
Again, we search for the preferred models in 2. In this case, the preferred model is the only one in the set, since it is trivially true that there is no other model in the set that is preferred to it. So, (2) = 3 = {ℐ 4 } = 2, which means that 2 is our fixed point.
Thus, we can conclude that ℐ 4 is the globally preferred justified -model and therefore the PKB model of K as expected.
In this paper, we built on the work in [
Regarding future work, we would like to further develop the formalism through a relaxation of some
of the requirements found in the current version, such as the restriction that the individuals found
in the exceptional assumptions must be named entities in the knowledge base. Moreover, we will
study the formal properties enjoyed by the resulting logic in order to compare it with other approaches
which use some notion of typicality in DLs for defeasible reasoning such as [