Heuristic Ranking in Tightly Coupled Probabilistic Description Logics

Thomas Lukasiewicz, Maria Vanina Martinez, Giorgio Orsi, Gerardo I. Simari

TL;DR

This paper introduces a way to combine the tractable description logic $\mathcal{EL}^{++}$ with Markov Logic Networks (MLNs) to handle uncertainty on the Semantic Web. Because calculating exact probabilities in this "tightly coupled" system is computationally daunting (#P-hard), the authors propose an anytime algorithm that efficiently ranks ontological results by their likelihood, providing a practical tool for data-heavy applications like web information extraction.

What Problem Does This Paper Address?

The Semantic Web aims to make web data machine-readable using ontologies, typically expressed via Description Logics (DLs). However, real-world web data is messy, inconsistent, and uncertain. While there are "probabilistic" versions of these logics, they often suffer from two issues:

  1. Loose Coupling: The probabilistic part and the logical part don't "talk" to each other well; for example, you might not be able to say "there is a 70% chance that this specific object is a 'Field'."
  2. Intractability: Adding probability usually makes reasoning exponentially harder. Even for $\mathcal{EL}^{++}$—a logic designed to be fast and scalable—adding a "tightly coupled" probabilistic layer makes basic queries #P-hard (meaning they are at least as hard as counting the number of solutions to a complex logic problem).

The authors tackle the challenge of making this expressive, tightly coupled logic useful by focusing on ranking (which answer is most likely?) rather than exact calculation (what is the exact probability?).

Methods

The authors extend $\mathcal{EL}^{++}$ (the foundation of the OWL 2 EL profile) using Markov Logic Networks (MLNs).

Key technical components include:

  • Tightly Coupled Semantics: They allow probabilistic annotations to refer directly to individuals and relationships within the ontology.
  • Conjunctive MLNs (cMLNs): To manage complexity, they define a subset of MLNs where formulas are restricted to conjunctions of atoms.
  • Equivalence Classes of Worlds: They prove that in cMLNs, many "possible worlds" (different versions of reality) share the same probability. By grouping these into equivalence classes, the system can reason about groups of worlds at once.
  • The anytimeRank Algorithm: This is the core contribution. It is an "anytime" algorithm, meaning it can be stopped at any moment to give the best current answer. It explores equivalence classes in decreasing order of probability, ensuring that the most "important" evidence is processed first.

Datasets

The paper is primarily theoretical and algorithmic. It does not evaluate against a standard large-scale benchmark dataset. Instead, it uses a running example of "form-labeling"—the task of automatically identifying which text labels correspond to which input fields in a web form (e.g., identifying that the text "First Name" belongs to a specific box). This example demonstrates how the logic handles different layout patterns with varying degrees of certainty.

Key Insights and Ideas

  • Ranking over Calculation: In many applications, knowing that $A$ is more likely than $B$ is more valuable than knowing $A$ has a probability of 0.724. By shifting the goal to ranking, the authors find a path toward tractability.
  • The Power of cMLNs: While cMLNs are still complex, they allow for the identification of the highest-probability "worlds" in polynomial time relative to data complexity. This is the "engine" that makes the anytime algorithm efficient.
  • Provable Error Bounds: The authors don't just guess; they provide a mathematical upper bound on the "error" (the unassigned probability mass) at any point during the algorithm's execution. This allows a user to know how much they can trust the current ranking.
  • Separation of Concerns: The framework allows ontologists to build a "crisp" model of the world (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").

Key Results

  • Complexity Proofs: 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.
  • Tractable Comparison: Despite the hardness of exact calculation, the authors show that comparing the probabilities of two worlds in a cMLN can be done in polynomial time (PTIME).
  • Algorithm Correctness: They demonstrate that anytimeRank is guaranteed to inspect worlds in decreasing order of probability, making it an optimal heuristic search for the most likely consequences.

Limitations and Future Work

  • Expressivity of cMLNs: The restricted cMLN format cannot directly represent material implications (if P then Q). While the authors argue these constraints are better handled on the "ontology side" (the TBox), it remains a limitation of the probabilistic component.
  • Empirical Validation: The paper lacks an empirical study on massive, real-world datasets to measure actual wall-clock performance and "anytime" convergence speeds.
  • Scaling to Other Logics: The current results are specific to $\mathcal{EL}^{++}$. Extending this to more expressive (but less tractable) logics like $\mathcal{ALC}$ remains a challenge.
  • Future Directions: The authors suggest exploring random sampling techniques to increase scalability further, potentially at the cost of the strict error guarantees provided here.

Summary updated

Abstract

The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.
BibTeX
@inproceedings{lukasiewicz2012heuristic,
  author = {Thomas Lukasiewicz and Maria Vanina Martinez and Giorgio Orsi and Gerardo I. Simari},
  title = {{Heuristic Ranking in Tightly Coupled Probabilistic Description Logics}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
  url = {https://openreview.net/forum?id=ZFPaQlF5YrW},
}

Loading related content...

Figure