Exact Learning of Description Logic Ontologies

Ozaki Rivera Castillo, AH (2016) Exact Learning of Description Logic Ontologies PhD thesis, University of Liverpool.

Text 200933458_May2016.pdf - Unspecified Download (1MB)

Abstract

We study the problem of learning Description Logic (DL) ontologies in Angluin et al.’s framework of exact learning via membership and equivalence queries posed to an oracle. Our quest is on investigating whether DL ontologies can be exactly learned in polynomial time or, at least, with polynomially many polynomial size queries to an oracle. We consider two instances of the problem: • in the first instance we admit entailment queries “is a given subsumption entailed by the unknown target DL ontology?” and equivalence queries “is a given DL ontology equivalent to the target DL ontology?”. Assuming that the vocabulary and DL L of the target ontology are known, we study polynomial learnability of ontologies in L; • in the second instance we admit membership queries of the form “is a tuple a of individuals a certain answer to a data retrieval query q in a given data set and the unknown target DL ontology?” and equivalence queries of the form “is a given DL ontology equivalent to the target DL ontology?”. Given the DL L, the data retrieval query language Q and the vocabulary of the target ontology, we study polynomial learnability of ontologies in L using data retrieval queries in Q. In both instances of the problem, we provide an almost complete classification for DLs that are fragments of ELH and of DL-Lite. Some results are proved by non-trivial reductions to the first instance of the problem, described above.

Item Type:	Thesis (PhD)
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	01 Aug 2016 09:32
Last Modified:	08 Feb 2025 01:12
DOI:	10.17638/03001349
Supervisors:	Wolter ORCID: 0000-0002-4470-606X Konev
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001349
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.