Motivation and Scope

Rules are currently in the focus within the Semantic Web architecture, and consequently interest and activity in this area has grown rapidly over recent years. They would allow the integration, transformation and derivation of data from numerous sources in a distributed, scalable, and transparent manner. The rules landscape features design aspects of rule markup; engineering of engines, translators, and other tools; standardization efforts, such as the recent Rules Interchange Format (RIF) activity at W3C; and applications. Rules complement and extend ontologies on the Semantic Web. They can be used in combination with ontologies, or as a means to specify ontologies. Rules are also frequently applied over ontologies, to draw inferences, express constraints, specify policies, react to events, discover new knowledge, transform data, etc. Rule markup languages enrich Web ontologies by supporting publishing rules on the Web, exchange rules between different systems and tools, share guidelines and policies, merge and maintain rulebases, and more. Yet, whereas the mark-up language OWL for Semantic Web ontologies is already undergoing the second round of the standardization process at W3C, the debate around a RIF is still ongoing. Because of the great variety in rule languages and rule engine technologies, this format will consist of a core language to be used along with a set of standard and non-standard extensions. These extensions need not all be combinable into a single unified language. As for the expressive power, two directions are followed: monotonic extensions towards full First Order Logic (FOL) and non-monotonic extensions based on the Logic Programming tradition, i.e. on Clausal Logics (CLs). Since the design of OWL has been based on Description Logics (DLs) [1] (more precisely on the SH family of very expressive DLs [13]), non-monotonic rule languages for the Semantic Web will most likely be inspired by old hybrid Knowledge Representation (KR) systems such as AL-log [6] and Carin [17] that integrate DLs and (fragments of) CLs. Such rule formalisms are of interest to us. Other uses of rules, e.g. in OWL 2, are beyond the scope of the paper.

The acquisition of Semantic Web rules is very demanding and can be automated though partially by applying Machine Learning (ML) algorithms. The ML approach known under the name of Inductive Logic Programming (ILP) [28] seems particularly promising for the following reasons. ILP is a form of Concept Learning rooted into Logic Programming. Thus it has been historically concerned with rule induction from examples and background knowledge within the KR framework of Horn Clausal Logic (HCL) and with the aim of prediction. The distinguishing feature of ILP, also with respect to other forms of Concept Learning, is the use of prior knowledge during the induction process. We claim that learning Semantic Web rules can be reformulated as learning rules by having ontologies as prior knowledge. This may motivate an interest of the Semantic Web community in ILP. In this paper we take a critical look at three ILP attempts at learning rules within hybrid DL-CL KR frameworks. From the comparative analysis of them we shall draw general conclusions that can be considered as guidelines for further ILP research of interest to the Semantic Web.

The paper is organized as follows. Section 2 first provides essential information on the ILP methodological apparatus for non informed readers. Section 3 briefly describes three major forms of integration of DLs and CLs. Section 4 provides a state-of-the-art survey of ILP proposals for the hybrid DL-CL formalisms considered in Section 3 and outlines directions of future work. Section 5 concludes the paper with final remarks. Appendixes A and B provide the basic notions of DLs and CLs, respectively.

Learning rules with ILP

Inductive Logic Programming (ILP) was born at the intersection between Concept Learning and Logic Programming. From Concept Learning it has inherited the inferential mechanisms for induction, the most prominent of which is generalization. A distinguishing feature of ILP with respect to other forms of Concept Learning is the use of background knowledge (BK). From Logic Programming it has borrowed the KR framework, i.e. HCL.

