Combining Logic Programming with Description Logics and Machine Learning for the Semantic Web

Abstract

In this paper we consider an extension of Logic Programming that tackles the Semantic Web challenge of acquiring rules combined with ontologies. To face this bottleneck problem we propose a framework that resorts to the expressive and deductive power of DL+log and adopts the methodological apparatus of Inductive Logic Programming.

Introduction

Combining rules and ontologies is a hot topic in the (Semantic) Web area as testified by the intense activity and the standardization efforts of the Rule Interchange Format working group at W3C. Yet the debate around a unified language for (Semantic) Web rules is still open. Indeed, combining rules and ontologies raises several issues in Knowledge Representation (KR) due to the many differences between the underlying logics, Clausal Logics (CLs) [ 17 ] and Description Logics (DLs) [ 1 ] respectively. Among the many recent KR proposals, DL+log [ 23 ] is a very powerful framework that allows for the tight integration of DLs and disjunctive Datalog with negation (Datalog¬∨) [ 7 ]. A point in favour of DL+log is its decidability for many DLs, notably for SHIQ [ 12 ]. Since the design of OWL has been based on the SH family of very expressive DLs [ 11 ], SHIQ+log is a good candidate for investigation in the Semantic Web context.

The upcoming standard rule language for the Semantic Web, if well-founded from the KR viewpoint, will be equipped with reasoning algorithms. In KR tradition deductive reasoning is the most widely studied. Yet, other forms of reasoning will become necessary. E.g., acquiring and maintaining Semantic Web rules is very demanding and can be automated though partially by applying Machine Learning algorithms. In this paper, we consider a decidable instantiation of DL+log obtained by choosing SHIQ for the DL part and Datalog¬ for the CL part, and face the problem of defining inductive reasoning mechanisms on it. To solve the problem, we propose to resort to the methodological apparatus of that form of Machine Learning known under the name of Inductive Logic Programming (ILP) [ 19 ]. We extend some known ILP techniques to SHIQ + log¬ and illustrate them with examples relevant to the Semantic Web context.

The paper is organized as follows. Section 2 briefly introduces hybrid DL-CL formalisms and ILP. Section 3 introduces the KR framework of DL+log. Section 4 defines the ILP framework for inducing SHIQ+log¬ rules. Section 5 provides a comparative analysis of our proposal with related work. Section 6 concludes the paper with final remarks. 2 2.1

Background

Logic Programming and Description Logics

Description Logics (DLs) are a family of KR formalims 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 1). 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. The former extends AL with (arbitrary) concept negation (or complement), 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 1). Conversely, in the DL SHIQ [ 12 ] 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 1).

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 TBox whereas individuals and assertions form the ABox. A SHIQ KB encompasses also a RBox which consists of axioms concerning abstract roles. The semantics of DLs is usually defined through a mapping to First Order Logic (FOL) [ 2 ]. An interpretation I = (ΔI , ·I ) for a DL KB consists of a non-empty domain ΔI and a mapping function ·I . In particular, individuals are mapped to elements of ΔI such that aI 6= bI if a 6= b (Unique Names Assumption (UNA) [ 21 ]). Yet in SHIQ UNA does not hold by default [ 10 ]. Thus individual equality (inequality) assertions may appear in a SHIQ KB (see Table 1). 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.

The integration of DLs and Logic Programming 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 [ 8 ], and gives raise to KR systems that will be referred to as DL-CL hybrid systems in the rest of the paper. The motivation for investigating and developing such systems is to improve on representational adequacy and deductive power by preserving decidability. In particular, combining DLs with CLs can easily yield to undecidability if the interface between bottom (resp. top) concept ⊥ (resp. >) ∅ (resp. ΔI ) atomic concept A AI ⊆ ΔI (abstract) role R RI ⊆ ΔI × ΔI (abstract) inverse role R− (RI )− (abstract) individual a aI ∈ ΔI

concept negation concept intersection

concept union value restriction existential restriction at least number restriction at most number restriction at least qualif. number restriction at most qualif. number restriction

role intersection concept equivalence axiom concept subsumption axiom role equivalence axiom role inclusion axiom concept assertion

role assertion individual equality assertion individual inequality assertion

