We describe two applications of re nement operators that can generalise and specialise concepts expressed in the ALC description logic language. The rst application addresses the problem of analysing the joint coherence of some given concepts w.r.t. a background ontology. To this end, we apply Thagard's computational theory of coherence, in combination with semantic similarity between concepts de ned by means of the generalisation operator. The second application focuses on repairing an inconsistent collective ontology that may result from the vote on axioms of multiple experts based on principles from social choice theory and judgment aggregation. We use the re nement operators, together with a reference ontology, to weaken some axioms and to repair the collective ontology.
Consistency checking, concept subsumption, or instance checking, are typical
reasoning problems in Description Logic (DL). They allow one to verify critical
properties of ontologies before publication. A published ontology will then form
one more brick of semantic knowledge on the web. Typical inference problems
thus help knowledge experts at developing good ontologies in the same way that
model checking is helping hardware engineers at making hardware without design
aws. But reasoning in DL may also have a more active role in the creation of
ontologies. Non-standard inference problems [
Whilst in the DL literature these problems are essentially approached as
reasoning tasks [
In this paper, we extend and amend the de nitions of our re nement
operator for ALC concepts as presented in [
The second application is related to the problem of obtaining useful information from possibly inconsistent opinions on the collaborative web. We consider possibly inconsistent collective ontologies that may result when multiple experts are asked to vote on a set of axioms in a domain of interest. We then use the re nement operators, together with a reference ontology, to weaken some axioms and to repair the collective ontology. 2
We take an ontology to be a set of formulas in an appropriate logical language, describing our domain of interest. Which logic we use precisely is not crucial for illustrating the proposed approach, but as much formal work on ontologies makes use of description logics (DLs), we will use these logics for all of our examples. A signi cant widely used basic description logic is ALC, which is the logic we shall be working with here.
We present the basics of ALC. For full details we refer to the literature [
C ::= A j :C j C u C j C t C j 8R:C j 9R:C : We collect all ALC concepts over NC and NR in L(ALC; NC ; NR).
A TBox is a nite set of concept inclusions of the form C v D (where C and D are concept descriptions). It is used to store terminological knowledge regarding the relationships between concepts. An ABox is a nite set of formulas of the form A(a) (\object a is an instance of concept A") and R(a; b) (\objects a and b stand to each other in the R-relation"). It is used to store assertional knowledge regarding speci c objects. The semantics of ALC is de ned in terms of interpretations I = ( I ; I ) that map each object name to an element of its domain I , each atomic concept to a subset of the domain, and each role name to a binary relation on the domain. An interpretation I is a model of a TBox T i it satis es all the axioms in T . Given a TBox T and two concept descriptions C and D, we say that C is subsumed by D w.r.t. T , denoted as C vT D, i CI DI for every model I of T . Given a TBox T and two concept descriptions C and D, we say that C is strictly subsumed by D w.r.t. T , denoted as C @T D, i C vT D and it is not the case that D vT C. Finally, we write C T D when C vT D and D vT C.
Re nement operators of ALC concepts
Re nement operators are a well-known notion in Inductive Logic Programming
where they are used to structure a search process for learning concepts from
examples. In this setting, two types of re nement operators exist:
specialisation re nement operators and generalisation re nement operators. While the
former constructs specialisations of hypotheses, the latter constructs
generalisations [
Given the quasi-ordered set hL(ALC; Nc; NR); vi, a generalisation re nement operator is de ned as follows:
T (C)
fC0 2 L(ALC; Nc; NR) j C vT C0g : Whereas a specialisation re nement operator is de ned as follows: T (C)
fC0 2 L(ALC; Nc; NR) j C0 vT Cg :
Generally speaking, a generalisation re nement 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. A specialisation operator, instead, returns a set of
descriptions that are more speci c. Whilst specialisation operators for ALC (and
other description logics) have been studied in the literature [
In order to de ne the re nement operators for ALC, we need some auxiliary de nitions. In the following, we assume that complex concepts C are rewritten into negation normal form, and thus negation only appears in front of atomic concepts. We will use = and 6= between ALC concepts to denote syntactic identity and di erence, respectively.
De nition 1. Let T be an ALC TBox with concept names from NC . The set of subconcepts of T is given by 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(?) = f?g sub(>) = f>g 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.1 Intuitively, the upward set of the concept C collects the most speci c subconcepts found in the Tbox T that are more general (subsume) C; conversely, the downward set of C collects the most general subconcepts from T that are subsumed by C. The concepts in sub(T ) are some concepts that are relevant in the context of TBox T , and that are used as building blocks for generalisations and specialisations. It is readily seen that given a nite TBox T the set sub(T ) is also nite. The properties of sub(T ) guarantee that the upward and downward cover sets are nite.
De nition 2. Let T be an ALC TBox over NC . The upward cover set of the concept C with respect to T is:
UpCovT (C) := fD 2 sub(T ) j C vT D
and there is no D0 2 sub(T ) with C @T D0 @T Dg : The downward cover set of the concept C with respect to T is:
DownCovT (C) := fD 2 sub(T ) j D vT C (1) (2) In the following, we note nnf the function that for every concept C, returns its negative normal form nnf(C). We can now de ne our generalisation re nement operator for ALC as follows.
De nition 3. Let T be an ALC TBox. We de ne T , the generalisation re nement operator w.r.t. T , inductively over the structure of concept descriptions as:
T (A) = UpCovT (A) T (>) = UpCovT (>)
T (?) = UpCovT (?)
T (:A) = fnnf(:C) j C 2 DownCovT (A)g [ UpCovT (:A) T (C u D) = fC0 u D j C0 2 T (C)g[fC u D0 j D0 2 T (D)g[UpCovT (C u D) T (C t D) = fC0 t D j C0 2 T (C)g [ fC t D0 j D0 2 T (D)g[UpCovT (C t D) T (8R:C) = f8R:C0 j C0 2 T (C)g [ UpCovT (8R:C)
T (9R:C) = f9R:C0 j C0 2 T (C)g [ UpCovT (9R:C) When there is no ambiguity, or to refer to an arbitrary TBox, we can omit the subscript T from the operator T .
Given a generalisation re nement operator , ALC concepts are related by re nement paths as described next.
De nition 4. For every concept C, we note i(C) the i-th iteration of its
generalisation. It is inductively de ned as follows:
1 Downward and upward cover sets were similarly de ned in [
De nition 5. The minimal number of generalisations to be applied in order to generalise C to D is called the distance between C and D, noted (C ! D). Formally, (C ! D) = minfj j j 0 and D 2 j (C)g.
( ! ) is a partial function that is de ned only when the concept passed as rst argument can eventually be re ned into the concept passed as second argument.
De nition 6. The set of all concepts that can be reached from C by means of in a nite number of steps is (C) = [ i(C) : Although generalisation niteness holds, it is not the case that (C) is nite for every concept C. Indeed, the iterated application of can produce an in nite chain of generalisations. The following example illustrates that.
Example 1. Let T := fA v 9r:Ag. At the rst iteration we have (A) = fA; 9r:Ag. Then we have (9r:A) = f9r:A; 9r:9r:Ag [ f>g. (Notice that > is reached: > 2 2(A).) Continuing the iteration of the generalisation of the concept description A, we have (9r:)kA 2 k(A) for every k 0.
This is not a feature that is caused by the existential quanti cation alone. Similar
examples exist that involve universal quanti cation, disjunction and conjunction.
To address this issue, one can make some assumptions over the structure of the
TBox, for instance, by restricting to no-cyclic TBoxes. Alternatively, we can
take into account the syntactic depth of concepts, by restricting the number of
nested quanti ers, conjunctions, and disjunctions in a concept description to a
xed constant k [
T ;k(C) := (
T (C) if depth(C)
k
We can de ne a specialisation operator in an analogous way.
De nition 8. Let T be an ALC TBox. We de ne T , the specialisation re nement operator w.r.t. T , inductively over the structure of concept descriptions as:
T (A) = DownCovT (A) T (>) = DownCovT (>)
T (?) = DownCovT (?)
T (:A) = fnnf(:C) j C 2 UpCovT (A)g [ DownCovT (:A) T (C u D) = fC0 u D j C0 2 T (C)g[fC u D0 j D0 2 T (D)g[DownCovT (C u D) T (C t D) = fC0 t D j C0 2 T (C)g [ fC t D0 j D0 2 T (D)g[DownCovT (C t D) T (8R:C) = f8R:C0 j C0 2 T (C)g [ DownCovT (8R:C)
T (9R:C) = f9R:C0 j C0 2 T (C)g [ DownCovT (9R:C) Naturally, properties analogous to the ones of Lemma 1 hold for the specialisation operator as well. Since can yield an in nite specialisation chain, its de nition can be extended by taking into account the depth of a concept description as done for the generalisation operator.
T ;k(C) := (
T (C) if depth(C)
k
When there is no ambiguity, or to refer to an arbitrary TBox, we can omit the subscript T from the operator T . Just as we did for the generalisation operator , we denote i (resp. ) to be the i-th iteration (resp. the unbounded nite iteration) of the specialisation operator . The distance between concepts ( ! ) w.r.t. the specialisation is also de ned as expected.
Given a body of knowlegde, Thagard [
Thagard provides a clear technical description of the coherence problem as a constraint satisfaction problem, but he does not clarify the nature of the coherence and incoherence relations that arise between pieces of information. In this section, we show how coherence and incoherence relations between concepts can be determined according to a similarity based on the generalisation operator . Secondly, we show how conceptual coherence, one of the types of coherence proposed by Thagard, can be used to decide the coherence between ALC concepts. 4.1
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 9. 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 ! >).
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 ! >). Thus, 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.
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 [
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 associate this `su ciently similar' condition with a value . The intuition behind the following de nition is that similar concepts whose common generalisation is far from > should cohere, and incohere otherwise.
De nition 11 (Coherence Relations). Given a set fC1; : : : ; Cng of ALC concepts, concept descriptions C; D 62 f>; ?g, we will say for each pair of concepts hCi; Cj i (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.
Based on the previous de nition we can determine the coherence graph as follows.
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 11, 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, but our Def. 11 can give rise also to graded versions of coherence and incoherence relations.
Then, given a coherence graph, one is interested in nding a partition that
maximises the number of satis ed constraints, where constraints are coherence
and incoherence relations. Roughly speaking, a constraint is satis ed if when
two concepts cohere, they fall in the same partition; and when two concepts
incohere, each of them falls in a di erent partition [
Analysing the joint coherence of ALC concepts Given an ALC TBox representing a background ontology, and a set of ALC concepts fC1; : : : ; Cng as input, we analyse their joint coherence as follows. First, we 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 justication of why certain concepts were partitioned together.
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. 5
For this application, we restrict our attention to TBox axioms. As usual, a TBox T is consistent if it has a model, and inconsistent otherwise. The relation j=O denotes the consequence relation w.r.t. an ontology O.
This section follows the presentation of [
Consider an arbitrary but xed nite set of ALC TBox statements over this alphabet. We call the agenda and any set O an ontology. We denote the set of all those ontologies that are consistent by On( ).
Let N = f1; : : : ; ng be a nite set of agents (or individuals ). Each agent i 2 N provides a consistent ontology Oi 2 On( ). An ontology pro le is a vector O = (O1; : : : ; On) 2 On( )N of consistent ontologies, one for each agent. We write N O := fi 2 N j 2 Oig for the set of agents that include in their ontology under pro le O. Our object of study are ontology aggregators.
F : On( )N ! 2 mapping any pro le of consistent ontologies to an ontology. Observe that, according to this de nition, the ontology we obtain as the outcome of an aggregation process needs not be consistent. With no surprise, this is the case of the majority rule, which is nonetheless widely applied in any political scenarios. In our setting, the majority rule is de ned as follows.
ontology aggregator Fm mapping any given pro le O 2 On( )N to the ontology Fm(O) := n 2 j #N O > n o 2 : In the remainder of this section we propose to repair inconsistent collective ontologies obtained from the aggregation of experts' individual ontologies. 5.2
Roughly speaking, weakening an axiom C v D amounts to enlarging the set of interpretations that satisfy the axiom. This could be done in di erent ways: Either by substituting C v D with C v D0, where D0 is a more general concept than D (i.e., its interpretation is larger); or, by modifying the axiom C v D to C0 v D, where C0 is a more speci c concept than C; or even by generalising and specialising simultaneously to obtain C0 v D0.
Given an ontology O, we denote the set of its concept names of O by NCO. We want to de ne a procedure to change axioms gradually by replacing them with less restrictive axioms. Recall that O denotes the generalisation of a concept and O denotes its specialisation with respect to a given ontology O. De nition 15 (Axiom weakening). Given an axiom C v D of O, the set of weakenings of C v D in O, denoted by gO(C v D) is the set of all axioms C0 v D0 such that
C0 =
O(C) and D0 =
O(D) : If the ontology O is consistent, the weakening of an axiom in O is always satis ed by a super set of the interpretations that satisfy the axiom. Let I = ( I ; I ) be an interpretation. Then by de nition the class of all entities that ful l the axiom C v D is ( I n CI ) [ DI . A weakening of C v D either specialises C, therefore restricting CI , and accordingly extending I n CI , or generalises D, therefore, extending DI . Hence, the set of entities for which C v D holds is a subset of the set of entities for which any axiom in gO(C v D) holds. The following result holds.
Lemma 2. For every axiom , if 2 gO( ), then j=O .
Moreover, note that ? v > always belongs to gO(C v D). We want to model how to repair any inconsistent set of axioms Y of ALC, by appealing to a consistent reference ontology R. Notice that, even though it is not desirable, R can be dissociated from the axioms in the collective ontology. If the ontology R does not refer to some of the atomic concepts in C or D, then their generalisation is the most general concept > and their specialisation is the most speci c concept ?.2
Any inconsistent set of axioms Y can in principle be repaired by means of a sequence of weakenings of the axioms in Y with respect to R.
Lemma 3. Let R be a consistent reference ontology and Y a minimally inconsistent set of axioms. There exists a subset f 1; : : : ; ng Y and weakenings i0 2 gR( i) for i; 1 i n such that (Y n f 1; : : : ; ng) [ f 10; : : : ; n0g [ R is consistent.
The lemma ensures that a minimally inconsistent set of axioms can be adequately weakened to be integrated consistently into another consistent ontology. In the worst case these axioms are weakened to become a tautology. However, we are interested in weakening axioms as little as possible to remain close to the original axioms. Notice that every axiom in gO(C v D) is obtained by applying and a nite number of times. Hence, we can de ne O to be a re nement distance in an ontology O, such that for every C0 v D0 2 gO(C v D),
O(C v D; C0 v D0) = (C !O C0) + (D !O D0) : Repair strategies can exploit this distance to guide the weakening of axioms that are the least stringent. Indeed, by minimising O, we are trying to nd the weakening of the axiom that is as close as possible to the original axiom in the context of O. Moreover, by trying to minimise the distance, we are trying to prevent non-informative axioms to be selected as weakenings. In other words, axioms like ? v >, ? v D, or C v > should only be selected if no other options are available. In principle, we can also provide re ned constraints on the generalisation and specialisation paths, e.g. by xing an ordering of the concepts of the ontology O that determines which concepts are to be generalised or specialised rst. 5.3
When F (O) is inconsistent, we can adopt the general strategy described in
Algorithm 1 to repair it w.r.t. a given ( xed) reference ontology R. The algorithm
nds all the minimally inconsistent subsets Y1; : : : ; Yn of F (O) (e.g., using the
methods from [
Future work includes a more systematic development of the introduced generalisation and specialisation operators employing a variety of semantics-driven de nitions. Furthermore, the duality between generalisaton and specialisation needs to be further studied.
On the tool side, we are currently working towards a full implementation of our re nement operators in order to evaluate their usefulness in larger scale real world examples.