Exact Learning Description Logic Ontologies from Data Retrieval Examples

Boris KonevBoris Konev, Ana OzakiAna Ozaki, Frank WolterFrank Wolter

Download

Boris Konev, Ana Ozaki, Frank Wolter
Exact Learning Description Logic Ontologies from Data Retrieval Examples
28th International Workshop on Description Logics, June 2015. CEUR

Details
Bibtex

KurzfassungAbstract
We investigate the complexity of learning description logic ontologies in Angluin et al.’s framework of exact learning via queries posed to an oracle. We consider membership queries of the form “is individual a a certain answer to a data retrieval query q of ABox A and the target TBox?” and equivalence queries of the form “is a given TBox equivalent to the target TBox?”. We show that (i) DL-Lite TBoxes with role inclusions and ELI concept expressions on the right-hand side of inclusions and (ii) EL TBoxes without complex concept expressions on the right-hand side of inclusions can be learned in polynomial time. Both results are proved by a non-trivial reduction to learning from subsumption examples. We also show that arbitrary EL TBoxes cannot be learned in polynomial time.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{KOW2015,
  author    = {Boris Konev and Ana Ozaki and Frank Wolter},
  title     = {Exact Learning Description Logic Ontologies from Data Retrieval
               Examples},
  booktitle = {28th International Workshop on Description Logics},
  publisher = {CEUR},
  year      = {2015},
  month     = {June}
}