¬C C1 u C2 C1 t C2 ∀R.C ∃R.C ≥ nR ≤ nR ≥ nS.C ≤ nS.C R1 u R2 C1 ≡ C2 C1 v C2 R ≡ S R v S a : C ha, bi : R a ≈ b a 6≈ b ΔI \ CI C1I ∩ C2I C1I ∪ C2I {x ∈ ΔI | ∀y (x, y) ∈ RI → y ∈ CI } {x ∈ ΔI | ∃y (x, y) ∈ RI ∧ y ∈ CI } {x ∈ ΔI | |{y|(x, y) ∈ RI }| ≥ n} {x ∈ ΔI | |{y|(x, y) ∈ RI }| ≤ n} {x ∈ ΔI | |{y ∈ CI |(x, y) ∈ SI }| ≥ n} {x ∈ ΔI | |{y ∈ CI |(x, y) ∈ SI }| ≤ n} R1I ∩ R2I C1I = C2I C1I ⊆ C2I RI = SI RI ⊆ SI aI ∈ CI (aI , bI ) ∈ RI aI = bI aI 6= bI them is not reduced. In [ 14 ] the family Carin of languages combining any DL and HCL is presented. Among the many important results of this study, it is proved that query answering in a logic obtained by extending ALCN R with nonrecursive Datalog rules, where both concepts and roles can occur in rule bodies, is decidable. Query answering is decided using constrained SLD-resolution, i.e. an extension of SLD-resolution with a modified version of tableau calculus. Another DL-CL hybrid system is AL-log [ 6 ] that integrates ALC [ 26 ] and Datalog [ 4 ] by constraining the variables occurring in the body of rules with ALC concept assertions. Constrained SLD-resolution for AL-log is decidable and offers a complete and sound method for answering ground queries by refutation. Besides decidability, another relevant issue is DL-safeness of hybrid DL-CL systems [ 22 ]. A safe interaction between the DL and the CL part of an hybrid KB allows to solve the semantic mismatch between DLs and CLs due to the different inferences that can be made under OWA and CWA respectively. In this respect, AL-log is DL-safe whereas Carin is not. 2.2

Logic Programming and Machine Learning

The research area born at the intersection of Logic Programming and Machine Learning, more precisely Concept Learning [ 18 ], is known under the name of Inductive Logic Programming (ILP) [ 19 ]. From Logic Programming ILP has borrowed the KR framework, i.e. Horn Clausal Logic (HCL). From Concept Learning it has inherited the inferential mechanisms for induction, the most prominent of which is generalization characterized as search through a partially ordered space of hypotheses. According to this vision, in ILP a hypothesis is a clausal theory (i.e., a set of rules) and the induction of a single clause (rule) requires (i) structuring, (ii) searching and (iii) bounding the space of hypotheses. 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. Actually quasi-orders are considered, therefore uncomparable pairs of clauses are admitted. One such ordering is θ-subsumption [ 20 ]: Given two clauses C and D, we say that C θ-subsumes D if there exists a substitution θ, such that Cθ ⊆ D. Given the usefulness of Background Knowledge (BK) in ILP, orders have been proposed that reckon with it, e.g. Buntine’s generalized subsumption [ 3 ]. Generalized subsumption only applies to definite clauses and the BK should be a definite program. 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 quasi-orders 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 clausal logic 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 (or from implications), 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.

Combining LP and DLs with DL+log The KR framework of DL+log [ 23 ] allows for the tight integration of DLs [ 1 ] and Datalog¬∨ [ 7 ]. 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 conjunctive queries (CQ) and unions of conjunctive queries (UCQ)1, by keeping the integration scheme still decidable. To a certain extent, DL+log is between AL-log [ 6 ] and Carin [ 14 ]. 3.1

Syntax

Formulas in DL+log are built upon three mutually disjoint predicate alphabets: an alphabet of concept names PC , an alphabet of role names PR, and an alphabet of Datalog predicates PD. We call a predicate p a DL-predicate if either p ∈ PC or p ∈ PR. Then, we denote by C a countably infinite alphabet of constant names. An atom is an expression of the form p(X), where p is a predicate of arity n and X is a n-tuple of variables and constants. If no variable symbol occurs in X, then p(X) is called a ground atom (or fact ). If p ∈ PC ∪ PR, the atom is called a DL-atom, while if p ∈ PD, it is called a Datalog atom.

