We address the problem of analysing the joint coherence of a number of concepts with respect to a background ontology. To address this problem, we explore the applicability of Paul Thagard's computational theory of coherence, in combination with semantic similarity between concepts based on a generalisation operator. In particular, given the input concepts, our approach computes maximally coherent subsets of these concepts following Thagard's partitioning approach, whilst returning a number of possible generalisations of these concepts as justi cation of why these concepts cohere.
In this paper, we aim at showing how Thagard's computational theory of
coherence [
Building upon Thagard's intuitions and principles for modelling coherence,
we propose a formalisation of Thagard's notion of conceptual coherence for
concepts represented in the description logic ALC [
Given a set of input concepts, our approach computes maximally coherent subsets of these concepts following Thagard's computational model for coherence as a constraint satisfaction problem. We show how these maximising partitions not only suggest which of the input concepts can jointly cohere, but also how inconsistent concepts can be repaired using generalisations, letting them become consistent w.r.t. the background ontology.
To generalise these concepts, we propose a generalisation re nement
operator which is inductively de ned over the structure of ALC concept descriptions.
Generalising DL concepts have been addressed in the DL literature in the
context of the non-standard reasoning tasks of nding the least common subsumer
of di erent concepts [
Thagard addresses the problem of determining which pieces of information to
accept and which to reject based on how they cohere and incohere among them,
given that, when two elements cohere, they tend to be accepted together or
rejected together; and when two elements incohere, one tends to be accepted
while the other tends to be rejected [
This can be reformulated as a constraint satisfaction problem as follows. Pairs of elements that cohere between them form positive constraints, and pairs of elements that incohere between them form negative constraints. If we partition the set of pieces of information we are dealing with into a set of accepted elements and a set of rejected elements, then a positive constraint is satis ed if both elements of the constraint are either among the accepted elements or among the rejected ones; and a negative constraint is satis ed if one element of the constraint is among the accepted ones and the other is among the rejected ones. The coherence problem is to nd the partition that maximises the number of satis ed constraints.
Note that in general we may not be able to partition a set of elements as to satisfy all constraints, thus ending up accepting elements that incohere between them or rejecting an element that coheres with an accepted one. The objective is to minimise these undesired cases. The coherence problem is known to be NP-complete, though there exist algorithms that nd good enough solutions of the coherence problem while remaining fairly e cient.
Depending on the kind of pieces of information we start from, and on the way the coherence and incoherence between these pieces of information is determined, we will be dealing with di erent kinds of coherence problems. So, in explanatory coherence we seek to determine the acceptance or rejection of hypotheses based on how they cohere and incohere with given evidence or with competing hypotheses; in deductive coherence we seek to determine the acceptance of rejection of beliefs based on how they cohere and incohere due to deductive entailment or contradiction; in analogical coherence we seek to determine the acceptance or rejection of mapping hypotheses based on how they cohere or incohere in terms of structure; and in conceptual coherence we seek to determine the acceptance or rejection of concepts based on how they cohere or incohere as the result of the positive or negative associations that can be established between them. Thagard discusses these and other kinds of coherence.
Although Thagard provides a clear technical description of the coherence
problem as a constraint satisfaction problem, and enumerates concrete principles
that characterise di erent kinds of coherences, he does not clarify the actual
nature of the coherence and incoherence relations that arise between pieces of
information, nor does he suggest a precise formalisation of the principles he
discusses. In [
In this section we give precise de nitions of the concepts intuitively introduced in the previous section.
De nition 1. A coherence graph is an edge-weighted, undirected graph of the form G = hV; E; wi, where: 1. V is a nite set of nodes representing pieces of information. 2. E V (2) (where V (2) = ffu; vg j u; v 2 V g) is a nite set of edges representing the coherence or incoherence between pieces of information. Edges of coherence graphs are also called constraints. 3. w : E ! [ 1; 1] n f0g is an edge-weighted function that assigns a value to the coherence between pieces of information.
When we partition the set V of vertices of a coherence graph (i.e., the set of pieces of information) into the sets A and R = V n A of accepted and rejected elements respectively, then we can say when a constraint|an edge between vertices|is satis ed or not by the partition.
De nition 2. Given a coherence graph G = hV; E; wi, and a partition (A; R) of V , the set of satis ed constraints C(A;R) E is given by:
C(A;R) = nfu; vg 2 E u 2 A i v 2 A; whenever w(fu; vg) > 0 o u 2 A i v 2 R; whenever w(fu; vg) < 0 All other constraints (i.e., those in E n C(A;R)) are said to be unsatis ed. The coherence problem is to nd the partition of vertices that satis es as many constraints as possible, i.e., to nd the partition that maximises the coherence value as de ned as follows, which makes coherence to be independent of the size of the coherence graph.
De nition 3. Given a coherence graph G = hV; E; wi, the coherence of a partition (A; R) of V is given by: X
jw(fu; vg)j (G; (A; R)) = fu;vg2C(A;R) jEj Notice that there may not exist a unique partition with a maximum coherence value. In fact, at least two partitions have the same coherence value, since (G; (A; R)) = (G; (R; A)) for any partition (A; R) of V . 3.2
Generalising ALC Descriptions
To generalise ALC concept descriptions, we propose a generalisation re nement
operator that extends our previous work in [
Roughly speaking, a generalisation operator takes a concept C as input and returns a set of descriptions that are more general than C by taking a Tbox T into account. In order to de ne a generalisation re nement operator for ALC, we need some auxiliary de nitions. In the following, we assume the TBox and set of concepts NC to be nite.3 De nition 4. Let T be a ALC TBox with concept names NC . The set of nontrivial subconcepts of T is given as sub(T ) = f>; ?g [
sub(C) [ sub(D) [
CvD2T where sub is de ned over the structure of concept descriptions as follows: sub(A) = fAg sub(?) = ; sub(>) = ; sub(:A) = f:A; Ag sub(C u D) = fC u Dg [ sub(C) [ sub(D) sub(C t D) = fC t Dg [ sub(C) [ sub(D) sub(8R:C) = f8R:Cg [ sub(C) sub(9R:C) = f9R:Cg [ sub(C) Based on sub(T ), we de ne the upward and downward cover sets of atomic concepts. In the following, we will assume that complex concepts C are rewritten into negation normal form, and that thus negation only appears in front of atomic concepts. For the following de nition, sub(T ) (De nition 4) guarantees the upward and downward cover sets to be nite. Intuitively, the upward set of A collects the most speci c subconcepts found in the Tbox T that are more general (subsume) A; conversely, the downward set of A collects the most general subconcepts from T that are subsumed by A. The downcover is only needed for the base case of generalising a negated atom. 3 To avoid any confusion, we point out that we use = and 6= between ALC concepts to denote syntactic identity and di erence, respectively.
De nition 5. Let T be an ALC TBox with concept names from NC . The upward cover set of an atomic concept A 2 NC [ f>; ?g with respect to T is given as:
UpCov(A) := fC 2 sub(T ) j A vT C and there is no C0 2 sub(T ) The downward cover set of an atomic concept A 2 NC [ f>; ?g with respect to T is given as:
DownCov(A) := fB 2 NC [ f>; ?g j B vT A and there is no B0 2 NC [ f>; ?g such that B @T B0 @T Ag (:A) = (A) = UpCov(A)
(f:B j B 2 DownCov(A)g (>) = f>g (?) = UpCov(?)
( We can now de ne our generalisation re nement operator for ALC as follows. De nition 6. Let T be an ALC TBox. We de ne the generalisation re nement operator inductively over the structure of concept descriptions as: if DownCov(A) 6= f?g otherwise.
fC0uDjC0 2 (C)g[fCuD0jD0 2 (D)g[fC; Dg (
fC0 t D j C0 2 (C)g [ fC t D0 j D0 2 (D)g (f8R:C0 j C0 2 (C)g (f9R:C0 j C0 2 (C)g if C 6= > otherwise. if C 6= > otherwise. (C u D) = (C t D) = (8R:C) = (9R:C) = f>g f>g f>g f>g f>g Lemma 1. is a nite operator; i.e., for any given complex ALC concept C, the set (C) is nite.
Given a generalisation re nement operator , ALC concepts are related by renement paths as described next.
De nition 7. A nite sequence C1; : : : ; Cn of ALC concepts is a generalisation path C1 ! Cn from C1 to Cn of the generalisation re nement operator i Ci+1 2 (Ci) for all i : 1 i < n. Then: (1) (2) if C or D 6= > otherwise. if C and D 6= > otherwise. { (C) denotes the set of all concepts that can be reached from C by means of in zero or a nite number of steps. { (C ! D) denotes the minimal number of generalisations to be applied in order to generalise C to D when D 2 ?(C).
The repeated application of the generalisation re nement operator allows us to nd descriptions that represent the properties that two or more ALC concepts have in common. This description is a common generalisation of ALC concepts.
For the sake of this paper, we are interested in common generalisations that have minimal distance from the concepts, or in case their distance is equal, the ones that are far from >.
De nition 8. An ALC concept description G is a common generalisation of C1 and C2 if G 2 (C1) \ (C2) and, furthermore, G is such that for any other G0 2 (C1) \ (C2) with (G0 6= G) we have: { (C1 ! G) + (C2 ! G) < (C1 ! G0) + (C2 ! G0), or { (C1 ! G) + (C2 ! G) = (C1 ! G0) + (C2 ! G0) and (G ! >)
(G0 ! >) At this point we should notice that common generalisations, as per the above de nition, are not unique. However, for any two common generalisations G and G0 of C1 and C2, (C1 ! G) + (C2 ! G) = (C1 ! G0) + (C2 ! G0) and (G ! >) = (G0 ! >). Any one of them will result in the same value for our generalisation-based similarity measure between concepts, and therefore in the same coherence or incoherence judgements. In the following, we denote C1NC2 a common generalisation of C1 and C2; C1NC2 is a concept that always exists. 3.3
The common generalisation of two concepts C and D can be used to measure the similarity between concepts in a quantitative way. To estimate the quantity of information of any description C we take into account the length of the minimal generalisation path that leads from C to the most general term >.
In order to de ne a similarity measure, we need to compare what is common
to C and D with what is not common. The length (CND ! >) estimates the
informational content that is common to C and D, and the lengths (C ! CND)
and (D ! CND) measures how much C and D are di erent. Then, the common
generalisation-based similarity measure can be de ned as follows [
The measure S estimates the ratio between the amount of information that is shared and the total information content. The range of the similarity function is the interval [0; 1], where 0 represents the minimal similarity between concepts (when their common generalisation is equal to >), and 1 represents maximal similarity (when the concepts are equivalent). 4
Thagard characterises conceptual coherence with these principles [
Association: A concept coheres with another concept if they are positively associated, i.e., if there are objects to which they both apply.
Given Concepts: The applicability of a concept to an object may be given perceptually or by some other reliable source.
Negative Association: A concept incoheres with another concept if they are negatively associated, i.e., if an object falling under one concept tends not to fall under the other concept.
Acceptance: The applicability of a concept to an object depends on the applicability of other concepts.
To provide a formal account of these principles we shall formalise Association and Negative Association between concepts expressed in a description logic, since these are the principles de ning coherence and incoherence. We shall assume coherence between two concept descriptions when they are su ciently similar so that \there are objects to which both apply;" and we shall assume incoherence when they are not su ciently similar so that \an object falling under one concept tends not to fall under the other concept."
In this formalisation of conceptual coherence, we determine this `su ciently similar' condition by taking into account the minimal length of the generalisation path from the common generalisation of two concepts to >. The intuition behind the following de nition is that similar concepts whose common generalisation is far from > should cohere, and incohere otherwise.
De nition 10 (Coherence Relations). Given a set fC1; : : : ; Cng of ALC concepts, we will say for each pair of concepts hCi; Cji (1 i; j n; i 6= j): { Ci coheres with Cj, if S (Ci; Cj) > 1 { Ci incoheres with Cj, if S (Ci; Cj) 1 where =
(CiNCj ! >) maxf (Ci ! >); (Cj ! >)g In this de nition, (CiNCj ! >) is normalised to the interval [0; 1] in order to make it comparable with the similarity measure. This is done by considering the range of values that (CiNCj ! >) can assume. Since the maximal value corresponds to the case in which the common generalisation of Ci and Cj is >, and the minimal value is 0, this interval is [0; maxf (Ci ! >); (Cj ! >)g].
Returning to the Thargardian principles, Symmetry follows from the de nition above, and Acceptance is captured by the aim of maximising coherence in a coherence graph.
the set of ALC concepts fC1; : : : ; Cng is the edge-weighted and undirected graph G = hV; E; wi whose vertices are C1; : : : ; Cn, whose edges link concepts that either cohere or incohere according to De nition 10, and whose edge-weight function w is given as follows: w(fC; Dg) = ( 1 if C and D cohere
1 if C and D incohere This de nition creates a concept graph in the sense of Thagard where only binary values `coheres' or `incoheres' are recorded, represented by `+1' and `-1', respectively. However, it should be noted that Def. 10 can give rise also to graded versions of coherence graphs, which we will explore in future work. 5
This section describes how we use coherence to analyse the joint coherence of a number of concepts with respect to a background ontology.
The overall idea is to compute the coherence graph and the maximising partitions for the input concepts, and use them to decide which concepts to keep and which ones to discard. The pairwise comparison and the maximising coherence degree partitions will give us the biggest subsets of coherent input concepts. Then, we compute the nearest common generalisations of the accepted concepts, to convey a justi cation of why certain concepts were partitioned together.
Given an ALC TBox representing a background ontology, and a set of ALC concepts fC1; : : : ; Cng as input, the process of evaluating the coherence of concepts can be described as follows: 1. We form the coherence graph for the input concepts C1; : : : ; Cn according to De nition 11. 2. We compute the coherence maximising partitions according to De nition 3. 3. We use the partitions to decide which concepts to accept. 4. For each maximising partition of accepted concepts, we compute the nearest common generalisations, and present them as justi cations of why these concepts were accepted.
Once the maximising partitions are computed, the coherence of the input concepts could be measured in terms of the coherence value of the coherencemaximising partitions. The degree of the coherence graph directly measures how much input concepts coheres with respect of the background ontology.
Black v GrayScale , GrayScale v Colours , Integers v Numbers , Animals v Physical Objects , Qualities u Abstract Objects v ? , Colours v Qualities , Domain(hasColour) = Physical Object , Domain(hasQuality) = >
Pets v Animals Black u White v ? Numbers v Abstract Objects Physical Objects u Abstract Objects v ? Primeness v Qualities Range(hasColour) = Colours Range(hasQuality) = Qualities
It is worth noticing that according to our de nition of coherence relation, inconsistent concepts can cohere provided that they are su ciently similar and their common generalisation is far from the > concept.
Example. Let us consider the ALC theory in the TBox in Figure 1 and the following three input concepts:
Black Cats White Cats Prime Numbers
Cats u 8hasColour:Black u 9hasColour:Black Cats u 8hasColour:White u 9hasColour:White
Integers u 9hasQuality:Primeness Black Cats and White Cats de ne black cats and white cats as cats that are coloured black and white respectively, whereas the Prime Numbers de nes the concept of prime numbers. We want to know whether these concepts cohere together or not.
Intuitively, Black Cats and White Cats, although inconsistent according to the background ontology, should cohere, since they \talk" about the same objects, i.e., cats. The Prime Numbers concept, instead, should incohere with Black Cats and White Cats, since the objects it applies to are essentially di erent.
The coherence graph for these three concepts is computed as follows and it is shown in Figure 2: The maximising partitions of coherence graph are A = fBlack Cats; White Catsg and R = fPrime Numbersg, and all constraints are satis ed (so (G; (A; R)) = 1). These concepts can still cohere, since they can be generalised in di erent ways.
For instance, by generalising Black and White to GrayScale, we can obtain the concept Cats u 8hasColour:GrayScale u 9hasColour:GrayScale that represents the category of gray-coloured cats. Or, by generalising Black and White to Colours, we can obtain the concept Cats u 8hasColour:Colour u 9hasColour:Colour that represents the category of coloured cats.
These generalisations, which can be obtained by applying our re nement operator , are to be considered explanations of why these concepts can cohere together. Therefore, our approach can improve the given `coherence claim' by presenting the best generalisations that let the concepts be consistent.
As far as complexity is concerned, since subsumption reasoning in ALC is exponential, our proposed methodology stays in the same complexity class of coherence theory as a constraint satisfaction problem, namely, NP. 6
This paper is a preliminary work, and the obvious next step would be to test it extensively on a number of real use cases, to verify the degree up to which our approach agrees with human intuitions.
There exist many possible variants of our de nitions of S (C; D) and , and
there is a very rich literature about similarity measures between concepts in
ontologies [
For instance, one possible criticism of our approach (as well as of any \edgebased" similarity measure) is that the path length between two concepts depends on the granularity of our upward cover set: in particular, it is possible that it contains a high number of elements along the shortest path from C to CND (and, consequently, for the similarity between C and D to be low, and for them to possibly be incoherent) merely because our TBox (and, therefore, our cover set) contains many more assertions about generalisations of C than about generalisations of CND.
It is not clear the degree up to which this is a problem in practice: for instance, it might be possible to reply that this is working as intended, since if our TBox contains many claims about concepts between C and CND then the di erences between these concepts are indeed particularly relevant in our context, and hence it is appropriate for C and D to be comparatively less coherent.
In any case, if necessary, there exist ways around this: for instance, given
an ABox of facts about various entities, we might employ semantic similarity
measures such as Resnik's [
We leave such issues, as well as the more general question of the evaluation of joint coherence analysis approaches, to further work. Here we contented ourselves with establishing a rst such approach, which may then be tweaked according to its performance and to its user's needs. 7
In this work, we introduced a novel approach to the problem of analysing the joint coherence of a number of concepts with respect to a background ontology. This paper should be seen as an attempt to (a) provide a formal account of conceptual coherence for a particular concept representation language, and (b) to explore its applicability for analysing the joint coherence of a number of concepts with respect to a background ontology.
With respect to (a), a previous attempt to formalise conceptual coherence
in the AL description logic is [
With respect to (b), we have only focused on how maximally coherent sets
suggest why inconsistent concepts can cohere together, and the way in which
these concepts can be generalised to steer inconsistency debugging. In the future,
we will investigate the relation of our approach to ontology debugging [