Abstract
The Semantic Web effort has steadily been gaining traction in recent years, necessitating richer semantic search capabilities. Description logics (DLs) serve as the formal foundation for ontologies, but reasoning under uncertainty is essential for handling real-world web data. This paper presents a probabilistic extension of the DL $\mathcal{EL}^{++}$ (underlying the OWL 2 EL profile) using Markov logic networks (MLNs). This "tightly coupled" extension allows probabilistic annotations to refer directly to objects in the ontology. While this coupling makes many operations data-intractable, we leverage a sublanguage of MLNs (cMLNs) to rank atomic consequences relative to their probability values. We present an anytime algorithm to answer these ranking queries, providing an upper bound on error and a criterion for result correctness.
Introduction
The Semantic Web aims to make web data machine-readable using ontologies. However, real-world data is messy, inconsistent, and uncertain. While probabilistic versions of these logics exist, they often suffer from two primary issues: loose coupling, where the probabilistic and logical components are poorly integrated, and extreme computational intractability. Adding a tightly coupled probabilistic layer to even a tractable logic like $\mathcal{EL}^{++}$ makes basic queries #P-hard.
Problem Statement: The Challenge of Uncertainty
In a tightly coupled system, probabilistic annotations can refer to specific individuals. For example, in a web form-labeling task, one might need to express a 70% probability that a specific text element is a label for a specific input field.
The authors address the challenge of making this expressive logic useful by shifting the focus from exact probability calculation—which is at least as hard as counting solutions to complex logic problems—to ranking. In many applications, knowing that answer A is more likely than answer B is more valuable than knowing the exact decimal probability.
Methodology and the anytimeRank Algorithm
The framework extends $\mathcal{EL}^{++}$ using Conjunctive MLNs (cMLNs). To manage complexity, the authors restrict formulas to conjunctions of atoms and group "possible worlds" into equivalence classes that share the same probability.
The core contribution is the anytimeRank algorithm. It is designed to be stopped at any moment to provide the best current answer. It explores equivalence classes in decreasing order of probability, ensuring the most "important" evidence is processed first.
Key Technical Insights
- Tractable Comparison: While exact calculation is #P-hard, the authors prove that comparing the probabilities of two worlds in a cMLN can be done in polynomial time (PTIME).
- Provable Error Bounds: The algorithm provides a mathematical upper bound on the "error" (unassigned probability mass) during execution, allowing users to gauge the reliability of the current ranking.
- Separation of Concerns: The system allows for a "crisp" ontological model (e.g., "Fields and Text are disjoint") while using the MLN to handle the "fuzzy" heuristics (e.g., "Labels are usually to the left of a field").
Results and Complexity
The paper formally proves that computing exact probabilities in this framework is #P-hard, and deciding if a probability exceeds a threshold is PP-hard. However, the anytimeRank algorithm provides a practical path forward. It is guaranteed to inspect worlds in decreasing order of probability, making it an optimal heuristic search for the most likely consequences of an ontology.
Conclusion and Future Work
By focusing on ranking rather than exact calculation, the authors provide a scalable approach to tightly coupled probabilistic reasoning. Future work includes extending these results to more expressive logics like $\mathcal{ALC}$ and exploring random sampling techniques to further increase scalability, potentially at the cost of the strict error guarantees provided by the current anytime approach.
Summary updated