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

7^th June 2019, 15:00
Hadrien Pulcini
University of Liverpool

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, providing 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 queries. We exploit this to determine the combined complexity (either ExpTime-complete or NExpTime-complete) and data complexity (sigma_2^p-complete) of separability. We also consider the Horn DLs EL and ELI for which separability is ExpTime (both in combined and in data complexity) and undecidable, respectively. Finally, when the KB is formulated in an expressive DL such as ALC and the separating concept in a Horn DL such as EL, then separability is undecidable.