=Paper=
{{Paper
|id=Vol-258/paper-35
|storemode=property
|title=Reasoning with OWL-DL in Inductive Logic Programming
|pdfUrl=https://ceur-ws.org/Vol-258/paper18.pdf
|volume=Vol-258
|dblpUrl=https://dblp.org/rec/conf/owled/Lisi07
}}
==Reasoning with OWL-DL in Inductive Logic Programming==
https://ceur-ws.org/Vol-258/paper18.pdf
Reasoning with OWL-DL in
Inductive Logic Programming
Francesca A. Lisi
Dipartimento di Informatica, Università degli Studi di Bari,
Via E. Orabona 4, 70125 Bari, Italy
lisi@di.uniba.it
Abstract. The use of background knowledge and the adoption of Horn
clausal logic as a knowledge representation and reasoning framework are
the distinguishing features of Inductive Logic Programming (ILP) with
respect to other approaches to concept learning. We argue that ILP can
not ignore the latest developments in Knowledge Engineering such as
ontologies and formalisms based on Description Logics. In this paper
we present an experience with OWL-DL reasoners in ILP within the
application context of the Semantic Web.
1 Introduction
Inductive Logic Programming (ILP) has been historically concerned with con-
cept 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 back-
ground knowledge in ILP systems is often not organized around a well-formed
conceptual model. This practice seems to ignore latest developments in Knowl-
edge Engineering such as ontologies [6] and formalisms based on Description
Logics (DLs) [2] which are playing a relevant role in the definition of the Se-
mantic 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.
2 The ILP system AL-QuIn
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 lan-
guage 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 min-
imum 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 start-
ing 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 Cref and
task-relevant concepts are designated,
– a multi-grained language {Ll }1≤l≤maxG of patterns
– a set {minsupl }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 ∈ Ll 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 ≥ minsupl 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 granular-
ity (maxG = 3). Minimum support thresholds are set to the following values:
minsup1 = 20%, minsup2 = 13%, and minsup3 = 10%. The data set and the
language of patterns will be illustrated in Example 2 and Example 3, respec-
tively.
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
Fig. 1. The ontology ΣCIA for AL-QuIn.
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 sub-
system Π 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 BCIA
that integrates a ALC component ΣCIA containing taxonomies rooted into the
concepts Country, EthnicGroup, Language and Religion and a Datalog com-
ponent ΠCIA containing facts1 extracted from the on-line 1996 CIA World Fact
Book2 . Note that Middle East countries have been defined as Asian countries
that host at least one Middle Eastern ethnic group:
MiddleEastCountry ≡ AsianCountry u ∃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 Also ΠCIA includes constrained
Datalog clauses such as:
believes(Code, Name)←
religion(Code, Name, Percent) & Code:Country, Name:Religion.
speaks(Code, Name)←
language(Code, Name, Percent) & Code:Country, Name:Language.
that define views on the relations religion and language, respectively.
The language L = {Ll }1≤l≤maxG of patterns allows for the generation of
AL-log unary conjunctive queries, called O-queries. Given a reference concept
Cref , an O-query Q to an AL-log knowledge base B is a (linked and connected)4
constrained Datalog clause of the form
Q = q(X) ← α1 , . . . , αm &X : Cref , γ1 , . . . , γn
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
Qt = q(X) ← &X : Cref
is called trivial for L because it only contains the constraint for the distinguished
variable X. Furthermore the language L is multi-grained, i.e. it contains expres-
sions at multiple levels of description granularity. Indeed it is implicitly defined
by a declarative bias specification which consists of a finite alphabet ∆ of Data-
log 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.
Example 3. To accomplish the task of Example 1 we define LCIA as the set of
O-queries with Cref = MiddleEastCountry that can be generated from the
alphabet ∆= {believes/2, speaks/2} of Datalog binary predicate names,
and the alphabets
3
We would like to remind the reader that ALC is a fragment of SHIQ.
4
For the definition of linkedness and connectedness see [17].
Γ 1 = {Language, Religion}
Γ 2 = {IndoEuropeanLanguage, . . . , MonotheisticReligion, . . .}
Γ 3 = {IndoIranianLanguage, . . . , MuslimReligion, . . .}
of ALC concept names for 1 ≤ l ≤ 3, up to maxD = 5. Examples of O-queries
in LCIA are:
Qt = q(X) ← & X:MiddleEastCountry
Q1 = q(X) ← speaks(X,Y) & X:MiddleEastCountry, Y:Language
Q2 = q(X) ← speaks(X,Y) & X:MiddleEastCountry, Y:IndoEuropeanLanguage
Q3 = q(X) ← believes(X,Y)& X:MiddleEastCountry, Y:MuslimReligion
where Qt is the trivial O-query for LCIA , Q1 ∈ L1CIA , Q2 ∈ L2CIA , and Q3 ∈ L3CIA .
Note that Q1 is an ancestor of Q2 .
The support of an O-query Q ∈ Ll w.r.t an AL-log knowledge base B is
defined as
supp(Q, B) =| answerset(Q, B) | / | answerset(Qt , B) |
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 Q2 turns out to be frequent because it has support
supp(Q2 , BCIA ) = (2/15)% = 13.3% (≥ minsup2 ). It is to be read as ’13.3 %
of Middle East countries speak an Indoeuropean language’. The two correct
answers to Q2 w.r.t. BCIA 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 discov-
ered 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 re-
spect 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 pat-
terns out of 99 candidate patterns compliant with the parameter settings. One
of these frequent patterns is Q2 .
3 Using Pellet in AL-QuIn
3.1 The coverage test
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 Ai each of which
refers to an individual ai of Cref . The link between Ai and ai is represented
with the Datalog literal q(ai ). The pair (q(ai ), Ai ) is called observation.
Example 6. By assuming MiddleEastCountry as reference concept, the obser-
vation AARM contains Datalog facts such as
language(’ARM’,’Armenian’,96).
language(’ARM’,’Russian’,2).
concerning the individual ’ARM’ whereas the observation AIR 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 prov-
ing that an O-query Q covers an observation (q(ai ), Ai ) w.r.t. K equals to proving
that θi = {X/ai } is a correct answer to Q w.r.t. Bi = K ∪ Ai .
Example 7. Checking whether Q2 covers the observation (q(’ARM’), AARM ) w.r.t.
KCIA is equivalent to answering the query
(0)
Q2 = ← q(’ARM’)
w.r.t. KCIA ∪ AARM ∪ Q2 . The coverage test for (q(’IR’), AIR ) is analogous.
A common practice in ILP is to use a reformulation operator, called sat-
uration [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 Σ.
3.2 Implementation issues
AL-QuIn is implemented with Prolog as usual in ILP. Thus, the actual repre-
sentation language in AL-QuIn is a kind of DatalogOI [23], i.e. the subset of
Datalog6= 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 6= 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), Y6=Z
is the DatalogOI rewriting of:
q(X) ← believes(X,Y), believes(X,Z) &
X:MiddleEastCountry, Y:MonotheisticReligion
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 SLD-
resolution on DatalogOI . 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 Ll 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. Σ
– DatalogOI 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 DatalogOI .
Example 9. The DatalogOI rewriting of the concept assertions derived for T 2
produces facts like:
c AfroAsiaticLanguage(’Arabic’).
...
c IndoEuropeanLanguage(’Armenian’).
...
c UralAltaicLanguage(’Kazak’).
...
c MonotheisticReligion(’ShiaMuslim’).
...
c PolytheisticReligion(’Druze’).
...
to be considered during coverage tests of O-queries in L2 .
The concept assertions, once translated to DatalogOI , are added to the
facts derived from the IDB of Π at the loading of each observation. The coverage
test therefore concerns DatalogOI rewritings of both O-queries and saturated
observations.
Example 10. The DatalogOI rewriting
q(X) ← c MiddleEastCountry(X), speaks(X,Y), c IndoEuropeanLanguage(Y)
of Q2 covers the DatalogOI rewriting:
c MiddleEastCountry(’ARM’).
speaks(’ARM’,’Armenian’).
...
c IndoEuropeanLanguage(’Armenian’).
...
of the saturated observation ÂARM .
Note that the translation from OWL-DL to DatalogOI 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.
4 Conclusions and future work
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 implementa-
tion of this feature was still lacking5 . Therefore, we have also shown how to use
5
AL-QuIn could actually deal only with concept hierarchies in DatalogOI .
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 candi-
date 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.
References
1. U. Assmann, J. Henriksson, and J.Maluszynski. Combining safe rules and ontolo-
gies by interfacing of reasoners. In J.J. Alferes, J. Bailey, W. May, and U. Schwer-
tel, editors, Principles and Practice of Semantic Web Reasoning, volume 4187 of
Lecture Notes in Computer Science, pages 33–47. Springer, 2006.
2. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P.F. Patel-Schneider, edi-
tors. The Description Logic Handbook: Theory, Implementation and Applications.
Cambridge University Press, 2003.
3. T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. Scientific Ameri-
can, May, 2001.
4. S. Ceri, G. Gottlob, and L. Tanca. Logic Programming and Databases. Springer,
1990.
5. 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.
6. A. Gómez-Pérez, M. Fernández-López, and O. Corcho. Ontological Engineering.
Springer, 2004.
7. 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.
8. U. Hustadt, B. Motik, and U. Sattler. Reducing SHIQ-description logic to dis-
junctive datalog programs. In D. Dubois, C.A. Welty, and M.-A. Williams, editors,
Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth
International Conference (KR2004), pages 152–162. AAAI Press, 2004.
9. J.-U. Kietz. Learnability of description logic programs. In S. Matwin and C. Sam-
mut, editors, Inductive Logic Programming, volume 2583 of Lecture Notes in Arti-
ficial Intelligence, pages 117–132. Springer, 2003.
10. N. Lavrač and S. Džeroski. Background knowledge and declarative bias in inductive
concept learning. In Klaus P. Jantke, editor, Analogical and Inductive Inference,
volume 642 of Lecture Notes in Computer Science, pages 51–71. Springer, 1992.
11. N. Lavrač, S. Džeroski, V. Pirnat, and V. Krizman. The utility of background
knowledge in learning medical diagnostic rules. Applied Artificial Intelligence,
7(3):273–293, 1993.
12. A.Y. Levy and M.-C. Rousset. Combining Horn rules and description logics in
CARIN. Artificial Intelligence, 104:165–209, 1998.
13. F.A. Lisi and F. Esposito. Efficient Evaluation of Candidate Hypotheses in AL-log.
In R. Camacho, R. King, and A. Srinivasan, editors, Inductive Logic Programming,
volume 3194 of Lecture Notes in Artificial Intelligence, pages 216–233. Springer,
2004.
14. F.A. Lisi and D. Malerba. Ideal Refinement of Descriptions in AL-log. In T. Hor-
vath and A. Yamamoto, editors, Inductive Logic Programming, volume 2835 of
Lecture Notes in Artificial Intelligence, pages 215–232. Springer, 2003.
15. F.A. Lisi and D. Malerba. Inducing Multi-Level Association Rules from Multiple
Relations. Machine Learning, 55:175–210, 2004.
16. H. Mannila and H. Toivonen. Levelwise search and borders of theories in knowledge
discovery. Data Mining and Knowledge Discovery, 1(3):241–258, 1997.
17. S.-H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Program-
ming, volume 1228 of Lecture Notes in Artificial Intelligence. Springer, 1997.
18. D. Page and A. Srinivasan. ILP: A short look back and a longer look forward.
Journal of Machine Learning Research, 4:415–430, 2003.
19. M.J. Pazzani and D.F. Kibler. The utility of knowledge in inductive learning.
Machine Learning, 9:57–94, 1992.
20. C. Rouveirol. Flattening and saturation: Two representation changes for general-
ization. Machine Learning, 14(1):219–232, 1994.
21. C. Rouveirol and L. De Raedt. The use of background knowledge for generalization
in ILP. In C. Rouveirol, editor, Proceedings of the ECAI-92 Workshop on Logical
Approaches to Machine Learning, 1992.
22. M. Schmidt-Schauss and G. Smolka. Attributive concept descriptions with com-
plements. Artificial Intelligence, 48(1):1–26, 1991.
23. G. Semeraro, F. Esposito, D. Malerba, N. Fanizzi, and S. Ferilli. A logic framework
for the incremental inductive synthesis of Datalog theories. In N.E. Fuchs, editor,
Proceedings of 7th International Workshop on Logic Program Synthesis and Trans-
formation, volume 1463 of Lecture Notes in Computer Science, pages 300–321.
Springer, 1998.
24. E. Sirin, B. Parsia, B. Cuenca Grau, A. Kalyanpur, and Y. Katz. Pellet: A practical
OWL-DL reasoner. Journal of Web Semantics, 2006.
25. A. Srinivasan, R.D. King, and M. Bain. An empirical study of the use of rele-
vance information in inductive logic programming. Journal of Machine Learning
Research, 4:369–383, 2003.
26. M. Turcotte, S. Muggleton, and M.J.E. Sternberg. The effect of relational back-
ground knowledge on learning of protein three-dimensional fold signatures. Ma-
chine Learning, 43(1/2):81–95, 2001.