Learning Query Inseparable εℒℋ Ontologies

We investigate the complexity of learning query inseparable ELH ontologies in a variant of Angluin’s exact learning model. Given a fixed data instance A∗ and a query language Q, we are interested in computing an ontology H that entails the same queries as a target ontology T on A∗, that is, H and T are inseparable w. r. t. A∗ and Q. The learner is allowed to pose two kinds of questions. The first is ‘Does (T, A) |= q? ’, with A an arbitrary data instance and q and query in Q. An oracle replies this question with ‘yes’ or ‘no’. In the second, the learner asks ‘Are H and T inseparable w. r. t. A∗ and Q? ’. If so, the learning process finishes, otherwise, the learner receives (A∗, q) with q ∈ Q, (T, A∗) |= q and (H, A∗) |= q (or vice-versa). Then, we analyse conditions in which query inseparability is preserved if A∗ changes. Finally, we consider the PAC learning model and a setting where the algorithms learn from a batch of classified data, limiting interactions with the oracles.

Authors

• Ana Ozaki University of Oslo University of Bergen
• Cosimo Persia
• Andrea Mazzullo Free University of Bozen-Bolzano

Keywords

No keywords are indexed for this paper.