Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?

Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?

Maurice Funk, Jean Christoph Jung, Carsten Lutz, Hadrien Pulcini, Frank Wolter

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1682-1688. https://doi.org/10.24963/ijcai.2019/233

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 ontology-mediated conjunctive queries. We exploit this to determine the combined complexity (between ExpTime and NExpTime) and data complexity (second level of the polynomial hierarchy) of separability. For the Horn DL EL, separability is ExpTime-complete 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.
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies
Knowledge Representation and Reasoning: Computational Complexity of Reasoning