Given a description logic DL, a DL+log KB B is a pair (Σ, Π), where Σ is a DL KB and Π is a set of Datalog¬∨ rules, where each rule R has the form p1(X1) ∨ . . . ∨ pn(Xn) ← r1(Y1), . . . , rm(Ym), s1(Z1), . . . , sk(Zk), ¬u1(W1), . . . , ¬uh(Wh) with n, m, k, h ≥ 0, each pi(Xi), rj (Yj ), sl(Zl), uk(Wk) is an atom and: – each pi is either a DL-predicate or a Datalog predicate; – each rj , uk is a Datalog predicate; – each sl is a DL-predicate; – (Datalog safeness) every variable occurring in R must appear in at least one of the atoms r1(Y1), . . . , rm(Ym), s1(Z1), . . . , sk(Zk); – (weak safeness) every head variable of R must appear in at least one of the atoms r1(Y1), . . . , rm(Ym).

We remark that the above notion of weak safeness allows for the presence of variables that only occur in DL-atoms in the body of R. On the other hand, the notion of DL-safeness can be expressed as follows: every variable of R must appear in at least one of the atoms r1(Y1), . . . , rm(Ym). Therefore, DL-safeness forces every variable of R to occur also in the Datalog atoms in the body of R, while weak safeness allows for the presence of variables that only occur in DL-atoms in the body of R. Without loss of generality, we can assume that in a DL+log KB (Σ, Π) all constants occurring in Σ also occur in Π. 1 A Boolean UCQ over a predicate alphabet P is a first-order sentence of the form ∃X.conj1(X) ∨ . . . ∨ conjn(X), where X is a tuple of variable symbols and each conji(X) is a set of atoms whose predicates are in P and whose arguments are either constants or variables from X. A Boolean CQ corresponds to a Boolean UCQ in the case when n = 1.

Example 1. Let us consider a DL+log KB B (adapted from [ 23 ]) integrating the following DL-KB Σ (ontology about persons) [A1] PERSON v ∃ FATHER−.MALE [A2] MALE v PERSON [A3] FEMALE v PERSON [A4] FEMALE v ¬MALE

MALE(Bob)

PERSON(Mary)

PERSON(Paul) FATHER(John,Paul)

and the following Datalog¬∨ program Π (rules about students): [R1] boy(X) ← enrolled(X,c1,bsc), PERSON(X), ¬girl(X) [R2] girl(X) ← enrolled(X,c2,msc), PERSON(X) [R3] boy(X)∨ girl(X) ← enrolled(X,c3,phd), PERSON(X) [R4] FEMALE(X) ← girl(X) [R5] MALE(X) ← boy(X) [R6] man(X) ← enrolled(X,c3,phd), FATHER(X,Y) enrolled(Paul,c1,bsc) enrolled(Mary,c1,bsc) enrolled(Mary,c2,msc) enrolled(Bob,c3,phd) enrolled(John,c3,phd) Note that the rules mix DL-literals and Datalog-literals. Notice that the variable Y in rule R6 is weakly-safe but not DL-safe, since Y does not occur in any Datalog predicate in R6.

3.2 Semantics

For DL+log two semantics have been defined: a first-order logic (FOL) semantics and a nonmonotonic (NM) semantics. In particular, the latter extends the stable model semantics of Datalog¬∨ [ 9 ]. According to it, DL-predicates are still interpreted under OWA, while Datalog predicates are interpreted under CWA. Notice that, under both semantics, entailment can be reduced to satisfiability. In a similar way, it can be seen that CQ answering can be reduced to satisfiability in DL+log. Consequently, Rosati [ 23 ] concentrates on the satisfiability problem in DL+log KBs. It has been shown that, when the rules are positive disjunctive, the above two semantics are equivalent with respect to the satisfiability problem. In particular, FOL-satisfiability can always be reduced (in linear time) to NMsatisfiability. Hence, the satisfiability problem under the NM semantics is in the focus of interest.

