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 classification tasks: the interdependencies among the attributes that define 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 classification. 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 satisfies 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 classification 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 define new, previously undefinable concepts. However, they always allow for a more cognitively grounded modelling of the intensional aspects of classifications, which are concerned with how the parts of a concept definition contribute to the classification 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 [1]. Extensions of that approach to description logics have been developed in [2]. Two related articles are [3] and [4], where cognitive features of categorisation have been modelled by means of sets of weighted predicative formulas. The main difference in the present approach is that we study weighted combinations of concepts by explicitly introducing syntactic operators on concepts extending the basic concept languages, and investigating their logical properties.
The intended applications of this framework are inspired by the idea of providing a cognitively meaningful representation of classification tasks. Cognitive models of concepts and classification are usually grouped into the prototype view, the exemplar view, and the knowledge view also called theory-theory (see [5,6]), but also Gärdenfors's theory of conceptual spaces [7] and Barsalou's theory of frames [8] enter this category. They hardly rely on logical representation of concepts, however. In this paper, we want to explore the possibility of extending logic-based representations of concepts to capture aspects of cognitive modelling.
In particular, we will see how the proposed operators allow for representing the prototype view of classification under a concept, cf. ( [9]). Moreover, a number of cognitively relevant phenomena can be represented in this setting. For instance, the marginal contribution of the attributes entering the definition of a complex concept, the contextual dependence of a classification task on the available information, and the typicality of an instances, cf. [10]. Our work here is largely independent of the specifics of the concept language used; we will here use standard definitions and terminology from description logics [11], primarily working with the language ALC.
We introduce a class of m-ary operators, denoted by the symbol ∇ ∇ (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 satisfied concepts, a certain threshold is met.
The new logic is denoted by ALC ∇ ∇ R , where weights and thresholds range over real numbers r ∈ R. In the following we will refer to the languages for brevity just as ALC ∇ ∇ . To define the extended language of ALC ∇ ∇ , we add combination operators as follows, which behave syntactically just like m-ary modalities. We assume a vector of m weights w ∈ R m and a threshold value t ∈ R. Each pair w, t specifies an operator: if C 1 , . . . , C m are concepts of ALC, then ∇ ∇ t w (C 1 , . . . , C m ) is a concept of ALC ∇ ∇ . Note that in this basic definition, the possible nesting of the operator is excluded. 3For C i ∈ ALC, the set of ALC ∇ ∇ concepts is then described by the grammar:
The semantics of the operator is obtained by extending the definition of the semantics of ALC as follows. Let I = (∆ I , • I ) be an interpretation of ALC. We define the value of a d ∈ ∆ I under a ∇ ∇-concept C = ∇ ∇ t w (C 1 , . . . , C m ) by setting:
The interpretation (i.e., the extension) of a ∇ ∇-concept in I = (∆ I , • I ) is then:
To better visualise the weights an operator associates to the concepts, we sometimes use the notation ∇ ∇ t ((C 1 , w 1 ), . . . , (C m , w m )) instead of ∇ ∇ t w (C 1 , . . . , C m ). In the following examples, we will consider the value of an object name a (aka individual constant) wrt. a ∇ ∇-concept for interpretations that satisfy a certain knowledge base K (i.e. a set of formulas).
Definition 1 (Weights relative to a knowledge base). Let a be an object name of ALC and K an ALC knowledge base. We set The definition 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 = {Red(a), ∃above.Blue(a), Blue Coloured}, 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 Coloured.
The value of a returned by v K C is computed as follows. Firstly, if a satisfies Red, then a satisfies Red Round, so the weight w 1 can be obtained. Moreover, since Blue Coloured ∈ K and a satisfies ∃above.Blue, then a satisfies ∃above.Coloured, so also the weight w 2 can be obtained. Thus,
We discuss a few general properties of the ∇ ∇ 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-defined: the ∇ ∇s of equivalent concepts return equivalent concepts, i.e. equivalence is a congruence for the tooth. For every I,
Proof. Assume an interpretation I such that
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 w i ∈ R + 0 we have:
Proof. We assume all weights are non-negative and establish 4. Assume that
Since the weight associated to D i is the same as the weight associated to C i the sum does not change. (ii) Suppose d / ∈ C I i and d ∈ D I i . In this case, the sum now adds the weight associated to D i . Since the weights are non-negative, the sum is increasing, thus
Extending on this result, only under certain conditions does the tooth operator fit in between the conjunction and the disjunction of the concepts. Namely,
Indeed, for any d ∈ (C 1 . . . C m ) I the value v I C (d) would be zero, and hence
Indeed, for any
That is, by adding positive attributes to the definition of a concept, we cannot invalidate the categorisation of an instance under the concept. The properties of weights affect the classification in the following way. Uniform permutations of weights and concepts arguments correspond to the same concept. For every permutation σ:
When
Moreover, every positive transformation of weights and thresholds returns the same sets of entities. For every k > 0, we have that:
For every k, we have that:
One example of Eq. 11, which can be represented as shown in Figure 1, is the following:
We discuss in this section the definability of concepts from the purely extensional point of view. Every (complex) concept C of ALC can be trivially represented by means of ∇ ∇ t (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 define C. We first focus solely on the Boolean structure of complex concepts followed by a discussion of counting and maximisation.
For instance, the Boolean operators can be expressed as special cases of ∇ ∇ of atomic concepts:
More generally, some Boolean functions can be captured with ∇ ∇, without having recourse to complex concepts as arguments. In the case of Boolean functions over two variables (i.e. atomic concepts) C 1 and C 2 , we obtain the following:
The operator ∇ ∇ is thus, by itself, a functionally complete logical connective if we allow for nesting the operator. However, it is impossible to represent (C 1 ¬C 2 ) (¬C 1 C 2 ) (the symmetric difference, XOR) and (C 1 C 2 ) (¬C 1 ¬C 2 ) (both or none, the negation of XOR) without recursion (that is, nesting of the ∇ ∇), complex concepts as arguments, or without the Boolean combination of more than one ∇ ∇.
Indeed, suppose that the symmetric difference C 1 XOR C 2 is definable as an expression of the form ∇ ∇ t w (C 1 , C 2 , , ⊥) for w = (w 1 , w 2 , w , w ⊥ ). Then it can be easily verified that w 1 > 0, since for
A similar argument shows that w 2 > 0 as well; but then, for
Of course, one can use the following Boolean combinations, using the previous characterizations:
With complex concept arguments, we have:
With nesting, we could do:
On the other hand, given any expression ∇ ∇ t w (C 1 , . . . , C m ), consider the set Γ = {U ⊆ {1 . . . n} : i∈U w i ≥ t} of all sets of indices that, if they were the only ones corresponding to concepts that are satisfied by an individual d in an interpretation I, would make it so that d ∈ ∇ ∇ t w (C 1 , . . . , C m ) I . Then we have at once that ∇ ∇ t w (C 1 , . . . , C m ) is logically equivalent to
Notice that this translation may lead to an exponentially longer formula.
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 definition applies the concepts C 1 , . . . , C m . We can define a concept D such that d is in D I iff the majority of concepts among C 1 . . . , C m applies to d. In this case, we are assuming that all the m concepts have equal weight and d is classified under the majority iff it satisfies more than m 2 concepts. Equivalently, we associate weight 2 to each concept C i and we set t = m: ∇ ∇ m ((C 1 , 2), . . . , (C m , 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 ∈ {1, . . . , m} of the concepts in the scope of ∇ ∇.
Moreover, a preferential structure on the combined concepts can be rendered by means of (Borda) scores: ∇ ∇ t ((C 1 , s 1 ), . . . , (C m , s m )), where the weights are subject to the constraint s 1 ≥ • • • ≥ s m . This means that, e.g., satisfying C 1 is more important than C 2 , and so on. By choosing the weights and the threshold in a suitable way, we can then express situations where satisfying the first l concepts is significant, or dominating for the classification. I.e., the combined weight of the first l concepts will suffice 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 define the set of instances that at most reach a given threshold:
and the concept of instances that exactly score a certain threshold value t:
Finally, it is interesting to consider the set of entities that maximally satisfy a combination of concepts C 1 , . . . C m of ALC. That is, we may define an operator with the following semantics:
∇ ∇ max ((C1, w1), . . . (Cm, wm))
Defining ∇ ∇ max in terms of ∇ ∇ t would require to use a universal role, which significantly increases the expressive power of ALC [12]. First of all, let us see how the ∇ ∇ max operator may be defined in terms of the universal modality. Given a tuple w = (w 1 . . . w m ) of weights, let S = { i a i w i : a i ∈ {0, 1}} be the (finite) set of all possible scores that can be obtained by using these weights; and then, let = min{|v − v | : v, v ∈ S} be the smallest possible distance between different scores. Then we have that
Proof. Indeed, suppose that I, d |= ∇ ∇ max w (C 1 . . . C m ) for some individual d of our domain. 4 We leave a detailed study of the ∇ ∇ max operator and similar extensions for future work.
We see now how the ∇ ∇ operators allow for representing fine-grained dependencies among the attributes that define 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 = ∇ ∇ t w (C 1 , . . . , C m ). That is, we focus on how K |= ∇ ∇ t w (C 1 , . . . , C m ) (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
(a) for φ i ∈ K}. In this case, the satisfaction of each φ i contributes independently of the other formulas in K. We say that the function
(a) for φ i ∈ K}. 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 defined by four attributes: E = ∇ ∇ t ((Large, w 1 ), (Heavy, w 2 ), (hasTrunk, w 3 ), (Grey, w 4 ))
This definition entails that each of the attributes in E contributes independently of the others to the classification of an object as an elephant.
Consider a knowledge base K = {Large(a), (a), that is, v K E is an additive wrt. the formulas in K.
By exploiting complex concept descriptions in the scope of ∇ ∇, we can enable positive and negative synergies among the attributes.
Example 3. Suppose now we redefine the concept elephant as follows, where we suppose that w 5 > w 1 + w 3 , w 6 > w 2 + w 3 , and w 7 > w 3 + w 4 and each W i is positive.
E =∇ ∇ t ((Large, w 1 ), (Heavy, w 2 ), (hasTrunk, w 3 ), (Grey, w 4 ), (Large hasTrunk, w 5 ), (Heavy hasTrunk, w 6 ), (Grey hasTrunk, w 7 ))
In this case, the relevance of the pieces of information in K = {Large (a). The meaning of this representation is that adding "having a trunk" significantly increases the importance of the combination of attributes for classifying an elephant. Accordingly the value of v K E 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 classification. 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 suffer. For instance, the concept of flu may be represented as follows:
FLU =∇ ∇((Fever Nausea, w 1 ), (Fever Spots, −w 2 ), (Nausea Spots, −w 3 ), (Fever, w 4 ), (Nausea, w 5 ))
In this case, the combination of fever and nausea is highly significant for the diagnosis, whereas adding the symptom 'spots' significantly decreases the reliability of the classification under FLU, because it is a strong indication of chickenpox. So, w 1 > w 4 + w 5 and w 2 and w 3 are both greater than w 1 + w 4 + w 5 . That is, the function v K FLU is sub-additive on K = {Fever(a), Nausea(a), Spots(a)}.
Complex concepts occurring as arguments of ∇ ∇ 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 [1] to the case of DLs.
We illustrate how the ∇ ∇ operators can represent the cognitive approach to concepts based on prototypes. In particular, we follow [13] where a "prototype is a prestored representation of the usual properties associated with the concept's instances" [13, p.487]. A prototype is represented in terms of a set of attributes (e.g., colour or weight) and a set of values for each attribute (e.g., red and blue for the colour-attribute). The relevance of an attribute for classifying an object-e.g., the relevance of colour for classifying apples-is represented by its diagnosticity (a numerical value), while the salience of an attribute-value represents its typicality (also a numerical value)-e.g., how frequent is for apple to have a red colour.
Let us define a prototype π C for a concept C as (where Q j i is the i-th value of the j-th attribute, s j i is the salience of Q j i wrt. C, d j is the diagnosticity of the j-th attribute wrt. C):
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 Q j i ∩ Q j k = ∅ for i = k. Assume now to know some attribute-values of a given object a. The classification 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 ∇ ∇ operator that directly considers the attribute-values, the saliences, and the diagnosticities in the prototype π C (where we assume Q
The classification 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 Q i j in C. Note that the object-prototype similarity is here simply rendered by summing up all the weights of the matching Q i j . The discussion of more sophisticated 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 define prototypes in this rich setting, we will use the ∇ ∇ max operator, or approximate it by carefully selecting the threshold.
This setting allows for defining a typicality operator, as in [10]. The most typical instances of a concept can be defined as those instances that maximise the sum of weights in w. Notice that the instances can be ordered in terms of typicality with respect to a concept C, by means of the values v I C (cf. [10]). Thus, in principle, we can enable comparisons between instances concerning their typicality wrt. a concept and introduce various degrees of typicality.
Finally, the ∇ ∇ =t operator may be used to define 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.
We introduced a class of operators for defining complex concepts that weigh the role of the defining 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 ∇ ∇-operators as well as studying succinctness effects is part of future work.
We further illustrated how the operators may be applied to render cognitively meaningful mechanisms for classification. 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 [14]. Another line of research will deepen the comparison with the formal studies on typicality (e.g. [10]), work on threshold concepts [15], relaxed query answering [16], and the relation and combination with similarity frameworks based on a notion of distance (e.g. [17][18][19]).