=Paper=
{{Paper
|id=Vol-477/paper-22
|storemode=property
|title=Modelling Object Typicality in Description Logics
|pdfUrl=https://ceur-ws.org/Vol-477/paper_23.pdf
|volume=Vol-477
|dblpUrl=https://dblp.org/rec/conf/dlog/BritzHM09
}}
==Modelling Object Typicality in Description Logics==
<pdf width="1500px">https://ceur-ws.org/Vol-477/paper_23.pdf</pdf>
<pre>
      Modelling object typicality in Description Logics

             Katarina Britz1,3 , Johannes Heidema2 , and Thomas Meyer1,3
                         1
                           KSG, Meraka Institute, CSIR, South Africa
                2
                    Dept of Mathematical Sciences, University of South Africa
                      3
                        School of Computing, University of South Africa
                             arina.britz@meraka.org.za
                            johannes.heidema@gmail.com
                            tommie.meyer@meraka.org.za




       Abstract. We present a semantic model of typicality of concept members in de-
       scription logics that accords well with a binary, globalist cognitive model of class
       membership and typicality. We define a general preferential semantic framework
       for reasoning with object typicality in description logics. We propose the use of
       feature vectors to rank concept members according to their defining and charac-
       teristic features, which provides a modelling mechanism to specify typicality in
       composite concepts.



1   Introduction

The study of natural language concepts in cognitive psychology has led to a range of
hypotheses and theories regarding cognitive constructions such as concept inclusion,
composition, and typicality. Description logics have been very successful in modelling
some of these cognitive constructions, for example IS-A and PART-OF. In this paper,
we focus on the semantic modelling of typicality of concept members in such a way
that it accords well with empirically well-founded cognitive theories of how people
construct and reason about concepts involving typicality. We do not attempt to survey
all models of concept typicality, but briefly outline some aspects of the debate:
    According to the unitary model of concept typicality and class membership, vari-
ations in both graded class membership and typicality of class members reflect differ-
ences in similarity to a concept prototype. Both class membership and typicality are
determined by placing some criterion on the similarity of objects to the concept proto-
type [14, 15]. In contrast, according to the binary model of concept typicality and class
inclusion, typicality and concept membership reflect essentially different cognitive pro-
cesses. Concepts have defining features providing necessary and sufficient conditions
for class membership, as well as characteristic features indicating typicality within that
class [7, 24, 25].
    According to the localist view of concepts, the meaning of a compound concept
is a function of the meanings of its semantic constituents. In contrast, according to
the globalist view, the meaning of concepts are entrenched in our world knowledge,
which is context-dependant and cannot be decomposed into, or composed from, our
understanding of basic building blocks [16, 23]. Concept typicality can therefore not be
determined from concept definition alone, but requires a world view to provide context
relative to which typicality may be determined.
    Description logics cannot resolve any of these debates, but we can use DLs to model
some aspects of them. In particular, we can model typicality of concept members based
on their characteristic features. We can also model compositional aspects of typicality.
Other aspects, such as the graded class membership that underpins the unitary model,
and non-compositionality of compound class membership in the globalist view, cannot
be modelled using DLs, or at least not in an intuitively natural way. In [30] a model of
graded concept membership was proposed, but this presented a marked departure from
classical DL reasoning. We therefore restrict our attention to the binary model, with a
compositional model of class membership, where being a member of a class is an all-or-
nothing affair, and membership of compound concepts are determined by membership
of their atomic constituents or defining features, while characteristic features contribute
to induce degrees of typicality within a class.
    Description logics have gained wide acceptance as underlying formalism in intelli-
gent knowledge systems over complex structured domains, providing an unambiguous
semantics to ontologies, and balancing sufficient expressive power with efficient rea-
soning mechanisms [2]. The nature of DL reasoning has traditionally been deductive,
but there have been a fair number of proposals to extend DLs to incorporate some form
of defeasible reasoning, mostly centered around the incorporation of some form of de-
fault rules, e.g. [9].
    In a previous paper [6], we presented a general preferential semantic framework
for defeasible subsumption in description logics, analogous to the KLM preferential se-
mantics for propositional entailment [5, 19]. We gave a formal semantics of defeasible
subsumption, as well as a translation of defeasible subsumption to classical subsump-
tion within a suitably rich DL language. This was done by defining a preference order
on objects in a knowledge base, which allowed for defeasible terminological statements
of the form “All the most preferred objects in C are also in D”.
    In practice, an ontology may call for different preference orders on objects, and
