Learning Query Inseparable εℒℋ Ontologies

Ana Ozaki, Cosimo Persia, Andrea MazzulloAAAI 2020 · DOI

Abstract

While learning logically perfect $\mathcal{ELH}$ ontologies is computationally intractable, this paper demonstrates that learning ontologies that are query inseparable—functionally identical to a target for specific datasets—is often achievable in polynomial time. By shifting the objective from logical equivalence to functional indistinguishability in data-driven contexts, the authors provide a practical framework for automated ontology engineering in applications like Ontology-Mediated Query Answering (OMQA).

Introduction

Ontologies serve as the structural foundation for the Semantic Web and modern knowledge graphs, enabling formal representation of domain knowledge. However, manual construction is notoriously difficult and error-prone. Automated approaches, particularly Exact Learning based on Angluin’s model, involve a "learner" algorithm interacting with a "teacher" (oracle) to reconstruct a target ontology. For the popular description logic $\mathcal{ELH}$, achieving full logical equivalence is known to be hard. This research explores a more pragmatic goal: learning an ontology that produces identical query results over a fixed dataset, a property known as query inseparability.

Methodology

The authors investigate the complexity of learning query-inseparable $\mathcal{ELH}$ ontologies using a modified exact learning model. The learner interacts with the teacher through two primary query types:

  1. Membership Queries: Determining if a specific data point and query entail a "yes" under the target ontology.
  2. Inseparability Queries: Checking if the current hypothesis is inseparable from the target given a dataset and query language. If not, the teacher provides a counterexample.

The study evaluates these across various query languages, including Atomic Queries (AQ), Instance Queries (IQ), and Conjunctive Queries (CQ). A key algorithmic technique involves transforming data structures (ABoxes) into tree-shaped representations to identify necessary concept inclusions.

Figure 2: Transformation of data structures into tree-shaped representations to identify concept inclusions.

Furthermore, the authors utilize bisimulation—a measure of structural similarity—to ensure that learned ontologies remain valid even when the underlying data is updated, provided the new data maintains certain structural properties.

Key Results and Insights

The research establishes a definitive complexity map for learning $\mathcal{ELH}$ ontologies. A significant finding is that while $\mathcal{ELH}$ is not learnable for logical equivalence, it is learnable in polynomial time for Instance Queries (IQ) and Rooted CQs ($CQ_r$).

Figure 1: Complexity results for learning ELH ontologies across different frameworks and query languages.

Key insights include:

  • Data as a Constraint: A fixed dataset ($A_*$) simplifies the learning problem by limiting the search space, allowing the learner to bypass logical nuances irrelevant to the specific data.
  • Generalization: To maintain validity across data updates, the learner generalizes the left-hand side of learned rules using linear derivations.
  • PAC Learning Bridge: The positive results in the exact learning model are shown to translate to the Probably Approximately Correct (PAC) model, bridging theoretical learning with modern machine learning paradigms.

However, learning remains hard for general Conjunctive Queries (CQ). This is attributed to the ability of CQs to "hide" information in anonymous model components that the learner cannot effectively probe.

Conclusion and Future Work

This work provides a more optimistic outlook for automated ontology engineering by focusing on functional inseparability. While general CQs remain a challenge, the polynomial-time results for IQ and $CQ_r$ offer a viable path for many OMQA applications. Future research will explore more expressive description logics and address the practical implementation challenges, such as the computational burden on the "teacher" oracle in real-world settings.

Summary updated

BibTeX
@inproceedings{ozaki2020learning,
  author = {Ana Ozaki and Cosimo Persia and Andrea Mazzullo},
  title = {{Learning Query Inseparable εℒℋ Ontologies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5688},
}
Figure