Bisimulation-Based Concept Learning in Description Logics

Abstract

Concept learning in description logics (DLs) is similar to binary classi cation in traditional machine learning. The di erence is that in DLs objects are described not only by attributes but also by binary relationships between objects. In this paper, we develop the rst bisimulation-based method of concept learning in DLs for the following setting: given a knowledge base KB in a DL, a set of objects standing for positive examples and a set of objects standing for negative examples, learn a concept C in that DL such that the positive examples are instances of C w.r.t. KB, while the negative examples are not instances of C w.r.t. KB.

-

In this paper we continue our study [ 12, 15, 7, 4 ] on concept learning in description logics (DLs). This problem is similar to binary classi cation in traditional machine learning. The di erence is that in DLs objects are described not only by attributes but also by binary relationships between objects. The major settings of concept learning in DLs are as follows: 1. Given a knowledge base KB in a DL L and sets E+, E of individuals, learn a concept C in L such that: (a) KB j= C(a) for all a 2 E+, and (b) KB j= :C(a) for all a 2 E . The set E+ (resp. E ) contains positive (resp. negative) examples of C. 2. The second setting di ers from the previous one only in that the condition (b) is replaced by the weaker one: KB 6j= C(a) for all a 2 E . 3. Given an interpretation I and sets E+, E of individuals, learn a concept C in L such that: (a) I j= C(a) for all a 2 E+, and (b) I j= :C(a) for all a 2 E . Note that I 6j= C(a) is the same as I j= :C(a).

As an early work on concept learning in DLs, Cohen and Hirsh [ 3 ] studied PAC-learnability of the CLASSIC description logic (an early DL formalism) and its sublogic C-CLASSIC. They proposed a concept learning algorithm based on \least common subsumers". In [ 9 ] Lambrix and Larocchia proposed a simple concept learning algorithm based on concept normalization.

Badea and Nienhuys-Cheng [ 1 ], Iannone et al. [ 8 ], Fanizzi et al. [ 6 ], Lehmann and Hitzler [ 10 ] studied concept learning in DLs by using re nement operators as in inductive logic programming. The works [ 1, 8 ] use the rst mentioned setting, while the works [ 6, 10 ] use the second mentioned setting. Apart from re nement operators, scoring functions and search strategies also play important roles in algorithms proposed in those works. The algorithm DL-Learner [ 10 ] exploits genetic programming techniques, while DL-FOIL [ 6 ] considers also unlabeled data as in semi-supervised learning.

Nguyen and Szalas [ 12 ] applied bisimulation in DLs [ 5 ] to model indiscernibility of objects. Their work is pioneering in using bisimulation for concept learning in DLs. It also concerns concept approximation by using bisimulation and Pawlak's rough set theory [ 13, 14 ]. In [ 15 ] Tran et al. generalized and extended the concept learning method of [ 12 ] for DL-based information systems. They took attributes as basic elements of the language. An information system in a DL is a nite interpretation in that logic. Thus, both the works [ 12, 15 ] use the third mentioned setting. In [ 7 ] Ha et al. developed the rst bisimulation-based method, called BBCL, for concept learning in DLs using the rst mentioned setting. Their method uses models of KB and bisimulation in those models to guide the search for the concept to be learned. It is formulated for a large class of useful DLs, with well-known DLs like ALC, SHIQ, SHOIQ, SROIQ. The work [ 7 ] also introduced dual-BBCL, a variant of BBCL, for concept learning in DLs using the rst mentioned setting.

In this paper, we develop the rst bisimulation-based method, called BBCL2, for concept learning in DLs using the second mentioned setting, i.e., for learning a concept C such that: KB j= C(a) for all a 2 E+, and KB 6j= C(a) for all a 2 E , where KB is a given knowledge base in the considered DL, and E+, E are given sets of examples of C. This method is based on the dual-BBCL method (of concept learning in DLs using the rst mentioned setting) from our joint work [ 7 ]. We make appropriate changes for dealing with the condition \KB 6j= C(a) for all a 2 E " instead of \KB j= :C(a) for all a 2 E ".

The rest of this paper is structured as follows. In Section 2, we recall notation and semantics of DLs. We present our BBCL2 method in Section 3 and illustrate it by examples in Section 4. We conclude in Section 5. Due to the lack of space, we will not recall the notion of bisimulation in DLs [ 5, 7 ], but just mention the use of the largest auto-bisimulation relations and list the bisimulation-based selectors [ 7 ].