correspondingly, multiple defeasible subsumption relations within a single knowledge
base. An object may be typical (or preferable) with respect to one property, but not
another. For example, a guppy may be considered a typical pet fish, even though it is
neither a typical fish, nor a typical pet [24]. So we may want a pet typicality order on
pets, a fish typicality order on fish, and some way of combining these orders into a pet
fish typicality order. That is, we want to order objects in a given class according to their
typicality with respect to the chosen features of that class. The subjective world view
adopted in the fish shop may be different from that adopted in an aquarium, or a pet
shop, hence the features deemed relevant may differ in each case, and this has to be
reflected in the respective typicality orders.
    Relative to a particular interpretation of a DL, any concept C partitions all objects in
the domain according to their class membership into those belonging to C, and those not
belonging to C. This yields a two-level preference order, with all objects in C preferred
to all those not in C. This order may be refined further to distinguish amongst objects in
C, but even the basic two-level order suffices to define an important class of preferential
subsumption relations, namely those characterising the stereotypical reasoning of [21].
    A suitable preference order on objects may be employed to obtain a notion of de-
feasible subsumption that relaxes the deductive nature of classical subsumption. To this
end, we introduce a parameterised defeasible subsumption relation @   ∼j , used to express
terminological statements of the form C @  ∼j D, where C and D are arbitrary concepts,
and @ ∼j is induced by a preference order ≤j . If ≤j prefers objects in A to objects out-
side of A, we say that C is preferentially subsumed by D relative to A iff all objects in
C that are typical in A (i.e. preferred by the typicality order corresponding to A), are
also in D.
    When translated into our DL terminology, the proposal of [21] reads as follows:
Given concepts C, D and S such that S represents a best stereotype of C, we say that
C is preferentially subsumed by D relative to S if all stereotypical objects in C also
belongs to D.
    The rest of the paper is structured as follows: We first fix some standard semantic
terminology on description logics that will be useful later on. After giving some back-
ground on rational preference orders, we introduce the notion of an ordered interpreta-
tion, and present a formal semantics of parameterised defeasible subsumption. This is a
natural extension of the work presented in [6], and provides a way of reasoning defea-
sibly with the IS-A relationship between concepts relative to a given concept. We then
put forward two approaches to the definition of a derived typicality order on concepts,
namely atomic composition and feature composition. We argue that feature composition
is the more general approach, and is not as vulnerable to arguments against composi-
tionality as is the case with atomic composition. We show how feature vectors may be
used to determine typicality compositionally, taking into account semantic context.


2     Preliminaries
2.1   DL Terminology
In the standard set-theoretic semantics of concept descriptions, concepts are interpreted
as subsets of a domain of interest, and roles as binary relations over this domain. An
interpretation I consists of a non-empty set ∆I (the domain of I) and a function ·I
(the interpretation function of I) which maps each atomic concept A to a subset AI of
∆I , and each atomic role R to a subset RI of ∆I × ∆I . The interpretation function
is extended to arbitrary concept descriptions (and role descriptions, if complex role
descriptions are allowed in the language) in the usual way.
     A DL knowledge base consists of a Tbox which contains terminological axioms,
and an Abox which contains assertions, i.e. facts about specific named objects and re-
lationships between objects in the domain. Depending on the expressive power of the
DL, a knowledge base may also have an Rbox which contains role axioms.
     Tbox statements are concept inclusions of the form C v D, where C and D
are (possibly complex) concept descriptions. C v D is also called a subsumption
statement, read “C is subsumed by D”. An interpretation I satisfies C v D, writ-
ten I C v D, iff C I ⊆ DI . C v D is valid, written |= C v D, iff it is satisfied by
all interpretations.
     Rbox statements include role inclusions of the form R v S, and assertions used to
define role properties such as asymmetry.
    Objects named in the Abox are referred to by a finite number of individual names.
These names may be used in two types of assertional statements – concept assertions of
the form C(a) and role assertions of the form R(a, b), where C is a concept description,
R is a role description, and a and b are individual names. To provide a semantics for
Abox statements it is necessary to add to every interpretation an injective denotation
function which satisfies the unique names assumption, mapping each individual name a
to a different element aI of the domain of interpretation ∆I . An interpretation I satisfies
the assertion C(a) iff aI ∈ C I ; it satisfies R(a, b) iff (aI , bI ) ∈ RI .
    An interpretation I satisfies a DL knowledge base K iff it satisfies every statement