Example 2. With reference to Example 1, it can be easily verified that all NMmodels for B satisfy the following ground atoms: – boy(Paul) (since rule R1 is always applicable for {X/Paul} and R1 acts like a default rule, which can be read as follows: if X is a person enrolled in course c1, then X is a boy, unless we know for sure that X is a girl); – girl(Mary) (since rule R2 is always applicable for {X/Mary}); – boy(Bob) (since rule R3 is always applicable for {X/Bob}, and, by rule R4, the conclusion girl(Bob) is inconsistent with Σ); – MALE(Paul) (due to rule R5); – FEMALE(Mary) (due to rule R4).

Notice that B |=NM FEMALE(Mary), while Σ 6|=F OL FEMALE(Mary). In other words, adding rules has indeed an effect on the conclusions one can draw about DL-predicates. Moreover, such an effect also holds under the FOL semantics of DL+log-KBs, since it can be verified that B |=F OLFEMALE(Mary) in this case. 3.3

Reasoning

The problem statement of satisfiability for finite DL+log KBs relies on the following problem known as the Boolean CQ/UCQ containment problem2 in DLs: Given a DL-TBox T , a Boolean CQ Q1 and a Boolean UCQ Q2 over the alphabet PC ∪ PR, Q1 is contained in Q2 with respect to T , denoted by T |= Q1 ⊆ Q2, iff, for every model I of T , if Q1 is satisfied in I then Q2 is satisfied in I. The algorithm NMSAT-DL+log for deciding NM-satisfiability of DL+log KBs looks for a guess (GP , GN ) of the Boolean CQs in the DL-grounding of Π, denoted as grp(Π), that is consistent with the DL-KB Σ (Boolean CQ/UCQ containment problem) and such that the Datalog¬∨ program Π(GP , GN ) has a stable model. Details of how obtaining grp(Π) and Π(GP , GN ) can be found in [ 23 ].

The decidability of reasoning in DL+log, thus of ground query answering, depends on the decidability of the Boolean CQ/UCQ containment problem in DL. Consequently, ground queries can be answered by applying NMSAT-DL+log. Theorem 1 [ 23 ] For every description logic DL, satisfiability of DL+log-KBs (both under FOL semantics and under NM semantics) is decidable iff Boolean CQ/UCQ containment is decidable in DL.

Corollary 1. Given a DL+log KB (Σ, Π) and a ground atom α, (Σ, Π) |= α iff (Σ, Π ∪ {← α}) is unsatisfiable.

From Theorem 1 and from previous results on query answering and query containment in DLs, it follows the decidability of reasoning in several instantiations of DL+log. Since SHIQ is the most expressive DL for which the Boolean CQ/UCQ containment is decidable [ 10 ], we consider SHIQ+log¬ (i.e. SHIQ extended with weakly-safe Datalog¬ rules) as the KR framework in our study of ILP for the Semantic Web. 2 This problem was called existential entailment in [ 14 ]. We consider the task of inducing new SHIQ+log¬ rules from an already existing SHIQ+log¬ KB. At this stage of work the scope of induction does not matter. Therefore the term ’observation’ is to be preferred to the term ’example’. We choose to work within the setting of learning from interpretations which requires an observation to be represented as a set of ground unit clauses.

We assume that the data are represented as a SHIQ+log¬ KB B where the intensional part K (i.e., the TBox T plus the set ΠR of rules) plays the role of background knowledge and the extensional part (i.e., the ABox A plus the set ΠF of facts) contributes to the definition of observations. Therefore ontologies may appear as input to the learning problem of interest.

Example 3. Suppose we have a SHIQ+log¬ KB (adapted from [ 23 ]) consisting of the following intensional knowledge K: [A1] RICHuUNMARRIED v ∃ WANTS-TO-MARRY−.> [R1] RICH(X) ← famous(X), ¬ scientist(X) and the following extensional knowledge F :

UNMARRIED(Mary)

UNMARRIED(Joe)

famous(Mary) famous(Paul) famous(Joe) scientist(Joe) that can be split into FJoe = {UNMARRIED(Joe), famous(Joe), scientist(Joe)}, FMary = {UNMARRIED(Mary), famous(Mary)}, and FPaul = {famous(Paul)}.

The language L of hypotheses must allow for the generation of SHIQ+log¬ rules starting from three disjoint alphabets PC (L) ⊆ PC (B), PR(L) ⊆ PR(B), and PD(L) ⊆ PD(B). More precisely, we consider linked3 and range-restricted4 weakly-safe Datalog¬ clauses of the form