In Concept Learning, thus in ILP, generalization is traditionally viewed as search through a partially ordered space of inductive hypotheses [26]. According to this vision, an inductive hypothesis is a clausal theory and the induction of a single clause requires (i) structuring, (ii) searching and (iii) bounding the space of clauses [28]. First we focus on (i) by clarifying the notion of ordering for clauses. An ordering allows for determining which one, between two clauses, is more general than the other. Since partial orders are considered, uncomparable pairs of clauses are admitted. One such ordering is θ-subsumption [29]: Given two clauses C and D, we say that C θ-subsumes D if there exists a substitution θ, such that Cθ ⊆ D1 . Given the usefulness of BK, orders have been proposed that reckon with it. Among them, generalized subsumption [2] is of major interest to this paper: Given two definite clauses C and D standardized apart and a definite program K, we say that C K D iff there exists a ground substitution θ for C such that (i) head(C)θ = head(D)σ and (ii) K ∪ body(D)σ |= body(C)θ where σ is a Skolem substitution for D with respect to {C}∪K. Generalized subsumption is also called semantic generality in contrast to θ-subsumption which is a purely syntactic generality. In the general case, generalized subsumption is undecidable and does not introduce a lattice on a set of clauses. Because of these problems, θ-subsumption is more frequently used in ILP systems. Yet for Datalog generalized subsumption is decidable and admits a least general generalization. Once structured, the space of hypotheses can be searched (ii) by means of refinement operators. A refinement operator is a function which computes a set of specializations or generalizations of a clause according to whether a top-down or a bottom-up search is performed. The two kinds of refinement operator have been therefore called downward and upward, respectively. The definition of refinement operators presupposes the investigation of the properties of the various orderings and is usually coupled with the specification of a declarative bias for bounding the space of clauses (iii). Bias concerns anything which constrains the search for theories, e.g. a language bias specifies syntactic constraints on the clauses in the search space.

Induction with ILP generalizes from individual instances/observations in the presence of BK, finding valid hypotheses. Validity depends on the underlying setting. At present, there exist several formalizations of induction in ILP that can be classified according to the following two orthogonal dimensions: the scope of induction (discrimination vs characterization) and the representation of observations (ground definite clauses vs ground unit clauses) [5]. Discriminant induction aims at inducing hypotheses with discriminant power as required in tasks such as classification. In classification, observations encompass both positive and negative examples. Characteristic induction is more suitable for finding regularities in a data set. This corresponds to learning from positive examples only. The second dimension affects the notion of coverage, i.e. the condition under which a hypothesis explains an observation. In learning from entailment, hypotheses are clausal theories, observations are ground definite clauses, and a hypothesis covers an observation if the hypothesis logically entails the observation. In learning from interpretations, hypotheses are clausal theories, observations are Herbrand interpretations (ground unit clauses) and a hypothesis covers an observation if the observation is a model for the hypothesis.

KR behind Semantic Web Rules

The definition of a rule language for the Semantic Web follows the tradition of KR research on hybrid systems, i.e. those systems which are constituted by two or more subsystems dealing with distinct portions of a single KB by performing specific reasoning procedures [10]. The motivation for investigating and developing such systems is to improve on two basic features of KR formalisms, namely representational adequacy and deductive power, by preserving the other crucial feature, i.e. decidability. Indeed DLs and CLs are FOL fragments incomparable as for the expressiveness and the semantics2 but combinable under certain conditions [30]. In particular, combining DLs with HCL can easily yield to undecidability if the interaction scheme between the DL and the CL part of an hybrid KB does not fulfill the condition of safeness, i.e. does not solve the semantic mismatch between DLs and CLs [27,31].

A comprehensive study of the effects of combining DLs and CLs (more precisely, Horn rules) can be found in [17]. Special attention is devoted to the DL ALCN R. The results of the study can be summarized as follows: (i) answering conjunctive queries over ALCN R TBoxes is decidable, (ii) query answering in ALCN R extended with non-recursive Datalog rules, where both concepts and roles can occur in rule bodies, is also decidable, as it can be reduced to answering a union of conjunctive queries (UCQ)3 , (iii) if rules are recursive, query answering becomes undecidable, (iv) decidability can be regained by disallowing certain combinations of constructors in the logic, and (v) decidability can be regained by requiring rules to be role-safe, where at least one variable from each role literal must occur in some non-DL-atom. The integration framework proposed in [17] and known as Carin is therefore unsafe. Reasoning in Carin is based on constrained SLD-resolution, i.e. an extension of SLD-resolution with a tableau calculus for DLs to deal with DL literals in the rules. Constrained SLD-refutation is a complete and sound method for answering ground queries.

AL-log [6] is a safe hybrid KR system that integrates ALC [34] and Datalog [4]. In particular, variables occurring in the body of rules may be constrained with ALC concept assertions to be used as 'typing constraints'. This makes rules applicable only to explicitly named objects. As in Carin, query answering is decided using the constrained SLD-resolution which however in AL-log is decidable and runs in single non-deterministic exponential time.