in K. A DL knowledge base K entails a DL statement φ, written as K |= φ, iff every
interpretation that satisfies K also satisfies φ.



2.2   Preferential semantics


In a preferential semantics for a propositional language, one assumes some order rela-
tion on propositional truth valuations (or on interpretations or worlds or, more generally,
on states) to be given. The intuitive idea captured by the order relation is that interpreta-
tions higher up (greater) in the order are more typical in the context under consideration,
than those lower down. For any given class C, we assume that all objects in the appli-
cation domain that are in (the interpretation of) C are more typical of C than those
not in C. This is a technical construction which allows us to order the entire domain,
instead of only the members of C. This leads us to take as starting point a finite set of
preference orders {≤j : j ∈ J } on objects in the application domain, with index set J .
If ≤j prefers any object in C to any object outside of C, we call ≤j a C-order.
    To ensure that the subsumption relations eventually generated are rational, i.e. sat-
isfy a weak form of strengthening on the left (see [10, 22], and the rational monotonicity
postulate near the end of Section 3.1), we assume the preference orders to be modular
partial orders, i.e. reflexive, transitive, anti-symmetric relations such that, for all a, b, c
in ∆I , if a and b are incomparable and a is strictly below c, then b is also strictly below
c.
    Modular partial orders have the effect of stratifying each ∆I into layers, with any
two elements in the same layer being unrelated to each other, and any two elements in
different layers being related to each other. (We could also have taken the preference
order to be a total preorder, i.e. a reflexive, transitive relation such that, for all a, b in
∆I , a and b are comparable. Since there is a bijection between modular partial orders
and total preorders on ∆I , it makes no difference for present purposes which formalism
we choose.)
    We further assume that the order relation has no infinite chains (and hence, in
Shoham’s terminology [27, p.75], is bounded, which is the dual of well-founded, which
in turn implies, in the terminology of [19], that the order relation is smooth). In the pres-
ence of transitivity, this implies that, for every nonempty subset X of ∆I and a ∈ X,
there is an element b ∈ X, maximal in X, with b greater than or equal to a.
3     Preferential subsumption
We now develop a formal semantics for preferential subsumption in description logics.
We assume a DL language with a finite set of preference orders {j : j ∈ J } in its sig-
nature. We make the preference orders on the domain of interpretation explicit through
the notion of an ordered interpretation: (I, {≤j : j ∈ J }) is the interpretation I with
preference orders {≤j : j ∈ J } on the domain ∆I .
    The preference orders on domain elements may be constrained by means of role
assertions of the form a j b for j ∈ J , where the interpretation of j is ≤j , that is,
Ij =≤j :
Definition 1. An ordered interpretation (I, {≤j : j ∈ J }) satisfies an assertion a j b
iff aI ≤j bI .
    We do not make any further assumptions about the DL language at present, but
assume that concept and role assertions, concept and role constructors, and classical
subsumption are interpreted in the standard way, ignoring the preference orders of or-
dered interpretations.
    We first introduce the notion of satisfaction by an ordered interpretation, thereafter
we relax the semantics of concept inclusion to arrive at a definition of satisfaction of
a parameterised preferential subsumption relation @  ∼j by an ordered interpretation. Fi-
nally, we define what it means for a preferential subsumption statement to be entailed
by a knowledge base.

3.1    Satisfaction
Definition 2. An ordered interpretation (I, {≤j : j ∈ J }) consists of an interpretation
I and finite, indexed set of modular partial orders {≤j : j ∈ J } without infinite chains
over its domain ∆I .

Definition 3. An ordered interpretation (I, {≤j : j ∈ J }) satisfies
C v D, written (I, {≤j : j ∈ J }) C v D, iff I satisfies C v D.

      The preferential semantics of @
                                    ∼j is then defined as follows:

Definition 4. An ordered interpretation (I, {≤j : j ∈ J }) satisfies the preferential
                                                              I     I
subsumption C @∼j D, written (I, {≤j : j ∈ J })  C@∼j D, iff Cj ⊆ D , where


            CjI = {x ∈ C I : there is no y ∈ C I such that x ≤j y and x 6= y}.

    For brevity, we shall at times write ≤J instead of {≤j : j ∈ J }. We make no
assumption about which concept or role constructors are part of the DL language under
consideration, but assume that, if present, the constructors u, t and ¬ are interpreted
in the standard way, ignoring the order on I. Some of the properties of @
                                                                        ∼j listed below
