We introduce a family of operators to combine Description Logic concepts. They aim to characterise complex concepts that apply to instances that satisfy \enough" of the concept descriptions given. For instance, an individual might not have any tusks, but still be considered an elephant. To formalise the meaning of \enough", the operators take a list of weighted concepts as arguments, and a certain threshold to be met. We commence a study of the formal properties of these operators, and study some variations. The intended applications concern the representation of cognitive aspects of classi cation tasks: the interdependencies among the attributes that de ne a concept, the prototype of a concept, and the typicality of the instances.
We begin the project of extending description logics to model cognitively relevant features of classi cation. We start from familiar Description Logic formalisms (in particular from ALC), which is an important logical language to model concepts and concept combinations in knowledge representation. We introduce a family of operators which apply to sets of concept descriptions and return a composed concept whose instances are those that satisfy \enough" of the listed concept descriptions. To provide a meaning of \enough", the operator takes a list of weighted concepts as argument, as well as a threshold. The combined concept applies to every instance whose sum of the weights of the concepts it satis es meets the threshold. Using a threshold, the presentation focuses on crisp categorisations. Although the framework of weighted concepts easily adapts to a many-valued setting, we do not admit degrees of classi cation here.
Depending on the base description logic used, the operators introduced might or might not extend the extensional expressivity of the concept language in the sense of increasing the expressive power to de ne new, previously unde nable concepts. However, they always allow for a more cognitively grounded modelling of the intensional aspects of classi cations, which are concerned with how the parts of a concept de nition contribute to the classi cation task overall. The operators also allow for more compact representations.
The approach to weighted logics that we follow here takes inspiration from
the use of sets of weighted proposition for representing utility functions in [
The intended applications of this framework are inspired by the idea of
providing a cognitively meaningful representation of classi cation tasks. Cognitive
models of concepts and classi cation are usually grouped into the prototype view,
the exemplar view, and the knowledge view also called theory-theory (see [
In particular, we will see how the proposed operators allow for
representing the prototype view of classi cation under a concept, cf. ([
We introduce a class of m-ary operators, denoted by the symbol rr (spoken `tooth'), for combining concepts. Each operator works a follows: i) it takes a list of concept descriptions, ii) it associates a vector of weights to them, and iii) it returns a complex concept that applies to those instances that satisfy a certain combination of concepts, i.e., those instances for which, by summing up the weights of the satis ed concepts, a certain threshold is met.
The new logic is denoted by ALCrrR , where weights and thresholds range over real numbers r 2 R. In the following we will refer to the languages for brevity just as ALCrr. To de ne the extended language of ALCrr, we add combination operators as follows, which behave syntactically just like m-ary modalities. We assume a vector of m weights w 2 Rm and a threshold value t 2 R. Each pair w, t speci es an operator: if C1; : : : ; Cm are concepts of ALC, then rrtw(C1; : : : ; Cm) is a concept of ALCrr. Note that in this basic de nition, the possible nesting of the operator is excluded.3 3 In a more ne-grained de nition ALCirrK , i 0, is the logic with i levels of allowed nesting and where weights and thresholds range over K; we will comment on this further below. vCI (d) =
X i2f1;:::;mg
fwi j d 2 CiI g (rrtw(C1; : : : ; Cm))I = fd 2
I j vCI (d) tg The interpretation (i.e., the extension) of a rr-concept in I = ( I ; I ) is then: For Ci0 2 ALC, the set of ALCrr concepts is then described by the grammar:
C ::= A j :C j C u C j C t C j 8R:C j 9R:C j rrtw(C10; : : : ; Cm0) The semantics of the operator is obtained by extending the de nition of the semantics of ALC as follows. Let I = ( I ; I ) be an interpretation of ALC. We de ne the value of a d 2 I under a rr-concept C = rrtw(C1; : : : ; Cm) by setting: To better visualise the weights an operator associates to the concepts, we sometimes use the notation rrt((C1; w1); : : : ; (Cm; wm)) instead of rrtw(C1; : : : ; Cm).
In the following examples, we will consider the value of an object name a (aka individual constant) wrt. a rr-concept for interpretations that satisfy a certain knowledge base K (i.e. a set of formulas).
name of ALC and K an ALC knowledge base. We set
X i2f1;:::;mg vCK(a) := fwi j K j= Ci(a)g I.e., vCK(a) gives the accumulated weight of those Ci that are entailed by K to satisfy a.
Note that for positive weights, a given name a and a xed interpretation I such that I j= K, we always have that vCK(a) vCI (aI ).
Example 1. Consider the set of concepts C = fRed; Round; Colouredg and the concept C de ned by means of the rr operator
C = rrt((Red t Round; w1); (9above:Coloured; w2)) The de nition of C means that the relevant information to establish the categorisation under C of an object is whether (i) it is red or round, and (ii) it is above a coloured thing.
Consider the following knowledge base K = fRed(a); 9above:Blue(a); Blue v Colouredg, i.e., an agent knows that the object a is red and it is above a blue thing and that blue things are coloured, Blue v Coloured.
The value of a returned by vCK is computed as follows. Firstly, if a satis es Red, then a satis es Red t Round, so the weight w1 can be obtained. Moreover, since Blue v Coloured 2 K and a satis es 9above:Blue, then a satis es 9above:Coloured, so also the weight w2 can be obtained. Thus, vCK(a) is w1 +w2. If w1 + w2 t, then a is classi ed under C. (1) (2) 2.1
We discuss a few general properties of the rr operators which allow for reasoning about combinations of concepts.
Firstly, we note that, for every possible choice of weights and thresholds, the operator is well-de ned: the rrs of equivalent concepts return equivalent concepts, i.e. equivalence is a congruence for the tooth. For every I,
CiI = DiI =) (rrtw(C1; : : : ; Ci; : : : ; Cm))I = (rrtw(C1; : : : ; Di; : : : ; Cm))I (3) Proof. Assume an interpretation I such that CI = DI . Suppose that d 2 i i (rrtw(C1; : : : ; Ci; : : : ; Cm))I , thus, by de nition, Pfwi j d 2 CiI g t. Since Di is equivalent to Ci, d is also in (rrtw(C1; : : : ; Di; : : : ; Cm))I . tu Consider now the following statement, which resembles the monotonicity condition of (normal) modal operators. The statement holds true whenever the weights are non-negative numbers, i.e. for wi 2 R0+ we have:
CI i
DiI =) (rrtw(C1; : : : ; Ci; : : : ; Cm))I (rrtw(C1; : : : ; Di; : : : ; Cm))I (4) Proof. We assume all weights are non-negative and establish 4. Assume that CiI DiI . Suppose d 2 rrtw(C1; : : : ; Ci; : : : ; Cm))I , then, by de nition, Pfwi j d 2 Cig t. We have two relevant cases: (i) d 2 CiI , thus, by assumption, d 2 DI . Since the weight associated to Di is the same as the weight associated i to Ci the sum does not change. (ii) Suppose d 2= CiI and d 2 DiI . In this case, the sum now adds the weight associated to Di. Since the weights are non-negative, the sum is increasing, thus Pfwi j d 2 Cig + wi is still greater than t. tu Extending on this result, only under certain conditions does the tooth operator t in between the conjunction and the disjunction of the concepts. Namely, t > 0 =) (rrtw(C1; : : : ; Cm))I (C1 t t Cm)I Indeed, for any d 62 (C1 t : : : t Cm)I the value vCI (d) would be zero, and hence d 62 rrtw(C1; : : : ; Cm))I .
On the other hand, (5) (6) t
X wi =) (C1 u i u Cm)I (rrtw(C1; : : : ; Cm))I Indeed, for any d 2 (C1 u : : : u Cm)I we have that vCI (d) = Pi wi t and hence that d 2 (rrtw(C1; : : : ; Cm))I . +
Moreover, if the set of weights is restricted to non-negative numbers, wi 2 R0 , then: (rrtw(C1; : : : ; Cm))I (rrw;wm+1 (C1; : : : ; Cm; Cm+1))I t (7) That is, by adding positive attributes to the de nition of a concept, we cannot invalidate the categorisation of an instance under the concept.
C2 C1 1
1 2
C1 0
0 1 (rrtw(C1; : : : ; Cm))I = (rrkk tw(C1; : : : ; Cm))I For every k, we have that:
t t+k (rr(w1;:::;wm)(C1; : : : ; Cm))I = (rr(w1;:::;wm;k)(C1; : : : ; Cm; >))I One example of Eq. 11, which can be represented as shown in Figure 1, is the following: (C1 u C2)I = (rr(1;1)(C1; C2))I = (rr(1;1; 1)(C1; C2; >))I
2 1 2 1 Fig. 1. Consider: rr(1;1)(C1; C2) (on the left) and rr(1;1; 1)(C1; C2; >) (to the right).
The properties of weights a ect the classi cation in the following way. Uniform permutations of weights and concepts arguments correspond to the same concept. For every permutation : (rrtw(C1; : : : ; Cm))I = (rr (w)( (C1; : : : ; Cm)))I t When C1I = C2I (in particular when C1 = C2): (rr(w1;:::;wm)(C1; : : : ; Cm))I = (rr(w1+w2;w3;:::;wm)(C1; C3; : : : ; Cm))I t t Moreover, every positive transformation of weights and thresholds returns the same sets of entities. For every k > 0, we have that:
We discuss in this section the de nability of concepts from the purely extensional point of view. Every (complex) concept C of ALC can be trivially represented by means of rrt(t)(C). However, it is interesting to discuss whether we can provide a representation of C in terms of weights to be associated with the atomic concepts that de ne C. We rst focus solely on the Boolean structure of complex concepts followed by a discussion of counting and maximisation.
C2 (8) (9) (10) (11) 3.1
For instance, the Boolean operators can be expressed as special cases of rr of atomic concepts: { (C1 u C2)I = (rr(1;1)(C1; C2))I
2 { (C1 t C2)I = (rr(1;1)(C1; C2))I
1 { (:C1)I = (rr( 1)(C1))I
0
More generally, some Boolean functions can be captured with rr, without having recourse to complex concepts as arguments. In the case of Boolean functions over two variables (i.e. atomic concepts) C1 and C2, we obtain the following: > = rr(00;0)(C1; C2) C1 = rr(11;0)(C1; C2) :C1 = rr(0 1;0)(C1; C2) C1 u C2 = rr(21;1)(C1; C2)
1 C1 u :C2 = rr(1; 1)(C1; C2) C1 t C2 = rr(11;1)(C1; C2)
0 C1 t :C2 = rr(1; 1)(C1; C2) ? = rr(10;0)(C1; C2) C2 = rr(10;1)(C1; C2) :C2 = rr(00; 1)(C1; C2) :C1 u C2 = rr(1 1;1)(C1; C2)
0 :C1 u :C2 = rr( 1; 1)(C1; C2) :C1 t C2 = rr(0 1;1)(C1; C2) :C1 t :C2 = rr( 11; 1)(C1; C2)
The operator rr is thus, by itself, a functionally complete logical connective if we allow for nesting the operator. However, it is impossible to represent (C1 u :C2) t (:C1 u C2) (the symmetric di erence, XOR) and (C1 u C2) t (:C1 u :C2) (both or none, the negation of XOR) without recursion (that is, nesting of the rr), complex concepts as arguments, or without the Boolean combination of more than one rr.
Indeed, suppose that the symmetric di erence C1 XOR C2 is de nable as an expression of the form rrtw(C1; C2; >; ?) for w = (w1; w2; w>; w?). Then it can be easily veri ed that w1 > 0, since for d 62 C1I [ C2I we must have that vCI (d) = w> < t while for d 2 C1I n C2I we have that vCI (d) = w> + w1 t. A similar argument shows that w2 > 0 as well; but then, for d 2 C1I \ C2I we have that vCI (d) = w> + w1 + w2 > t and hence I; d j= rrtw(C1; C2; >; ?).
Of course, one can use the following Boolean combinations, using the previous characterizations:
1 0 { (C1 u :C2) t (:C1 u C2) = rr(1; 1)(C1; C2) t rr( 1;1)(C1; C2) { (C1 u C2) t (:C1 u :C2) = rr(21;1)(C1; C2) t rr( 11; 1)(C1; C2) With complex concept arguments, we have: With nesting, we could do: 0 2 { (C1 u C2) t (:C1 u :C2) = rr( 1; 1;2)(C1; C2; rr(1;1)(C1; C2)) On the other hand, given any expression rrtw(C1; : : : ; Cm), consider the set = fU f1 : : : ng : Pi2U wi tg of all sets of indices that, if they were the only ones corresponding to concepts that are satis ed by an individual d in an interpretation I, would make it so that d 2 rrtw(C1; : : : ; Cm)I . Then we have at once that rrtw(C1; : : : ; Cm) is logically equivalent to
G U2 0 i2U
l i2f1:::ngnU
1 :CiA Notice that this translation may lead to an exponentially longer formula. 3.2
The combination operators can be instantiated to capture, in a compact way, a large class of concept compositions. Suppose that D is a complex concept whose de nition applies the concepts C1; : : : ; Cm.
We can de ne a concept D such that d is in DI i the majority of concepts among C1 : : : ; Cm applies to d. In this case, we are assuming that all the m concepts have equal weight and d is classi ed under the majority i it satis es more than m2 concepts. Equivalently, we associate weight 2 to each concept Ci and we set t = m: rrm((C1; 2); : : : ; (Cm; 2)). In a similar way, we can introduce operators that use a quota rule, i.e they apply to instances that satisfy at least a number q 2 f1; : : : ; mg of the concepts in the scope of rr.
Moreover, a preferential structure on the combined concepts can be rendered by means of (Borda) scores: rrt((C1; s1); : : : ; (Cm; sm)), where the weights are subject to the constraint s1 sm. This means that, e.g., satisfying C1 is more important than C2, and so on. By choosing the weights and the threshold in a suitable way, we can then express situations where satisfying the rst l concepts is signi cant, or dominating for the classi cation. I.e., the combined weight of the rst l concepts will su ce to classify under the concept, and if weights are set high enough, this condition can be turned into a necessary one.
Finally, it is possible to de ne the set of instances that at most reach a given threshold: rr t((C1; w1); : : : (Cm; wm) rr t((C1; w1); : : : ; (Cm; wm)) (12) and the concept of instances that exactly score a certain threshold value t: rr=t((C1; w1); : : : (Cm; wm) rrt((C1; w1); : : : ; (Cm; wm) u rr t((C1; w1); : : : (Cm; wm) (13) 3.3
Finally, it is interesting to consider the set of entities that maximally satisfy a
combination of concepts C1; : : : Cm of ALC. That is, we may de ne an operator
with the following semantics:
rrmax((C1; w1); : : : (Cm; wm)) I
= fd 2
j vCI (d)
vCI (d0) for all d0 2
g
(14)
De ning rrmax in terms of rrt would require to use a universal role, which
signi cantly increases the expressive power of ALC [
First of all, let us see how the rrmax operator may be de ned in terms of the universal modality. Given a tuple w = (w1 : : : wm) of weights, let S = fPi aiwi : ai 2 f0; 1gg be the ( nite) set of all possible scores that can be obtained by using these weights; and then, let = minfjv v0j : v; v0 2 Sg be the smallest possible distance between di erent scores. Then we have that rrwmax(C1 : : : Cm)
G rrtw(C1 : : : Cm) u 8U::rrtw+ (C1 : : : Cm) (15) t2S Proof. Indeed, suppose that I; d j= rrwmax(C1 : : : Cm) for some individual d of our domain.4 Now let t = vCI (d): then, by de nition, t vCI (d0) for all individuals d0 2 . This implies that I; d j= rrtw(C1 : : : Cm) and that I; d0 6j= rrtw+ (C1 : : : Cm) for all d0 2 , which implies at once that I; d j= rrtw(C1 : : : Cm)u t+ (C1 : : : Cm) as required. 8U::rrw
Conversely, suppose that I; d j= rrtw(C1 : : : Cm) u 8U::rrtw+ (C1 : : : Cm) for some t 2 S. Then vCI (d) = t, and for all individuals d0 2 we have that I; d0 6j= rrtw+ (C1 : : : Cm), which by the de nition of implies at once that vCI (d0) t. Thus I; d j= rrwmax(C1 : : : Cm), and this concludes the proof. tu
Conversely, given the rrmax operator it is possible to de ne the universal modality as 8U:C rr(ma1x)(C) u C (16) (rr(ma1x)(C)). Thus CI = Proof. Indeed, suppose that I; d j= 8U:C. This means that I; d0 j= C for all individuals d0 2 ; and, therefore, v(IC; 1)(d0) = 1 for all d0 2 . In particular, we thus have that I; d j= C; and moreover, v(IC; 1)(d) = 1 = v(IC; 1)(d0) for all d0 2 , and so I; d j= rr(ma1x)(C). So I; d j= (rr(ma1x)(C)) u C, as required.
Conversely, if I; d j= (rr(ma1x)(C)) u C then rst of all we have that I; d j= C and that therefore v(IC; 1)(d) = 1. Now take any other individual d0 2 . We state that I; d0 j= C as well; indeed, if instead I; d0 6j= C we would have that
I I v(C; 1)(d0) = 0 > v(C; 1)(d), which is impossible since by assumption I; d j= as required. tu
We leave a detailed study of the rrmax operator and similar extensions for future work. 4 This is a mild abuse of notation for d 2 rrwmax(C1 : : : Cm)I . In what follows, we will freely write expressions like I; d j= C with the intended meaning of d 2 CI .
We see now how the rr operators allow for representing ne-grained dependencies among the attributes that de ne a concept. We may call this feature intensional expressivity. We study situations where an agent who has knowledge represented by K performs the task of classifying an object a under the concept C = rrtw(C1; : : : ; Cm). That is, we focus on how K j= rrtw(C1; : : : ; Cm) (a) and we discuss how the pieces of knowledge in K may contribute to satisfy the attributes occurring in C.
We say that the function vCK is additive on the information in K = f 1; : : : ; lg i for every individual a, vCK(a) = PfvCf ig(a) for i 2 Kg. In this case, the satisfaction of each i contributes independently of the other formulas in K. We say that the function vCK is super-additive on K i for every a, vCK(a) PfvCf ig(a) for i 2 Kg and sub-additive i vCK(a) PfvCf ig(a) for i 2 Kg. Super-additivity represents positive synergies between the information provided by K, whereas sub-additivity expresses negative synergies. We illustrate this by means of the following examples.
Example 2. Suppose that the concept elephant E is de ned by four attributes:
E = rrt((Large; w1); (Heavy; w2); (hasTrunk; w3); (Grey; w4)) This de nition entails that each of the attributes in E contributes independently of the others to the classi cation of an object as an elephant.
Consider a knowledge base K = fLarge(a); Heavy(a); hastrunk(a); Grey(a)g. Then, vEK(a) = vLarge(a)(a) + vHeavy(a)(a) + vEGrey(a)(a) + vEhasTrunk(a)(a), that is,
E E vEK is an additive wrt. the formulas in K.
By exploiting complex concept descriptions in the scope of rr, we can enable positive and negative synergies among the attributes.
Example 3. Suppose now we rede ne the concept elephant as follows, where we suppose that w5 > w1 + w3, w6 > w2 + w3, and w7 > w3 + w4 and each Wi is positive.
E0 =rrt((Large; w1); (Heavy; w2); (hasTrunk; w3); (Grey; w4);
(Large u hasTrunk; w5); (Heavy u hasTrunk; w6); (Grey u hasTrunk; w7)) In this case, the relevance of the pieces of information in K = fLarge(a); Heavy(a); hasTrunk(a); Grey(a)g outweighs the sum of the values of each attribute. That vEL0arge(a)(a) + vEH0eavy(a)(a) + vEG0rey(a)(a) + vEh0asTrunk(a)(a). is, vEK0 (a)
The meaning of this representation is that adding \having a trunk" signi cantly increases the importance of the combination of attributes for classifying an elephant. Accordingly the value of vEK0 is in this case super-additive on K. In the case of sub-additive functions, the combination of two or more attributes may lower the salience for the classi cation. The combination of the use of conjunctions of concepts and negative weights allows for modelling how certain attributes may decrease the salience of the combination of other attributes. Example 4. Suppose that we want to classify an individual according to the disease that she may su er. For instance, the concept of u may be represented as follows: FLU =rr((Fever u Nausea; w1); (Fever u Spots; w2); (Nausea u Spots; w3); (Fever; w4); (Nausea; w5)) In this case, the combination of fever and nausea is highly signi cant for the diagnosis, whereas adding the symptom `spots' signi cantly decreases the reliability of the classi cation under FLU, because it is a strong indication of chickenpox. So, w1 > w4 + w5 and w2 and w3 are both greater than w1 + w4 + w5. That is, the function vFKLU is sub-additive on K = fFever(a); Nausea(a); Spots(a)g.
Complex concepts occurring as arguments of rr provide a way to express
many types of dependencies among the weights of the attributes. A
comprehensive study of this type of expressivity is left for a future work and requires
rephrasing the results in [
We illustrate how the rr operators can represent the cognitive approach to
concepts based on prototypes. In particular, we follow [
Let us de ne a prototype C for a concept C as (where Qij is the i-th value of the j-th attribute, sij is the salience of Qij wrt. C, dj is the diagnosticity of the j-th attribute wrt. C):
C = f(Q11; s11 d1); : : : ; (Qr1; sr1 d1); : : : ; (Q1n; s1n dn); : : : ; (Qnm; snm dn)g: Note that here we weighted the salience of each attribute-value with the diagnosticity of the attribute, but more elaborate strategies exist. Furthermore, the attributes within a single dimension are assumed as mutually exclusive, e.g., if something is red, then it is not of any other colour, formally Qij \ Qjk = ; for i 6= k. Assume now to know some attribute-values of a given object a. The classi cation of a under the concept C is usually done by leveraging on a (usually metric) function that establishes, on the basis of the matching of features, how similar the object a and the prototype of C are.
In our setting, we can introduce a concept C by using a rr operator that directly considers the attribute-values, the saliences, and the diagnosticities in the prototype C (where we assume Qij u Qjk ? for i 6= k): C = rrt((Q11 ; s11 d1); : : : ; (Qr1 ; sr1 d1); : : : ; (Q1n ; s1n dn); : : : ; (Q mn ; snm dn)) The classi cation under C applies then to the objects that have enough features in common with the prototype to exceed the threshold t, i.e., they are close enough with respect to the prototype. We can also individuate the prototypical instances of C as the objects (if they exist) that satisfy all the Qji in C.
Note that the object-prototype similarity is here simply rendered by summing up all the weights of the matching Q i . The discussion of more sophisticated j choices to measure the distance to the prototype is left for future work. Moreover, in our setting, we can enable synergies between attributes in a super-additive or in a sub-additive fashion. However, to de ne prototypes in this rich setting, we will use the rrmax operator, or approximate it by carefully selecting the threshold.
This setting allows for de ning a typicality operator, as in [
Finally, the rr=t operator may be used to de ne similarity of instances with respect to a (number of) concept(s), that is, those instances that are not distinguishable in terms of the complex concept. 6
We introduced a class of operators for de ning complex concepts that weigh the role of the de ning attributes. We presented a few general properties of these operators, and we started investigating their expressivity. Pinpointing the exact expressivity of various combinations of DLs and rr-operators as well as studying succinctness e ects is part of future work.
We further illustrated how the operators may be applied to render
cognitively meaningful mechanisms for classi cation. Future work will be dedicated
to properly investigate the logical properties of the operators and their natural
extensions, and to apply them to describe salient cognitive features of concepts
such as concept combinations and blending [