p(X) ← r1(Y1), . . . , rm(Ym), s1(Z1), . . . , sk(Zk), ¬u1(W1), . . . , ¬uh(Wh) where the unique literal p(X) in the head represents the target predicate, denoted as c if p is a Datalog-predicate and as C if p is a SHIQ-predicate. In the following we provide examples for these two cases of rule learning, one aimed at inducing c(X) ← rules and the other C(X) ← rules. The former kind of rule will enrich the Datalog part of the KB, whereas the latter will extend the DL part (i.e., the input ontology). 3 A clause H is linked if each literal li ∈ H is linked. A literal li ∈ H is linked if at least one of its terms is linked. A term t in some literal li ∈ H is linked with linking-chain of length 0, if t occurs in head(H), and with linking-chain of length d + 1, if some other term in li is linked with linking-chain of length d. The link-depth of a term t in li is the length of the shortest linking-chain of t. 4 A clause H is range-restricted if each variable occurring in head(H) also occur in body(H).

Example 4. Suppose that the Datalog-predicate happy is the target predicate and the set PD(Lhappy) ∪ PC (Lhappy) ∪ PR(Lhappy) = {famous/1} ∪ {RICH/1} ∪ {WANTS-TO-MARRY/2} provides the building blocks for the language Lhappy. The following SHIQ+log¬ rules happy can be considered hypotheses for the target predicate happy. bNeoltoengthinagt tHo3hLappy is weakly-safe.

Example 5. Suppose now that the target predicate is the DL-predicate LONER. If LLONER is defined over PD(LLONER) ∪ PC (LLONER) = {famous/1, scientist/1} ∪ {UNMARRIED/1}, then the following SHIQ+log¬ rules

LONER(X) ← scientist(X) LONER(X) ← scientist(X), UNMARRIED(X)

LONER(X) ← ¬famous(X) belong to LLONER and represent hypotheses for the target predicate LONER.

In order to support with ILP techniques the induction of SHIQ+log¬ rules, the language L of hypotheses needs to be equipped with a generality order , and a coverage relation covers so that (L, ) is a search space and covers defines the mappings from ( , ) to the set O of observations. The next subsections are

L devoted to these issues. 4.1

The hypothesis ordering

The definition of a generality order for hypotheses in L can disregard neither the peculiarities of SHIQ+log¬ nor the methodological apparatus of ILP. One issue arises from the presence of NAF literals (i.e., negated Datalog literals) both in the background knowledge and in the language of hypotheses. As pointed out in [ 25 ], rules in normal logic programs are syntactically regarded as Horn clauses by viewing the NAF-literal ¬p(X) as an atom not p(X) with the new predicate not p. Then any result obtained on Horn logic programs is directly carried over to normal logic programs. Assuming one such treatment of NAF literals, we propose to adapt generalized subsumption [ 3 ] to the case of SHIQ+log¬ rules. The resulting generality relation will be called K-subsumption, briefly K, from now on. We provide a characterization of K that relies on the reasoning tasks known for DL+log and from which a test procedure can be derived. Definition 1. Let H1, H2 ∈ L be two hypotheses standardized apart, K a background knowledge, and σ a Skolem substitution for H2 with respect to {H1} ∪ K. We say that H1 K H2 iff there exists a ground substitution θ for H1 such that (i) head(H1)θ = head(H2)σ and (ii) K ∪ body(H2)σ |= body(H1)θ.

