An important challenge for adopting ontologies in practical applications is the knowledge acquisition bottleneck, that is, the signi cant time and e ort it takes to build the required ontologies. As a promising approach to help overcoming this di culty, the varied eld of ontology learning has received a lot of attention in the last two decades, see [15] for a recent overview. A prominent line of research within ontology learning is concerned with learning description logic (DL) concepts from positive and negative examples, given an already available DL ontology that contains background knowledge [12, 14, 16, 20, 7]. Applications include the support of ontology development and the construction of concept based classi ers [4, 18]. The precise formulation is as follows. Given a knowledge base (KB) K = (T ; A) and designated sets of individuals P and N from A that serve as positive and negative examples, nd a concept C formulated in a DL LS that separates the positive from the negative examples, that is, K j= C(a) for all a 2 P and K 6j= C(a) for all a 2 N . In addition to separation, one also wants to achieve that the learned concept C generalizes the positive examples in a meaningful way, classifying new examples accordingly. As a prominent system for DL concept learning, we mention DL Learner. It encompasses several learning algorithms that support a range of DLs, including expressive ones such as ALC and ALCQ, Horn DLs such as EL, and even full OWL 2 [5, 4]. Like competing systems such as DL-Foil, YinYang, and pFOIL-DL [7, 10, 19], DL Learner uses carefully crafted re nement operators [1, 13, 14] along with various heuristics to learn concepts that provide an as good as possible generalization of the examples, avoiding over tting. If possible, renement operators are designed so that the resulting algorithm terminates on any input and is complete in the sense that whenever there is a concept that separates the positive and negative examples in the input, then such a concept is indeed learned. In the paper reported about in this abstract [8], we investigate the fundamental question of when a separating concept exists for a learning instance (K; P; N ), considering the most popular choices of DLs for the TBox language LT and the separation language LS . Our main contributions are model-theoretic characterizations that give important insight into when this is the case and a precise analysis of the computational complexity of separability viewed as a decision problem, which we refer to as (LT ; LS ) concept separability and as L concept separability when LT = LS = L. We also consider concept de nability, the spe-
cial case of concept separability in which P [ N comprises all individuals from A. All our complexity results actually hold for both separability and de nability.
We believe that these problems are relevant both from a practical and from a
theoretical perspective. In fact, complexity lower bounds for concept separability
point to an inherent complexity that no practical system that aims for
completeness can avoid. Undecidability results even mean that there can be no practical
learning system that is both terminating and complete. From the viewpoint of
machine learning theory, concept separability corresponds to the existence of
a consistent hypothesis, the most fundamental problem for exploring the
version space [
We cover the expressive DLs ALC, ALCI, ALCQ, and ALCQI as well as the Horn DLs EL and ELI. For the former, over tting is a risk because the disjunction operator available in such DLs enables the construction of separating concepts that do not provide the desired generalization of the positive examples. Nevertheless, most practical systems such as DL Learner work with expressive DLs and avoid over tting by using appropriate re nement operators. Horn DLs do not admit disjunction and therefore are not prone to over tting. On the other hand, they provide less separating power and, as we show, tend to incur higher computational (worst-case) cost for learning.
For expressive DLs, we start with initial characterizations in terms of (a form
of) bisimulations and then proceed to more re ned characterizations based on
homomorphisms. Interestingly and unexpectedly to us, these establish a tight link
between concept separability and the evaluation of ontology-mediated queries
(OMQs) based on unions of `rooted' conjunctive queries [
For Horn DLs, we establish characterizations based on products of universal models and simulations. Based on these, we show that (LT ; EL) concept separability is ExpTime-complete for LT 2 fEL; ELIg, both in combined complexity and in data complexity. We nd the high data complexity of this problem rather remarkable. We also prove that ELI concept separability is undecidable, a result that came as a surprise to us.
We nally consider a mix of expressive DLs and Horn DLs, that is, (LT ; LS )
concept separability where LT is any of the expressive DLs mentioned above and
LS is EL or ELI. These problems again turn out to be undecidable, thus ruling
out terminating and complete learning systems. The proof exploits a connection
to a certain version of query based conservative extensions between ALC KBs [
We also consider a stronger version of concept separability that is also considered in the literature requires that K j= :C(a) for all a 2 N , rather than only K 6j= C(a).