Inductive Logic Programming (ILP) has been historically concerned with concept learning from examples and background knowledge within the representation framework of Horn clausal logic and with the aim of prediction [17]. Though the use of background knowledge has been widely recognized as one of the strongest points of ILP when compared to other forms of inductive learning [19,21,10] and has been empirically studied in several application domains [11,26,25], the background knowledge in ILP systems is often not organized around a well-formed conceptual model. This practice seems to ignore latest developments in Knowledge Engineering such as ontologies [6] and formalisms based on Description Logics (DLs) [2] which are playing a relevant role in the definition of the Semantic Web [3]. Indeed the standard mark-up language OWL for the ontological layer of the Semantic Web has been based on the very expressive DL SHIQ [7]. In a recent position paper, Page and Srinivasan have pointed out that the use of special-purpose reasoners in ILP is among the pressing issues that have arisen from the most challenging ILP applications of today [18]. We think that this is the case for ILP applications in the Semantic Web area.
In this paper we report on an experience with OWL-DL reasoners in ILP. In particular, we choose AL-QuIn [14,13] as the ILP system and Pellet as the OWL-DL reasoner [24]. The paper is structured as follows. Section 2 briefly describes AL-QuIn. Section 3 illustrates the use of Pellet in AL-QuIn. Section 4 draws conclusions and outlines directions of future work.
The ILP system AL-QuIn (AL-log Query Induction) [14,13] supports a data mining task known under the name of frequent pattern discovery. In data mining a pattern is considered as an intensional description (expressed in a given language L) of a subset of a given data set r. The support of a pattern is the relative frequency of the pattern within r and is computed with the evaluation function supp. The task of frequent pattern discovery aims at the extraction of all frequent patterns, i.e. all patterns whose support exceeds a user-defined threshold of minimum support. The blueprint of most algorithms for frequent pattern discovery is the levelwise search [16]. It is based on the following assumption: If a generality order for the language L of patterns can be found such that is monotonic w.r.t. supp, then the resulting space (L, ) can be searched breadth-first starting from the most general pattern in L and by alternating candidate generation and candidate evaluation phases. In particular, candidate generation consists of a refinement step followed by a pruning step. The former derives candidates for the current search level from patterns found frequent in the previous search level. The latter allows some infrequent patterns to be detected and discarded prior to evaluation thanks to the monotonicity of . AL-QuIn solves a variant of the frequent pattern discovery problem which takes concept hierarchies into account during the discovery process, thus yielding descriptions at multiple granularity levels up to a maximum level maxG. More formally, given a data set r including a taxonomy T where a reference concept C ref and task-relevant concepts are designated, a multi-grained language {L l } 1≤l≤maxG of patterns a set {minsup l } 1≤l≤maxG of user-defined minimum support thresholds the problem of frequent pattern discovery at l levels of description granularity, 1 ≤ l ≤ maxG, is to find the set F of all the patterns P ∈ L l that describe the reference concept w.r.t. the task-relevant concepts and turn out to be frequent in r. Note that P 's with support s such that (i) s ≥ minsup l and (ii) all ancestors of P w.r.t. T are frequent in r. Note that a pattern Q is considered to be an ancestor of P if it is a coarser-grained version of P .
Example 1. As a showcase we consider the task of finding frequent patterns that describe Middle East countries (reference concept) w.r.t. the religions believed and the languages spoken (task-relevant concepts) at three levels of granularity (maxG = 3). Minimum support thresholds are set to the following values: minsup 1 = 20%, minsup 2 = 13%, and minsup 3 = 10%. The data set and the language of patterns will be illustrated in Example 2 and Example 3, respectively.
In AL-QuIn data and patterns are represented according to the hybrid knowledge representation and reasoning system AL-log [5]. In particular, the data set r is represented as an AL-log knowledge base B, thus composed of a structural part and a relational part. The structural subsystem Σ is based on ALC [22] and allows for the specification of knowledge in terms of classes (concepts), binary relations between classes (roles), and instances (individuals). In particular, the TBox T contains is-a relations between concepts (axioms) whereas the ABox A contains instance-of relations between individuals (resp. pairs of individuals) and concepts (resp. roles) (assertions). The relational subsystem Π is based on an extended form of Datalog [4] that is obtained by using ALC concept assertions essentially as type constraints on variables.
Example 2. For the task of interest, we consider an AL-log knowledge base B CIA that integrates a ALC component Σ CIA containing taxonomies rooted into the concepts Country, EthnicGroup, Language and Religion and a Datalog component Π CIA containing facts 1 extracted from the on-line 1996 CIA World Fact Book 2 . Note that Middle East countries have been defined as Asian countries that host at least one Middle Eastern ethnic group:
MiddleEastCountry ≡ AsianCountry ∃Hosts.MiddleEastEthnicGroup.
1 http://www.dbis.informatik.uni-goettingen.de/Mondial/mondial-rel-facts.flp 2 http://www.odci.gov/cia/publications/factbook/ In particular, Armenia ('ARM') and Iran ('IR') are classified as Middle East countries because the following membership assertions hold in Σ CIA : 'ARM':AsianCountry. 'IR':AsianCountry. 'Arab':MiddleEastEthnicGroup. 'Armenian':MiddleEastEthnicGroup. <'ARM','Armenian'>:Hosts. <'IR','Arab'>:Hosts.
More details on Σ CIA can be found in Figure 1. 3 that define views on the relations religion and language, respectively.
The language L = {L l } 1≤l≤maxG of patterns allows for the generation of AL-log unary conjunctive queries, called O-queries. Given a reference concept C ref , an O-query Q to an AL-log knowledge base B is a (linked and connected) 4constrained Datalog clause of the form
where X is the distinguished variable and the remaining variables occurring in the body of Q are the existential variables. Note that α j , 1 ≤ j ≤ m, is a Datalog literal whereas γ k , 1 ≤ k ≤ n, is an assertion that constrains a variable already appearing in any of the α j 's to vary in the range of individuals of a concept defined in B. The O-query
only contains the constraint for the distinguished variable X. Furthermore the language L is multi-grained, i.e. it contains expressions at multiple levels of description granularity. Indeed it is implicitly defined by a declarative bias specification which consists of a finite alphabet ∆ of Datalog predicate names and finite alphabets Γ l (one for each level l of description granularity) of ALC concept names. Note that the α i 's are taken from A and γ j 's are taken from Γ l . We impose L to be finite by specifying some bounds, mainly maxD for the maximum depth of search and maxG for the maximum level of granularity.
The support of an O-query Q ∈ L l w.r.t an AL-log knowledge base B is defined as
where answerset(Q, B) is the set of correct answers to Q w.r.t. B. An answer to Q is a ground substitution θ for the distinguished variable of Q. An answer θ to Q is a correct (resp. computed) answer w.r.t. B if there exists at least one correct (resp. computed) answer to body(Q)θ w.r.t. B. Thus the computation of support relies on query answering in AL-log.
Example 4. The pattern Q 2 turns out to be frequent because it has support supp(Q 2 , B CIA ) = (2/15)% = 13.3% (≥ minsup 2 ). It is to be read as '13.3 % of Middle East countries speak an Indoeuropean language'. The two correct answers to Q 2 w.r.t. B CIA are 'ARM' and 'IR'.
The system AL-QuIn implements the aforementioned levelwise search method for frequent pattern discovery. In particular, candidate patterns of a certain level k (called k-patterns) are obtained by refinement of the frequent patterns discovered at level k−1. In AL-QuIn patterns are ordered according to B-subsumption (which has been proved to fulfill the abovementioned condition of monotonicity [15]). The search starts from the most general pattern in L and iterates through the generation-evaluation cycle for a number of times that is bounded with respect to both the granularity level l (maxG) and the depth level k (maxD).
Example 5. After maxD = 5 search stages, AL-QuIn returns 53 frequent patterns out of 99 candidate patterns compliant with the parameter settings. One of these frequent patterns is Q 2 .
3 Using Pellet in AL-QuIn
In ILP the evaluation of inductive hypotheses (like candidate patterns in frequent pattern discovery) w.r.t. a set of observations (data units) is usually referred to as the coverage test because it checks which observations satisfy (are covered by) the hypothesis. Since evaluation is the most computationally expensive step when inducing hypotheses expressed in (fragments of) first-order logic, an appropriate choice of representation for observations can help speeding up this step. In AL-QuIn the extensional part of Π is partitioned into portions A i each of which refers to an individual a i of C ref . The link between A i and a i is represented with the Datalog literal q(a i ). The pair (q(a i ), A i ) is called observation. Example 6. By assuming MiddleEastCountry as reference concept, the observation A ARM contains Datalog facts such as language('ARM','Armenian',96). language('ARM','Russian',2). concerning the individual 'ARM' whereas the observation A IR consists of facts like language('IR','Turkish',1). language('IR','Kurdish',9). language('IR','Baloch',1). language('IR','Arabic',1). language('IR','Luri',2). language('IR','Persian',58). language('IR','Turkic',26). related to the individual 'IR'.
In ILP the coverage test must take the background knowledge into account. The portion K of B which encompasses the whole Σ and the intensional part (IDB) of Π is considered as background knowledge for AL-QuIn. Therefore proving that an O-query Q covers an observation (q(a i ), A i ) w.r.t. K equals to proving that
Example 7. Checking whether Q 2 covers the observation (q('ARM'), A ARM ) w.r.t. K CIA is equivalent to answering the query
The coverage test for (q('IR'), A IR ) is analogous.
A common practice in ILP is to use a reformulation operator, called saturation [20], to speed-up the coverage test. It enables ILP systems to make background knowledge explicit within the observations instead of implicit and apart from the observations. In the following we will discuss the implementation of the coverage test in AL-QuIn and clarify the role of Pellet in supporting the saturation of observations w.r.t. a OWL-DL background knowledge Σ.
AL-QuIn is implemented with Prolog as usual in ILP. Thus, the actual representation language in AL-QuIn is a kind of Datalog OI [23], i.e. the subset of Datalog = equipped with an equational theory that consists of the axioms of Clark's Equality Theory augmented with one rewriting rule that adds inequality atoms s = t to any P ∈ L for each pair (s, t) of distinct terms occurring in P . Note that concept assertions are rendered as membership atoms, e.g. a : C becomes c C(a).
Example 8. The following query q(X) ← c MiddleEastCountry(X), believes(X,Y), c MonotheisticReligion(Y), believes(X,Z), Y =Z is the Datalog OI rewriting of:
where the absence of a ALC constraint for the variable Z explains the need for the inequality atom.
When implementing the coverage test in AL-QuIn, the goal has been to reduce the reasoning mechanism of AL-log (constrained SLD-resolution) to SLDresolution on Datalog OI . A crucial issue in this mapping is to deal with the satisfiability tests of ALC constraints w.r.t. Σ which are required by constrained SLD-resolution because they are performed by applying the tableau calculus for ALC. The reasoning on the constraint part of O-queries has been replaced by preliminary saturation steps of the observations w.r.t. the background knowledge Σ. By doing so, the observations are completed with concept assertions that can be derived from Σ.
Retrieving all the individuals of a concept C is known in DLs as the retrieval problem [2]. Here, the retrieval is called levelwise because it follows the layering of T : individuals of concepts belonging to the l-th layer T l of T are retrieved all together. Conversely the retrieval for the reference concept is made only once at the beginning of the whole discovery process because it makes explicit knowledge of interest to all the levels of granularity. This makes SLD-refutations of queries in L l work only on extensional structural knowledge at the level l of description granularity.
A Java application, named OWL2Datalog, has been developed to support the saturation of observations w.r.t. a OWL-DL background knowledge Σ in AL-QuIn. To achieve this goal, it supplies the following functionalities:
levelwise retrieval w.r.t. Σ -Datalog OI rewriting of (asserted and derived) concept assertions of Σ The former is implemented by a client for the DIG server Pellet. The latter relies on the former, meaning that the results of the levelwise retrieval are exported to Datalog OI . Note that the translation from OWL-DL to Datalog OI is possible because we assume that all the concepts are named. This means that an equivalence axiom is required for each complex concept in the knowledge base. Equivalence axioms help keeping concept names (used within constrained Datalog clauses) independent from concept definitions.
In this paper we have shown how to use the OWL/DL reasoner Pellet to make an existing ILP system, AL-QuIn, compliant with the latest developments in Knowledge Engineering, i.e. ontologies and DL-based ontology languages. We would like to emphasize that AL-QuIn was originally conceived to deal with background knowledge in the form of taxonomic ontologies but the implementation of this feature was still lacking 5 . Therefore, we have also shown how to use Pellet to make AL-QuIn fulfill its design requirements. More precisely, the Java application OWL2Datalog relies on the reasoning services of Pellet to support the saturation of observations w.r.t. background knowledge in AL-QuIn. In ILP saturation has been mentioned as a way of speeding-up the evaluation of candidate hypotheses. In our case it encompasses a transformation step that compiles DL-based background knowledge down to the usual Datalog-like formalisms of ILP systems. In this respect, the pre-processing method proposed by Kietz [9] to enable legacy ILP systems to work within the framework of the hybrid KR&R system CARIN [12] is related to ours but it lacks an implementation. Analogously, the method proposed in [8] for translating OWL-DL to disjunctive Datalog is far too general with respect to the specific needs of our application. Rather, the proposal of interfacing existing reasoners to combine ontologies and rules [1] is more similar to ours in the spirit.
For the future we plan to implement the functionalities of OWL2Datalog as a plugin for Protégé-2000. Also we intend to compare AL-QuIn with other ILP systems able to deal with ontological background knowledge as soon as they are implemented and deployed.