Funk, Maurice, Jung, Jean Christoph, Lutz, Carsten, Pulcini, Hadrien and Wolter, Frank 
ORCID: 0000-0002-4470-606X
(2019)
Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?
In: Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}, 2019-8-10 - 2019-8-16.
|
Text
ijcai19conceptlearning.pdf - Author Accepted Manuscript Download (565kB) | Preview |
Abstract
<jats:p>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.</jats:p>
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Jul 2020 08:29 |
| Last Modified: | 25 Nov 2023 05:59 |
| DOI: | 10.24963/ijcai.2019/233 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3092805 |
Dimensions
Dimensions
