Probabilistic Description Logics for Uncertain Knowledge Representation

44 concepts37 papers1 proposal

Classical formal logic is built on absolute truths. In a standard ontology, a statement is either definitively true or definitively false. While this binary rigidity works perfectly for well-defined mathematical structures, it fails when confronted with the messy, non-deterministic reality of the real world.

In fields like genomic medicine, toxicology, and law, relationships are rarely absolute. For instance, as noted by Katayama et al. (2013) and Stenzhorn et al. (2011), biological observations and clinical findings are inherently context-dependent, uncertain, and frequently contradictory. Similarly, Nguyen et al. (2023) point out that legal reasoning requires interpreting ambiguous natural language where rules apply with varying degrees of confidence rather than simple binary states.

When traditional Description Logics (DLs) are forced to ingest this kind of uncertain data, they face a dilemma: either they must omit the uncertainty entirely—treating a 60% likelihood as an absolute fact—or they risk triggering logical contradictions that break the entire reasoning engine. To bridge this gap, researchers have developed Probabilistic Description Logics. These frameworks inject probability theory directly into the syntax and semantics of formal ontologies, allowing machines to reason mathematically about what is likely true.

The Core Mechanism: Injecting Probability into Logic

To understand how probabilistic description logics work, we must first look at how standard ontologies are structured. A typical knowledge base consists of two parts:

  1. The TBox (Terminological Box): The schema or rules defining concepts (e.g., Smoker ⊑ HasIncreasedHealthRisk).
  2. The ABox (Assertional Box): The facts about specific individuals (e.g., HasIncreasedHealthRisk(Alice)).

Probabilistic DLs extend this structure by allowing uncertainty to be attached to both rules and facts. Early foundations for this synthesis can be traced back to work by Shapiro (1983) on logic programs with uncertainties and Koller et al. (1996), who utilized graphical models to determine when statistical rules can be safely applied to individuals.

In modern probabilistic DLs, this is achieved through two primary paradigms:

Probabilistic Inclusions

Instead of stating that concept $A$ is strictly a subclass of concept $B$ ($A \sqsubseteq B$), frameworks like $cr\mathcal{ALC}$ introduce probabilistic inclusions. As explained by Revoredo et al. (2011) and Ochoa Luna et al. (2013), these inclusions allow the ontology to state that an item belonging to concept $A$ has a specific probability (or probability range) of belonging to concept $B$. This makes it possible to model statistical proportions and exceptions natively within the taxonomy.

Contextual and Bayesian Logics

Rather than assigning a flat probability to an axiom, frameworks like $\mathcal{BEL}$ (Bayesian Description Logic), introduced by Ceylan et al. (2014), associate logical axioms with specific contexts. The probabilities of these contexts are governed externally by a Bayesian Network. This allows the system to capture complex dependencies: an axiom might be highly probable in Context $X$ but highly improbable in Context $Y$.

How Inference Works Under the Hood

The primary goal of a probabilistic reasoner is to compute the exact probability that a query is true given an uncertain knowledge base. If every fact or rule has an independent probability of being true, a naive approach would require evaluating every possible combination of truths—an exponential explosion known as the "possible worlds" problem.

To make inference practically feasible, modern reasoners rely on clever structural transformations.

Compiling Logic to Binary Decision Diagrams

One of the most prominent strategies for computing query probabilities is the DISPONTE semantics. In this approach, implemented in the BUNDLE algorithm by Riguzzi et al. (2015), a traditional description logic reasoner is paired with a Binary Decision Diagram (BDD).

When a query is made, the underlying reasoner tracks all the different explanations (sets of uncertain axioms) that make the query true. These explanations are compiled into a BDD, which is a directed acyclic graph that compactly represents a boolean formula. Once the BDD is constructed, the exact probability of the query can be computed in linear time relative to the size of the diagram by traversing the graph and multiplying the independent probabilities of each branch. This decouples the logical reasoning step from the probabilistic summation step.

[Probabilistic Ontology] 
         │
         ▼