may therefore be irrelevant in some DLs. For example, rational monotonicity is only
relevant in a DL which can express negated concepts.
    Preferential subsumption is supraclassical, nonmonotonic and defeasible, in the fol-
lowing senses of these terms:
 Supraclassicality: If (I, ≤J ) C v D then (I, ≤J ) C @      ∼j D for all j ∈ J .
 Nonmonotonicity: (I, ≤J ) C @     ∼j D does not necessarily imply
   (I, ≤J ) C u C 0 @    ∼j D for any j ∈ J .
 Defeasibility: (I, ≤J ) C @   ∼j D does not necessarily imply (I, ≤J )      C v D for
   any j ∈ J .
    The following properties of @ ∼j are analogous to the familiar properties of rational
preferential entailment [19, 22].
 Reflexivity: (I, ≤J ) C @   ∼j C.
 And: If (I, ≤J ) C @    ∼j D and (I, ≤J ) C @   ∼j F then (I, ≤J )    C@∼j D u F .
 Or: If (I, ≤J ) C ∼j F and (I, ≤J ) D ∼j F then (I, ≤J ) C t D @
                      @                        @
                                                                            ∼j F .
 Left logical equivalence: If (I, ≤J ) C v D and (I, ≤J ) D v C and
    (I, ≤J ) C @   ∼j F then (I, ≤J )    D@ ∼j F .
 Left defeasible equivalence: If (I, ≤J ) C @   ∼j D and (I, ≤J )     D@∼j C and
    (I, ≤J ) C ∼j F then (I, ≤J ) D ∼j F .
                   @                        @

 Right weakening: If (I, ≤J ) C @    ∼j D and (I, ≤J )     D v F then
    (I, ≤J ) C @   ∼j F .
 Cautious monotonicity: If (I, ≤J ) C @    ∼j D and (I, ≤J )     C@ ∼j F then
    (I, ≤J ) C u D ∼j F .@

 Rational monotonicity: If (I, ≤J ) C @    ∼j D and (I, ≤J ) 1 C ∼j ¬F then
                                                                   @

    (I, ≤J ) C u F ∼j D.@

 Cut: If (I, ≤J ) C u D @    ∼j F and (I, ≤J )     C@∼j D then (I, ≤J )    C@ ∼j F .


3.2   Entailment
Satisfaction for defeasible subsumption is defined relative to a fixed, ordered interpre-
tation. We now take this a step further, and develop a general semantic theory of entail-
ment relative to a knowledge base using ordered interpretations. Note that, although the
knowledge base may contain preferential subsumption statements, entailment from the
knowledge base is classical and monotonic.
Definition 5. The preferential subsumption statement C @       ∼j D is valid, written |= C ∼j D,
                                                                                           @

iff it is satisfied by all ordered interpretations (I, {≤j : j ∈ J }).
Definition 6. A DL knowledge base K entails the preferential subsumption statement
C@ ∼j D, written K |= C ∼j D, iff every ordered interpretation that satisfies K also sat-
                        @

isfies C @
         ∼j D.
The following properties of @  ∼j are direct consequences of its corresponding properties
relative to a fixed, ordered interpretation:
 @ is supraclassical: If K |= C v D then also K |= C @ D.
 ∼j                                                  ∼j
 @ is nonmonotonic: K |= C @ D does not necessarily imply that K |= C u C 0 @D.
 ∼j                           ∼j                                            ∼
 @ is defeasible: K |= C @ D does not necessarily imply that K |= C v D.
 ∼j                       ∼j

    The other properties of @∼j listed earlier relative to a fixed, ordered interpretation
extend analogously in the context of entailment relative to a knowledge base. For ex-
                      ∼j relative to K reads K |= C ∼j C.
ample, reflexivity of @                               @
4     Typicality of derived concept membership
In Section 2 we presented a semantic framework to model typicality of concept mem-
bership: ≤j is a C-order if it ranks any object in C higher than any object outside of C.
We now address the question of derived typicality orders. We distinguish between two
possible approaches to resolve this problem:
 1. Atomic composition: Here we use the atomic constituents or defining features of
    each compound concept C as building blocks. We combine their respective typical-
    ity orders recursively, depending on the operators used in the syntactic construction
    of C. Say C ≡ A u B, and typicality orders ≤j and ≤k are defined such that ≤j
    is an A-order and ≤k is a B-order respectively. We may then form a new typicality
    order for C by composing ≤j and ≤k according to some composition rule for u.
 2. Feature composition: Here we identify the relevant features of each concept C. For
    each object a belonging to C, we form a feature vector characterising a. These
    feature vectors are then used to determine the typicality of a in C.
