=Paper=
{{Paper
|id=None
|storemode=property
|title=Exact Learning of TBoxes in EL and DL-Lite
|pdfUrl=https://ceur-ws.org/Vol-1014/paper_53.pdf
|volume=Vol-1014
|dblpUrl=https://dblp.org/rec/conf/dlog/KonevLW13
}}
==Exact Learning of TBoxes in EL and DL-Lite==
https://ceur-ws.org/Vol-1014/paper_53.pdf
Exact Learning of TBoxes in EL and DL-Lite
Boris Konev1 and Carsten Lutz2 and Frank Wolter1
1
Department of Computer Science, University of Liverpool, UK
2
Department of Computer Science, University of Bremen, Germany
Abstract. We study polynomial time learning of description logic TBoxes in An-
gluin et al.’s framework of exact learning via queries. We admit entailment queries
(“is a given subsumption entailed by the target TBox?”) and equivalence queries
(“is a given TBox equivalent to the target TBox?”), assuming that the signature
and logic of the target TBox are known. We present three main results: (1) TBoxes
formulated in the extension of DL-Litecore with ELI-concepts on the right-hand
side of concept inclusions can be learned in polynomial time. (2) Neither general
nor acyclic EL TBoxes can be learned in polynomial time. (3) EL TBoxes with
only concept names on the right-hand side of concept inclusions can be learned in
polynomial time. It follows, in particular, that non-polynomial time learnability
of EL TBoxes is caused by the interaction between existential restrictions on the
right and left-hand side of concept inclusions.
1 Introduction
Successfully deploying a description logic (DL) in a concrete application requires to
carefully capture the relevant domain knowledge in a DL ontology. This is a subtle,
error-prone, and time consuming task, which is further hindered by the fact that do-
main experts are rarely experts in ontology engineering and, conversely, ontology en-
gineers are often not sufficiently familiar with the domain to be modeled. From its
beginnings, DL research was driven by the aim to provide various forms of support for
ontology engineers, assisting them in the design of high-quality ontologies. Examples
include the ubiquitous task of ontology classification [9], bootstrapping ontology design
from examples [11, 12] and checking the completeness of the modeling in a systematic
way [10].
Machine learning (ML) techniques are natural candidates for supporting ontology
engineering by partly automatizing the design process, and in fact ML approaches have
been proposed for ontology engineering in non-DL-contexts. There, the main focus is
on mining the relevant terms of the application domain from bodies of text and semi-
structured data with the aim of including them in the ontology as concept and role
names. Some approaches also support learning of subsumptions between these terms,
that is, subsumptions between concept names [15, 13]. In the context of DL ontologies,
though, the main difficulty is to develop a detailed modeling of the relevent concepts
of the domain using the logical operators provided by the DL at hand. The aim of this
paper is to investigate the latter problem and to study the theoretical foundations of
learning ontologies that are formulated in variations of the description logics EL and
DL-Lite, using Angluin et al.’s framework of exact learning via queries [3].
We are interested in learning a target TBox T that is formulated in a given DL and
whose signature Σ (the concept and role names that occur in T ) is also known, by
posing queries to an oracle. Intuitively, the oracle can be thought of as a domain expert
that interacts with the learning algorithm. We consider two forms of oracle queries:
– entailment queries: does T entail a given Σ-concept inclusion C v D? These
queries are answered by the oracle with ‘yes’ or ’no’.
– equivalence queries: is a given Σ-TBox (the hypothesis) equivalent to T ? The or-
acle answers ‘yes’ if H and T are logically equivalent and ‘no’ otherwise. It then
returns a Σ-inclusion C v D such that T |= C v D and H 6|= C v D (a positive
counterexample), or vice versa (a negative counterexample).
We generally assume that the inclusions used in entailment queries and returned by
equivalence queries are of the same form as the inclusions allowed in the target TBox.
Our aim is to find (deterministic) learning algorithms that run in polynomial time
and consequently also make only polynomially many oracle queries. More precisely,
we require that there is a two-variable polynomial p(n, m) such that at every point of
the algorithm execution, the time spent up to that point is bounded by p(n, m), where
n is the size of the target TBox T to be learned and m is the size of the largest (positive
or negative) counterexample that was returned by the oracle until the considered point
of the execution. If such an algorithm exists, we say that L-TBoxes are polynomial time
learnable.
When the target TBox is formulated in a description logic L such that for any sig-
nature Σ, the number of L-concept inclusions is polynomial in the size of Σ, then L-
TBoxes are trivially polynomial time learnable. This is actually the case even when only
entailment queries (but no equivalence queries) are available, and also when only equiv-
alence queries (but no entailment queries) are available. Consequently, DL-Litecore -
TBoxes and DL-LiteR -TBoxes are polynomial time learnable. We thus start our investi-
gation with considering the more interesting case of DL-Lite∃ , which is the extension of
DL-Litecore that allows any ELI-concept on the right-hand side of concept inclusions.
Although the number of Σ-concept inclusions is no longer polynomial in the size of Σ,
we are still able to establish that DL-Lite∃ -TBoxes are polynomial time learnable.
We then switch to the case of EL-TBoxes. It is known that propositional Horn for-
mulas (which correspond to EL-TBoxes without existential restrictions) can be learned
in polynomial time when both entailment and equivalence queries are available, but
not when one of the types of queries is disallowed [16, 4, 1], see also [5]. We show
that, in contrast, general EL TBoxes and even acyclic EL TBoxes are not polynomial
time learnable. To analyze the reasons for this, we consider the fragment ELlhs of EL
in which TBoxes consist of concept inclusions with only concept names on the right
hand side. It turns out that ELlhs TBoxes are polynomial time learnable. Note that the
corresponding fragment ELrhs that allows only concept names on the left hand side of
concept inclusions is a fragment of DL-Lite∃ , and thus also admits polynomial time
learning. Consequently, non-polynomial time learnability of (acyclic) EL TBoxes is
caused by the interaction between existential restrictions on the right- and left-hand
side of concept inclusions.
Missing proofs are given in the appendix of the full version of this paper available
at http://cgi.csc.liv.ac.uk/∼ frank/publ/publ.html
Related Work. In the learning literature, entailment queries are regarded as a special
type of membership queries which can take many different forms [21]. Learning us-
ing membership and equivalence queries appears to be the most successful protocol for
exact learning in Angluin’s framework. Apart from propositional Horn formulas, im-
portant polynomial time learnable classes for this protocol include regular sets [2] and
monotone DNF [3]. Exploring the possibilities of extending the learning algorithm for
propositional Horn formulas to (fragments) of first-order Horn logic has been a major
topic in exact learning [22, 6]. Note that ELlhs can be regarded as a fragment of first-
order Horn logic. Existing approaches either disallow recursion, bound the number of
individual variables per Horn clause, or admit additional queries in the learning proto-
col. None of this is the case in our setup. Another topic related to our work is exact
learning of schema mappings in data exchange, as recently studied in [23]. In this and
some other studies mentioned above, membership queries take the form of interpreta-
tions (“is a given interpretation a model of the target theory?”). In the DL context, exact
learning has been studied for CLASSIC in [17] where it is shown that single CLAS-
SIC concepts (but not TBoxes) can be learned in polynomial time (here membership
queries consist of concepts). Learning single concepts using refinement operators has
been studied in [19].
2 Preliminaries
Let NC be a countably infinite set of concept names and NR a countably infinite set
of role names. We consider a dialect of DL-Lite that we call DL-Lite∃ , defined as fol-
lows [14]. A role is a role name or an inverse role r− with r ∈ NR . A basic concept is
either a concept name or of the form ∃r.>, with r a role. A DL-Lite∃ concept inclusion
(CI) is of the form B v C, where B is a basic concept and C is an ELI-concept, that
is, C is formed according to the rule
C, D := A | > | C uD | ∃r.C | ∃r− .C
where A ranges over NC and r ranges over NR . A DL-Lite∃ TBox is a finite set of DL-
Lite∃ inclusions. As usual, an EL-concept is an ELI-concept that does not use inverse
roles, an EL concept inclusion has the form C v D with C and D EL-concepts, and
a (general) EL TBox is a finite set of EL concept inclusions [8]. We use C ≡ D as an
abbreviation for the inclusions C v D and D v C. An EL TBox T is called acyclic if
it consists of inclusions A v C and A ≡ C such that A is a concept name, no concept
names occurs more than once on the left hand side of an inclusion in T , and T contains
no cycles [18].
A signature Σ is a finite set of concept and role names. The size of a concept C,
denoted with |C|, is the length of the string that represents it, where concept names and
Pnames are considered to be of length one. The size of a TBox T , denoted with |T |,
role
is CvD∈T |C| + |D|.
3 DL-Lite∃ -TBoxes are Learnable in Polynomial Time
We prove that DL-Lite∃ -TBoxes can be learned in polynomial time.3 We assume that
the target TBox is in named form, that is, it contains for each role r a concept name
Ar such that ∃r.> v Ar ∈ T and Ar v ∃r.> ∈ T . This assumption is without
loss of generality since any (polynomial time) learning algorithm for TBoxes in named
form can be transformed into one for unrestricted TBoxes: the learning algorithm still
uses the concept names Ar in its internal representations (although they are no longer
included in the target signature Σ), and replaces each Ar with ∃r.> in queries to the
oracle and when ultimately returning the TBox that is has learned.
As a first step, the learning algorithm for DL-Lite∃ TBoxes determines the set of all
inclusions B1 v B2 with T |= B1 v B2 and B1 , B2 basic concepts. Since the target
signature Σ is known to the learner, this requires at most (2|Σ|)2 entailment queries. We
write B1 ≡T B2 when T |= B1 v B2 and T |= B2 v B1 . After completing the first
step, the learning algorithm fixes for each [B]T = {B 0 | B ≡T B 0 } a representative
A[B]T ∈ [B]T which we may assume to be a concept name since T is in named form.
A DL-Lite∃ inclusion A v C is in reduced form if all basic concepts that occur in it
are among the chosen representatives. We assume without further notice that all concept
inclusions considered by the learner are in reduced form. In particular, counterexamples
returned by the oracle are immediately converted into this form.
For a transparent formulation of the learning algorithm, it is useful to identify each
ELI concept C with a finite tree TC whose nodes are labeled with sets of concept
names and whose edges are labeled with roles. Specifically, TC has a root node aC and
non-root nodes aD for every occurrence of a subconcept ∃r.D of C; each node aD is
labeled with the set of concept names l(aD ) = {A | A is a top-level conjunct of D}
and every edge (aDu∃r.D0 , aD0 ) is labeled with the role {r}. Conversely, every tree T
of the described form gives rise to an ELI concept CT in the obvious way. We will
not always distinguish explicitly between C and its tree representation TC and talk, for
example, about the nodes and subtrees of an ELI concept.
The following notion plays a central role in the learning algorithm. Let T be a
DL-Lite∃ TBox. A DL-Lite∃ inclusion A v C is T -essential if it is in reduced form,
T |= A v C, and the following conditions are satisfied:
1. A v C is concept saturated for T : if C 0 results from C by adding a concept name
A0 to the label of some node, then T 6|= A v C 0 .
2. A v C is sibling-merged for T : if C 0 is the result of identifying two siblings in C,
then T 6|= A v C 0 .
3. A v C is parent/child-merged for T : if C 0 is the result of identifying a parent and
a child of a node in the tree representation of C, then T 6|= A v C 0 .
4. A v C is minimal for T : if C contains an edge (d, d0 ) such that A0 is in the node
label of d and l(d, d0 ) = r, then T 6|= A0 v ∃r.C 0 where C 0 corresponds to the
subtree rooted at d0 (where A0 6= A if d is the root of C).
3
We assume that the CIs used in entailment and in equivalence queries and those returned as
counterexamples by the oracle are also formulated in DL-Lite∃ . It is also conceivable to use
more expressive logics instead.
Algorithm 1 The learning algorithm for DL-Lite∃
1: Compute Hbasic = {B1 v B2 | T |= B1 v B2 , B1 , B2 basic} (entailment queries)
2: Let Hadd = ∅
3: while Equivalent(Hbasic ∪ Hadd )? returns “no” do
4: Let B v D be the returned positive counterexample for T relative to Hbasic ∪ Hadd
5: Find a T -essential inclusion A v C with Hbasic ∪ Hadd 6|= A v C (entailment queries)
6: if there is A v C 0 ∈ Hadd then
7: Find T -essential inclusion A v C 00 such that |= C 00 v C u C 0 (entailment queries)
8: Replace A v C 0 by A v C 00 in Hadd
9: else
10: add A v C to Hadd
11: end if
12: end while
13: Set H = Hbasic ∪ Hadd .
In Points 2 and 3, we only consider the merging of nodes that are reachable via the
same role. In Point 3, for example, C 0 is the result of selecting two edges (d1 , d) and
(d, d2 ) such that l(d1 , d) is the inverse of l(d, d2 ) and merging d1 with d2 , labeling
the resulting node with l(d1 ) ∪ l(d2 ). The algorithm for learning DL-Lite∃ TBoxes is
given as Algorithm 1. In the remainder of this section, we prove that this algorithm is
indeed capable of learning DL-Lite∃ TBoxes in named form, and that it runs in poly-
nomial time. First observe that in Line 4 the assumption that a positive counterexample
is returned by the oracle (i.e., an inclusion entailed by T but not by Hbasic ∪ Hadd ) is
justified by the construction of Hbasic ∪ Hadd in Lines 1, 8, and 10 which ensure that
T |= Hbasic ∪ Hadd . We now show that Lines 5 and 7 can be implemented using only
polynomially many entailment queries. In the next lemma, we consider Line 5.
Lemma 1. Given a positive counterexample A v C for T relative to Hbasic ∪ Hadd ,
one can construct a T -essential A0 v C 0 with Hbasic ∪ Hadd 6|= A0 v C 0 using
polynomially many entailment queries in |C| and |T |.
Proof. Assume the DL-Lite∃ concept inclusion A v C is given. We may assume that
A v C is in reduced form and exhaustively apply the following rules, which rely on
posing entailment queries to the oracle:
(Saturation) if T |= A v C 0 and C 0 results from C by adding a concept name A0 to the
label of some node, then replace A v C by A v C 0 .
(Sibling merging) if T |= A v C 0 and C 0 is the result of identifying two siblings in C,
then replace A v C by A v C 0 .
(Parent/child merging) if T |= A v C 0 and C 0 is the result of identifying a parent and
a child of a node in C, then replace A v C by A v C 0 .
(Minimization) if T |= A0 v ∃r.C 0 and A0 v ∃r.C 0 is obtained from A v C by
selecting an edge (d, d0 ) in C such that A0 is in the node label of d, l(d, d0 ) = r, and C 0
corresponds to the subtree rooted at d0 , and A0 6= A if d is the root of C, then replace
A v C by
(a) A0 v ∃r.C 0 if Hbasic ∪ Hadd 6|= A0 v ∃r.C 0 ;
(b) A v C|d0 ↓ , where C|d0 ↓ is obtained from C by removing the subtree generated by
d0 from C, otherwise.
In the first three rules, we have T |= A v C 0 and |= C 0 v C if A v C is replaced by
A v C 0 . Hence Hbasic ∪ Hadd 6|= A v C 0 . In the last rule, observe that
{A0 v ∃r.C 0 , A v C|d0 ↓ } |= A v C.
Hence, independently of whether (a) or (b) applies, the result of the rule application is
entailed by T and not entailed by Hbasic ∪ Hadd . It follows directly from the definition
of the rules that the final concept inclusion is T -essential. Clearly, the number of rule
applications is bounded by |C| × |Σ|. (Note that if d is the root of C in the last rule,
then T |= A v A0 and T 6|= A0 v A because concept inclusions are in reduced form;
thus, this rule does not lead to non-termination of rule application.) o
The following lemma addresses Line 7 and is proved in the appendix.
Lemma 2. Assume that A v C1 and A v C2 are T -essential. Then one can construct
a T -essential A v C such that |= C v C1 u C2 using polynomially many entailment
queries in |C1 | + |C2 |.
If the algorithm terminates, then it obviously terminates with a hypothesis Hbasic ∪Hadd
that is logically equivalent to T . It thus remains to be shown that the algorithm runs in
polynomial time. Observe that Hadd contains at most one concept inclusion A v C for
each concept name A. At each step in the while-loop either a fresh A v C is added to
Hadd (if no inclusion with A on the left exists in Hadd ) or one such A v C is replaced
by a fresh A v C 0 with |= C 0 v C and 6|= C v C 0 . Termination in polynomial
time thus follows if the number of replacements of one A v C by a fresh A v C 0 is
bounded by a polynomial. It follows from the condition that A v C and A v C 0 are T -
essential that the tree corresponding to C is obtained from the tree correponding to C 0
by removing subtrees. Now termination in polynomial time follows from the following
lemma which is proved in the appendix using canonical models for DL-Lite∃ -TBoxes.
Let n(C) denote the number of nodes in the tree representation of C.
P
Lemma 3. If A v C is T -essential, then n(C) ≤ AvD∈T n(D).
It is proved in the appendix that all four properties of T -essential inclusions are neces-
sary to ensure that Algorithm 1 is correct and polynomial time. We formulate the main
result of this section.
Theorem 1. DL-Lite∃ TBoxes are polynomial time learnable using entailment and
equivalence queries.
4 EL TBoxes are not Polynomial Time Learnable
We show that acyclic EL TBoxes cannot be learned in polynomial time. Consequently,
the same is true for general EL TBoxes. Although the target TBox is acyclic, we assume
that CIs used in entailment queries and in equivalence queries and those returned as
counterexamples are formulated in unrestricted EL; in particular, compound concepts
are allowed both on the left- and right-hand side.
The proof is inspired by Angluin’s lower bound for the following abstract learning
problem [3]: a learner aims to identify one of N distinct sets L1 , . . . , LN which have
the property that there exists a set L∩ for which Li ∩ Lj = L∩ , for any i 6= j. It is
assumed that L∩ is not a valid argument to an equivalence query. The learner can pose
membership queries “x ∈ L?” and equivalence queries “H = L?”. Then in the worst
case it takes at least N − 1 membership and equivalence queries to exactly identify
a hypothesis Li from L1 , . . . , LN . The proof proceeds as follows. At every stage of
computation the oracle maintains a set of hypotheses S, which the learner is not able
to distinguish based on the answers given so far. Initially, S = {L1 , . . . , LN }. When
the learner asks a membership query x, the oracle returns ’Yes’ if x ∈ L∩ and ’No’
otherwise. In the latter case, the (unique) Li such that x ∈ Li is removed from S. When
the learner asks an equivalence query H, the oracle returns ‘No’ and a counterexample
x ∈ L∩ ⊕ H (the symmetric difference of L∩ and H). This always exists as L∩ is not
a valid query. If the counterexample x is not a member of L∩ , (at most one) Li ∈ S
such that x ∈ Li is eliminated from S. In the worst case, the learner has to reduce the
cardinality of S to one to exactly identify a hypothesis, which takes N − 1 queries.
Similarly to the method outlined above, in our proof of Theorem 2 we maintain a
set of acyclic EL TBoxes S whose members the learning algorithm is not able to distin-
guish based on the answers obtained so far. We start with S = {T1 , . . . , TN }, where N
is superpolynomial in the sizes of every TBox Ti , and describe an oracle that responds
to entailment and equivalence queries. For didactic purposes, we first present a set of
acyclic TBoxes T1 , . . . , TN , for which the oracle can respond to entailment queries
in the way described above but which is polynomial time learnable when equivalence
queries are also allowed. We then show how the TBoxes can be modified to obtain a
family of acyclic TBoxes that is not polynomial time learnable using entailment and
equivalence queries.
To present the TBoxes, we introduce the following abbreviation. If n > 0 and σ =
σ 1 σ 2 . . . σ n is a sequence of role names where every σ j is either the role name r or the
role name s, and C is a concept, then the expression ∃σ.C stands for ∃σ 1 .∃σ 2 . . . ∃σ n .C.
There are N = 2n different sequences σ of length n. For every such sequence σ, con-
sider the acyclic EL TBox Tσ defined as
Tσ = {A v ∃σ.M u X0 } ∪ T0 with
T0 = {X0 v ∃r.X1 u ∃s.X1 , X1 v ∃r.X2 u ∃s.X2 , . . . , Xn−1 v ∃r.Xn u ∃s.Xn }
where T0 generates a full binary tree with edges labelled with role names r and s and
with X0 at the root, X1 at level 1 and so on; and M is a concept name that ‘marks’ a
particular path in this tree given by the sequence σ. One can use Angluin’s strategy to
show that TBoxes from the set S of all such TBoxes Tσ cannot be learned in polynomial
time using entailment queries: notice that for no sequence σ 0 6= σ of length n we have
Tσ |= A v ∃σ 0 .M . Thus, following Angluin’s strategy, an entailment query of the
form A v ∃σ.M eliminates at most one TBox from the set of TBoxes that the learner
cannot distinguish. This observation can be generalized to arbitary entailment queries
since one can prove, similarly to the proof of Lemma 4, for any C v D that either
{A v X0 } ∪ T0 |= C v D or at most one TBox from S entails C v D. It follows that
acyclic EL TBoxes are not polynomial time learnable using entailment queries only.
Unfortunately, a single equivalence query is sufficient to learn any TBox from S
in two steps: given the equivalence query {A v X0 } ∪ T0 , the oracle has no other
option but to reveal the target TBox Tσ as A v ∃σ.M can be found ‘inside’ every
counterexample. Our strategy to avoid this kind of equivalence queries is to modify
T1 , . . . , TN in such a way that even though a TBox T∩ axiomatizing the intersection
over the set of consequences of each Ti , i ≤ N , exists, its size is exponential and so
cannot be used as an equivalence query by a polynomial learning algorithm.
For every n > 0 and every n-tuple L = (σ1 , . . . , σn ), where every σi is a role
sequence of length n, we define an acyclic EL TBox TL as the union of T0 and the
following inclusions:4
A1 v ∃σ1 .M u X0 An v ∃σn .M u X0
...
B1 v ∃σ1 .M u X0 Bn v ∃σn .M u X0
A ≡ X0 u ∃σ1 .M u · · · u ∃σn .M.
Σn denotes the signature of L. Let Ln be a set of n-tuples such that for every 1 ≤ i ≤ n
and every L, L0 ∈ Ln with L = (σ1 , . . . , σn ), L0 = (σ10 , . . . , σn0 ), if σi = σj0 then
L = L0 and i = j. Then for any sequence σ of length n there exists a unique L ∈ Ln
and a unique i ≤ n such that TL |= Ai v ∃σ.M and TL |= Bi v ∃σ.M . There are
N = b2n /nc different tuples in Ln . Notice that N is superpolynomial in the size of TL ,
for every L ∈ Ln . dn
Every TL , for L ∈ Ln , entails, among other inclusions, i=1 Ci v A, where every
Ci is either Ai or Bi . There are 2n different such inclusions, which indicates that the
size of the ‘intersection TBox’ requires superpolynomially many axioms. It follows
from Lemma 5 below that this is indeed the case.
The following lemma (proved in the appendix) enables us to respond to entailment
queries without eliminating too many TBoxes from the list S of TBoxes that the learner
cannot distinguish.
Lemma 4. For every EL concept inclusion C v D over Σn :
– either for every L ∈ Ln we have TL |= C v D or
– the number of different L ∈ Ln such that TL |= C v D does not exceed |C|.
To illustrate the result consider two TBoxes TL and TL0 , where L = (σ1 , . . . , σn ) and
L0 = (σ10 , . . . , σn0 ). Then the inclusion X0 u ∃σ1 .M u ∃σ10 .M u A2 u · · · u An v A
is entailed by both TL and TL0 but not by any other TL00 .
Now we turn our attention to equivalence queries. We show that given any polyno-
mial size equivalence query H the oracle can return a counterexample inclusion C v D
such that either (i) H |= C v D and TL |= C v D for at most one L ∈ Ln or (ii)
H 6|= C v D and for every L ∈ Ln we have TL |= C v D. Thus, such a counterexam-
ple eliminates at most one TL from the set S of TBoxes the learner cannot distinguish.
4
In fact, to prove non-polynomial learnability, it suffices to consider ∃σ1 .M u· · ·u∃σn .M v A
in place of the concept equality; however, inclusions of this form are not allowed in acyclic
TBoxes.
In addition we have to take extra care of the size of counterexamples as the learning al-
gorithm is allowed to run in time polynomial not only in the size of the target TBox but
also in the size of the largest counterexample to equivalence queries returned by the or-
acle. For instance, if the hypothesis TBox H contains an inclusion C v D, which is not
entailed by any TL , one cannot simply return C v D as a counterexample as the learner
will be able to ‘pump up’ its running time by posing a sequence of equivalence queries
with spurious Hi = {Ci v Di } as an argument such that the size of Ci+1 v Di+1
is double the size of Ci v Di . Then at every stage in a run of the learning algorithm,
the running time will be polynomial in the size of the input and the size of the largest
counterexample received so far, but the overall running time will be exponential in the
size of input. The following lemma addresses this issue.
Lemma 5. For any n > 0 and any EL TBox H in Σn with |H| < 2n there exists an
EL CI C v D over Σn such that (i) the size of C v D does not exceed 6n and (ii) if
H |= C v D then TL |= C v D for at most one L ∈ Ln and if H 6|= C v D then for
every L ∈ Ln we have TL |= C v D.
The following is the main result of this section.
Theorem 2. Neither general EL TBoxes nor acyclic EL TBoxes are polynomial time
learnable using entailment and equivalence queries.
Proof. Assume that acyclic EL TBoxes are polynomial time learnable. Then there
exists a learning algorithm with running time at any stage bounded by a polynomial
p(n, m). Choose n such that b2n /nc > (p(n, 6n))2 and let S = Ln . We follow An-
gluin’s strategy of removing TBoxes from S in such a way that the learner cannot dis-
tinguish between any of the remaining TBoxes. Given an entailment query C v D, if
TL |= C v D for every L ∈ Ln , the answer is ‘yes’; otherwise the answer is ‘no’ and
all L ∈ Ln such that TL |= C v D are removed from S. Given an equivalence query
H the answer is ‘no’, a counterexample C v D guaranteed by Lemma 5 is produced,
and (at most one) TL such that TL |= C v D is removed from S.
As all counterexamples produced are smaller than 6n, the overall running time of
the algorithm is bounded by p(n, 6n). Hence, the learner asks not more than p(n, 6n)
queries and the size of every query does not exceed p(n, 6n). By Lemmas 4 and 5, at
most (p(n, 6n))2 TBoxes are removed from S during the run of the algorithm. But then
the algorithm cannot distinguish between any remaining TBoxes based on the given
answers and we have derived a contradiction. o
5 ELlhs TBoxes are Polynomial Time Learnable
We consider the restriction ELlhs of general EL TBoxes where only concept names
are allowed on the right-hand side of concept inclusions. As in Section 3, we assume
that CIs used in entailment queries and in equivalence queries and those returned as
counterexamples are also of this restricted form. Our algorithm extends the polynomial
time agorithm for learning propositional Horn theories from [4].
We first introduceSsome notation. An interpretation I is a tree interpretation if the
directed graph (∆I , r∈NR rI ) is a tree and rI ∩ sI = ∅ for all distinct r, s ∈ NR .
Algorithm 2 The learning algorithm for ELlhs TBoxes
1: Let I be the empty sequence (of finite tree interpretations)
2: Let H = ∅ be the empty hypothesis
3: while Equivalent(H)? returns “no” do
4: Let C v A be the returned positive counterexample for T relative to H
5: Find an essential T -countermodel I with I |= H (entailment queries)
6: if there is a J ∈ I such that J 6⇒ (I ×r J ) and I ×r J 6|= T then
7: Let J be the first such element of I
8: Find an essential T -countermodel J 0 ⊆ I ×r J (entailment queries)
9: replace J in I with J 0
10: else
11: append I to I
12: end if
13: Construct H = {CI v A | I ∈ I, T |= CI v A} (entailment queries)
14: end while
We generally denote the root of a tree interpretation I with ρI . The product of two
interpretations I and J is the interpretation I × J with ∆I×J = ∆I × ∆J , (d, e) ∈
AI×J if d ∈ AI and e ∈ AJ , and ((d, e), (d0 , e0 )) ∈ rI×J if (d, d0 ) ∈ rI and
(e, e0 ) ∈ rJ , for any concept name A and role name r. Products preserve the truth of
EL concept inclusions [20] and the product of tree interpretations is a disjoint union
of tree interpretations. If I and J are tree interpretations, we denote by I ×r J the
tree interpretation contained in I × J rooted in (ρI , ρJ ). Let I, J be interpretations,
d ∈ ∆I and e ∈ ∆J . A relation ∼ ⊆ ∆I × ∆J is a simulation from (I, d) to
(J , e) if the following conditions are satisfied [20]: (i) d ∼ e; (ii) d ∈ AI and d ∼ e
implies e ∈ AJ ; (iii) (d, d0 ) ∈ rI and d ∼ e implies d0 ∼ e0 for some e0 ∈ ∆J with
(e, e0 ) ∈ rJ . We write (I, d) ⇒ (J , e) to indicate that there is a simulation from
(I, d) to (J , e). For an EL-concept C, we write IC to denote the tree interpretation
that is obtained by viewing C as an interpretation in the natural way. Similarly, given
a tree interpretation I we denote by CI the EL-concept obtained by viewing I as a
concept. An interpretation I is a T -countermodel if I 6|= T . For a tree interpretation I,
let I|−root denote the interpretation obtained from I by removing the root ρI of I. For
any element of I, let I|− d↓ be I with the subtree rooted at d removed. A T -countermodel
is essential if the following conditions are satisfied:
1. I|−
root |= T ;
2. I|− I
d↓ |= T for all d ∈ ∆ \ {ρI }.
Note that there is a close connection between essential T -countermodels and positive
counterexamples for T relative to H. More precisely, if T is a target TBox and H a
hypothesis, then every essential T -countermodel I with I |= H gives rise to at least
one positive counterexample for T relative to H of the form CI v A, where A is a
concept name and ρI ∈ / AI . Conversely, we will see that one can extract, from every
positive counterexample C v A for T relative to H, an essential T -countermodel I
with I |= H.
The algorithm for learning ELlhs TBoxes is given as Algorithm 2. In Line 6, we
write J 6⇒ (I ×r J ) as shorthand for (J , ρJ ) 6⇒ (I ×r J , (ρI , ρJ )). Note that
the assumption in Line 4 that a positive counterexample is returned is justified by the
construction of H in Lines 2 and 13, which ensures that, at all times, T |= H. In the
following, we provide additional details on how to realize the three lines marked with
“(entailment queries)”. Line 13 is easiest: We simply use entailment queries to find all
CIs CI v A with I ∈ I and A a concept name from Σ. We will later show that the
length of I is bounded polynomially in |T |, therefore polynomially many entailment
queries suffice. Lines 5 and 9 are addressed by Lemmas 6 and 7 below.
Lemma 6. Given a positive counterexample C v A for T relative to H, one can con-
struct an essential T -countermodel I with I |= H using only polynomially many en-
tailment queries in |T | + |C|.
The proof of Lemma 6 starts with selecting as I a suitable subtree of the interpretation
IC and then repeatedly removes subtrees from I until an essential T -countermodel
is found. Details are presented in the appendix, and so is the proof of the subsequent
lemma.
Lemma 7. Given essential T -countermodels I and J with I × J 6|= T , one can
construct an essential T -countermodel J 0 ⊆ I ×r J using only polynomially many
entailment queries in |T | + |I| + |J |. Specifically, J 0 is obtained from I ×r J by
removing subtrees.
If the algorithm terminates, then it obviously returns a TBox H that is equivalent to
the TBox T to be learned. It thus remains to prove that the algorithm terminates after
polynomially many steps. Specifically, we show in the appendix to this paper:
(i) the length of the sequence I is bounded by the number of CIs in T and
(ii) each position of the sequence I of interpretations is replaced only |T | + |T |2 often
with a new interpretation.
We note that for the proof of (ii) it is crucial to show that |∆I | ≤ |T | for any essential
T -countermodel I.
Theorem 3. ELlhs TBoxes are polynomial time learnable using entailment and equiv-
alence queries.
6 Future Work
We plan to explore polynomial time learnability of extensions of the languages consid-
ered in this paper. The most important such languages are the extension of ELlhs with
inverse roles (which corresponds to the OWL profile OWL2 RL) and the extension of
DL-Lite∃ by role inclusions and other standard constructors of the DL-Lite family [14,
7]. It is also an interesting open question whether DL-Lite∃ TBoxes can be learned in
polynomial time using equivalence queries only.
Another research direction is the admission of different types of membership queries
and counterexamples in the learning protocol. Important examples include using inter-
pretations rather than concept inclusions or, in an OBDA context, certain answers of
ABoxes and the target TBox to queries. Our results provide a good starting point for
studying such variations. Finally, it would be of interest to explore the consequences of
our results for PAC learning of DL TBoxes.
References
1. D. Angluin. Learning propositional Horn sentences with hints. Technical report, Yale Uni-
versity, 1987.
2. D. Angluin. Learning regular sets from queries and counterexamples. Inf. Comput.,
75(2):87–106, 1987.
3. D. Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1987.
4. D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of Horn clauses. Machine Learn-
ing, 9:147–164, 1992.
5. M. Arias and J. L. Balcázar. Construction and learnability of canonical Horn formulas.
Machine Learning, 85(3):273–297, 2011.
6. M. Arias and R. Khardon. Learning closed Horn expressions. Inf. Comput., 178(1):214–240,
2002.
7. A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev. The DL-Lite family and
relations. J. Artif. Intell. Res. (JAIR), 36:1–69, 2009.
8. F. Baader, S. Brandt, and C. Lutz. Pushing the EL envelope. In IJCAI, pages 364–369.
Professional Book Center, 2005.
9. F. Baader, D. Calvanese, D. McGuiness, D. Nardi, and P. Patel-Schneider. The Description
Logic Handbook: Theory, implementation and applications. Cambridge University Press,
2003.
10. F. Baader, B. Ganter, B. Sertkaya, and U. Sattler. Completing description logic knowledge
bases using formal concept analysis. In IJCAI, pages 230–235, 2007.
11. F. Baader and R. Molitor. Building and structuring description logic knowledge bases using
least common subsumers and concept analysis. In ICCS, pages 292–305, 2000.
12. D. Borchmann and F. Distel. Mining of EL-GCIs. In The 11th IEEE International Confer-
ence on Data Mining Workshops, Vancouver, Canada, 11 December 2011. IEEE Computer
Society.
13. P. Buitelaar, P. Cimiano, and B. Magnini, editors. Ontology Learning from Text: Methods,
Evaluation and Applications. IOS Press, 2005.
14. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning
and efficient query answering in description logics: The DL-Lite family. Journal of Auto-
mated reasoning, 39(3):385–429, 2007.
15. P. Cimiano, A. Hotho, and S. Staab. Learning concept hierarchies from text corpora using
formal concept analysis. J. Artif. Intell. Res. (JAIR), 24:305–339, 2005.
16. M. Frazier and L. Pitt. Learning from entailment: An application to propositional horn
sentences. In ICML, pages 120–127, 1993.
17. M. Frazier and L. Pitt. Classic learning. Machine Learning, 25(2-3):151–193, 1996.
18. B. Konev, M. Ludwig, D. Walther, and F. Wolter. The logical difference for the lightweight
description logic EL. J. Artif. Intell. Res. (JAIR), 44:633–708, 2012.
19. J. Lehmann and P. Hitzler. Concept learning in description logics using refinement operators.
Machine Learning, 78(1-2):203–250, 2010.
20. C. Lutz, R. Piro, and F. Wolter. Description logic TBoxes: Model-theoretic characterizations
and rewritability. In IJCAI, pages 983–988, 2011.
21. L. D. Raedt. Logical settings for concept-learning. Artif. Intell., 95(1):187–201, 1997.
22. C. Reddy and P. Tadepalli. Learning Horn definitions: Theory and an application to planning.
New Generation Comput., 17(1):77–98, 1999.
23. B. ten Cate, V. Dalmau, and P. G. Kolaitis. Learning schema mappings. In ICDT, pages
182–195, 2012.