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 [
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 [
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 [
In a previous paper [
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 [
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 [
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 [
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 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 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, written I C v D, iff CI DI . C v D is valid, written j= 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 2 CI ; it satisfies R(a; b) iff (aI ; bI ) 2 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 j= , iff every interpretation that satisfies K also satisfies . 2.2
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 f j : j 2 J g 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 [
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 [
We now develop a formal semantics for preferential subsumption in description logics. We assume a DL language with a finite set of preference orders f j : j 2 J g in its signature. We make the preference orders on the domain of interpretation explicit through the notion of an ordered interpretation: (I; f j : j 2 J g) is the interpretation I with preference orders f j : j 2 J g 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 2 J , where the interpretation of j is j , that is, jI = j : Definition 1. An ordered interpretation (I; f j : j 2 J g) satisfies an assertion a iff aI j bI . j b
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. 3.1
Definition 2. An ordered interpretation (I; f j : j 2 J g) consists of an interpretation I and finite, indexed set of modular partial orders f j : j 2 J g without infinite chains over its domain I .
Definition 3. An ordered interpretation (I; f j : j 2 J g) satisfies C v D, written (I; f j : j 2 J g) C v D, iff I satisfies C v D. CjI = fx 2 CI : there is no y 2 CI such that x j y and x 6= yg:
For brevity, we shall at times write J instead of f j : j 2 J g. 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 following senses of these terms: Supraclassicality: If (I ; J ) C v D then (I ; J ) C @j D for all j 2 J . Nonmonotonicity: (I ; J ) C @j D does not necessarily imply
(I ; J ) C u C0 @j D for any j 2 J .
Defeasibility: (I ; J ) C @j D does not necessarily imply (I ; J ) any j 2 J .
C v D for
The following properties of @j are analogous to the familiar properties of rational
preferential entailment [
And: If (I ; J ) C @j D and (I ; J ) Or: If (I ; J ) C @j F and (I ; J ) Left logical equivalence: If (I ; J ) (I ; J ) C @j F then (I ; J ) Left defeasible equivalence: If (I ; (I ; J ) C @j F then (I ; Right weakening: If (I ; J )
(I ; J ) C @j F .
Cautious monotonicity: If (I ; J ) (I ; J ) C u D @j F .
Rational monotonicity: If (I ; J ) (I ; J ) C u F @j D.
Cut: If (I ; J ) C u D @j F and (I ;
J )
J ) J ) J )
J )
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.
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 j= 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 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 [
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
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 8eats: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 9eats:F ish. Similarly, Bird and 9eats:F ish are both defining features of Seabird.
Seabird
Bird u 9eats:F ish P enguin v Seabird
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 hC1; : : : ; Cni with corresponding preference vector h 1; : : : ; ni such that j is a Cj -order, for 1 j n, and weight vector hw1; : : : ; wni such that wj 2 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; : : : ; Cni be a feature vector with corresponding preference vector h 1; : : : ; ni. The level of an object x 2 relative to preference order j , written levelj (x), is defined recursively as follows: levelj (x) := >><8 01 iiff xx iiss jj --mmianxiimmaalliinnCjII;nCjI ;
maxflevelj (y) : y <j xg + 1 for non-minimal objects in CI ; > j >: minflevelj (y) : x <j yg) 1 for non-maximal objects in I nCjI : 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 2 Cj , and levelj (x) = 0 for x 62 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 2 , 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; : : : ; Cni, preference vector h 1; : : : ; ni and weight vector hw1; : : : ; wni, let f : I ! Z0, such that f (a) :=
M axf1; Pn
j=1(levelj (a) 0 otherwise wj )g if a 2 CI ; for any object a 2 . The associated preference relation k on
given by: a k b iff f (a) f (b); for some k 2 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
We conclude this section with an illustrative example. Suppose we have the following terminological statements:
P enguin v Bird u F lightless u Aquatic Southern v :Equatorial GalapagosP enguin v P enguin (1) (2) (3) (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: level1(a) :=
< 1 if a is atypical in P enguinI ; : 0 otherwise: Let 2 be the modular default 9habitat:Equatorial-order that partitions this concept into two classes. Then: level2(a) :=
We now construct a feature vector for GalapagosP enguin. We choose P enguin as relevant defining feature, and 9habitat: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 hP enguin; 9habitat:Equatoriali. Its preference vector is h 1; 2i, 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: 8 4 if a is typical in P enguinI and a 2 9habitat:EquatorialI ; > >>> 3 if a is atypical in P enguinI and a 2 9habitat:EquatorialI ; < 2 if a is typical in P enguinI and a 2 8habitat:SouthernI ; >> 1 if a is atypical in P enguinI and a 2 8habitat: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: (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 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 h2; 1i 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 9habitat:Equatorial: f4(a) := 8 5 if a is typical in P enguinI and a 2 9habitat:EquatorialI ; > >>> 4 if a is typical in P enguinI and a 2 8habitat:SouthernI ; < 3 if a is atypical in P enguinI and a 2 9habitat:EquatorialI ; >> 2 if a is atypical in P enguinI and a 2 8habitat: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:
GalapagosP enguin @48habitat:Southern (6)
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.
[
Methods for the composition of preference orders have been studied in the social
choice literature [
We presented a semantic framework for modelling object typicality in description
logics. In [
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. 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 Intelligence 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. Olive´, and S. Ram, editors, Proceedings of ER 2006, volume 4215 of LNCS, pages 98–111. Springer-Verlag, Berlin Heidelberg, 2006.