Irrespective of the composition rules applied, atomic composition is vulnerable to the
same criticisms that have been levied against localist, compositional cognitive models
of typicality of concept membership [23].
     Feature composition is also compositional, but, in contrast with atomic composition,
it is not localist. That is, the typicality of a member of a concept may be influenced by
characteristic features that do not constitute part of the definition of the concept. For
example, the diet of penguins may be a relevant characteristic feature in determining
their typicality, but atomic composition cannot take this into account when determining
typicality unless this feature forms part of the definition of a penguin.
     Atomic composition may be viewed as a restricted version of feature composition,
since any defining feature may be considered a relevant feature. Hence, we will only
consider feature composition further. We consider the definition of feature vectors, their
normalisation, and their composition.

4.1   Feature vectors
The features of a concept come in two guises: They are either characteristic features,
co-determining typicality of objects in the concept, or they are defining features of the
concept. In a description logic extended with suitable preferential subsumption rela-
tions, characteristic features may be introduced on the right-hand side of preferential
subsumption statements. For example, in the axioms given below, if @  ∼1 is derived from
the P enguin-order ≤1 , then ∀eats.F ish is a characteristic feature of P enguin. Defin-
ing features are introduced on the right hand-side of classical subsumption statements.
For example, in the following axioms, Seabird is a defining feature of P enguin, so
are Bird and ∃eats.F ish. Similarly, Bird and ∃eats.F ish are both defining features
of Seabird.
                            Seabird ≡ Bird u ∃eats.F ish
                           P enguin v Seabird
                                    ∼1 ∀eats.F ish
                           P enguin @
    The question arises whether relevant features should be determined algorithmically
through some closure operator, or whether their identification is a modelling decision.
While defining features can easily be derived from the knowledge base, this is not ob-
vious in the case of characteristic features. We therefore view the choice of relevant
features as a modelling decision, in accordance with a globalist view of concepts as
context sensitive. The choice of features relevant for a particular concept, and their re-
spective preference orders are therefore determined by a subjective world view and have
to be re-evaluated in each new context.

Definition 7. A feature vector is an n-tuple of concepts hC1 , . . . , Cn i with correspond-
ing preference vector h≤1 , . . . , ≤n i such that ≤j is a Cj -order, for 1 ≤ j ≤ n, and
weight vector hw1 , . . . , wn i such that wj ∈ Z, for 1 ≤ j ≤ n.

    We do not place any formal relevance restriction on the choice of elements of a
feature vector, as this is a modelling decision. We may even, for example, have two
feature vectors for F ish, one for use in the fish shop, and one for the pet shop. We
may also define different preference orders for the same concept, for use in different
contexts. For example, miniature, colourful fish may be typical in a pet shop, but not
even relevant in a fish shop.
    Next, we consider the normalisation of preference orders, which paves the way for
their composition.

Definition 8. Let hC1 , . . . , Cn i be a feature vector with corresponding preference vec-
tor h≤1 , . . . , ≤n i. The level of an object x ∈ ∆ relative to preference order ≤j , written
levelj (x), is defined recursively as follows:

                 1 if x is ≤j -minimal in CjI ;
               
               
                 0 if x is ≤j -maximal in ∆I \CjI ;
               
               
 levelj (x) :=
                max{levelj (y) : y <j x} + 1 for non-minimal objects in CjI ;
               
                 min{levelj (y) : x <j y}) − 1 for non-maximal objects in ∆I \CjI .
               

    Definition 8 maps objects in the domain to integers. We note that the absence of
infinite ≤j -chains ensures that levelj is defined on the whole of ∆. Given any feature
Cj in the feature vector, Definition 8 assigns a positive level to all objects in Cj , and
a non-positive level to all objects not in Cj . In the case where ≤j is a two-level order,
levelj (x) = 1 for x ∈ Cj , and levelj (x) = 0 for x 6∈ Cj .
    It is not difficult to see (given the modularity of the preference orders) that this
mapping preserves the relative order of elements in the corresponding preference order:

Proposition 1. For any x, y ∈ ∆, x ≤j y iff levelj (x) ≤ levelj (y).
     We now have the required apparatus to compose the chosen preference orders of a
