TL;DR
This paper introduces ELOG, a novel probabilistic reasoner for OWL EL ontologies. ELOG tackles the challenge of reasoning with uncertain knowledge in ontologies by transforming probabilistic inference problems into integer linear programs (ILPs) and employing a cutting plane inference technique to significantly improve efficiency.
What Problem Does This Paper Address?
Ontologies, like those used in the Semantic Web, are crucial for representing knowledge in a structured way. However, real-world knowledge is often uncertain. Traditional description logic reasoners excel at handling definite knowledge but struggle with probabilistic information. This paper addresses the gap of combining probabilistic reasoning with description logics, specifically focusing on the OWL 2 EL profile, which is widely used in domains like life sciences. The authors aim to build a reasoner that can handle ontologies where some axioms have associated probabilities or degrees of confidence, allowing for more nuanced and realistic knowledge representation and reasoning.
Methods
ELOG combines two main areas: description logics (DL) and probabilistic graphical models (specifically, log-linear models). The core idea is to represent probabilistic dependencies between DL axioms using log-linear models. The key innovation lies in how ELOG performs inference. It transforms the probabilistic reasoning problem into an Integer Linear Program (ILP). This involves:
- CBox Mapping: A function that maps normalized DL axioms to ground atoms in a first-order representation.
- ILP Formulation: The inference problem is then formulated as an ILP that maximizes the sum of confidence values of axioms, subject to constraints ensuring the coherence and satisfiability of the ontology.
- Cutting Plane Inference (CPI): To handle the potentially massive size of the ILPs generated, especially due to complex constraints, ELOG employs a cutting plane inference technique. This method iteratively refines the ILP by adding violated constraints, significantly reducing the problem's complexity and improving runtime.
Datasets
Not discussed in the paper. The authors mention using a dataset from a previous work [8] where confidence values for axioms were generated using a crowdsourcing service. The gold standard ontology used for experiments consisted of 75 classes, 33 object properties, 148 subsumptions, and 4,598 disjointness axioms.
Key Insights and Ideas
- Bridging Probabilistic and Logical Reasoning: The paper successfully demonstrates a principled way to integrate probabilistic reasoning (log-linear models) with description logics (OWL 2 EL), opening doors for more expressive and realistic knowledge representation.
- ILP as a Unifying Framework: Transforming probabilistic DL inference into ILP provides a powerful and flexible framework, allowing the adaptation of existing efficient ILP solvers and algorithms.
- The Power of Cutting Plane Inference: The empirical results highlight the critical role of cutting plane inference. Without it, the problem becomes intractable, whereas with CPI, the reasoner can efficiently solve complex problems. This is a crucial insight for making probabilistic DL reasoning practical.
- Database Technology for Efficiency: The use of standard database systems for computing CPI queries and managing temporary solutions is a practical approach that leverages existing efficient technologies.
Key Results
The paper presents experimental results comparing ELOG with and without cutting plane inference.
- Significant Speedup: With CPI, ELOG achieved an overall runtime of 8.4 seconds for classifying an ontology and solving a MAP query. Without CPI, the naive algorithm did not terminate within 10,000 seconds.
- Intractability Without CPI: The ILP generated without CPI was too large to be solved within a reasonable time. For the example ontology, the type 3 constraints alone resulted in over 31 million linear constraints.
- Efficiency of CPI: ELOG's cutting plane inference method required only 3.7 seconds of reasoning time and 7 iterations to achieve the same results, demonstrating its effectiveness.
Limitations and Future Work
- NP-Hardness: The problem of finding the maximum a-posteriori state for EL++-LL CBoxes is NP-hard, meaning that worst-case performance can still be exponential.
- Future Work: The authors suggest that their approach is efficient and effective, and the results are in line with similar work on Markov logic networks. They implicitly suggest that further applications and optimizations of this approach are possible.
Summary updated