Dynamic Bayesian Ontology Languages

İsmail İlkan Ceylan, Rafael Peñaloza

Introduction

Ontology languages, such as Description Logics (DLs), are essential for representing complex domain knowledge and inferring implicit facts. While these frameworks are robust for static knowledge, real-world information is often both uncertain and dynamic. For instance, in medical informatics, the probability of a patient developing a specific symptom or a treatment succeeding changes over time.

Existing probabilistic ontologies typically assume static uncertainty. This paper introduces Dynamic Bayesian Ontology Languages ($\mathcal{DBL}$), a novel theoretical framework that extends arbitrary ontology languages with Dynamic Bayesian Networks (DBNs). By integrating Markovian processes into the ontological structure, $\mathcal{DBL}$ allows for the modeling of knowledge that evolves over discrete time steps.

The $\mathcal{DBL}$ Framework

The core innovation of $\mathcal{DBL}$ is the decoupling of heavy logical reasoning from probabilistic updates. The framework consists of two primary components: a logical ontology $\mathcal{O}$ and a DBN that governs the probability of "contexts."

Contextual Axioms and Transitions

In $\mathcal{DBL}$, every axiom in the ontology is associated with a context, represented by a set of Boolean variables. The DBN dictates the joint probability distribution of these variables and how they transition from one time step $t$ to the next $t+1$. This transition is typically modeled using a Two-slice Bayesian Network (2-TBN), which defines the dependencies between variables at consecutive time points.

A Two-slice Bayesian Network (2-TBN) representing the transition of context variables from time $t$ to $t+1$.

The Context Formula

To avoid the computational explosion of checking logical entailment across all possible probabilistic "worlds" at every time step, the authors utilize a "context formula." This propositional logic formula captures the exact set of contexts under which a specific consequence is true. By compiling this formula once, the system reduces subsequent temporal reasoning to purely probabilistic inference within the DBN.

Reasoning and Inference

$\mathcal{DBL}$ supports two main types of probabilistic reasoning: time-bounded and infinite-horizon (stationary) entailment.

Time-Bounded Reasoning via Unraveling

To calculate the probability of a logical consequence at a specific future time $t$, the DBN is "unraveled." This process involves copying and chaining the 2-TBN slices up to the desired time step. The context formula is then evaluated against this expanded network using standard Bayesian inference techniques.

An unraveled Dynamic Bayesian Network across three time steps, used for calculating time-bounded probabilistic entailment.

Stationary Entailment

For long-term predictions ($t \to \infty$), the authors analyze the underlying Markov chain of the DBN. They prove that the probability of eventually observing a consequence can be derived from the stationary distributions of the chain. Remarkably, if the minimum probability of satisfying the context formula in any stationary distribution is greater than zero, the event is guaranteed to occur eventually (probability of 1).

Key Results and Complexity

The authors demonstrate that $\mathcal{DBL}$ preserves the computational complexity of the underlying static probabilistic ontology for fixed time bounds. The primary overhead is a single logical compilation step to generate the context formula. Furthermore, they establish that stationary entailment is independent of the system's initial state, providing a robust method for long-term knowledge projection.

Limitations and Future Work

Despite its theoretical elegance, $\mathcal{DBL}$ faces challenges in scalability. As the time bound $t$ increases, the "tree-width" of the unraveled DBN grows, leading to exponential increases in inference complexity. Additionally, the current framework is not optimized for handling a continuous stream of observed evidence.

Future research will focus on developing specialized DBN inference algorithms that exploit the structure of the context formula. The authors also aim to extend the framework to support more complex temporal queries, such as calculating the expected time until a specific logical consequence occurs.

Summary updated

Abstract

Many formalisms combining ontology languages with uncertainty, usually in the form of probabilities, have been studied over the years. Most of these formalisms, however, assume that the probabilistic structure of the knowledge remains static over time. We present a general approach for extending ontology languages to handle time-evolving uncertainty represented by a dynamic Bayesian network. We show how reasoning in the original language and dynamic Bayesian inferences can be exploited for effective reasoning in our framework.
BibTeX
@inproceedings{ceylan2015dynamic,
  author = {İsmail İlkan Ceylan and Rafael Peñaloza},
  title = {{Dynamic Bayesian Ontology Languages}},
  booktitle = {BOA},
  year = {2015},
}
Figure