We present a semantic model of typicality of concept members in description 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 characteristic features, which provides a modelling mechanism to specify typicality in composite concepts.
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, variations in both graded class membership and typicality of class members reflect differences 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 prototype [14,15]. In contrast, according to the binary model of concept typicality and class inclusion, typicality and concept membership reflect essentially different cognitive processes. 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-ornothing 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 intelligent knowledge systems over complex structured domains, providing an unambiguous semantics to ontologies, and balancing sufficient expressive power with efficient reasoning 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 default 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 semantics for propositional entailment [5,19]. We gave a formal semantics of defeasible subsumption, as well as a translation of defeasible subsumption to classical subsumption 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 defeasible 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 outside 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 background on rational preference orders, we introduce the notion of an ordered interpretation, 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 defeasibly 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 compositionality as is the case with atomic composition. We show how feature vectors may be used to determine typicality compositionally, taking into account semantic context.
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 A I of ∆ I , and each atomic role R to a subset R I 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 relationships 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 D, where C and D are (possibly complex) concept descriptions. C D is also called a subsumption statement, read "C is subsumed by D". An interpretation
Rbox statements include role inclusions of the form R 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 a I of the domain of interpretation ∆ I . An interpretation I satisfies the assertion
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 φ.
In a preferential semantics for a propositional language, one assumes some order relation 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 interpretations 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 application 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. satisfy 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 presence 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.
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 signature. 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, I j =≤ j : Definition 1. An ordered interpretation (I, {≤ j : j ∈ J }) satisfies an assertion a j b iff a I ≤ j b I .
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 ordered 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. Finally, we define what it means for a preferential subsumption statement to be entailed by a knowledge base.
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 D, written (I, {≤ j : j ∈ J }) C D, iff I satisfies C D.
The preferential semantics of ∼j is then defined as follows: Definition 4. An ordered interpretation (I, {≤ j : j ∈ J }) satisfies the preferential subsumption C ∼j D, written (I, {≤ j : j ∈ J }) C ∼j D, iff C I j ⊆ D I , where
there is no y ∈ C I such that x ≤ j y and x = 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 , 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 following senses of these terms: Supraclassicality: If (I, ≤ J ) C D then (I, ≤ J ) C ∼j D for all j ∈ J . Nonmonotonicity: (I, ≤ J ) C ∼j D does not necessarily imply (I, ≤ J ) C C ∼j D for any j ∈ J . Defeasibility: (I, ≤ J ) C ∼j D does not necessarily imply (I, ≤ J ) C D for any j ∈ J .
The following properties of ∼j are analogous to the familiar properties of rational preferential entailment [19,22].
Satisfaction for defeasible subsumption is defined relative to a fixed, ordered interpretation. We now take this a step further, and develop a general semantic theory of entailment 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 satisfies C ∼j D.
The following properties of ∼j are direct consequences of its corresponding properties relative to a fixed, ordered interpretation:
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 example, reflexivity of ∼j relative to K reads K |= C ∼j C.
In Section 2 we presented a semantic framework to model typicality of concept membership: ≤ 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 typicality orders recursively, depending on the operators used in the syntactic construction of C. Say C ≡ A 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 . 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.
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 relations, 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. Defining 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 ∃eats.F ish P enguin Seabird P enguin ∼1 ∀eats.F ish
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 obvious 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 respective 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 C 1 , . . . , C n with corresponding preference vector ≤ 1 , . . . , ≤ n such that ≤ j is a C j -order, for 1 ≤ j ≤ n, and weight vector w 1 , . . . , w n such that w j ∈ 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 C 1 , . . . , C n be a feature vector with corresponding preference vector ≤ 1 , . . . , ≤ n . The level of an object x ∈ ∆ relative to preference order ≤ j , written level j (x), is defined recursively as follows:
in ∆ I \C I j ; max{level j (y) : y < j x} + 1 for non-minimal objects in C I j ; min{level j (y) : x < j y}) − 1 for non-maximal objects in ∆ I \C I j .
Definition 8 maps objects in the domain to integers. We note that the absence of infinite ≤ j -chains ensures that level j is defined on the whole of ∆. Given any feature C j in the feature vector, Definition 8 assigns a positive level to all objects in C j , and a non-positive level to all objects not in C j . In the case where ≤ j is a two-level order, level j (x) = 1 for x ∈ C j , and level j (x) = 0 for x ∈ C j .
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 level j (x) ≤ level j (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.
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.
We conclude this section with an illustrative example. Suppose we have the following terminological statements: P enguin Bird F lightless Aquatic
(1) P enguin ∼1 ∀habitat.Southern
(2) Southern ¬Equatorial
(3) GalapagosP enguin P enguin (4) Line (2) of the TBox states that the habitat of typical penguins is restricted to the southern 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:
Let 2 be the modular default ∃habitat.Equatorial-order that partitions this concept into two classes. Then:
We now construct a feature vector for GalapagosP enguin. We choose P enguin as relevant defining feature, and ∃habitat.Equatorial as relevant characteristic feature. 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 P enguin, ∃habitat.Equatorial . Its preference vector is 1 , 2 , and as weight vector we choose 1, 2 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 enguin I and a ∈ ∃habitat.Equatorial I ; 3 if a is atypical in P enguin I and a ∈ ∃habitat.Equatorial I ; 2 if a is typical in P enguin I and a ∈ ∀habitat.Southern I ; 1 if a is atypical in P enguin I and a ∈ ∀habitat.Southern I ; 0 otherwise. Note that the first case, i.e. where f 3 (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:
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 preference 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 2, 1 in the above example. This induces the following lexicographic order based on the features as above, in which having the defining feature P enguin takes precedence over the characteristic feature ∃habitat.Equatorial:
5 if a is typical in P enguin I and a ∈ ∃habitat.Equatorial I ; 4 if a is typical in P enguin I and a ∈ ∀habitat.Southern I ; 3 if a is atypical in P enguin I and a ∈ ∃habitat.Equatorial I ; 2 if a is atypical in P enguin I and a ∈ ∀habitat.Southern I ; 0 otherwise. As we had before, the case where f 4 (a) = 5 does not hold for any object a, as it contradicts terminological axiom (2) in the knowledge base. Using the preference order 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] proposed a model of graded membership, but their representation is not directly in terms of description logics. Approaches using extensions of description logics as the modelling 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] define 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 objects, 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.
We presented a semantic framework for modelling object typicality in description logics. 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 reasoning in a sufficiently expressive DL. This translation is also applicable when reasoning 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 therefore a modelling decision, unlike compound class membership, the meaning of which can be completely determined from the meanings of its atomic constituents.