The hybrid KR framework of DL+log [32] allows for the tight integration of Datalog ¬∨ [7] with DLs. More precisely, it allows a DL KB to be extended with weakly-safe Datalog ¬∨ rules. The condition of weak safeness allows to overcome the main representational limits of the approaches based on the DL-safeness condition, e.g. the possibility of expressing UCQs, by keeping the integration scheme still decidable. To a certain extent, DL+log is between AL-log and Carin. For DL+log two semantics have been defined: a FOL semantics and a nonmonotonic (NM) semantics. In particular, the latter extends the stable model semantics

ILP for Learning Semantic Web Rules

Hybrid KR systems combining DLs and (fragments of) HCL have very recently attracted some attention in the ILP community.

State of the Art

Only three ILP frameworks have been proposed that adopt a hybrid DL-CL representation for both hypotheses and background knowledge: [33] chooses Carin-ALN , [18] resorts to AL-log, and [20] builds upon SHIQ+log. A comparative analysis of the three is reported in Table 2. They can be considered as attempts at accommodating ontologies in ILP. Indeed, they can deal with ALN , ALC5 , and SHIQ ontologies respectively. Learning Semantic Web rules with ILP can be reformulated as learning rules by having ontologies as prior knowledge. Both proposals have been guided by a similar consideration when extending previous work in ILP to hybrid DL-CL KR frameworks.

Learning in Carin-ALN The framework proposed in [33] focuses on discriminant induction and adopts the ILP setting of learning from interpretations. Hypotheses are represented as Carin-ALN non-recursive rules with a Horn literal in the head that plays the role of target concept. The coverage relation of hypotheses against examples adapts the usual one in learning from interpretations to the case of hybrid Carin-ALN BK. The generality relation between two hypotheses is defined as an extension of generalized subsumption. Procedures for testing both the coverage relation and the generality relation are based on the existential entailment algorithm of Carin. Following [33], Kietz studies the learnability of Carin-ALN , thus providing a pre-processing method which enables ILP systems to learn Carin-ALN rules [16].

Learning in AL-log In [18], hypotheses are represented as constrained Datalog clauses that are linked, connected (or range-restricted), and compliant with the bias of Object Identity (OI) 6 . As opposite to [33], this framework is general, meaning that it is valid whatever the scope of induction (description/prediction) is. Therefore the literal in the head of hypotheses represents a concept to be either discriminated from others (discriminant induction) or characterized (characteristic induction). The generality relation for one such hypothesis language is an adaptation of generalized subsumption, named B-subsumption, to the AL-log KR framework. It gives raise to a quasi-order and can be checked with a decidable procedure based on constrained SLD-resolution [22]. Coverage relations for both ILP settings of learning from interpretations and learning from entailment have been defined on the basis of query answering in AL-log [19]. As opposite to [33], the framework has been implemented in an ILP system [24]. More precisely, an instantiation of it for the case of characteristic induction from interpretations has been considered. Indeed, the system supports a variant of a very popular data mining task -frequent pattern discovery -where rich prior conceptual knowledge is taken into account during the discovery process in order to find patterns at multiple levels of description granularity. The search through the space of patterns represented as unary conjunctive queries in AL-log and organized according to B-subsumption is performed by applying an ideal downward refinement operator [23].

Learning in SHIQ+log

The ILP framework presented in [20] represents hypotheses as SHIQ+log rules restricted to positive Datalog and organizes them according to a generality ordering inspired by generalized subsumption. The resulting hypothesis space can be searched by means of refinement operators either top-down or bottom-up. Analogously to [18], this framework encompasses both scopes of induction but, differently from [18], it assumes the ILP setting of learning from interpretations only. Both the coverage relation and the generality relation boil down to query answering in SHIQ+log, thus can be reformulated as satisfiability problems. Compared to [33] and [18], this framework shows an added value which can be summarized as follows. First, it relies on a more expressive DL, i.e. SHIQ. Second, it allows for inducing definitions for new DL concepts, i.e. rules with a SHIQ literal in the head. Third, it adopts a tighter form of integration between the DL and the CL part, i.e. the weakly-safe one. Learning in Carin-ALN [33] Learning in AL-log [18] Learning in SHIQ+log [20] prior