Notation and Semantics of Description Logics

A DL-signature is a nite set = I [ dA [ nA [ oR [ dR, where I is a set of individuals, dA is a set of discrete attributes, nA is a set of numeric attributes, oR is a set of object role names, and dR is a set of data roles.4 All the sets I , dA, nA, oR, dR are pairwise disjoint.

Let A = dA [ nA. Each attribute A 2 A has a domain dom(A), which is a non-empty set that is countable if A is discrete, and partially ordered by otherwise.5 (For simplicity we do not subscript by A.) A discrete attribute is a Boolean attribute if dom(A) = ftrue; falseg. We refer to Boolean attributes also as concept names. Let C dA be the set of all concept names of .

An object role name stands for a binary predicate between individuals. A data role stands for a binary predicate relating individuals to elements of a set range( ).

We denote individuals by letters like a and b, attributes by letters like A and B, object role names by letters like r and s, data roles by letters like and %, and elements of sets of the form dom(A) or range( ) by letters like c and d.

We will consider some (additional) DL-features denoted by I (inverse), O (nominal), F (functionality), N (unquanti ed number restriction), Q (quanti ed number restriction), U (universal role), Self (local re exivity of an object role). A set of DL-features is a set consisting of some or zero of these names.

Let be a DL-signature and be a set of DL-features. Let L stand for ALC, which is the name of a basic DL. (We treat L as a language, but not a logic.) The DL language L ; allows object roles and concepts de ned as follows: { if r 2 oR then r is an object role of L ; { if A 2 C then A is concept of L ; { if A 2 A n C and d 2 dom(A) then A = d and A 6= d are concepts of L ; { if A 2 nA and d 2 dom(A) then A d, A < d, A d and A > d are concepts of L ; { if C and D are concepts of L ; , R is an object role of L ; , r 2 oR, 2 dR, a 2 I , and n is a natural number then >, ?, :C, C u D, C t D, 8R:C and 9R:C are concepts of L ; if d 2 range( ) then 9 : d

f g is a concept of L ; if I 2 then r is an object role of L ; if O 2 then fag is a concept of L ; if F 2 then 1 r is a concept of L ; if fF; Ig then 1 r is a concept of L ; if N 2 then n r and n r are concepts of L ; if fN; Ig then n r and n r are concepts of L ; if Q 2 then n r:C and n r:C are concepts of L ; if fQ; Ig then n r :C and n r :C are concepts of L ; if U 2 then U is an object role of L ;

4 Object role names are atomic object roles.

5 One can assume that, if A is a numeric attribute, then dom(A) is the set of real numbers and is the usual linear order between real numbers.

(r )I = (rI ) 1

U I =

I

I >I =

I ?I = ; (A = d)I = fx 2

I j AI (x) = dg

(A 6= d)I = (:(A = d))I (A (A d)I = fx 2 d)I = fx 2

I j AI (x) is de ned; AI (x)

dg I j AI (x) is de ned; d

AI (x)g (A < d)I = ((A d) u (A 6= d))I (A > d)I = ((A d) u (A 6= d))I (:C)I =

I n CI (C u D)I = CI \ DI (C t D)I = CI [ DI fagI = faI g (9r:Self)I = fx 2

I j rI (x; x)g (9 :fdg)I = fx 2

I j I (x; d)g (8R:C)I = fx 2

I j 8y [RI (x; y) ) CI (y)]g (9R:C)I = fx 2

I j 9y [RI (x; y) ^ CI (y)] ( n R:C)I = fx 2 ( n R:C)I = fx 2

I j #fy j RI (x; y) ^ CI (y)g I j #fy j RI (x; y) ^ CI (y)g ng ng ( n R)I = ( n R:>)I

( n R)I = ( n R:>)I

An interpretation in L ; is a pair I = I ; I , where I is a non-empty set called the domain of I and I is a mapping called the interpretation function of I that associates each individual a 2 I with an element aI 2 I , each concept name A 2 C with a set AI I , each attribute A 2 A n C with a partial function AI : I ! dom(A), each object role name r 2 oR with a binary relation rI I I , and each data role 2 dR with a binary relation

I I range( ). The interpretation function I is extended to complex object roles and complex concepts as shown in Figure 1, where # stands for the cardinality of the set .

Given an interpretation I = I ; I in L ; , we say that an object x 2 I has depth k if k is the maximal natural number such that there are pairwise di erent objects x0; : : : ; xk of I with the properties that: { xk = x and x0 = aI for some a 2 I , { xi 6= bI for all 1 i k and all b 2 I , { for each 1 i k, there exists an object role Ri of L ; hxi 1; xii 2 RI .

i

By Ijk we denote the interpretation obtained from I by restricting the domain to the set of objects with depth not greater than k and restricting the interpretation function accordingly.

A role inclusion axiom in L ; is an expression of the form R1 : : : Rk v r, where k 1, r 2 oR and R1; : : : ; Rk are object roles of L ; di erent from U . A role assertion in L ; is an expression of the form Ref(r), Irr(r), Sym(r), such that Tra(r), or Dis(R; S), where r 2 oR and R; S are object roles of L ; di erent from U . Given an interpretation I, de ne that:

I j= R1 : : : Rk v r if R1I : : : RkI rI I j= Ref(r) if rI is re exive I j= Irr(r) if rI is irre exive I j= Sym(r) if rI is symmetric I j= Tra(r) if rI is transitive

I j= Dis(R; S) if RI and SI are disjoint, where the operator stands for the composition of binary relations. By a role axiom in L ; we mean either a role inclusion axiom or a role assertion in L ; . We say that a role axiom ' is valid in I (or I validates ') if I j= '.

A terminological axiom in L ; , also called a general concept inclusion (GCI) in L ; , is an expression of the form C v D, where C and D are concepts in L ; . An interpretation I validates an axiom C v D, denoted by I j= C v D, if CI DI .

An individual assertion in L ; is an expression of one of the forms C(a) (concept assertion), r(a; b) (positive role assertion), :r(a; b) (negative role assertion), a = b, and a 6= b, where r 2 oR and C is a concept of L ; . We will write, for example, A(a) = d instead (A = d)(a). Given an interpretation I, de ne that:

I j= a = b if aI = bI I j= a 6= b if aI 6= bI I j= C(a) if aI 2 CI I j= r(a; b) if aI ; bI I j= :r(a; b) if

We say that I validates an individual assertion ' if I j= '.

An RBox (resp. TBox, ABox) in L ; is a nite set of role axioms (resp. terminological axioms, individual assertions) in L ; . A knowledge base in L ; is a triple hR; T ; Ai, where R (resp. T , A) is an RBox (resp. a TBox, an ABox) in L ; . An interpretation I is a model of a \box" if it validates all the axioms/assertions of that \box". It is a model of a knowledge base hR; T ; Ai if it is a model of R, T and A. A knowledge base is satis able if it has a model. An individual a is said to be an instance of a concept C w.r.t. a knowledge base KB , denoted by KB j= C(a), if, for every model I of KB , aI 2 CI .

P1 : 2010 Awarded P6 : 2006 Awarded Example 2.1. This example is based on an example of [ 15, 7 ]. Let = fI; O; N; Qg;

I = fP1; P2; P3; P4; P5; P6g;

C = fPub; Awarded ; Adg; dA =

C ; nA = fYear g; oR = fcites; cited by g; dR = ;; R = fcites v cited by ; cited by v citesg; T = f> v Pubg; A0 = fAwarded (P1); :Awarded (P2); :Awarded (P3); Awarded (P4); :Awarded (P5); Awarded (P6); Year (P1) = 2010; Year (P2) = 2009; Year (P3) = 2008; Year (P4) = 2007; Year (P5) = 2006; Year (P6) = 2006; cites(P1; P2); cites(P1; P3); cites(P1; P4); cites(P1; P6); cites(P2; P3); cites(P2; P4); cites(P2; P5); cites(P3; P4); cites(P3; P5); cites(P3; P6); cites(P4; P5); cites(P4; P6)g; where the concept Pub stands for \publication". Then KB 0 = hR; T ; A0i is a knowledge base in L ; . The axiom > v Pub states that the domain of any model of KB 0 consists of only publications. The knowledge base KB 0 is illustrated in Figure 2 (on page 426). In this gure, nodes denote publications and edges denote citations (i.e., assertions of the role cites), and we display only information concerning assertions about Year , Awarded and cites. C

An L ; logic is speci ed by a number of restrictions adopted for the language L ; . We say that a logic L is decidable if the problem of checking satis ability of a given knowledge base in L is decidable. A logic L has the nite model property if every satis able knowledge base in L has a nite model. We say that a logic L has the semi- nite model property if every satis able knowledge base in L has a model I such that, for any natural number k, Ijk is nite and constructable.

As the general satis ability problem of context-free grammar logics is undecidable [ 2 ], the most general L ; logics (without restrictions) are also undecidable. The considered class of DLs contains, however, many decidable and useful logics. One of them is SROIQ - the logical base of the Web Ontology Language OWL 2. This logic has the semi- nite model property.

Concept Learning for Knowledge Bases in DLs

Let L be a decidable L ; logic with the semi- nite model property, Ad 2 C be a special concept name standing for the \decision attribute", and KB 0 = hR; T ; A0i be a knowledge base in L without using Ad. Let E+ and E be disjoint subsets of I such that the knowledge base KB = hR; T ; Ai with A = A0 [ fAd(a) j a 2 E+g [ f:Ad(a) j a 2 E g is satis able. The set E+ (resp. E ) is called the set of positive (resp. negative) examples of Ad. Let E = hE+; E i.

The problem is to learn a concept C as a de nition of Ad in the logic L restricted to a given sublanguage L y; y with y n fAdg and y such that: KB j= C(a) for all a 2 E+, and KB 6j= C(a) for all a 2 E .

Given an interpretation I in L ; , by y; y;I we denote the equivalence relation on I with the property that x y; y;I x0 i x is L y; y -equivalent to x0 (i.e., for every concept D of L y; y , x 2 DI i x0 2 DI ). By [7, Theorem 3], this equivalence relation coincides with the largest L y; y -auto-bisimulation y; y;I of I (see [ 7 ] for the de nition of this notion).

Let I be an interpretation. We say that a set Y I is divided by E if there exist a 2 E+ and b 2 E such that faI ; bI g Y . A partition P = fY1; : : : ; Ykg of I is said to be consistent with E if, for every 1 i n, Yi is not divided by E. Observe that if I is a model of KB then: { since C is a concept of L y; y , by [7, Theorems 2 and 3], CI should be the union of a number of equivalence classes of I w.r.t. y; y;I { we should have that aI 2 CI for all a 2 E+, and aI 2= CI for all a 2 E .

The idea is to use models of KB and bisimulation in those models to guide the search for C. We now describe our method BBCL2 (Bisimulation-Based Concept Learning for knowledge bases in DLs using the second setting). It constructs a set of E0 of individuals and sets of concepts C, C0. E0 will cover more and more individuals from E . The meaning of C is to collect concepts D such that KB j= D(a) for all a 2 E+. The set C0 is auxiliary for the construction of C. When a concept D does not satisfy the mentioned condition but is a \good" candidate for that, we put it into C0. Later, when necessary, we take disjunctions of some concepts from C0 and check whether they are good for adding to C. During the learning process, we will always have that: { KB j= (d C)(a) for all a 2 E+, { KB 6j= (d C)(a) for all a 2 E0 , where dfD1; : : : ; Dng = D1 u: : :uDn and d ; = >. We try to extend C to satisfy KB 6j= (d C)(a) for more and more a 2 E . Extending C enables extension of E0 . When E0 reaches E , we return the concept d C after normalization and simpli cation. Our method is not a detailed algorithm, as we leave some steps at an abstract level, open to implementation heuristics. In particular, we assume that it is known whether L has the nite model property, how to construct models of KB , and how to do instance checking KB j= D(a) for arbitrary D and a. The steps of our method are as follows. 1. Initialize E0 := ;, C := ;, C0 := ;. 2. (This is the beginning of a loop controlled by \go to" at Step 6.) If L has the nite model property then construct a (next) nite model I of KB . Otherwise, construct a (next) interpretation I such that either I is a nite model of KB or I = IjK

0 , where I0 is an in nite model of KB and K is a parameter of the learning method (e.g., with value 5). 3. Starting from the partition f I g, make subsequent granulations to reach the partition fYi1 ; : : : ; Yik g corresponding to y; y;I , where each Yij is characterized by an appropriate concept Cij (such that Yij = CiIj ). 4. For each 1 j k, if Yij contains some aI with a 2 E and no aI with a 2 E+ then: { if KB j= :Cij (a) for all a 2 E+ then if d C is not subsumed by :Cij w.r.t. KB (i.e. KB 6j= (d C v :Cij )) then add :Cij to C and add to E0 all a 2 E such that aI 2 Yij { else add :Cij to C0. 5. If E0 = E then go to Step 8. 6. If it was hard to extend C during a considerable number of iterations of the loop (with di erent interpretations I) then go to Step 7, else go to Step 2. 7. Repeat the following: (a) Randomly select some concepts D1; : : : ; Dl from C0 and

let D = (D1 t : : : t Dl). (b) If KB j= D(a) for all a 2 E+, d C is not subsumed by D w.r.t. KB (i.e., KB 6j= (d C) v D), and E n E0 contains some a such that KB 6j= (d C)(a), then: i. add D to C, ii. add to E0 all a 2 E n E0 such that KB 6j= (d C)(a), iii. if E0 = E then go to Step 8. (c) If it was still too hard to extend C during a considerable number of iterations of the current loop, or C is already too big, then stop the process with failure. 8. For each D 2 C, if KB 6j= d(CnfDg)(a) for all a 2 E then delete D from C. 9. Let C be a normalized form of d C.6 Observe that KB j= C(a) for all a 2 E+, and KB 6j= C(a) for all a 2 E . Try to simplify C while preserving this property, and then return it.

For Step 2, if L is one of the well known DLs, then I can be constructed by using a tableau algorithm (see [ 7 ] for references). During the construction, randomization is used to a certain extent to make I di erent from the interpretations generated in previous iterations of the loop.

We describe Step 3 in more details: { In the granulation process, we denote the blocks created so far in all steps by Y1; : : : ; Yn, where the current partition fYi1 ; : : : ; Yik g consists of only some of them. We do not use the same subscript to denote blocks of di erent

6 Normalizing concepts can be done, e.g., as in [11].

{ A, where A 2 Cy { A = d, where A 2 Ay n Cy and d 2 dom(A) { A d and A < d, where A 2 nyA, d 2 dom(A) and d is not a minimal element of dom(A) { A d and A > d, where A 2 nyA, d 2 dom(A) and d is not a maximal element of dom(A) { 9 :fdg, where 2 dyR and d 2 range( ) { 9r:Ci, 9r:> and 8r:Ci, where r 2 oyR and 1 i n { 9r :Ci, 9r :> and 8r :Ci, if I 2 y, r 2 oyR and 1 i n {{{ fa11g,rr,ifi,fOiFf2f2F;yIygaannddayr2a2ndIyoyrR2 oyR { l r and m r, if N 2 y, r 2 oyR, 0 < l # I and 0 m < # I { l r and m r , if fN; Ig y, r 2 oyR, 0 < l # I and 0 m < # I { l r:Ci and m r:Ci, if Q 2 y, r 2 oyR, 1 i n, 0 < l #Ci and 0 m < #Ci { l r :Ci and m r :Ci, if fQ; Ig y, r 2 oyR, 1 i n, 0 < l #Ci and 0 m < #Ci { 9r:Self, if Self 2 y and r 2 oyR

As a modi cation for Step 3, the granulation process can be stopped as soon as the current partition is consistent with E (or when some criteria are met).

But, if it is hard to extend C during a considerable number of iterations of the loop (with di erent interpretations I), then this loosening should be discarded.

Observe that, when :Cij is added to C, we have that aI 2 (:Cij )I for all a 2 E+. This is a good point for hoping that KB j= :Cij (a) for all a 2 E+. We check it, for example, by using some appropriate tableau decision procedure, and if it holds then we add :Cij to the set C. Otherwise, we add :Cij to C0. To increase the chance to have Cij satisfying the mentioned condition and being added to C, we tend to make Cij strong enough. For this reason, we do not use the technique with LargestContainer introduced in [ 12 ], and when necessary, we do not apply the above mentioned loosening for Step 3.

Note that any single concept D from C0 does not satisfy the condition KB j= D(a) for all a 2 E+, but when we take a number of concepts D1; : : : ; Dl from C0 we may have that KB j= (D1 t : : : t Dl)(a) for all a 2 E+. So, when it is really hard to extend C by directly using concepts :Cij (where Cij are the concepts used for characterizing blocks of partitions of the domains of models of KB ), we change to using disjunctions D1 t : : : t Dl of concepts from C0 as candidates for adding to C.

4 Illustrative Examples

Example 4.1. Let KB 0 = hR; T ; A0i be the knowledge base given in Example 2.1. Let E+ = fP4, P6g, E = fP1, P2, P3, P5g, y = fAwarded , cited byg and y = ;. As usual, let KB = hR; T ; Ai, where A = A0 [ fAd(a) j a 2 E+g [ f:Ad(a) j a 2 E g. Execution of our BBCL2 method on this example is as follows. 1. E0 := ;, C := ;, C0 := ;. 2. KB has in nitely many models, but the most natural one is I speci ed below, which will be used rst:

I = fP1; P2; P3; P4; P5; P6g; xI = x for x 2 fP1; P2; P3; P4; P5; P6g; PubI =

I ; Awarded I = fP1; P4; P6g; citesI = fhP1; P2i ; hP1; P3i ; hP1; P4i ; hP1; P6i ; hP2; P3i ; hP2; P4i ; hP2; P5i ; hP3; P4i ; hP3; P5i ; hP3; P6i ; hP4; P5i ; hP4; P6ig; cited byI = (citesI ) 1; the function Year I is speci ed as usual. 3. Y1 := I , partition := fY1g 4. Partitioning Y1 by Awarded : { Y2 := fP1; P4; P6g, C2 := Awarded , { Y3 := fP2; P3; P5g, C3 := :Awarded , { partition := fY2; Y3g. 5. Partitioning Y2: { All the selectors 9cited by:>, 9cited by:C2 and 9cited by:C3 partition

Y2 in the same way. We choose 9cited by:>, as it is the simplest one. { Y4 := fP4; P6g, C4 := C2 u 9cited by:>, { Y5 := fP1g, C5 := C2 u :9cited by:>, { partition := fY3; Y4; Y5g. 6. The obtained partition is consistent with E, having Y3 = fP2; P3; P5g E , Y4 = fP4; P6g = E+ and Y5 = fP1g E . (It is not yet the partition corresponding to y; y;I.) 7. Since Y3 E and KB j= :C3(a) for all a 2 E+, we add :C3 to C and add the elements of Y3 to E0 . Thus, C = f:C3g and E0 = fP2; P3; P5g. 8. Since Y5 E and KB j= :C5(a) for all a 2 E+ and d C is not subsumed by :C5 w.r.t. KB , we add :C5 to C and add the elements of Y5 to E0 . Thus, C = f:C3; :C5g, d C = ::Awarded u :(Awarded u :9cited by:>) and E0 = fP1; P2; P3; P5g. 9. Since E0 = E , we normalize d C to Awarded u 9cited by:> and return it as the result. (This concept denotes the set of publications which were awarded and cited.) C Example 4.2. Let KB 0, E+, E , KB and y be as in Example 4.1, but let y = fcited by; Year g. Execution of the BBCL2 method on this new example has the same rst two steps as in Example 4.1, and then continues as follows. (Year < 2008) u [(Year 2007) t 9cited by:(Year 2010)]: C = (Year < 2008) u 9cited by:(Year 2010) is a simpli ed form of the above concept, which still satis es that KB j= C(a) for all a 2 E+ and KB 6j= C(a) for all a 2 E . Thus, we return it as the result. (The returned concept denotes the set of publications released before 2008 that are cited by some publications released since 2010.) C

Discussion and Conclusion

We rst compare the BBCL2 method with the BBCL and dual-BBCL methods from our joint work [ 7 ]. First of all, BBCL2 is used for the second setting of concept learning in DLs, while BBCL and dual-BBCL are used for the rst setting. BBCL2 is derived from dual-BBCL, but it contains substantial modi cations needed for the change of setting. BBCL2 di ers from BBCL at Steps 1, 4, 5, 7, 8, 9, and di ers from dual-BBCL by the use of E0 at Steps 1, 4, 5 and 7.

Comparing the examples given in this paper and in [ 7 ], apart from detailed technical di erences in concept learning, it can be seen that the rst setting requires more knowledge7 in order to obtain similar e ects as the second setting. In other words, the second setting has e ects of a kind of closed world assumption, while the rst setting does not. The overall impression is that the second setting is more convenient than the rst one.

Recall that our BBCL2 method is the rst bisimulation-based method for concept learning in DLs using the second setting. As for the case of BBCL and dual-BBCL, it is formulated for the class of decidable ALC ; DLs that have the nite or semi- nite model property, where fI; O; F; N; Q; U; Selfg. This class contains many useful DLs. For example, SROIQ (the logical base of OWL 2) belongs to this class. Our method is applicable also to other decidable DLs with the nite or semi- nite model property. The only additional requirement is that those DLs have a good set of selectors (in the sense of [15, Theorem 10]).

Like BBCL and dual-BBCL, the idea of BBCL2 is to use models of the considered knowledge base and bisimulation in those models to guide the search for the concept. Thus, it is completely di erent from the previous works [ 6, 10 ] on concept learning in DLs using the second setting. As bisimulation is the notion for characterizing indiscernibility of objects in DLs, our BBCL2 method is natural and very promising. We intend to implement BBCL2 in the near future.

Acknowledgments

This paper was written during the rst author's visit at Warsaw Center of Mathematics and Computer Science (WCMCS). He would like to thank WCMCS for the support. This work was also supported by Polish National Science Centre (NCN) under Grant No. 2011/01/B/ST6/02759 as well as by Polish National Center for Research and Development (NCBiR) under Grant No. SP/I/1/77065/10 by the strategic scienti c research and experimental development program: \Interdisciplinary System for Interactive Scienti c and Scienti c-Technical Information".

References

1. L. Badea and S. -H. Nienhuys-Cheng. A re nement operator for description logics . In Proceedings of ILP' 2000 , volume 1866 of LNCS , pages 40 { 59 . Springer, 2000 .

7 like the assertions (:9cited by:>)(P1) and (8cited by:fP2; P3; P4g)(P5), which state that P1 is not cited by any publication and P5 is only cited by P2, P3 and P4

2. M. Baldoni , L. Giordano , and A. Martelli . A tableau for multimodal logics and some (un)decidability results . In Proceedings of TABLEAUX' 1998 , volume 1397 of LNCS , pages 44 { 59 . Springer, 1998 .

3. W.W. Cohen and H. Hirsh . Learning the Classic description logic: Theoretical and experimental results . In Proceedings of KR'1994 , pages 121 { 133 .

4. A.R. Divroodi , Q.-T. Ha , L.A. Nguyen , and H.S. Nguyen . On C-learnability in description logics . In Proceedings of ICCCI'2012 (1) , volume 7653 of LNCS , pages 230 { 238 . Springer, 2012 .

5. A.R. Divroodi and L.A. Nguyen . On bisimulations for description logics . In Proceedings of CS&P' 2011 , pages 99 {110 (see also arXiv: 1104 . 1964 ).

6. N. Fanizzi , C. d'Amato, and F. Esposito . DL-FOIL concept learning in description logics . In Proc. of ILP' 2008 , volume 5194 of LNCS , pages 107 { 121 . Springer, 2008 .

7. Q.-T. Ha, T.-L.-G. Hoang , L.A. Nguyen , H.S. Nguyen , A. Szalas , and T.-L. Tran . A bisimulation-based method of concept learning for knowledge bases in description logics . In Proceedings of SoICT'2012 , pages 241 { 249 . ACM, 2012 .

8. L. Iannone , I. Palmisano , and N. Fanizzi . An algorithm based on counterfactuals for concept learning in the Semantic Web . Appl. Intell., 26 ( 2 ): 139 { 159 , 2007 .

9. P. Lambrix and P. Larocchia . Learning composite concepts . In Proc. of DL ' 1998 .

10. J. Lehmann and P. Hitzler . Concept learning in description logics using re nement operators . Machine Learning , 78 ( 1-2 ): 203 { 250 , 2010 .

11. L.A. Nguyen . An e cient tableau prover using global caching for the description logic ALC . Fundamenta Informaticae , 93 ( 1-3 ): 273 { 288 , 2009 .

12. L.A. Nguyen and A. Szalas . Logic-based roughi cation . In A. Skowron and Z . Suraj, editors, Rough Sets and Intelligent Systems (To the Memory of Professor Zdzislaw Pawlak) , Vol. 1 , pages 529 { 556 . Springer, 2012 .

13. Z. Pawlak. Rough Sets . Theoretical Aspects of Reasoning about Data . Kluwer Academic Publishers, Dordrecht, 1991 .

14. Z. Pawlak and A. Skowron . Rudiments of rough sets . Inf. Sci. , 177 ( 1 ):3{ 27 , 2007 .

15. T.-L. Tran , Q.-T. Ha, T.-L.-G. Hoang , L.A. Nguyen , H.S. Nguyen , and A. Szalas . Concept learning for description logic-based information systems . In Proceedings of KSE'2012 , pages 65 { 73 . IEEE Computer Society, 2012 .