Note that condition (ii) is a variant of the Boolean CQ/UCQ containment problem because body(H2)σ and body(H1)θ are both Boolean CQs. The difference between (ii) and the original formulation of the problem is that K encompasses not only a TBox but also a set of rules. Nonetheless this variant can be reduced to the satisfiability problem for finite SHIQ+log¬ KBs. Indeed the skolemization of body(H2) allows to reduce the Boolean CQ/UCQ containment problem to a CQ answering problem5. Due to the aforementioned link between CQ answering and satisfiability, checking (ii) can be reformulated as proving that the KB (T , ΠR ∪ body(H2)σ ∪ {← body(H1)θ}) is unsatisfiable. Once reformulated this way, (ii) can be solved by applying the algorithm NMSAT-DL+log. Example 6. Let us consider the hypotheses H1happy H2happy happy(A) ← RICH(A) happy(X) ← famous(X) reported in Example 4 up to variable renaming. We want to check whether H1happy K H2happy holds. Let σ = {X/a} a Skolem substitution for H2happy with respect to K ∪ H1happy and θ = {A/a} a ground substitution for H1happy. The condition (i) is immediately verified. The condition (ii) K ∪ {famous(a)} |= RICH(a) is nothing else that a ground query answering problem in SHIQ+log. It can be proved that the query RICH(a) can not be satisfied because the rule R1 is not applicable for a. Thus, H1happy 6 K H2happy. Since H2happy 6 K H1happy, the two hypotheses are incomparable under K-subsumption. Conversely, it can be proved that H2happy K H3happy but not viceversa.

Example 7. Let us consider the hypotheses H1LONER H2LONER

LONER(A) ← scientist(A)

LONER(X) ← scientist(X),UNMARRIED(X) reported in Example 5 up to variable renaming. We want to check whether H1LONER K H2LONER holds. Let σ = {X/a} a Skolem substitution for H2LONER with respect to K ∪ H1LONER and θ = {A/a} a ground substitution for H1LONER. The condition (i) is immediately verified. The condition

(ii) K ∪ {scientist(a), UNMARRIED(a)} |= {scientist(a)} is a ground query answering problem in SHIQ+log. It can be easily proved that all NM-models for K ∪ {scientist(a), UNMARRIED(a)} satisfy scientist(a). Thus, H1LONER K H2LONER. The viceversa does not hold. Also it can be proved that H3LONER is incomparable with both H1LONER and H2LONER under K-subsumption. It is straightforward to see that the decidability of K-subsumption follows from the decidability of SHIQ+log¬. It can be proved that K is a quasi-order (i.e. it is a reflexive and transitive relation) for SHIQ+log¬ rules, therefore the space of hypotheses can be searched by refinement operators. 5 Since UNA does not necessarily hold in SHIQ, the (Boolean) CQ/UCQ containment problem for SHIQ boils down to the (Boolean) CQ/UCQ answering problem. The definition of a coverage relation depends on the representation choice for observations. An observation oi ∈ O is represented as a couple (p(ai), Fi) where Fi is a set containing ground facts concerning the tuple of individuals ai. We assume K ∩ O = ∅.

Definition 2. Let H ∈ L be a hypothesis, K a background knowledge and oi ∈ O an observation. We say that H covers oi under interpretations w.r.t. K iff K ∪ Fi ∪ H |= p(ai).

Note that the coverage test can be reduced to query answering in SHIQ+log¬ KBs which in its turn can be reformulated as a satisfiability problem of the KB. Example 8. The hypothesis H3happy mentioned in Example 4 covers the observation oMary = (happy(Mary), FMary) because K ∪ FMary ∪ H3happy |= happy(Mary). Indeed, all NM-models for B = K ∪ FMary ∪ H3happy satisfy: – famous(Mary) (trivial!); – ∃ WANTS-TO-MARRY−.>(Mary), due to the axiom A1 and to the fact that both RICH(Mary) and UNMARRIED(Mary) hold in every model of B; – happy(Mary), due to the above conclusions and to the rule R1. Indeed, since ∃WANTS-TO-MARRY−.>(Mary) holds in every model of B, it follows that in every model there exists a constant x such that WANTS-TO-MARRY(x,Mary) holds in the model, consequently from rule R1 it follows that happy(Mary) also holds in the model.

Note that H3happy does not cover the observations oJoe = (happy(Joe), FJoe) and oPaul = (happy(Paul), FPaul). More precisely, K ∪ FJoe ∪ H3happy 6|= happy(Joe) because scientist(Joe) holds in every model of B = K ∪ FJoe ∪ H3happy, thus making the rule R1 not applicable for {X/Joe}, therefore RICH(Joe) not derivable. Finally, K ∪ FPaul ∪ H3happy 6|= happy(Paul) because UNMARRIED(Paul) is not forced to hold in every model of B = K ∪ FPaul ∪ H3happy, therefore ∃WANTS-TO-MARRY−.>(Paul) is not forced by A1 to hold in every such model.