feature vector. We define the typicality of objects relative to a given concept, based on
its relevant features. The weight vector may be used in two ways – to normalise the
preference orders so that they have the same range, or to adjust the relative importance
of each feature. Normalisation can be done without intervention from the modeller, and
resonates better with the qualitative approach to typicality followed so far in the paper.
    The intuition of Definition 9 is that it ranks those objects that conform better to the
features of C in terms of typicality on a higher level. The function f first maps each
object in the domain to a non-negative integer. This induces a modular C-order, say ≤k ,
on objects in the domain.

Definition 9. Given concept C with feature vector hC1 , . . . , Cn i, preference vector
h≤1 , . . . , ≤n i and weight vector hw1 , . . . , wn i, let f : ∆I → Z0 , such that
                                       Pn
                               M ax{1, j=1 (levelj (a) × wj )} if a ∈ C I ;
                             
                    f (a) :=
                               0 otherwise

for any object a ∈ ∆. The associated preference relation ≤k on ∆ given by:

                                 a ≤k b iff f (a) ≤ f (b),

for some k ∈ J , is the typicality C-order induced by the features, preferences and
weights as above.

    Our choice for f is not arbitrary, but one can conceive of alternative functions,
such as taking the maximum of the input preferences instead of their sum. By choosing
different functions for different connectives, atomic composition can be simulated using
feature vectors.

4.2   Example
We conclude this section with an illustrative example. Suppose we have the following
terminological statements:

                       P enguin v Bird u F lightless u Aquatic                          (1)
                                ∼1 ∀habitat.Southern
                       P enguin @                                                       (2)
                       Southern v ¬Equatorial                                           (3)
                       GalapagosP enguin v P enguin                                     (4)

Line (2) of the TBox states that the habitat of typical penguins is restricted to the south-
ern regions. Note that we cannot derive from (2) and (4) that the habitat of typical
Galapagos penguins is restricted to the southern regions.
    Further, let 1 be a modular P enguin-order that partitions objects into typical
penguins, atypical penguins, and non-penguins. Then:
                                   
                                    2 if a is typical in P enguinI ;
                    level1 (a) := 1 if a is atypical in P enguinI ;
                                     0 otherwise.
                                   

Let 2 be the modular default ∃habitat.Equatorial-order that partitions this concept
into two classes. Then:
                                   1 if a ∈ ∃habitat.EquatorialI ;
                                 
                   level2 (a) :=
                                   0 otherwise.
    We now construct a feature vector for GalapagosP enguin. We choose P enguin
as relevant defining feature, and ∃habitat.Equatorial as relevant characteristic fea-
ture. That is, a Galapagos penguin is a penguin whose distinctive characteristic is that it
occurs in the equatorial region. The feature vector for GalapagosP enguin is therefore
hP enguin, ∃habitat.Equatoriali. Its preference vector is h1 , 2 i, and as weight
vector we choose h1, 2i in order to normalise the ranges of 1 and 2 . The resulting
derived preference order is 3 , obtained from:
                 
                 
                  4 if a is typical in P enguinI and a ∈ ∃habitat.EquatorialI ;
                  3 if a is atypical in P enguinI and a ∈ ∃habitat.EquatorialI ;
                 
                 
      f3 (a) := 2 if a is typical in P enguinI and a ∈ ∀habitat.SouthernI ;
                   1 if a is atypical in P enguinI and a ∈ ∀habitat.SouthernI ;
                 
                 
                 
                 
                   0 otherwise.
                 

    Note that the first case, i.e. where f3 (a) = 4, does not hold for any object a, as
it contradicts terminological axiom (2) in the knowledge base. This then induces the
following preferential subsumption statement:

                                       ∼3 ∃habitat.Equatorial
                     GalapagosP enguin @                                               (5)

So, typically, Galapagos penguins are found in the equatorial region, not exclusively in
the southern regions.
    Of course, in this example we could simply have stated this, but the point is that
defining and characteristic features may be used to derive compositionally the typicality
of objects in a class based on chosen relevant features. Our example gives a simple
illustration of this claim.
    We conclude this section with a few comments on the choice of weights in the
weight vector. In the above example, we normalised the weights so that the two prefer-
ence orders have the same range.
    We could also use the weight vector to give preference to some features over others.
