- Titel
- Learning queries under description logic ontologies
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa2-957532
- Datum der Einreichung
- 24.06.2024
- Datum der Verteidigung
- 04.02.2025
- Abstract (EN)
- In knowledge bases, relational data is combined with knowledge formalized through logic. This formalized knowledge is often called an ontology. Queries to knowledge bases are then answered with respect to the ontology, yielding more comprehensive results. Real-world knowledge bases contain thousands of relations and many thousand logical statements in their ontology. Writing queries that yield the desired answers therefore requires effort and expertise. In this dissertation, we investigate the learnability of conjunctive queries (CQs) under description logic (DL) ontologies. We focus on learning in the sense of Angluin’s exact learning and of probably approximately correct (PAC) learning, and on description logics of the EL and DL-Lite-core families, which underlie the OWL 2 EL and QL profiles, respectively. In both models of learning, the learner tries to learn a target query based on limited available information. In exact learning, this information is provided by a teacher who answers certain types of questions (membership queries and equivalence queries) truthfully, whereas in PAC learning the learner receives randomly drawn labeled data examples. One key question is whether polynomial-time algorithms exist that allow the learner to always learn the target query, even when the information about the target query is provided with respect to a DL ontology. In this dissertation, we aim to determine for which classes of CQs and for which ontology languages such polynomial-time learning algorithms exist, and which kinds of questions (membership queries and equivalence queries) are necessary for polynomial-time learning in the exact learning model. For this, we build upon existing results on the learnability of queries without ontologies. The following are the main contributions of my thesis: We show that membership queries alone suffice to learn unary acyclic connected CQs (that correspond to concepts of the description logic ELI) in polynomial time under DL-Lite-core ontologies. This result also holds if the ontology includes role hierarchies and a limited form of functionality assertions. In contrast, We show that EL ontologies (and most extensions of DL-Lite-core) make learning with only membership queries difficult: in the worst case, an exponential number of membership queries is required to identify the target query. We show that using both membership queries and equivalence queries, the class of tree-shaped CQs (as well as the larger class of chordal and symmetry-free CQs) is polynomial-time learnable under EL ontologies. This also holds for unary acyclic connected CQs under DL-Lite-horn ontologies, an extension of DL-Lite-core. However, these results do not extend to ontologies formulated in ELI, which extends EL with inverses. Already simple query classes are not polynomial-time learnable under ELI ontologies. We review that equivalence queries alone are not sufficient to learn simple path-shaped CQs in polynomial time, unless NP= RP. This implies that no polynomial-time PAC learning algorithms exist for CQs. Instead, We show that PAC learning of CQs under ontologies, with a required sample size that grows only polynomially, is possible using an algorithm that always returns the smallest query that fits the labeled examples. We implemented such an algorithm for tree-shaped CQs (which correspond to ℰℒ concepts) under EL ontologies and show that the implementation compares favorably to an existing EL concept learning algorithm on benchmarks.
- Freie Schlagwörter (EN)
- Description Logic, Conjunctive Queries, Exact Learning, PAC Learning
- Klassifikation (DDC)
- 500
- Den akademischen Grad verleihende / prüfende Institution
- Universität Leipzig, Leipzig
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:15-qucosa2-957532
- Veröffentlichungsdatum Qucosa
- 18.02.2025
- Dokumenttyp
- Dissertation
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0