It can be proved that H1happy covers oMary and oPaul, while H2happy all the three observations.

Example 9. With reference to Example 5, the hypothesis H3LONER does not cover the observation oMary = (LONER(Mary), FMary) because all NM-models for B = K ∪ FMary ∪ H3LONER do satisfy famous(Mary). Note that it does not cover the observations oPaul = (LONER(Paul), FPaul) and oJoe = (LONER(Joe), FJoe) for analogous reasons. It can be proved that H2LONER covers oMary and oJoe while H1LONER all three observations. 5

Related Work

Two ILP frameworks have been proposed so far that adopt a hybrid DL-CL representation for both hypotheses and background knowledge. The framework proposed in [ 24 ] 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 [ 24 ], Kietz studies the learnability of Carin-ALN , thus providing a pre-processing method which enables ILP systems to learn CarinALN rules [ 13 ]. In [ 15 ], the representation and reasoning means come from AL-log. Hypotheses are represented as constrained Datalog clauses. Note that this framework is general, meaning that it is valid whatever the scope of induction is. The generality relation for one such hypothesis language is an adaptation of generalized 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. 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. As opposite to [ 24 ], the framework has been partially implemented in an ILP system [ 16 ] that supports a variant of frequent pattern discovery where rich prior conceptual knowledge is taken into account in order to find patterns at multiple levels of description granularity.

The ILP framework presented in this paper differs from [ 24 ] and [ 15 ] in several respects as summarized in Table 2, notably the following ones. 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 relies on a more expressive yet decidable CL, i.e. Datalog¬. Forth, it adopts a tighter form of integration between the DL and the CL part, i.e. the weakly-safe one. Similarities also emerge from Table 2 such as the use of a semantic ordering for hypotheses in order to accommodate ontologies in ILP. Note that generalized subsumption is chosen for adaptation in all three ILP frameworks because definite clauses, though enriched with DL and NAF literals, are still used. 6

Final Remarks

In this paper, we have proposed an ILP framework built upon SHIQ+log¬. Indeed, well-known ILP techniques for induction have been reformulated in terms of the deductive reasoning mechanims of DL+log. Notably, we have defined a decidable generality ordering, K-subsumption, for SHIQ+log¬ rules on the basis of the decidable algorithm NMSAT-SHIQ+log. We would like to point out that the ILP framework proposed is suitable for inductive reasoning in the context of the Semantic Web for two main reasons. First, it adopts the DL which was the starting point for the design of the Web ontology language OWL. Second, it can deal with incomplete knowledge, thus coping with a more plausible scenario of the Web. Though the work presented in this paper can be considered as a feasibility study, it provides the principles for inductive reasoning in SHIQ+log¬. We would like to emphasize that they will be still valid for any other upcoming decidable instantiation of DL+log, provided that Datalog¬ is still considered for the CL part.

The Semantic Web offers several use cases for rules among which we can choose in order to see our ILP framework at work. As next step towards any practice, we plan to define ILP algorithms starting from the ingredients identified in this paper. Tractable cases, e.g. the instantiation of DL+log with DL-Lite (subset of SHIQ), will be of major interest. Also we would like to investigate the impact of having Datalog¬∨ both in the language of hypotheses and in the language for the background theory. The inclusion of the nonmonotonic features of SHIQ+log full will strengthen the ability of our ILP framework 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. Finally, we would like to study the complexity of K-subsumption.

References

1. F. Baader , D. Calvanese , D. McGuinness , D. Nardi , and P.F. Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, 2003 .

2. A. Borgida . On the relative expressiveness of description logics and predicate logics . Artificial Intelligence , 82 ( 1-2 ): 353 - 367 , 1996 .

3. W. Buntine . Generalized subsumption and its application to induction and redundancy . Artificial Intelligence , 36 ( 2 ): 149 - 176 , 1988 .

4. S. Ceri , G. Gottlob, and L. Tanca . What you always wanted to know about datalog (and never dared to ask) . IEEE Transactions on Knowledge and Data Engineering , 1 ( 1 ): 146 - 166 , 1989 .

5. L. De Raedt and L. Dehaspe. Clausal Discovery . Machine Learning , 26 ( 2-3 ): 99 - 146 , 1997 .

