Learning Multiple Description Logics Concepts

Abstract

Description logics based languages have became the standard representation scheme for ontologies. They formalize the domain knowledge using interrelated concepts, contained in terminologies. The manual de nition of terminologies is an expensive and error prone task, therefore automatic learning methods are a necessity. In this paper we lay the foundations of a multiple concept learning method that uses virtual concepts to aid the learning process, yielding more compact and readable terminologies. In this paper, we de ne virtual concepts and how they can be implemented in the current concept learning methods. We show through experiments how the method stacks up against other multiple concept learning methods.

Introduction

Description logics (DLs) [ 1 ] form a family of knowledge representation languages, with di erent expressive power, that are typically decidable fragments of rst order logic (FOL). With DL it is possible to represent domain concepts and their relations. Moreover, due to their computational power and expressiveness, they have been widely used in Semantic Web [ 2 ] for ontology representation.

The task of de ning the domain knowledge through a DL is usually done manually, which is time consuming and error prone, even more because the domain experts themselves do not always agree about the de nitions of concepts and their relationships [ 3 ]. Therefore, to consider applying machine learning techniques [ 4 ] for automatically learning in DLs is relevant and sometimes even required. A number of DL learning approaches have been proposed in the literature [ 5 ] [ 6 ]. In these approaches each concept is learned independently from each other, thus, none of the concepts being learned are considered in the de nition of the others. If this assumption is removed, the nal ontology could be clearer and closer to the way that the concepts are related in the underlying domain. In this sense, another question arises: "What is the best order to learn a set of 1 The rst author would like to thank CAPES for the nancial support through a master scholarship. related concepts?" In [ 7 ], we address this problem by de ning an algorithm that discovers a taxonomy of the concepts being learned and then uses this taxonomy to de ne the order for learning the concepts. However, since the order is de ned by a heuristic aimed at nding relations between concepts and subconcepts, it may be the case that the ordering found does not yield the best solution for the learning task. Moreover, during the learning process only previously learned concepts are considered.

In this paper, we lay the foundations of multiple concept learning using the ideas discussed in [ 7 ] as motivation. Thus, we propose a learning strategy that allows concepts not yet learned to appear in the de nition of other concepts, thus making possible to learn more compact and readable terminologies.

The paper is organized as follows. In Section 2, Description Logic and concept learning are reviewed. In Section 3, we present the proposed approach to learn multiple concepts. Section 4 presents some preliminary experimental results. Section 5 concludes the paper and presents the next steps of the research. 2

DLs and concept learning in DLs

DLs knowledge bases (KB) have two components: a TBox and an ABox. The TBox contains intensional knowledge in the form of a terminology. Knowledge is expressed in terms of individuals, concepts, and roles. Thus, the terminology consists of concepts, which denote a set of individuals and roles which denote binary relationships between individuals. In this paper, we assume the common assumption made about DL terminologies: (i) only one de nition for a concept name and (ii) concept de nitions are acyclic. The ABox is composed of assertions about the individuals of the domain. An assertion states that an individual belongs to a concept or that a pair of individuals satis es a role. Attached to a DL's KB there must be a reasoning mechanism, responsible for inferring information about individuals from the KB.

There are a number of existing approaches to automatically learn DLs concepts, most of them [ 5 ] [ 6 ] [ 8 ] are inspired by Inductive Logic Programming(ILP) [ 9 ] techniques. The goal is to induce concept descriptions from existing evidences. When learning a concept, one has the purpose of nding a generalized and correct de nition of such a concept from a set of examples, as de ned below:

De nition 1 (Concept Learning)

