Fuzzy Description Logics (DLs) are logics that allow to deal with vague structured knowledge. Although a relatively important amount of work has been carried out in the last years concerning the use of fuzzy DLs as ontology languages, the problem of automatically managing fuzzy ontologies has received very little attention so far. We report here our preliminary investigation on this issue by describing a method for inducing inclusion axioms in a fuzzy DL-Lite like DL.
Description Logics (DLs) [1] play a key role in the design of ontologies. An ontology consists of a hierarchical description of important concepts in a particular domain, along with the description of the properties (of the instances) of each concept. In this context, DLs are important as they are essentially the theoretical counterpart of the Web Ontology Language OWL 2 3, the current standard language to represent ontologies, and its pro les. 4 E.g., DL-Lite [2] is the DL behind the OWL 2 QL pro le and is especially aimed at applications that use very large volumes of instance data, and where query answering is the most important reasoning task.
On the other hand, it is well-known that \classical" ontology languages are not appropriate to deal with vague knowledge, which is inherent to several real world domains [21]. So far, several fuzzy extensions of DLs can be found in the literature (see the survey in [14]), which includes, among others a fuzzy DL-Lite like DL [23] which has been implemented in the SoftFacts system [23] 5.
Although a relatively important amount of work has been carried out in the last years concerning the use of fuzzy DLs as ontology languages, the problem of automatically managing fuzzy ontologies has received very little attention so far. In this work, we report our preliminary investigation on this issue by describing
Lukasiewicz logic b max(a + b 1; 0) b min(a + b; 1) a ) b min(1 a + b; 1)
Godel logic min(a; b) max(a; b) (1 if a 6 b b otherwise
Product logic
a b a + b a b min(1; b=a) a 1 a (1 if a = 0
(1 if a = 0 0 otherwise
0 otherwise a method for inducing inclusion axioms in a fuzzy DL-Lite like DL. The method follows the machine learning approach known as Inductive Logic Programming (ILP) by adapting known results in ILP concerning crisp rules to the novel case of fuzzy DL inclusion axioms.
The paper is structured as follows. Section 2 is devoted to preliminaries on Mathematical Fuzzy Logic, Fuzzy DLs and ILP. Section 3 describes our preliminary contribution to the problem in hand, also by means of an illustrative example. Section 4 concludes the paper with nal remarks and comparison with related work. In Mathematical Fuzzy Logic [7], the convention prescribing that a statement is either true or false is changed and is a matter of degree measured on an ordered scale that is no longer f0; 1g, but the [0; 1]. This degree is called degree of truth (or score) of the logical statement in the interpretation I. In this section, fuzzy statements have the form [r], where r 2 [0; 1] (see, e.g. [6,7]) and is a statement, which encode that the degree of truth of is greater or equal r.
A fuzzy interpretation I maps each basic statement pi into [0; 1] and is then extended inductively to all statements: I( ^ ) = I( ) I( ), I( _ ) = I( ) I( ), I( ! ) = I( ) ) I( ), I(: ) = I( ), I(9x: (x)) = supa2 I I( (a)), I(8x: (x)) = infa2 I I( (a)), where I is the domain of I, and , , ), and are so-called t-norms, t-conorms, implication functions, and negation functions, respectively, which extend the Boolean conjunction, disjunction, implication, and negation, respectively, to the fuzzy case.
One usually distinguishes three di erent logics, namely Lukasiewicz, Godel, and Product logics [7], whose combination functions are reported in Table 1. The operators for Zadeh logic, namely a b = min(a; b), a b = max(a; b), a = 1 a and a ) b = max(1 a; b), can be expressed in Lukasiewicz logic6. 6 More precisely, min(a; b) = a L (a )L b); max(a; b) = 1 min(1
A fuzzy set R over a countable crisp set X is a function R : X ! [0; 1]. The trapezoidal (Fig. 1 (a)), the triangular (Fig. 1 (b)), the L-function (left-shoulder function, Fig. 1 (c)), and the R-function (right-shoulder function, Fig. 1 (d)) are frequently used to specify membership degrees. In particular, the left-shoulder function is de ned as ls(x; a; b) = 81 > <
0 >:(b if x 6 a if x > b x)=(b a) if x 2 [a; b]
The notions of satis ability and logical consequence are de ned in the standard way. A fuzzy interpretation I satis es a fuzzy statement [r] or I is a model of [r], denoted I j= [r] i I( ) > r. 2.2
DL-Lite like description logic and its fuzzy extensions For computational reasons, the logic we adopt is based on a fuzzy extension of the DL-Lite DL without negation [23]. It supports at the intensional level unary relations (called concepts) and binary relations (called roles), while supports n-ary relations (relational tables) at the extensional level.
Formally, a knowledge base K = hF ; O; Ai consists of a facts component F , an ontology component O and an abstraction component A, which are de ned as follows (for a detailed account of the semantics, see [22]). Information can be retrieved from the knowledge base by means of an appropriate query language discussed later.
Facts Component. The facts component F is a nite set of expressions of the form
R(c1; : : : ; cn)[s] ;
where R is an n-ary relation, every ci is a constant, and s is a degree of truth
(or score) in [0; 1] indicating to which extent the tuple hc1; : : : ; cni is an instance
of relation R.7 Facts are stored in a relational database. We may omit the score
component and in such case the value 1 is assumed.
7 The score s may have been computed by some external tool, such as a classi er, etc.
(
Rl1 u : : : u Rlm v Rr ; where m > 1, all Rli and Rr have the same arity and each Rli is a so-called left-hand relation and Rr is a right-hand relation8. We assume that relations occurring in F do not occur in inclusion axioms (so, we do not allow that database relation names occur in O). Also we recall that from a semantics point of view, Godel logic is adopted. The intuition for one such semantics is that if a tuple c is instance of each relation Rli to degree si then c is instance of Rr to degree min(s1; : : : ; sm).
The exact syntax of the relations appearing on the left-hand and right-hand side of inclusion axioms is speci ed below:
Rl Rr ! A j R[i1; i2] ! A j R[i1; i2] j 9R:A where A is an atomic concept and R is a role with 1 6 i1; i2 6 2. Here R[i1; i2] is the projection of the relation R on the columns i1; i2 (the order of the indexes matters). Hence, R[i1; i2] has arity 2. Additionally, 9R:A is a so-called qualied existential quanti cation on roles which corresponds to the FOL formula 9y:R(x; y) ^ A(y) where ^ is interpreted as the t-norm in the Godel logic (see Table 1).
R 7! (c1; : : : ; cn)[cscore]:sql ;
(
We omit to write 9y when y is clear from the context; 4. zi; z0j are tuples of constants or variables in x or y; 5. s; s1; : : : ; sl are distinct variables and di erent from those in x and y; 6. pj is an nj -ary fuzzy predicate assigning to each nj -ary tuple cj a score pj (cj ) 2 [0; 1]. We require that an n-ary fuzzy predicate p is safe, that is, there is not an m-ary fuzzy predicate p0 such that m < n and p = p0.
Informally, all parameters are needed in the de nition of p. 7. f is a scoring function f : ([0; 1])l+h ! [0; 1], which combines the scores of the l relations Ri(c0i) and the n fuzzy predicates pj (c0j0) into an overall score s to be assigned to q(c). We assume that f is monotone, that is, for each v; v0 2 ([0; 1])l+h such that v 6 v0, it holds f (v) 6 f (v0), where (v1; : : : ; vl+h) 6 (v10; : : : ; vl0+h) i vi 6 vi0 for all i. We also assume that the computational cost of f and all fuzzy predicates pi is bounded by a constant; 8. Limit(k) indicates the number of answers to retrieve and is optional. If omitted, all answers are retrieved.
We call q(x)[s] its head, 9y:R1(z1)[s1]; : : : ; Rl(zl)[sl] its body and OrderBy(s = f (s1; : : : ; sl; p1(z01); : : : ; ph(z0h)) the scoring atom. We also allow the scores [s]; [s1], . . . , [sl] and the scoring atom to be omitted. In this case we assume the value 1 for si and s instead. The informal meaning of such a query is: if zi is an instance of Ri to degree at least or equal to si, then x is an instance of q to degree at least or equal to s, where s has been determined by the scoring atom.
The answer set ansK(q) over K of a query q is the set of tuples ht; si such that K j= q(t)[s] with s > 0 (informally, t satis es the query to non-zero degree s) and the score s is as high as possible, i.e. if ht; si 2 ansK(q) then (i) K 6j= q(t)[s0] for any s0 > s; and (ii) there cannot be another ht; s0i 2 ansK(q) with s > s0. 2.3
Inductive Logic Programming (ILP) was born at the intersection between Concept Learning and Logic Programming [16].
From Logic Programming it has borrowed the Knowledge Representation (KR) framework, i.e. the possibility of expressing facts and rules in the form of Horn clauses. In the following, rules are denoted by
B(x) ! H(x)
(
From Concept Learning it has inherited the inferential mechanisms for induction, the most prominent of which is generalisation. A distinguishing feature of ILP with respect to other forms of Concept Learning is the use of prior domain knowledge in the background during the induction process. The classical ILP problem is described by means of two logic programs: (i) the background theory K which is a set of ground facts and rules; (ii) the training set E which is a set of ground facts, called examples, pertaining to the predicate to be learnt. It is often split in E + and E , which correspond respectively to positive and negative examples. If only E + is given, E can be deduced by using the Closed World Assumption (CWA). A rule r covers an example e 2 E i K [ frg j= e. The task of induction is to nd, given K and E , a set H of rules such that: (i) 8e 2 E +; K [ H j= e (completeness of H) and (ii) 8e 2 E ; K [ H 6j= e (consistency of H). Two further restrictions hold naturally. One is that K 6j= E + since, in such a case, H would not be necessary to explain E +. The other is K [ H 6j= ?, which means that K [ H is a consistent theory. Usually, rule induction ts with the idea of providing a compression of the information contained in E .
A popular ILP algorithm for learning sets of rules is FOIL [18]. It performs a greedy search in order to maximise a gain function. The rules are induced until all examples are covered or no more rules are found that overcome the threshold. When a rule is induced, the positive examples covered by the rule are removed from E . This is the sequential covering approach underlying the function FOIL-Learn-Sets-of-Rules shown in Figure 2. For inducing a rule, the function FOIL-Learn-One-Rule reported in Figure 3 starts with the most general clause (> ! H(x)) and specialises it step by step by adding literals to the antecedent. The rule r is accepted when its con dence degree cf (r) (see later on) overcomes a xed threshold and it does not cover any negative example.
The Gain function is computed by the formula:
Gain(r0; r) = p (log2(cf (r0))
log2(cf (r))) ;
(
; + = ; do
2. while E 6
3. r FOIL-Learn-One-Rule(H, E+, E , K);
465... EEHr++ HfEe+[2nfrEEgr++; j;K [ r j= eg;
7. endwhile
8. return H
end
Given a Horn clause B(x) ! H(x), the con dence degree is given by:
cf (B(x) ! H(x)) = P (B(x) ^ H(x))=P (B(x)) :
(
IILP j= f i
K [ E j= f : The domain D is the Herbrand domain described by K and E . We take P as a uniform probability on D. So the con dence degree in a clause B(x) ! H(x) is: cf (B(x) ! H(x)) = jt 2 Dn j IILP j= B(t) and H(t) 2 E +j
jt 2 Dn j IILP j= B(t) and H(t) 2 E j
where j j denotes set cardinality. Testing all possible t 2 Dn is not tractable
in practice. However, we can equivalently restrict the computation to the
substitutions that map variables to constants in their speci c domains. In fact,
this computation is equivalent to a database query and thus, we can also use
some optimization strategy such as indexing or query ordering. This makes the
computation tractable although it remains costly.
(
Towards Learning Fuzzy DL-Lite like Inclusion Axioms
In this section we consider a learning problem where:
{ the target concept H is a DL-Lite atomic concept;
{ the background theory K is a DL-Lite like knowledge base hF ; O; Ai of the
form described in Section 2.2;
{ the training set E is a collection of fuzzy DL-Lite like facts of the form (
B v H where H is an atomic concept, B = C1 u : : : u Cm, and each concept Ci has syntax
C
! A j 9R:A j 9R:> :
(
Note that the language of hypotheses LH di ers from the language of the background theory LK as for the form of axioms. Yet the alphabet underlying LH is a subset of the alphabet for LK. Note also that H, in order to be acceptable, must be complete and consistent w.r.t. E, i.e. it must cover all the positive examples and none of the negative examples. 3.1
We now show how we may learn inclusion axioms of the form (
IILP j= C(t) i K [ E j= C(t)[s] and s > 0 : (14) That is, we write IILP j= C(t) i it can be inferred from K and E that t is an instance of concept C to a non-zero degree. Note that E is split into E+ and E . In order to distinguish between the two sets while using a uniform representation with K, we introduce two additional concepts, H+ and H , whose intension coincide with the sets E + and E , respectively, as well as the axioms H+ v H and H v H. We call K0 the background theory augmented with the training set represented this way, i.e. K0 = K [ E .
Now, in order to account for multiple fuzzy instantiations of fuzzy predicates
occurring in the inclusion axioms of interest to us, we customise (
Pt2P B(t) ) H(t) jDj (15) where { P = ft j IILP j= Ci(t) and H(t)[s] 2 E +g, i.e. P is the set of instances for which the implication covers a positive example; { D = ft j IILP j= Ci(t) and H(t)[s] 2 E g, i.e. D is the set of instances for which the implication covers an example (either positive or negative); { B(t) ) H(t) denotes the degree to which the implication holds for a certain instance t; { B(t) = min(s1; : : : ; sn), with K [ E j= Ci(t)[si]; { H(t) = s with H(t)[s] 2 E .
Clearly, the more positive instances supporting the inclusion axiom, the higher the con dence degree of the axiom.
Note that the con dence score can be determined easily by submitting appropriate queries via the query language described in Section 2.2. More precisely, proving the fuzzy entailment in (14) for each Ci is equivalent to answering a unique ranking query whose body is the conjunction of the relations Rl resulting from the transformation of Ci's into FOL predicates and whose score s is given by the minimum between sl's.
From an algorithm point of view, it su ces to change FOIL-Learn-One-Rule at step 7., where now l may be of any of the forms allowed in (13). More precisely, in line with the tradition in ILP and in conformance with the search direction in FOIL, we devise a specialization operator, i.e. an operator for traversing the hypotheses space top down, with the following re nement rules: 1. Add atomic concept (A) 2. Add complex concept by existential role restriction (9R:>) 3. Add complex concept by quali ed existential role restriction (9R:A) 4. Replace atomic concept (A replaced by A0 if A0 v A) 5. Replace complex concept (9R:A replaced by 9R:A0 if A0 v A) The rules are numbered according to an order of precedence, e.g. the addition of an atomic concept has priority over the addition of a complex concept obtained by existential role restriction. A rule can be applied when the preceding one in the list can not be applied anymore. Concept and role names in the alphabet underlying LH are themselves ordered. This implies that, e.g., the addition of an atomic concept is not possible anymore when all the atomic concepts in the alphabet have been already used in preceding applications of the rule. For illustrative purposes we consider the following case involving the classi cation of hotels as good ones. We assume to have a background theory K with a relational database F (reported in Figure 4), an ontology O 9 (illustrated in Figure 5) which encompasses the following inclusion axioms
and the following set A of abstraction statements:
FROM HotelTable h hasRank 7! (h:id; h:rank): SELECT h.id, h.rank
FROM HotelTable h cheapP rice 7! (h:id; r:price)[score]: SELECT h.id, r.price, cheap(r.price) AS score FROM HotelTable h, RoomTable r WHERE h.id = r.hotel
ORDER BY score closeT o 7! (f rom; to)[score]: SELECT d.from, d.to closedistance(d.time) AS score FROM DistanceTable d
ORDER BY score where cheap(p) is a function determining how cheap a hotel room is given its price, modelled as e.g. a so-called left-shoulder function cheap(p) = ls(p; 50; 100), while closedistance(d) = ls(d; 5; 25).
Assume now that: { H = GoodHotel; { E + = fGoodHotel(h1)[0:6]; GoodHotel(h2)[0:8]g; { E = fGoodHotel(h3)[0:4]g.
In order to have a uniform representation of the examples w.r.t. the background theory, we transform E as follows: GoodHotel+ v GoodHotel
GoodHotel+(h1)[0:6] GoodHotel+(h2)[0:8] GoodHotel (h3)[0:4] 9 http://donghee.info/research/SHSS/ObjectiveConceptsOntology(OCO).html r0 : > v GoodHotel r1 : Hotel v GoodHotel r2 : Hotel u 9cheapP rice:> v GoodHotel r3 : Hotel u 9cheapP rice:> u 9closeT o:Attraction v GoodHotel r4 : Hotel u 9cheapP rice:> u 9closeT o:P ark v GoodHotel r5 : Hotel u 9cheapP rice:> u 9closeT o:T ower v GoodHotel belong to LH = frjCi 2 f>; Hotel; 9cheapP rice; 9closeT ogg be read as: LK. They can r0 : Everything is a good hotel r1 : Every hotel is a good hotel r2 : Hotels having a cheap price are good hotels r3 : Hotels having a cheap price and close to an attraction are good hotels r4 : Hotels having a cheap price and close to a park are good hotels r5 : Hotels having a cheap price and close to a tower are good hotels thus highlighting the possibility of generating \extreme" hypotheses about good hotels such as r0 and r1. Of course, some of them will be discarded on the basis of their con dence degree.
Before showing how hypotheses evaluation is performed in our adaptation of FOIL, we illustrate the computation of the con dence degree for r3. It can be veri ed that for K0 1. The query qP (h)[s]
GoodHotel+(h); cheapP rice(h; p)[s1]; closeT o(h; a)[s2]; Attraction(a); s = min(s1; s2) has answer set ansK0 (qP ) = fhh1; 0:75i; hh2; 0:4ig over K0; 2. The query qD(h)[s] has answer set ansK0 (qD) = fhh1; 0:75i; hh2; 0:4i; hh3; 0:6ig over K0; 3. Therefore, according to (15), P = fh1; h2g, while D = fh1; h2; h3g; 4. As a consequence, cf (r3) = = Note that in qP the literals Hotel(h) and GoodHotel(h) are removed from the body in favour of GoodHotel+(h) because the concepts Hotel and GoodHotel subsume GoodHotel (due to a derived axiom) and GoodHotel+ (due to an asserted axiom) respectively. Analogously, in qD, the literal Hotel(h) is superseded by GoodHotel(h).
Analogously, we can obtain: cf (r2) = 0:8 ) 0:6 + 0:4 ) 0:8 3 = =
The function FOIL-Learn-One-Rule starts from r0 which is then
specialized into r1 by applying the re nement rule which adds an atomic concept,
Hotel, to the left-hand side of the axiom. As aforementioned, r0 and r1 are trivial
hypotheses, therefore we can skip the computation steps for them and go ahead.
In particular, the algorithm generates r2 from r1 by adding a complex concept
obtained as existential restriction of the role cheapP rice. This hypothesis is not
consistent with the training set, therefore it must be specialized in order not
to cover the negative example. Considering that r3, r4 and r5 are both possible
specializations of r2, we can now compute the information gain for each of them
according to (
log2(0:3333)) = ( 2:3219 + 1:5851) = Gain(r5; r2) = 1 (log2(0:3) log2(0:3333)) = ( 1:7369 + 1:5851) =
The algorithm will prefer r3. Yet r3 still covers the negative example, therefore it must be further re ned, e.g. by strengthening the quali ed restriction of closeT o. The algorithm then generates once again the axioms r4 and r5 which have the following values of information gain over r3: Gain(r4; r3) = 1 (log2(0:2) log2(0:5333)) = ( 2:3219 + 0:907) = The axiom r5 is more informative than r4, therefore it is preferred to r4. Also it does not cover the negative example. Indeed, the literal 9closeT o:T ower is a discriminant feature. Therefore, r5 becomes part of the target theory. Since one positive example is still uncovered, the computation continues within the function FOIL-Learn-Sets-of-Rules aiming at nding a complete theory, i.e. a theory which explains all the positive examples. 4
In this paper we have proposed a method for inducing ontology inclusion axioms within the KR framework of a fuzzy DL-Lite like DL where vagueness is dealt with the Godel logic. The method extends FOIL, a popular ILP algorithm for learning sets of crisp rules, in a twofold direction: from crisp to fuzzy and from rules to inclusion axioms. Indeed, related FOIL-like algorithms are reported in the literature [20,5,19] but they can only learn fuzzy rules. Another relevant work is the formal study of fuzzy ILP contributed by [10]. Yet, it is less promising than our proposal from the practical side. Close to our application domain, [9] faces the problem of inducing equivalence axioms in a fragment of OWL corresponding to the ALC DL. Last, the work reported in [11] is based on an ad-hoc translation of fuzzy Lukasiewicz ALC DL constructs into LP and then uses a conventional ILP method to lean rules. The method is not sound as it has been recently shown that the traduction from fuzzy DLs to LP is incomplete [15] and entailment in Lukasiewicz ALC is undecidable [4].
For the future we intend to study more formally the proposed specialization operator for the fuzzy DL being considered. Also we would like to investigate in depth the impact of Open World Assumption (holding in DLs) on the proposed ILP setting, and implement and experiment our method. Finally, it can be interesting to analyze the e ect of the di erent implication functions on the learning process. 13. T. Lukasiewicz and U. Straccia. Top-k retrieval in description logic programs under vagueness for the semantic web. In H. Prade, V.S. Subrahmanian, editors, Scalable Uncertainty Management, number 4772 in Lecture Notes in Computer Science, pages 16{30. Springer Verlag, 2007. 14. T. Lukasiewicz and U. Straccia. Managing uncertainty and vagueness in description logics for the semantic web. Journal of Web Semantics, 6:291{308, 2008. 15. B. Motik and R. Rosati. A faithful integration of description logics with logic programming. In M.M. Veloso, editor, IJCAI 2007, Proc. of the 20th Int. Joint Conf. on Arti cial Intelligence, pages 477{482, 2007. 16. S.-H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Programming, volume 1228 of Lecture Notes in Arti cial Intelligence. Springer, 1997. 17. A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati.
Linking data to ontologies. Journal of Data Semantics, 10:133{173, 2008.
18. J. R. Quinlan. Learning logical de nitions from relations. Machine Learning,
5:239{266, 1990.
19. M. Serrurier and H. Prade. Improving expressivity of inductive logic programming
by learning di erent kinds of fuzzy rules. Soft Computing, 11(