The definition of new concepts or roles for which extensional knowledge become available can turn out to be necessary to make a DL ontology evolve. In this paper we reformulate this task as a machine learning problem and study a solution based on techniques borrowed from that form of logic-based machine learning known under the name of Inductive Logic Programming (ILP). More precisely, we propose to adapt previous ILP results to the knowledge representation framework of DL+log in order to learn rules to be used for changing SHIQ ontologies.
Encoding of human knowledge in ontologies using logical formalisms, e.g.
Description Logics (DLs) [
The use of prior or background knowledge (BK) during the learning process
is a distinguishing feature of Inductive Logic Programming (ILP) [
The paper is organized as follows. Section 2 introduces the KR framework of DL+log. Section 3 states the learning problem of interest, defines the core ingredients of an ILP solution to it and sketches an application scenario in Ontology Evolution. Section 4 concludes the paper with final remarks. 2
The KR framework of DL+log [
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. 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 is a Boolean UCQ with n = 1.
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 Π.
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¬∨ [
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 set G of 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 on NMSAT-DL+log can be found in [
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 [
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 [
We consider the problem of inducing rule-based definitions of concepts/roles that do not occur in an existing SHIQ ontology. At this stage of work the scope of induction does not matter. Therefore the term ’observation’ is to be preferred to the term ’example’.
Definition 1. Given: – a SHIQ+log¬ KB B – a new target SHIQ predicate name p – a set O of observations for p – a language L of hypotheses the problem of inducing a definition for p is to build a hypothesis H ∈ L for p such that B ∪ H is correct w.r.t. O.
We assume that the intensional part K (i.e., the TBox T plus the set ΠR of
rules) of B plays the role of BK and the extensional part F (i.e., the ABox A
plus the set ΠF of facts) contributes to the definition of observations. We choose
to work within the setting of learning from interpretations [
Example 1. Suppose we have a SHIQ+log¬ KB (adapted from [
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)}. Note that [R2] is weakly-safe but not DL-safe because the variable Y does not occur in any Datalog literal of [R2].
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 p is a SHIQ-predicate, each rj, uk is a Datalog-predicate, and each sl is a SHIQ-predicate. Note that p represents the target predicate, i.e. the predicate to be defined by learned SHIQ+log¬ rules.
Example 2. Suppose that the target predicate is the SHIQ-concept 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) ← UNMARRIED(X)
LONER(X) ← ¬famous(X) belong to LLONER and represent hypotheses of definition for LONER. Example 3. Suppose now that the SHIQ-role LIKES is the target predicate and the set PD(LLIKES) ∪ PC (LLIKES) ∪ PR(LLIKES) = {happy/1} ∪ {RICH/1} ∪ {WANTS-TO-MARRY/2} provides the building blocks for the language LLIKES. The following SHIQ+log¬ rules
LIKES(X,Y) ← WANTS-TO-MARRY(X,Y) LIKES(X,Y) ← WANTS-TO-MARRY(X,Y), happy(X) LIKES(X,Y) ← WANTS-TO-MARRY(X,Y), RICH(Y)
LIKES(X,Y) ← happy(X), RICH(Y) H1LONER H2LONER H3LONER H4LONER H1LIKES H2LIKES H3LIKES H4LIKES 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). belonging to LLIKES can be considered hypotheses of definition for LIKES.
Note that a hypothesis H may consist of more than one SHIQ+log¬ rule. Also H is valid as a solution to the learning problem in hand if it changes the input ontology by keeping it consistent. This requirement is guaranteed by the correcteness condition in Definition 1. 3.2
In order to solve the learning problem in hand with the ILP methodological
approach , the language L of hypotheses needs to be equipped with (i) a generality
order , and (ii) a coverage relation covers so that (L, ) is a search space and
covers defines the mappings from (L, ) to the set O of observations.
A generality order for SHIQ+log¬ rules 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 [
Definition 2. Let H1, H2 ∈ L be two hypotheses standardized apart, K a background knowledge, and σ a Skolem substitution5 for H2 with respect to {H1}∪K. We say that H1 is more general than H2 under K-subsumption (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 problem. 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. 5 Let B be a clausal theory and H be a clause. Let X1, . . . , Xn be all the variables appearing in H, and a1, . . . , an be distinct constants not appearing in B or H. Then the substitution {X1/a1, . . . , Xn/an} is called a Skolem substitution for H w.r.t. B. Example 4. Let us consider the hypotheses H1LONER H2LONER
LONER(A) ← scientist(A)
LONER(X) ← scientist(X),UNMARRIED(X) reported in Example 2 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, H3LONER K H2LONER and H4LONER is incomparable with all the first three hypotheses.
EHx2LaImKESplaen5d. HW1LiItKhES refKereHnc3LeIKEtSo. CEoxnavmeprsleely3,, tihte chaynpobtehepsreosveHd2LItKhESa,t HH3L1LIIKKEESS, anKd H4LIKES are incomparable 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.
A coverage relation for SHIQ+log¬ rules 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 p is the target SHIQ predicate, ai is a tuple of individuals occurring in the ABox A and Fi is a set containing ground facts concerning individuals in ai. Note that when p is a SHIQ role name, the tuple ai is a pair < ai1, ai2 > of individuals and the set Fi is given by the union of Fi1 and Fi . We assume K ∩ O = ∅.
2 Definition 3. 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).
Therefore 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 6. With reference to Example 2, the hypothesis H1LONER covers the observation oJoe = (LONER(Joe), FJoe) because all NM-models for B = K ∪ FJoe ∪ H1LONER do satisfy scientist(Joe). Note that it does not cover the observations oPaul = (LONER(Paul), FPaul) and oMary = (LONER(Mary), FMary). The hypothesis H2LONER convers only oJoe for analogous reasons. It can be proved that H3LONER covers oMary and oJoe while H4LONER none of the three observations. Example 7. None of the hypotheses H1LIKES, H2LIKES, and H3LIKES reported in Example 3 cover observations concerning couples of known individuals. Conversely, H4LIKES covers the observation o<Mary,Paul> = (LIKES(Mary,Paul), FMary ∪ FPaul) because all NM-models for B = K ∪ FMary ∪ FPaul ∪ H4LIKES satisfy: – happy(Mary), due to the axiom A1 and to the rule R2. Indeed, since from A1 ∃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; – RICH(Paul), since the default rule R1 is always applicable for Paul. Note that H4LIKES covers also o<Mary,Mary> = (LIKES(Mary,Mary), FMary). 3.3
A proof-of-concept application scenario in Ontology Evolution
The ingredients identified in the previous section are the starting point for the
definition of ILP algorithms, that once implemented, can support the evolution
of ontologies. Before clarifying how, we remind the reader that - according to
[
We argue that the phases 1.-3. are crucial from our point of view. Indeed change capturing (1.) provides the target predicate and the observations for one or more learning problems of the form as in Definition 1. Once captured this way, each change is represented (2.) as the hypothesis inductively generated according to Definition 1. A particular attention must then be paid to the semantics of those changes (3.) that contain NAF literals because they can affect the ontology consistency. Indeed the change operations considered in this paper, i.e. the creation of a concept and the creation of a role, both boil down to the addition of new rules to the input SHIQ+log¬ KB as illustrated in the following example. Example 8. Let us suppose that for the concept LONER we have oJoe as a positive example and oMary and oPaul as negative examples. From this set of observations, an ILP algorithm implementing the ingredients identified in Section 3.2 and adopting a top-down strategy can induce H1LONER as the hypothesis of rule-based definition for LONER because it covers all positive examples and none of the negative examples w.r.t. the BK of Example 1. Conversely, if oJoe and oMary are both positive examples and oPaul is the only negative example for LONER, the hypothesis H3LONER will be returned.
Let us now suppose that o<Mary,Paul> and o<Mary,Mary> are positive examples for the role LIKES and any other observation is considered as negative example. In this case, the hypothesis H4LIKES is the inductively correct definition of LIKES. 4
In this paper, we have proposed an ILP framework built upon SHIQ+log¬
which is a decidable instantiation of the most powerful KR framework
currently available for the integration of DLs and CLs. 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 supporting the evolution of a SHIQ ontology for
two main reasons. First, it induces rules with a SHIQ predicate in the head.
Second, it can deal with incomplete knowledge, thus coping with a more
plausible scenario of ontology evolution. Though the work presented in this paper
can be considered as a feasibility study, it provides the principles for learning 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 ILP framework presented in this paper
differs from the related proposals [
As next step towards any practice, we plan to define ILP algorithms starting
from the ingredients identified in this paper. Also, we intend to study in more
depth the application of these algorithms to Ontology Evolution, e.g. in the
light of related work such as [