Given: { a knowledge base KB, { a target concept T arget such as T arget 2= KB, { a set of target examples E, divided into positive (Ep) and negative (En) examples, such that E = Ep [ En

Find: { A de nition of the concept C(T arget

KB \ C 6j= En.

C) such that KB [ C j= Ep and

Although De nition 1 requires that the learned concept covers all the positive examples and none of the negative examples, these hard criteria are usually relaxed to enable the induction.

The concept learning task can be expanded to multiple concept learning, as de ned below:

De nition 2 (Multiple Concept Learning)

Given: { knowledge base KB, { n concept learning tasks fAC1 ; AC2 ; : : : ; ACn g, where ACi = fEpi ; Eni g

Find:

{ KB0 = KB [ T , where T is a taxonomy which holds the concepts de nitions found in the n concept learning tasks.

In this paper we focus on multiple concept learning methods that return a T that have compact de nitions.

In [ 7 ] we presented a pre-processing method for multiple concept learning called terminology learning. It yields compact terminologies by de ning an order to execute each concept learning task. This order is de nied by nding, before the learning process, all the subsumee and subsumer relationships among the concept learning tasks using the shared individuals in the example sets as evidence.

However, although the subsumee and subsumer relation is important when devising an order, it is not the only relationship among concepts that can impact the later learned de nition. Thus, in this paper we follow a di erent approach to nd out the concepts that should be used to de ne another concept. Instead of directly nding a taxonomy from the set of examples, we let the learning algorithm decide what is the best way of de ning each concept. 3

Multiple DL Concept Learning

The concept learning task can be viewed as a search problem over the space of concepts, created using three basic elements [ 5 ]: (i) a re nement operator to build the search tree of concepts; (ii) a search algorithm to control how this search tree is traversed; (iii) a scoring function to evaluate the nodes of the tree and to point out the best current concept candidate.

The re nement operator is responsible for de ning a number of rules, from which a valid candidate de nition for a concept is yielded. The candidate de nitions are created from combinations of known concepts, roles and constructors. The constructors are di erent according to the DL language chosen. We propose to take into account an additional type of concept when the re nement operator is generating a concept de nition, henceforth called virtual concept.

Virtual concepts are concepts that do not have an explicit de nition yet. As usual, these concepts have a set of examples related to it, divided into positives and negative examples. Once a de nition for a concept is learned, it should have considered the individuals marked as positive examples as belonging to it. On the other hand, the negative examples are the individuals that do not belong to that concept and its de nition should be able to indicate that. Since each concept has these sets of examples associated to it, it is possible to take into account the set of examples instead of the concept de nition when referring to a concept. In this way, we can say that, while a concept is not selected to be the target one, it also behaves as a virtual concept.

In order to consider virtual concepts in the concept learning task, it is necessary to make the scoring function cope with them. Usually, the scoring function is either the cover relationship or a variation of it. The cover relationship is a function that evaluates how many positive and negative examples are inferred by a candidate de nition. So this can be achieved by transforming the example sets of a virtual concept into assertion inside the ABox, e.g., Albert 2 Ep of C, then the assertion C(Albert) will be added to the ABoxes of all concept learning tasks that could use the virtual concept C.

We argue that adding the assertions of a virtual concept can have the same result as that of the regular inference if the following assumptions holds: all the virtual concepts in the multiple concept learning task should share the same ABox and all the relevant individuals for a particular virtual concept should be covered in one of its example sets. If that is indeed the case, it is possible to use virtual concepts in the same way that other non-target instantiated concepts are used inside the concept learning task. Moreover, the addition of virtual concepts in the learning process will allow it to nd concept de nitions more compact then the ones found with the terminology learning method [ 7 ]. The terminology learning method only deals with one type of usage relationship between virtual concepts, the subsumee and subsumer relationship. This kind of relationship is only related to the concept and subconcept relationship, e.g. in the kinship domain we have Grandfather v Father. However, it can not reliably work with relationships that di ers from subsumer and subsumee, for example, the disjunction between Grandfather and Grandmother to de ne Grandparent. The method proposed in this paper is capable of dealing with it because we turn the learning task into the responsible component for nding relationships between concepts.

The proposed method has the local goal to nd the most compact de nition for a single virtual concept. The major concern that arises from this is the formation of cycles. This could be avoided by two di erent approaches: (i) when constructing the ABox' for a target concept, the addition of facts associated to virtual concepts that uses the current target concept in their de nition can be avoided. (ii) with a post-processing procedure. The rst one is likely to be more e cient in returning a solution, but does not guarantee that this is the optimal solution, while the second may have a better chance to return the optimal solution, but some concepts may be relearned several times, i.e., the learning process can become less e cient.

Preliminary Experiments

To evaluate the proposed method some experiments were devised considering the concepts GRANDPARENT (GP), GRANDFATHER (GF) and GRANDMOTHER (GM) from the Family ontology.

A knowledge base of the family domain was used to run the experiments 3. Each individual cited in the knowledge base is either a positive example or a negative example to a concept. The description learning component chosen to learn the concepts is the DL-Learner system with default settings, since it is a largely used environment to learn DLs.

The rst analysis we conducted showed that our proposal, Multiple Concept Learning (MCL), is able to learn a terminology more compact and readable than the Concept Learning (CL) approach, which learns the concepts individually and independently. Table 1 shows the de nition for the three concepts. Notice that GRANDPARENT is de ned as a disjunction of the two other concepts.

Another evaluation concerns whether MCL is able to learn a more compact terminology when compared with the Terminology Learning (TL) task. For this comparison, we considered two concept orders for MCL: (i) < GRANDPARENT; GRANDFATHER; GRANDMOTHER > and (ii) < GRANDMOTHER; GRANDFATHER; GRANDPARENT >.

The rst one, was found by the approach proposed in [ 7 ] and then is the same one used by TL. Moreover, we avoid cycles by changing the correspondent ABox as described in Section 3. The results in Table 1 shows that di erent learning orders yield di erent results, and that the proposed method can achieve the same result as the terminology learning by reversing the order. This demonstrates that the proposed method is more versatile than the terminology learning, because it isn't bound to a learning order, while still maintaining the accuracy.

To sum up, these results point out that the method has the potential for nding compact solutions when avoiding cycles with pre-processing (MCL + Order 1 or 2), and its ability to nd optimal solutions, if a post processing method to avoid cycle is used (MCL). 5

Conclusion and future remarks

In this paper we laid the foundations over which a multiple concept learning method could be built. We de ned a new type of concept, the virtual concept, analogous with the de nition of the concept learning task, but with a twist to make it usable inside the existing learning process of another concept. The proposed method opens the possibility of nding all the possible usage relationships among virtual concepts. Because of this, we argued that the use of virtual concepts could yield better results than the ones found with the method presented in [ 7 ] and in regular concept learning methods. We also presented directions to deal with the cycle problem that may appear with the use of this method. An 3 ftp://ftp.cs.utexas.edu/pub/mooney/forte Experiment Concept De nition Length

GP EXISTS parent.EXISTS parent.TOP. 5 CL GF (male AND EXISTS parent.EXISTS parent.TOP). 7 GM (female AND EXISTS parent.EXISTS parent.TOP). 7

GP (grandfather OR grandmother). 3 MCL GF (grandparent AND male). 3 GM (grandparent AND female). 3

GP EXISTS parent.EXISTS parent.TOP. 5 TL=CL+Order GF (grandparent AND male). 3 GM (grandparent AND female). 3

GP (grandfather OR grandmother). 3 MCL+Order 1 GF (male AND EXISTS married.grandmother). 5 GM (female AND EXISTS parent.EXISTS parent.TOP). 7

GP EXISTS parent.EXISTS parent.TOP. 5 MCL+Order 2 GF (grandparent AND male). 3

GM (grandparent AND female). 3 experiment concerning the Kinship domain showed that it is possible to learn a clearer and more compact terminology without requiring a good ordering of the concepts.

In the future we would like to analyze the behavior of the method on di erent data sets and di erent DL languages, since we believe the proposed method is capable to work with all possible constructors sets.

References

1. F. Baader and W. Nutt , \ Basic description logics," in The description logic handbook (F. Baader , D. L. McGuinness , D. Nardi , and P. F. Patel-Schneider , eds.), pp. 47 { 100 , Cambridge University Press, 2 ed., may 2010 .

2. T. Berners-Lee , J. Hendler , and O. Lassila , \ The semantic web," Scienti c American , vol. 5 , no. 284 , p. 34 , 2001 .

3. A. Maedche and S. Staab , \ Ontology learning for the semantic web," IEEE Intelligent Systems and Their Applications , vol. 16 , no. 2 , pp. 72 { 79 , 2001 .

4. T. Mitchell, Machine Learning. New York: McGraw-Hill , 1997 .

5. J. Lehmann and P. Hitzler , \ Concept learning in description logics using re nement operators," Machine Learning , vol. 78 , no. 1-2 , pp. 203 { 250 , 2010 .

6. N. Fanizzi , C. d'Amato, and F. Esposito , \ Dl-foil concept learning in description logics," in Proceedings of the 18th International Conference on Inductive Logic Programming (ILP-2008) , vol. 5194 LNAI of Lecture Notes in Computer Science , pp. 107 { 121 , Springer, 2008 .

7. R. Melo , K. Revoredo , and A. Paes , \ Terminology learning through taxonomy discovery," BRACIS "to appear" , 2013 .

8. L. Iannone , I. Palmisano , and N. Fanizzi , \ An algorithm based on counterfactuals for concept learning in the semantic web," Applied Intelligence , vol. 26 , no. 2 , pp. 139 { 159 , 2007 .

9. L. De Raedt, Logical and Relational Learning . Springer, 2008 .