Directions of Research

From the comparative analysis of the ILP frameworks reviewed in Section 4.1, a common feature emerges: All proposals resort to Buntine's generalized subsumption and extend it in a non-trivial way. This choice is due to the fact that, among the semantic generality orders in ILP, generalized subsumption applies only to definite clauses, therefore suits well the hypothesis language in all three frameworks. Following these guidelines, new ILP frameworks can be designed to deal with more or differently expressive hybrid DL-CL languages according to the DL chosen (e.g., learning Carin-ALCN R rules), or the clausal language chosen (e.g., learning recursive Carin rules), or the integration scheme (e.g., learning Carin rules with DL-literals in the head). An important requirement will be the definition of a semantic generality relation for hypotheses to take into account the background knowledge. Of course, generalized subsumption may turn out to be not suitable for these upcoming ILP frameworks, e.g. for the case of learning disjunctive DL+log rules. Speaking of which, the inclusion of nonmonotonic features like negation and disjunction -admissible in DL+log full -into the language for hypotheses and background knowledge will strengthen the ability of the ILP frameworks to deal with incomplete knowledge by performing an inductive form of commonsense reasoning. One such ability can turn out to be useful in the Semantic Web, and complementary to reasoning with uncertainty and under inconsistency. Also it would be interesting to investigate how the nature of rules (i.e., the intended context of usage) may impact the learning process as for the scope of induction and other variables in the learning problem statement. E.g., the problem of learning AL-log rules for classification purposes differ greatly from the apparently similar learning problem faced in [24].

Besides theoretical issues, most future work will have to be devoted to implementation and application. When moving to practice, issues like efficiency and scalability become of paramount importance. These concerns may drive the attention of ILP research towards less expressive hybrid KR frameworks in order to gain in tractability, e.g. instantiations of DL+log with DL-Lite [3]. Applications can come out of some of the many use cases for Semantic Web rules specified by the RIF W3C Working Group. Considering the current trend to have within ontologies rather than on top of ontologies, it is worthwhile to explore the possibility of learning rules for ontology evolution according to the proof-of-concept scenario described in [21].

Final remarks

Building rules on top of ontologies for the Semantic Web poses several challenges not only to KR researchers investigating suitable hybrid DL-CL formalisms but also to the ML community which has been historically interested in application areas where the Knowledge Acquisition bottleneck is particularly severe.

In this paper, we have revised the ML literature addressing the problem of learning hybrid DL-CL rules. Only three ILP works have been found that propose a solution to this problem [33,18,20]. They adopt Carin-ALN , AL-log and SHIQ+log as KR framework, respectively. Note that matching Closely related to DL-CL KR systems are the hybrid formalims arising from the study of many-sorted logics, where a FOL language is combined with a sort language which can be regarded as an elementary DL [8]. In this respect the study of a sorted downward refinement [9] can be also considered as a contribution to the problem of interest to this paper. Finally, some work as been done on discovering frequent association patterns [15] in the form of DL-safe rules [27].

A Description Logics

DLs are a family of decidable FOL fragments that allow for the specification of knowledge in terms of classes (concepts), binary relations between classes (roles), and instances (individuals) [1]. Complex concepts can be defined from atomic concepts and roles by means of constructors (see Table 3). E.g., concept descriptions in the basic DL AL are formed according to only the constructors of atomic negation, concept conjunction, value restriction, and limited existential restriction. The DLs ALC and ALN are members of the AL family [34]. The former extends AL with (arbitrary) concept negation (also called complement and equivalent to having both concept union and full existential restriction), whereas the latter with number restriction. The DL ALCN R adds to the constructors inherited from ALC and ALN a further one: role intersection (see Table 3). Conversely, in the DL SHIQ [14] it is allowed to invert roles and to express qualified number restrictions of the form ≥ nS.C and ≤ nS.C where S is a simple role (see Table 3). Also transitivity holds for roles.