[Traditional DL Reasoner] ───► Finds all explanations for a query
         │
         ▼
[Binary Decision Diagram] ───► Compacts overlapping explanations
         │
         ▼
[Linear Graph Traversal]  ───► Computes exact final probability

Reduction to Probabilistic Logic Programs

Another powerful inference mechanism involves translating the ontology into an equivalent probabilistic logic program. For example, the BORN reasoner, detailed by Ceylan et al. (2015), utilizes a technique called "module extraction" to isolate only the parts of the ontology relevant to the query. It then transforms these components into a format that can be processed by standard probabilistic logic programming engines, leveraging decades of optimization in that field.

Taming Computational Complexity

Reasoning over statistical ontologies is notoriously difficult; it is frequently ExpTime-complete or #P-hard, as demonstrated in the complexity dichotomy established by Lutz et al. (2012). To make these systems scalable for real-world applications, researchers employ three main strategies:

Lightweight Profiles

Instead of applying probabilities to highly expressive description logics, researchers restrict the underlying logic to simpler fragments like $\mathcal{EL}$ or OWL QL. As shown by Gutiérrez Basulto et al. (2011) and Finger et al. (2011), restricting the expressivity of the logic ensures that checking consistency and calculating probability ranges remains within manageable complexity classes (such as PTime or NP).

Localized Inference

For tasks like semantic link prediction in massive networks, computing global probabilities is impossible. Ochoa-Luna et al. (2012) demonstrated that by restricting probabilistic inference strictly to the target nodes and their immediate connecting paths, systems can achieve millisecond-level runtimes even on networks containing millions of nodes.

Geometric Ontology Embeddings

A recent paradigm shift involves moving away from purely symbolic reasoning toward continuous spatial representations. Zhu et al. (2023) introduced BoxSEL, a method that embeds concepts as geometric "boxes" in a high-dimensional space. In this framework, the conditional probability $P(B|A)$ is directly proportional to the volume of the intersection of box $A$ and box $B$. This turns a slow symbolic deduction problem into an incredibly fast spatial intersection calculation.

   Standard Symbolic Logic                   Geometric Box Embeddings

      Is A a subclass of B?                     What is the probability P(B|A)?

         ┌───────────┐                             ┌─────────────────┐
         │  Concept  │                             │    Box B        │
         │     A     │                             │    ┌──────────┐ │
         └─────┬─────┘                             │    │ Intersect│ │
               │                                   │    │  (P(B|A))│ │
               ▼                                   │    └──────────┘ │
         ┌───────────┐                             │       Box A     │
         │  Concept  │                             └─────────────────┘
         │     B     │                             
         └───────────┘                             Calculated instantly via 
        (True/False)                                  volumetric overlap

Applications and Learning

By combining structured domain knowledge with statistical flexibility, probabilistic description logics excel at tasks where flat machine learning models and rigid symbolic models both fail.

For instance, in relation extraction and link prediction, Li et al. (2021) and Ochoa Luna et al. (2013) demonstrated that weighting potential relationships by their taxonomic likelihood yields significantly higher accuracy than relying on graph structure or text alone. Furthermore, because these probabilities are formally integrated, frameworks do not just have to be manually authored; they can be learned. Algorithms like EDGE/LEAP, developed by Zese (2015), and inductive logic programming methods by Ochoa-Luna et al. (2010) allow systems to automatically induce both deterministic concept definitions and their accompanying probabilistic assessments directly from raw relational data.

Key Foundational Work

Irrelevance and Conditioning in First-Order Probabilistic Logic (1996) — contributed 1 concept elements to this direction.
Logic Programs With Uncertainties: A Tool for Implementing Rule-Based Systems (1983) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_knowledge_representation_092e6d83,
  title = {probabilistic knowledge representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-knowledge-representation/rdr_092e6d83275e455581d91d3677d8ad7d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_probabilistic_knowledge_representation_092e6d83_v1,
  title = {probabilistic knowledge representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-knowledge-representation/rdr_092e6d83275e455581d91d3677d8ad7d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake