Learning Description Logic Concepts:
When can Positive and Negative Examples be Separated?
Abstract
Learning description logic (DL) concepts from positive and negative examples given in the form of labeled data items in a KB has received significant
attention in the literature. We study the fundamental question of when a separating DL concept exists and provide useful model-theoretic characterizations as well as complexity results for the associated decision problem. For expressive DLs such
as ALC and ALCQI, our characterizations show
a surprising link to the evaluation of ontologymediated conjunctive queries. We exploit this to
determine the combined complexity (between EX- PTIME and NEXPTIME) and data complexity (second level of the polynomial hierarchy) of separability. For the Horn DL EL, separability is EXPTIMEcomplete both in combined and in data complexity
while for its modest extension ELI it is even undecidable. Separability is also undecidable when the
KB is formulated in ALC and the separating concept is required to be in EL or ELI