Consider using the weight vector h2, 1i in the above example. This induces the follow-
ing lexicographic order based on the features as above, in which having the defining fea-
ture P enguin takes precedence over the characteristic feature ∃habitat.Equatorial:
                 
                 
                   5 if a is typical in P enguinI and a ∈ ∃habitat.EquatorialI ;
                  4 if a is typical in P enguinI and a ∈ ∀habitat.SouthernI ;
                 
                 
      f4 (a) := 3 if a is atypical in P enguinI and a ∈ ∃habitat.EquatorialI ;
                    2 if a is atypical in P enguinI and a ∈ ∀habitat.SouthernI ;
                 
                 
                 
                 
                    0 otherwise.
                 

    As we had before, the case where f4 (a) = 5 does not hold for any object a, as it
contradicts terminological axiom (2) in the knowledge base. Using the preference order
4 obtained from f4 , we cannot deduce the subsumption statement obtained in (5)
above, but instead now find that the habitat of typical Galapagos penguins is restricted
to the southern regions:

                                       ∼4 ∀habitat.Southern
                     GalapagosP enguin @                                               (6)
5   Related work

Notions of typicality have been studied in a wide variety of contexts, most of them
beyond the scope of this paper. In the context of ontologies, Yeung and Leung [30] pro-
posed a model of graded membership, but their representation is not directly in terms
of description logics. Approaches using extensions of description logics as the mod-
elling language to model uncertainty include the probabilistic approach of Koller et al.
[17] and fuzzy approaches such as that of Straccia [28, 29]. Giardona et al. [11, 12] de-
fine a nonmonotonic extension of the description logic ALC to reason about typicality,
while Grossi et al. [13] use contexts, modelled as sets of description logic models, to
describe a version of typicality. In order to be able to determine similarity between ob-
jects, Sheremet et al. [26] extend the description logic ALCQIO with the constructors
of the similarity logic SL. Finally, Lambrix et al. [20] introduce an intelligent search
engine based on default description logics, used to represent typical information about
a topic.
    Methods for the composition of preference orders have been studied in the social
choice literature [1] with a recent trend towards the computational aspects of social
choice theory [8]. The combination of preference orders has also attracted attention
in studies on belief merging [18]. In the latter context, preference aggregation using
possibilistic logic approaches [3, 4] is of particular interest for two reasons. Firstly, a
whole range of concrete combination operators have been studied. Secondly, the issue
of normalisation is dealt with implicitly due to the nature of the constraints imposed in
a possibilistic setting, which means that commensurability is never an issue.


6   Conclusion

We presented a semantic framework for modelling object typicality in description log-
ics. In [6] we showed how reasoning with a single typicality order on the domain of
interpretation (and the induced defeasible subsumption relation) can be reduced to rea-
soning in a sufficiently expressive DL. This translation is also applicable when reason-
ing with typicality of individual concept members, as presented in this paper.
    We also presented a proposal for deriving new typicality orders from existing ones
using feature vectors. Our proposal is compositional, and rooted in a globalist cognitive
stance on the semantics of typicality. The determination of compositional rules is there-
fore a modelling decision, unlike compound class membership, the meaning of which
can be completely determined from the meanings of its atomic constituents.


References
 1. K. J. Arrow. Social choice and individual values (2nd edition). Wiley, New York, 1963.
 2. F. Baader, I. Horrocks, and U. Sattler. Description logics. In F. van Harmelen, V. Lifschitz,
    and B. Porter, editors, Handbook of Knowledge Representation, pages 135–180. Elsevier,
    Amsterdam, 2008.
 3. Salem Benferhat, Didier Dubois, and Henri Prade. Towards a possibilistic logic handling of
    preferences. In IJCAI, pages 1370–1375, 1999.
 4. Salem Benferhat and Souhila Kaci. Logical representation and fusion of prioritized informa-
    tion based on guaranteed possibility measures: Application to the distance-based merging of
    classical bases. Artificial Intelligence, 148(1–2):291–333, 2003.
 5. K. Britz, J. Heidema, and W. Labuschagne. Semantics for dual preferential entailment. Jour-
    nal of Philosophical Logic, 2009. To appear.
 6. K. Britz, J. Heidema, and T. Meyer. Semantic preferential subsumption. In Proceedings of
    KR2008, pages 476–484. AAAI Press, 2008.
 7. N. Chater, K. Lyon, and T. Meyers. Why are conjunctive categories overextended? Journal
    of Experimental Psychology: Learning, Memory, and Cognition, 16(3):497–508, 1990.
 8. Yann Chevaleyre, Ulle Endriss, Jérôme Lang, and Nicolas Maudet. A short introduction to
    computational social choice. In Proceedings of the 33rd Conference on Current Trends in
    Theory and Practice of Computer Science (SOFSEM-2007), volume 4362 of Lecture Notes
    in Computer Science. Springer-Verlag, January 2007.
 9. F.M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation
    as failure. ACM Transactions on Computational Logic, 3(2):177–225, 2002.