A A I ⊆ ∆ I (abstract) role R R I ⊆ ∆ I × ∆ I (abstract) inverse role R − (R I ) − (abstract) individual a a I ∈ ∆ I concept negation ¬C ∆ I \ C I concept intersection C1 C2 C I 1 ∩ C I 2 concept union C1 C2 C I 1 ∪ C I 2 value restriction ∀R.C {x ∈ ∆ I | ∀y (x, y) ∈ R I → y ∈ C I } existential restriction ∃R.C {x ∈ ∆ I | ∃y (x, y) ∈ R I ∧ y ∈ C I } at least number restriction ≥ nR {x ∈ ∆ I | |{y|(x, y) ∈ R I }| ≥ n} at most number restriction ≤ nR {x ∈ ∆ I | |{y|(x, y) ∈ R I }| ≤ n} at least qualif. number restriction ≥ nS.C {x ∈ ∆ I | |{y ∈ C I |(x, y) ∈ S I }| ≥ n} at most qualif. number restriction ≤ nS.C {x ∈ ∆ I | |{y ∈ C I |(x, y) ∈ S I }| ≤ n} role intersection R1 R2 R I 1 ∩ R I 2 concept equivalence axiom C1 ≡ C2 C I 1 = C I 2 concept subsumption axiom C1 C2 C I 1 ⊆ C I 2 role equivalence axiom R ≡ S R I = S I role inclusion axiom R S R I ⊆ S I

A DL knowledge base (KB) can state both is-a relations between concepts (axioms) and instance-of relations between individuals (resp. couples of individuals) and concepts (resp. roles) (assertions). Concepts and axioms form the so-called TBox (Terminological Box, or intensional part of a DL KB) whereas individuals and assertions form the so-called ABox (Assertional Box, or extensional part of a DL KB). A SHIQ KB encompasses also a RBox (Role Box) which consists of axioms concerning abstract roles. The direct semantics of DLs is shown in Table 3. An interpretation I = (∆ I , • I ) for a DL KB consists of a domain ∆ I and a mapping function • I . Individuals are mapped to elements of ∆ I such that a I = b I if a = b (Unique Names Assumption (UNA). Yet in SHIQ UNA does not hold by default [12]. Thus individual equality (inequality) assertions may appear in a SHIQ KB (see Table 3). Also the KB represents many different interpretations, i.e. all its models. This is coherent with the Open World Assumption (OWA) that holds in FOL semantics. The main reasoning task for a DL KB is the consistency check that is performed by applying decision procedures based on tableau calculus. Decidability of reasoning is crucial in DLs.

B Clausal Logics

The basic element in Clausal Logics (CLs) is the atom of the form p(t i , . . . , t ki ) such that each p is a predicate symbol and each t j is a term. A term is either a constant or a variable or a more complex term obtained by applying a functor to simpler term. Constant, variable, functor and predicate symbols belong to mutually disjoint alphabets. A literal is an atom either negated or not. A clause is a universally quantified disjunction of literals. Usually the universal quantifiers are omitted to simplify notation, therefore a clause is a disjunctive formula like [25] and deductive databases [4].

In the logic programming context, the model-theoretic semantics of HCL is based on the notion of Herbrand interpretation. The corresponding prooftheoretic semantics is based on the Closed World Assumption (CWA) and is the starting point for a deductive reasoning mechanism, i.e. SLD-resolution, which is sound and complete by refutation.

In the deductive database context, a version of HCL free from functors and recursion leads to Datalog [4]. The main reasoning task in Datalog is query answering. A query Q to a Datalog program D is a Datalog clause with n = 0 and m > 0. An answer to a query Q is a substitution θ for the variables of Q. An answer is correct with respect to the Datalog program D if D |= Qθ. The answer set to a query Q is the set of answers to Q that are correct w.r.t. D and such that Qθ is ground. Answers are computed by SLD-refutation. Disjunctive Datalog (Datalog ∨ ) is a variant of Datalog where disjunctions may appear in the rule heads [7]. Advanced versions (Datalog ¬∨ ) also allow for negated literals in the rule bodies, which can be handled according to a semantics for negation in CL, e.g. stable model semantics [11]. Under such semantics, a Datalog ¬∨ program may have several alternative models (but possibly none), each corresponding to a possible view of the reality.