=Paper=
{{Paper
|id=Vol-3739/paper-9
|storemode=property
|title=Defeasible Reasoning with Prototype Descriptions: A New Preference Order
|pdfUrl=https://ceur-ws.org/Vol-3739/paper-9.pdf
|volume=Vol-3739
|authors=Gabriele Sacco,Loris Bozzato,Oliver Kutz
|dblpUrl=https://dblp.org/rec/conf/dlog/SaccoBK24
}}
==Defeasible Reasoning with Prototype Descriptions: A New Preference Order==
https://ceur-ws.org/Vol-3739/paper-9.pdf
Defeasible Reasoning with Prototype Descriptions:
A New Preference Order
Gabriele Sacco1,2 , Loris Bozzato3 and Oliver Kutz2
1
Fondazione Bruno Kessler, Via Sommarive 18, 38123 Trento, Italy
2
Free University of Bozen-Bolzano, Piazza Domenicani 3, 39100, Bolzano, Italy
3
DiSTA - Università dell’Insubria, Via O. Rossi 9, 21100 Varese, Italy
Abstract
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.
Keywords
Non-monotonic logic, Typicality, Description Logics, Exceptions
1. Introduction
The study of defeasible reasoning and its modelling through non-monotonic logics has a long story
in Artificial Intelligence [1, 2]. More recently, approaches for representing non-monotonicity have
been proposed also in the context of Descriptions Logics (DL) [3, 4]. Following this direction, in [5] we
started developing a formal approach for defeasible reasoning in DLs which satisfies some desiderata
extracted from the studies on generics [6] and which moreover takes into account some insights we
could identify within the philosophical and cognitive research on phenomena related to exceptions and
defeasibility.
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 [5] in section 2, proposing also a new terminology for some key definitions
in order to simplify the presentation. Then, section 3 treats the new preference by firstly describing a
problematic case for the previous one, then giving the formal definitions, and finally by showing that
through those new definitions we are able to reach the desired conclusion in the outlined problematic
case.
2. DLs with Weighted Prototypes
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.
DL 2024: 37th International Workshop on Description Logics, June 18–21, 2024, Bergen, Norway
$ gsacco@fbk.eu (G. Sacco); loris.bozzato@uninsubria.it (L. Bozzato); oliver.kutz@unibz.it (O. Kutz)
0000-0001-5613-5068 (G. Sacco); 0000-0003-1757-9859 (L. Bozzato); 0000-0003-1517-7354 (O. Kutz)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
2.1. Syntax: Features, Prototype Definitions, Prototype Knowledge Bases
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 [7]. Intuitively, the weights associated to the features can be then combined to compute a
score denoting the degree of typicality of an instance w.r.t. the prototype: for the current definition,
weights are assumed to be positive and features are independent.
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 sufficient 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 [8].
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 different
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 different prototypes. In an initial proposal, we
simply constrained the weights of features to be in the [0, 1] interval and to prescribe further that they
would add up to 1, i.e. prototypes were simply assumed to be given as positive and normalised [9]: in
the following sections, we provide instead a more general proposal for normalising prototype scores.
With respect to [9], in the current definition of prototype definition we allow any general concept to
characterise the weighted features.
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 [10]), also depending on the “degree of membership” of the individual to the given prototype
(i.e., the satisfaction of its features).
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. ◇
2.2. Semantics: Justified Models
The semantics of PKBs is based on standard interpretations for the underlying DL ℒΣ . In fact, interpre-
tations 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 [10]:
intuitively, for an axiom 𝛼 ∈ ℒΣ the instantiation of 𝛼 with 𝑒 ∈ NI, written 𝛼(𝑒), is the specialization
of 𝛼 to 𝑒.1 In other words, we “apply” the axiom to the individual 𝑒, e.g. if the axiom means that dogs
are trusted and we instantiate it to Balto, we are saying that if Balto is a dog, then it is trusted.
Definition 5 (Exception assumptions and clashing sets). An exception assumption is a pair ⟨𝛼, 𝑒⟩ where
𝛼 ∈ 𝑇𝑃 is a prototype axiom, 𝑒 ∈ 𝒜 is an individual name and such that 𝛼(𝑒) is an axiom instantiation
of 𝛼.
A clashing set for ⟨𝛼, 𝑒⟩ is a satisfiable set 𝑆⟨𝛼,𝑒⟩ of ABox assertions s.t. 𝑆⟨𝛼,𝑒⟩ ∪ {𝛼(𝑒)} is unsatisfiable.
1
As in [10], 𝛼(𝑒) can be formally specified via the FO-translation of 𝛼.
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 interpreta-
tion 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 different 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.
2.3. Semantics: Prototype Score and Preference
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 [7], such a degree is computed from the prototype features
that are satisfied by the instances and their score. Ideally, the prototype score of an individual allows us
to determine preferences over models: for an individual, axioms on prototypes with higher score are
preferred to the ones on lower scoring prototypes; thus the measure needs to be comparable across
different prototypes.
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: different
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.
2.4. Semantics: Model Independent Prototype Score
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:
∑︁
𝑚𝑎𝑥𝑃 = max( 𝑤𝑖 | 𝑆 𝑃 ∈ 𝑆 𝑃 )
𝐶𝑖 ∈𝑆𝑃
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:
∑︁
𝑚𝑖𝑛𝑃 = 𝑤𝑖
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 [0, 1], allowing for comparison of prototype scores on the same individual.
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 compar-
ison 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 ⟩. As-
suming that they are also 𝜒-models, we can check if the two are also justi-
fied. Since, the clashing assumptions have the following clashing sets, respectively
{Wolf(balto), Trusted(balto), Dog(cerberus), ¬Trusted(cerberus)} for the clashing as-
sumptions 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.
3. A New Preference Order
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:
𝜒1 = {⟨𝐷 ⊑ T⟩, 𝑏 >, ⟨𝐻𝐴 ⊑ 𝐷𝐶, 𝑏⟩}
𝜒2 = {⟨𝐷 ⊑ T, 𝑏⟩, ⟨𝑊 𝐴 ⊑ ¬𝐷𝐶, 𝑏⟩}
𝜒3 = {⟨𝑊 ⊑ ¬T, 𝑏⟩, ⟨𝐻𝐴 ⊑ 𝐷𝐶, 𝑏⟩}
𝜒4 = {⟨𝑊 ⊑ ¬T, 𝑏⟩, ⟨𝑊 𝐴 ⊑ ¬𝐷𝐶, 𝑏⟩}
We can now compute the normalised typicality scores, which are respectively:
𝑛𝑠𝑐𝑜𝑟𝑒𝐷 (𝑏) = 0, 8; 𝑛𝑠𝑐𝑜𝑟𝑒𝑊 (𝑏) = 0, 4;
𝑛𝑠𝑐𝑜𝑟𝑒𝐻𝐴 (𝑏) = 0, 7; 𝑛𝑠𝑐𝑜𝑟𝑒𝑊 𝐴 (𝑏) = 0, 8.
Consequently, the order we have on sets of exception assumptions is:
𝜒3
𝜒4 𝜒1
𝜒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
ℐ𝜒4 . ◇
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 different 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
different 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 model-
independent 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 iff ∀ℐ𝜒𝑖 , ℐ𝜒𝑗 ∈ 𝑀 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 applica-
tion 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 iff ℐ𝜒 ∈ 𝑀𝑛
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 ℐ𝜒2 ℐ𝜒3 ℐ𝜒4
𝑛𝑠𝑐𝑜𝑟𝑒𝐷 (𝑏) 0, 8 0, 8 0, 8 0, 8
𝑛𝑠𝑐𝑜𝑟𝑒𝑊 (𝑏) 0, 4 0, 4 0, 4 0, 4
𝑛𝑠𝑐𝑜𝑟𝑒𝐻𝐴 (𝑏) 0, 7 0, 7 1 1
𝑛𝑠𝑐𝑜𝑟𝑒𝑊 𝐴 (𝑏) 0, 8 0, 8 0, 8 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.
4. Conclusions and Future Work
In this paper, we built on the work in [5] by refining the terminology, simplifying the formal setting,
and by proposing a new preference mechanism that allows to overcome certain shortcomings of the
previous one.
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 [11, 12]. A logical analysis
comprehending a consistency proof and a discussion of the coherence between the knowledge base and
the weights of the features is needed too, along with a study of the computational costs. Finally, we will
propose an implementation of our approach in the framework of Answer Set Programming.
Acknowledgements. This work was partially supported by the GULP - Gruppo Ricercatori e Utenti
Logic Programming. The support is gratefully acknowledged.
References
[1] C. Strasser, G. A. Antonelli, Non-monotonic Logic, in: E. N. Zalta (Ed.), The Stanford Encyclopedia
of Philosophy, Summer 2019 ed., Metaphysics Research Lab, Stanford University, 2019.
[2] J. McCarthy, P. J. Hayes, Some Philosophical Problems from the Standpoint of Artificial Intelligence,
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1987, p. 26–45.
[3] L. Giordano, V. Gliozzi, N. Olivetti, G. Pozzato, Semantic characterization of rational closure: From
propositional logic to description logics, Artificial Intelligence 226 (2015) 1–33. URL: https://www.
sciencedirect.com/science/article/pii/S0004370215000673. doi:https://doi.org/10.1016/j.
artint.2015.05.001.
[4] K. Britz, G. Casini, T. Meyer, K. Moodley, U. Sattler, I. Varzinczak, Principles of klm-style defeasible
description logics, ACM Trans. Comput. Logic 22 (2020). URL: https://doi.org/10.1145/3420258.
doi:10.1145/3420258.
[5] G. Sacco, L. Bozzato, O. Kutz, Defeasible reasoning with prototype descriptions: First steps, in:
Proceedings of the 36th International Workshop on Description Logics (DL 2023), volume 3515 of
CEUR Workshop Proceedings, CEUR-WS.org, 2023.
[6] G. Sacco, L. Bozzato, O. Kutz, Generics in defeasible reasoning. exceptionality, gradability, and
content sensitivity, 2023. Accepted at 7th CAOS Workshop ‘Cognition and Ontologies’, 9th Joint
Ontology Workshops (JOWO 2023), co-located with FOIS 2023, 19-20 July, 2023, Sherbrooke,
Québec, Canada.
[7] P. Galliani, G. Righetti, O. Kutz, D. Porello, N. Troquard, Perceptron connectives in knowledge
representation, in: C. M. Keet, M. Dumontier (Eds.), Knowledge Engineering and Knowledge
Management, Springer International Publishing, Cham, 2020, pp. 183–193.
[8] D. Porello, O. Kutz, G. Righetti, N. Troquard, P. Galliani, C. Masolo, A toothful of concepts: Towards
a theory of weighted concept combination, in: Description Logics, volume 2373 of CEUR Workshop
Proceedings, CEUR-WS.org, 2019.
[9] G. Sacco, L. Bozzato, O. Kutz, Introducing weighted prototypes in description logics for defea-
sible reasoning, in: A. F. Agostino Dovier (Ed.), Proceedings of the 38th Italian Conference on
Computational Logic, CEUR Workshop Proceedings, Udine, Italy, 2023.
[10] L. Bozzato, T. Eiter, L. Serafini, Enhancing context knowledge repositories with justifiable excep-
tions, Artif. Intell. 257 (2018) 72–126.
[11] L. Giordano, D. Theseider Dupré, Weighted defeasible knowledge bases and a multipreference
semantics for a deep neural network model, in: Logics in Artificial Intelligence: 17th European
Conference, JELIA 2021, Virtual Event, May 17–20, 2021, Proceedings 17, Springer, 2021, pp.
225–242.
[12] K. Britz, J. Heidema, T. Meyer, Modelling object typicality in description logics, in: A. Nicholson,
X. Li (Eds.), AI 2009: Advances in Artificial Intelligence, Springer Berlin Heidelberg, Berlin,
Heidelberg, 2009, pp. 506–516.