6. F.M. Donini , M. Lenzerini , D. Nardi , and A. Schaerf . AL-log: Integrating Datalog and Description Logics . Journal of Intelligent Information Systems , 10 ( 3 ): 227 - 252 , 1998 .

7. T. Eiter , G. Gottlob, and H. Mannila . Disjunctive Datalog. ACM Transactions on Database Systems , 22 ( 3 ): 364 - 418 , 1997 .

8. A.M. Frisch and A.G. Cohn . Thoughts and afterthoughts on the 1988 workshop on principles of hybrid reasoning . AI Magazine , 11 ( 5 ): 84 - 87 , 1991 .

9. M. Gelfond and V. Lifschitz . Classical negation in logic programs and disjunctive databases. New Generation Computing , 9 ( 3 /4): 365 - 386 , 1991 .

10. B. Glimm , I. Horrocks, C. Lutz , and U. Sattler . Conjunctive query answering for the description logic SHIQ . Journal of Artificial Intelligence Research , 31 : 151 - 198 , 2008 .

11. I. Horrocks, P.F. Patel-Schneider , and F. van Harmelen. From SHIQ and RDF to OWL: The making of a web ontology language . Journal of Web Semantics , 1 ( 1 ): 7 - 26 , 2003 .

12. I. Horrocks, U. Sattler , and S. Tobies . Practical reasoning for very expressive description logics . Logic Journal of the IGPL , 8 ( 3 ): 239 - 263 , 2000 .

13. J.-U. Kietz. Learnability of description logic programs . In S. Matwin and C. Sammut, editors, Inductive Logic Programming , volume 2583 of Lecture Notes in Artificial Intelligence , pages 117 - 132 . Springer, 2003 .

14. A.Y. Levy and M.-C. Rousset. Combining Horn rules and description logics in CARIN . Artificial Intelligence , 104 : 165 - 209 , 1998 .

15. F.A. Lisi . Building Rules on Top of Ontologies for the Semantic Web with Inductive Logic Programming . Theory and Practice of Logic Programming , 8 ( 03 ): 271 - 300 , 2008 .

16. F.A. Lisi and D. Malerba . Inducing Multi-Level Association Rules from Multiple Relations . Machine Learning , 55 : 175 - 210 , 2004 .

17. J.W. Lloyd . Foundations of Logic Programming. Springer, 2nd edition , 1987 .

18. T.M. Mitchell. Generalization as search . Artificial Intelligence , 18 : 203 - 226 , 1982 .

19. S. -H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Programming , volume 1228 of Lecture Notes in Artificial Intelligence . Springer, 1997 .

20. G.D. Plotkin . A note on inductive generalization . Machine Intelligence , 5 : 153 - 163 , 1970 .

21. R. Reiter . Equality and domain closure in first order databases . Journal of ACM , 27 : 235 - 249 , 1980 .

22. R. Rosati . Semantic and computational advantages of the safe integration of ontologies and rules . In F. Fages and S. Soliman, editors, Principles and Practice of Semantic Web Reasoning , volume 3703 of Lecture Notes in Computer Science, pages 50 - 64 . Springer, 2005 .

23. R. Rosati . DL+ log: Tight integration of description logics and disjunctive datalog . In P. Doherty, J. Mylopoulos , and C. A . Welty, editors, Proc. of Tenth International Conference on Principles of Knowledge Representation and Reasoning , pages 68 - 78 . AAAI Press, 2006 .

24. C. Rouveirol and V. Ventos . Towards Learning in CARIN-ALN . In J. Cussens and A . Frisch, editors, Inductive Logic Programming , volume 1866 of Lecture Notes in Artificial Intelligence , pages 191 - 208 . Springer, 2000 .

25. C. Sakama . Nonmonotonic inductive logic programming . In T. Eiter, W. Faber , and M. Truszczynski, editors, Logic Programming and Nonmonotonic Reasoning , volume 2173 of Lecture Notes in Computer Science, pages 62 - 80 . Springer, 2001 .

26. M. Schmidt-Schauss and G. Smolka . Attributive concept descriptions with complements . Artificial Intelligence , 48 ( 1 ): 1 - 26 , 1991 .