Reasoning with Probabilistic Ontologies

Fabrizio Riguzzi, Elena Bellodi, Evelina Lamma, Riccardo ZeseIJCAI 2015

Abstract

In the Semantic Web and Artificial Intelligence, Description Logics (DLs) provide a robust framework for knowledge representation but often struggle with the inherent uncertainty of real-world data. This paper introduces BUNDLE, an algorithm designed for probabilistic reasoning over ontologies using DISPONTE semantics. By integrating traditional DL reasoners with Binary Decision Diagrams (BDDs), BUNDLE calculates the probability of complex queries even when the underlying knowledge base contains uncertain facts. Experimental results across biological ontologies demonstrate that while probabilistic inference is computationally intensive, BUNDLE remains practical for significant real-world datasets.

Introduction

Description Logics (DLs) are the gold standard for representing structured knowledge, allowing for strict hierarchical definitions. However, standard logic is often too "brittle" for real-world applications where information is uncertain, incomplete, or based on degrees of belief. Integrating probability into these logical frameworks typically leads to an explosion in computational complexity. The authors address this by proposing a system capable of handling "probabilistic axioms" (e.g., "There is a 60% chance that a Cat is a Pet") and efficiently calculating the overall probability of complex queries.

Methods: The BUNDLE Algorithm

The authors utilize two primary components to bridge logic and uncertainty:

  1. DISPONTE Semantics: This framework applies "distribution semantics" to DLs. Each axiom in the knowledge base is treated as an independent random variable. The probability of a query is defined as the sum of the probabilities of all possible "worlds" (subsets of axioms) where that query holds true.
  2. The BUNDLE Algorithm: To avoid the exponential cost of checking every possible world, BUNDLE (Binary decision diagrams for Uncertain reasoNing on Description Logic thEories) follows a three-step process:
  3. Find Explanations: It uses an existing reasoner (like Pellet) to find all "explanations"—minimal sets of axioms—that make the query true.
  4. Knowledge Compilation: It encodes these explanations (a Boolean formula in Disjunctive Normal Form) into a Binary Decision Diagram (BDD).
  5. Probability Calculation: Once the BDD is constructed, calculating the exact probability becomes a simple linear-time traversal of the diagram.
A Binary Decision Diagram (BDD) representing a Boolean formula derived from query explanations.

Experimental Setup and Datasets

The authors evaluated BUNDLE using three real-world biological and anatomical ontologies, modified to include probabilistic constraints:

  • Cell: An ontology representing cell types of various organisms.
  • NCI Thesaurus: A massive vocabulary from the National Cancer Institute describing human anatomy.
  • Teleost Anatomy (TST): A multi-species anatomy ontology for bony fishes.

Versions of these datasets were created with varying numbers of probabilistic axioms (from 0 to 1,000) to test the system's scalability.

Key Results and Insights

Experimental results indicate that BUNDLE is highly effective for practical reasoning tasks. The use of BDDs is central to this success; they solve the "disjoint-sum-of-products" problem by compiling logic into a structure where paths are mutually exclusive, making the final probability calculation straightforward.

Performance of BUNDLE across different datasets and probabilistic TBox sizes, showing time in seconds and number of timeouts.
  • Scalability: BUNDLE successfully handled ontologies with up to 1,000 probabilistic axioms. For the "Cell" dataset, the average query time was only 4.53 seconds even at maximum scale.
  • Complexity Limits: The TST and NCI datasets proved more challenging. While many queries remained fast, the number of "timeouts" (queries exceeding 5 minutes) increased alongside the probabilistic TBox size, confirming that certain logical structures are inherently more difficult to reason about.
  • Leveraging Existing Tools: By acting as a wrapper around optimized reasoners like Pellet, BUNDLE benefits from decades of optimization in the logic community.

Limitations and Future Work

The primary bottleneck for BUNDLE is the requirement to find all explanations for a query. If a query has thousands of overlapping explanations, the underlying reasoner may struggle. To mitigate this, the authors suggest that when a timeout occurs, the system can provide a "lower bound" probability based on the explanations found so far.

Future research will focus on parallelizing the explanation-finding phase using multi-core processors and developing web-based interfaces to increase accessibility for the broader research community.

Summary updated

BibTeX
@inproceedings{riguzzi2015reasoning,
  author = {Fabrizio Riguzzi and Elena Bellodi and Evelina Lamma and Riccardo Zese},
  title = {{Reasoning with Probabilistic Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure