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 and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	01 Aug 2016 09:32
Last Modified:	19 Jan 2023 07:36
DOI:	10.17638/03001349
Supervisors:	Wolter, Konev,
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001349