10. M. Freund, D. Lehmann, and P. Morris. Rationality, transitivity and contraposition. Artificial
    Intelligence, 52(2):191–203, 1991.
11. L. Giordano, V. Gliozzi, N. Olivetti, and G.L. Pozzato. Preferential description logics. In
    N. Dershowitz and A. Voronkov, editors, Proceedings of LPAR 2007, volume 4790 of LNAI,
    pages 257–272. Springer-Verlag, 2007.
12. L. Giordano, V. Gliozzi, N. Olivetti, and G.L. Pozzato. Reasoning about typicality in prefer-
    ential description logics. In S. Hölldobler, C. Lutz, and H. Wansing, editors, Proceedings of
    JELIA 2008, volume 5293 of LNAI, pages 192–205. Springer-Verlag, 2008.
13. D. Grossi, F. Dignum, and J-J.C. Meyer. Context in categorization. In L. Serafini and
    P. Bouquet, editors, Proceedings of CRR’05, volume 136 of CEUR Workshop Proceedings.
    CEUR-WS, 2005.
14. J.A. Hampton. Overextension of conjunctive concepts: Evidence for a unitary model of con-
    cept typicality and class inclusion. Journal of Experimental Psychology: Learning, Memory,
    and Cognition, 14(1):12–32, 1988.
15. J.A. Hampton. Concepts as prototypes. The Psychology of Learning and Motivation, 46:79–
    113, 2006.
16. H. Kamp and B. Partee. Prototype theory and compositionality. Cognition, 57:129–191,
    1995.
17. D. Koller, A. Levy, and A. Pfeffer. P-CLASSIC: A tractable probabilistic description logic.
    In Proceedings of AAAI 97, pages 390–397. AAAI Press, 1997.
18. Sébastien Konieczny and Ramón Pino Pérez. Merging information under constraints: a log-
    ical framework. Journal of Logic and Computation, 12(5):773–808, 2002.
19. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and
    cumulative logics. Artificial Intelligence, 44:167–207, 1990.
20. P. Lambrix, N. Shahmehri, and N. Wahllöf. A default extension to description logics for
    use in an intelligent search engine. In S. Hölldobler, C. Lutz, and H. Wansing, editors, Pro-
    ceedings of the 31st Annual Hawaii International Conference on System Sciences, volume 5,
    pages 28–35. IEEE Computer Society, 1998.
21. D. Lehmann. Stereotypical reasoning: Logical properties. Logic Journal of the IGPL,
    6(1):49–58, 1998.
22. D. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial
    Intelligence, 55:1–60, 1992.
23. K. Lyon and N. Chater. Localist and globalist approaches to concepts. In K.J. Gilhooly,
    M.T.G. Keane, R.H.Logie, and G. Erdos, editors, Lines of Thinking. John Wiley & Sons Ltd,
    1990.
24. D.N. Osherson and E.E. Smith. Gradedness and conceptual combination. Cognition, 12:299–
    318, 1982.
25. D.N. Osherson and E.E. Smith. On typicality and vagueness. Cognition, 64:189–206, 1997.
26. M. Sheremet, D Tishkovsky, F. Wolter, and M. Zakhharyaschev. A logic for concepts and
    similarity. Journal of Logic and Computation, 17(3):415–452, 2007.
27. Y. Shoham. Reasoning about Change: Time and Causation from the Standpoint of Artificial
    Intelligence. The MIT Press, Cambridge, MA, 1988.
28. Umberto Straccia. A fuzzy description logic. In Proceedings of AAAI 98, pages 594–599.
    AAAI Press, 1998.
29. Umberto Straccia. Reasoning within fuzzy description logics. Journal of Artificial Intelli-
    gence Research, 14:137–166, 2001.
30. C. Yeung and H. Leung. Ontology with likeliness and typicality of objects in concepts. In
    D.W. Embley, A. Olivé, and S. Ram, editors, Proceedings of ER 2006, volume 4215 of LNCS,
    pages 98–111. Springer-Verlag, Berlin Heidelberg, 2006.

</pre>