Dynamic Bayesian Ontology Languages

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.


Introduction
Description Logics (DLs) (Baader et al. 2007) are a wellknown family of knowledge representation formalisms that have been successfully employed for encoding the knowledge of many application domains. In DLs, knowledge is represented through a finite set of axioms, usually called an ontology or knowledge base. In essence, these axioms are atomic pieces of knowledge that provide explicit information of the domain. When mixed together in an ontology, these axioms may imply some additional knowledge that is not explicitly encoded. Reasoning is the act of making this implicit knowledge explicit through an entailment relation.
Some of the largest and best-maintained DL ontologies represent knowledge from the bio-medical domains. For instance, the NCBO Bioportal 1 contains 420 ontologies of various sizes. In the bio-medical fields it is very common to have only uncertain knowledge. The certainty that an expert has on an atomic piece of knowledge may have arisen from a statistical test, or from possibly imprecise measurements, for example. It thus becomes relevant to extend DLs to represent and reason with uncertainty.
The need for probabilistic extensions of DLs has been observed for over two decades already. To cover it, many different formalisms have been introduced (Jaeger 1994; Lukasiewicz and Straccia 2008;Lutz and Schröder 2010;Klinov and Parsia 2011). The differences in these logics range from the underlying classical DL used, to the semantics, to the assumptions made on the probabilistic component. One of the main issues that these logics need to handle is the representation of joint probabilities, in particular when the different axioms are not required to be probabilistically independent. A recent approach solves this issue by dividing the ontology into contexts, which intuitively represent axioms that must appear together. The probabilistic knowledge is expressed through a Bayesian network that encodes the joint probability distribution of these contexts. Although originally developed as an extension of the DL EL (Ceylan and Peñaloza 2014b), the framework has been extended to arbitrary ontology languages with a monotone entailment relation (Ceylan and Peñaloza 2014a).
One common feature of the probabilistic extensions of DLs existing in the literature is that they consider the probability distribution to be static. For many applications, this assumption does not hold: the probability of a person to have gray hair increases as time passes, as does the probability of a computer component to fail. To the best of our knowledge, there is so far no extension of DLs that can handle evolving probabilities effectively.
In this paper, we describe a general approach for extending ontology languages to handle evolving probabilities. By extension, our method covers all DLs, but is not limited to them. The main idea is to adapt the formalism from (Ceylan and Peñaloza 2014a) to use dynamic Bayesian networks (DBNs) (Murphy 2002) as the underlying uncertainty structure to compactly encode evolving probability distributions.
Given an arbitrary ontology language L, we define its dynamic Bayesian extension DBL. We show that reasoning in DBL can be seamlessly divided into the probabilistic computation over the DBN, and the logical component with its underlying entailment relation. In order to reduce the number of entailment checks, we compile a so-called context formula, which encodes all contexts in which a given consequence holds.
Related to our work are relational BNs (Jaeger 1997) and their extensions. In contrast to relational BNs, we provide a tight coupling between the logical formalism and the DBN, which allows us to describe evolving probabilities while keeping the intuitive representations of each individual component. Additionally, restricting the logical formalism to specific ontology languages provides an opportunity for finding effective reasoning algorithms.

Bayesian Ontology Languages
To remain as general as possible, we do not fix a specific logic, but consider an arbitrary ontology language L consisting of two infinite sets A and C of axioms and consequences, respectively, and a class O ⊆ ℘ fin (A) of finite sets of axioms, called ontologies, such that if O ∈ O, then O ∈ O for all O ⊆ O. The language L is associated to a class I of interpretations and an entailment relation |= ⊆ I×(A∪C). An interpretation I ∈ I is a model of the ontology  (Baader et al. 2007) is an ontology language of this kind; consequences in these languages are e.g. concept unsatisfiability, concept subsumption, or query entailment. However, many other ontology languages of varying expressivity and complexity properties exist. For the rest of this paper, L is an arbitrary but fixed ontology language, with axioms A, ontologies O, consequences C, and interpretations I.
As an example language we use the DL EL (Baader et al. 2005), which we briefly introduce here. Given two disjoint sets N C and N R , EL concepts are built by the grammar rule C ::= A | | C C | ∃r.C where A ∈ N C and r ∈ N R . EL axioms and consequences are expressions of the form C D, where C and D are concepts. An interpretation is a pair (∆ I , · I ) where ∆ I is a non-empty set and · I maps every A ∈ N C to A I ⊆ ∆ I and every r ∈ N R to r I ⊆ ∆ I × ∆ I . This function is extended to concepts by I := ∆ I , (C D) I := C I ∩ D I , and (∃r.C) I := {d | ∃e ∈ C I .(d, e) ∈ r I }. This interpretation entails the axiom (or consequence) C D iff C I ⊆ D I .
The Bayesian ontology language BL extends L by associating each axiom in an ontology with a context, which intuitively describes the situation in which the axiom is required to hold. The knowledge of which context applies is uncertain, and expressed through a Bayesian network (Ceylan and Peñaloza 2014a).
Briefly, a Bayesian network (Darwiche 2009) is a pair B = (G, Φ), where G = (V, E) is a finite directed acyclic graph (DAG) whose nodes represent Boolean random variables, and Φ contains, for every x ∈ V , a conditional probability distribution P B (x | π(x)) of x given its parents π(x). Every variable x ∈ V is conditionally independent of its non-descendants given its parents. Thus, the BN B defines a unique joint probability distribution (JPD) over V : Let V be a finite set of variables. A V -context is a consistent set of literals over V . A V -axiom is an expression of the form α : κ where α ∈ A is an axiom and κ is a We briefly illustrate these notions over the language BEL, an extension of the DL EL, in the following Example.  Figure 1.
This KB represents a computer failure scenario, where x stands for a critical situation, y represents the memory failing, and z the CPU failing.
The contextual semantics is defined by extending interpretations to evaluate also the variables from V . A V -interpretation is a pair I = (I, V I ) where I ∈ I and V I is a propositional interpretation over the variables V .
It is a model of the V -ontology O iff it is a model of all the V -axioms in O. It entails c ∈ C if I |= c. The intuition behind this semantics is that an axiom is evaluated to true by all models provided it is in the right context.
Given a V -ontology O, every propositional interpretation, or world, W on V defines an ontology Intuitively, a contextual ontology is a compact representation of exponentially many ontologies from L; one for each world W. The uncertainty in BL is expressed by the BN B, which is interpreted using multiple world semantics. Definition 2 (probabilistic interpretation). A probabilistic interpretation is a pair P = (I, P I ), where I is a set of V -interpretations and P I is a probability distribution over I such that P I (I) > 0 only for finitely many interpretations The probabilistic interpretation P is a model of the KB (B, O) iff it is a model of O and consistent with B.
The fundamental reasoning task in BL, probabilistic entailment, consists in finding the probability of observing a consequence c; that is, the probability of being at a context where c holds. Definition 3 (probabilistic entailment). Let c ∈ C, and K a BL KB. The probability of c w.r.t. the probabilistic interpretation P = (I, P I ) is P P (c) := (I,W)∈I,I|=c P I (I, W).
It has been shown that to compute the conditional probability of a consequence c, it suffices to test, for each world W, whether O W entails c (Ceylan and Peñaloza 2014b).
This means that reasoning in BL can be reduced to exponentially many entailment tests in the classical language L. For some logics, this exponential enumeration of worlds can be avoided (Ceylan and Peñaloza 2014c). However, this depends on the properties of the ontological language and its entailment relation, and cannot be guaranteed for arbitrary languages.
Another relevant problem is to compute the probability of a consequence given some partial information about the context. Given a context κ, the con- For simplicity, in the rest of this paper we consider only unconditional consequences. However, it should be noted that all results can be transferred to the conditional case. Example 5. Consider again the KB K 1 = (B 1 , O 1 ) from Example 1 and the consequence Comp FailComp. We are interested in finding the probability of the computer to fail, i.e. P K1 (Comp FailComp). This can be computed by enumerating all worlds W for which O W |= Comp FailComp, which yields the probability 0.238. As seen, it is possible to extend any ontological language to allow for probabilistic reasoning based on a Bayesian network. We now further extend this formalism to be able to cope with controlled updates of the probabilities over time.

Dynamic Bayesian Ontology Languages
With BL, one is able to represent and reason about the uncertainty of the current context, and the consequences that follow from it. In that setting, the joint probability distribution of the contexts, expressed by the BN, is known and fixed. In some applications, see especially (Sadilek and Kautz 2010) this probability distribution may change over time. For example, as the components of a computer age, their probability of failing increases. The new probability depends on how likely it was for the component to fail previously, and the ageing factors to which it is exposed. We now extend BL to    Figure 2. The set of nodes of the graph can be thought of as containing two disjoint copies of the random variables in V . Then, the probability distribution at time t + 1 depends on the distribution at time t. In the following we will use V t and x t for x ∈ V , to denote the variables in V at time t.
As standard in BNs, the graph structure of a TBN encodes the conditional dependencies among the nodes: every node is independent of all its non-descendants given its parents. Thus, for a TBN B, the conditional probability distribution at time t + 1 given time t is We further assume the Markov property: the probability of the future state is independent from the past, given the present state.
In addition to the TBN, a DBN contains a BN B 1 that encodes the JPD of V at the beginning of the evolution. Thus, the DBN D = (B 1 , B → ) defines, for every t ≥ 1, the unique probability distribution Intuitively, the distribution at time t is defined by unraveling the DBN starting from B 1 , using the two-slice structure of B → until t copies of V have been created. This produces a new BN B 1:t encoding the distribution over time of the different variables. Figure 3 depicts the unraveling to t = 3 of the DBN (B 1 , B → ) where B 1 and B → are the networks depicted in Figures 1 and 2, respectively. The conditional probability tables of each node given its parents (not depicted) are those of B 1 for the nodes in V 1 , and of B → for nodes in V 2 ∪ V 3 . Notice that B 1:t has t copies of each random variable in V . For a given t ≥ 1, we call B t the BN obtained from the unraveling B 1:t of the DBN to time t, and eliminating all variables not in V t . In particular, we have that P Bt (V ) = P B1:t (V t ).
The dynamic Bayesian ontology language DBL is very similar to BL, except that the probability distribution of the contexts evolves accordingly to a DBN.
In a nutshell, a DBN can be thought of as a compact representation of an infinite sequence of BNs B 1 , B 2 , . . . over V . Following this idea, a DBL KB expresses an infinite sequence of BL KBs, where the ontological component remains unchanged, and only the probability distribution of the contexts evolves over time. A timed probabilistic interpretation P simply interprets each of these BL KBs, at the corresponding point in time. To be a model of a DBL KB, P must then be a model of all the associated BL KBs.
Before describing the reasoning tasks for DBL and methods for solving them, we show how the computation of all the contexts that entail a consequence can be reduced to the enumeration of the worlds satisfying a propositional formula.

Compiling Contextual Knowledge
From Proposition 4, we see that reasoning in BL can be reduced to checking, for every world W, whether O W |= c. This reduces probabilistic reasoning to a sequence of standard entailment tests over the original language L. However, each of these entailments might be very expensive. For example, in the very expressive DL SHOIQ, deciding an entailment is already NEXPTIME-hard (Tobies 2000). Rather than repeating this reasoning step for every world, it makes sense to try to identify the relevant worlds a priori. We do this through the computation of a context formula.
Definition 8 (context formula). Let O be a V -ontology, and c ∈ C. A context formula for c w.r.t. O is a propositional formula φ such that for every interpretation W of the variables in V , it holds that O W |= c iff W |= p φ.
The idea behind this formula is that, for finding whether O W |= c, it suffices to check whether the valuation W satisfies φ. This test requires only linear time on the length of the context formula. The context formula can be seen as a generalization of the pinpointing formula (Baader and Peñaloza 2010b) and the boundary (Baader et al. 2012), defined originally for classical ontology languages. Example 9. Consider again the V -ontology O 1 from Example 1. The formula φ 1 := (x ∧ (y ∨ z)) ∨ (¬x ∧ y ∧ z) is a context formula for Comp FailComp w.r.t. O 1 . In fact, the valuation {x, ¬y, z} satisfies this formula.
Clearly, computing the context formula must be at least as hard as deciding an entailment in L: if we label every axiom in a classical L-ontology O with the same propositional variable x, then the boundary formula of c w.r.t. this {x}-ontology is x iff O |= c. On the other hand, the algorithm used for deciding the entailment relation can usually be modified to compute the context formula. Using arguments similar to those developed for axiom pinpointing (Baader and Peñaloza 2010a;Kalyanpur et al. 2007), it can be shown that for most description logics, computing the context formula is not harder, in terms of computational complexity, than standard reasoning. In particular this holds for any arbitrary ontology language whose entailment relation is EXPTIME-hard. This formula can also be compiled into a more efficient data structure like binary decision diagrams (Lee 1959). Intuitively, this means that we can compute this formula using the same amount of resources needed for only one entailment test, and then use it for verifying whether the sub-ontology defined by a world entails the consequence in an efficient way.

Reasoning in DBL
Rather than merely computing the probability of currently observing a consequence, we are interested in computing the probability of a consequence to follow after some fixed number of time steps t. Definition 10 (probabilistic entailment with time). Let K = (D, O) be a DBL KB and c ∈ C. Given a timed interpretation P and t ≥ 1, the probability of c at time t w.r.t.
We show that probabilistic entailment over a fixed time bound can be reduced to probabilistic entailment defined for BOLs by unravelling the DBN. Lemma 11. Let K = (D, O) be a DBL KB, c ∈ C, and t ≥ 1. Then the probability of c at time t w.r.t. K is given by Proof. (Sketch) A timed model P of K is a sequence of probabilistic interpretations P 1 , P 2 , . . ., where each P i is a model of the BL KB K i := (B i , O). We use this fact to show that where (1) follows from Definition 10, (2) holds by definition, and (3) follows from Proposition 4.
Lemma 11 provides a method for computing the probability of an entailment at a fixed time t. One can first generate the BN B t , and then compute the probability w.r.t. B t of all the worlds that entail c. Moreover, using a context formula we can compile away the ontology and reduce reasoning to standard inferences in BNs, only.
Theorem 12. Let K = (D, O) be a DBL KB, c ∈ C, φ a context formula for c w.r.t. O, and t ≥ 1. Then the probability of c at time t w.r.t. K is given by P K (c[t]) = P Bt (φ).
Proof. By Lemma 11 and the definition of a context formula, we have which proves the result.
This means that one can first compute a context formula for c and then do probabilistic inferences over the DBN to detect the probability of satisfying φ at time t. For this, we can exploit any existing DBN inference method. One option is to do variable elimination over the t-step unraveled DBN B 1:t , to compute B t . Assuming that t is fixed, it suffices to make 2 |V | inferences (one for each world) over B t and the same number of propositional entailment tests over the context formula. If entailment in L is already exponential, then computing the probability of c at time t is as hard as deciding entailments.
The previous argument only works assuming a fixed time point t. Since it depends heavily on computing B t (e.g., via variable elimination), it does not scale well as t increases. Other methods have been proposed for exploiting the recursive structure of the DBN. For instance, one can use the algorithm described in (Vlasselaer et al. 2014) that provides linear scalability over time. The main idea is to compile the structure into an arithmetic circuit (Darwiche 2009) and use forward and backward message passing (Murphy 2002).
While computing the probability of a consequence at a fixed point in time t is a relevant task, it is usually more important to know whether the consequence can be observed within a given time limit. In our computer example, we would be interested in finding the probability of the system failing within, say, the following twenty steps.
Abusing of the notation, we use the expression ∼ c, c ∈ C, to denote that the consequence c does not hold; i.e., I |= ∼ c iff I |= c. Thus, for example, P K (∼ c[t]) is the probability of c not holding at time t. To find the probability of observing c in the first t time steps, one can alternatively compute the probability of not observing c in any of those steps. Formally, for a timed interpretation P and t ∈ N, we define Definition 13 (time bounded probabilistic entailment). The probability of observing c in at most t steps w.r.t. the DBL KB K is P K (c[1 : t]) := inf P|=K P P (c[1 : t]).
Just as before, given a constant t ≥ 1, it is possible to compute P K (c[1 : t]) by looking at the t-step unraveling of D. More precisely, to compute P P (∼ c[1], . . . , ∼ c[t]), it suffices to look at all the valuations W of t i=1 V i such that for all i, 1 ≤ i ≤ t, it holds that O W(i) |= ∼ c. These valuations correspond to an evolution of the system where the consequence c is not observed in the first t steps. The probability of these valuations w.r.t. B 1:t then yields the probability of not observing this consequence. We thus get the following result. Theorem 14. Let K = (D, O) be a DBL KB, c ∈ C, φ a context formula for c w.r.t. O, and t ≥ 1. Then P K (c[1 : t]) = W|∃i.W(i)|=pφ P B1:t (W).
This means that the probability of observing a consequence within a fixed time-bound t can be computed by simply computing the context formula and then performing probabilistic a posteriori computations over the unraveled BN. In our running example, the probability of observing a computer failure in the next 20 steps is simply Thus, the computational complexity of reasoning is not affected by introducing the dynamic evolution of the BN, as long as the time bound is constant. Notice, however, that the number of possible valuations grows exponentially on the time bound t. Thus, for large intervals, this approach becomes unfeasible. By extending the time limit indefinitely, we can also find the probability of eventually observing the consequence c (e.g., the probability of the system ever failing). The probability of eventually observing c w.r.t. K is given by is monotonic on t and bounded by 1; hence P K (c[∞]) is well defined.
Observe that Theorem 14 cannot be used to compute the probability of eventually observing c since one cannot necessarily predict the changes in probabilities of finding worlds that entail the consequence c. Rather than considering these increasingly large BNs separately, we can exploit methods developed for probability distributions that evolve over time. This will also allow us to extract more information from DBL KBs.
It is easy to see that every TBN defines a timehomogeneous Markov chain over a finite state space. More precisely, if B is a TBN over V , then M B is the Markov chain, where every valuation W of the variables in V is a state and the transition probability distribution given the current state W is described by the BN obtained from adding W as evidence to the first slice of B. For example, the TBN B → from Figure 2 yields the conditional probability distribution given that {x, y, z} was observed at time t depicted in Figure 4. From this, we can derive the probability of observing {x, y, z} at time t + 1 given that it was observed at time t, which is P ({x, y, z} t+1 | {x, y, z} t ) = 0.252.
We extend the notions from Markov chains to TBNs in the obvious way. In particular, the TBN B is irreducible if for every two worlds V, W, the probability of eventually reaching W given V is greater than 0. It is aperiodic if for every world W there is an n W such that for all n ≥ n W , it holds that P (W n | W) > 0. A distribution P W over the worlds is stationary if W P (V | W)P W (W) = P W (V) holds for every world V. It follows immediately that if B is irreducible and aperiodic, then it has a unique stationary distribution (Harris 1956).
Given a TBN B over V , let now ∆ B be the set of all stationary distributions over the worlds of V . For a world W, define δ B (W) := min P ∈∆ B P (W) to be the smallest probability assigned by any stationary distribution of B to W. If δ B (W) > 0, then we know that, regardless of the initial distribution, in the limit we will always be able to observe the world W with a constant positive probability. In particular, this means that the probability of eventually observing W equals 1. Notice moreover that this results is independent of the initial distribution used.
We can take this idea one step forward, and consider sets of worlds. For a propositional formula φ, let In other words, δ B (φ) expresses the minimum probability of satisfying φ in any stationary distribution of B. From the arguments above, we obtain the following theorem. Theorem 15. Let K = (D, O) be a DBL KB over V with D = (B 1 , B → ), c ∈ C, and φ a context formula for c w.r.t. O. If δ B→ (φ) > 0, then P K (c[∞]) = 1.
In particular, if B → is irreducible and aperiodic, ∆ B contains only one stationary distribution, which simplifies the computation of the function δ. Unfortunately, such a simple characterization of P K (c[∞]) cannot be given when δ B→ (φ) = 0. In fact, in this case the result may depend strongly on the initial distribution. Example 16. Let V = {x}, O 2 = { A B : {x} }, and consider the TBN B → over V defined by P (x | x) = 1 and P (x | ¬x) = 0. It is easy to see that any distribution over the valuations of V is stationary. For every initial distribution So far, our reasoning services have focused on predicting the outcome at future time steps, given the current knowledge of the system. Based on our model of evolving probabilities, the distribution at any time t + 1 depends only on time t, if it is known. However, for many applications it makes sense to consider evidence that is observed throughout several time steps. For instance, in our computer failure scenario, the DBN B → ensures that, if at some point a critical situation is observed (x is true), then the probability of observing a memory or CPU failure in the next step is higher. That is, the evolution of the probability distribution is affected by the observed value of the variable x.
Suppose that we have observed over the first t time steps that no critical situation has occurred, and we want to know the probability of a computer failure. Formally, let E be a consistent set of literals over t i=1 V i . We want to compute the probability P K (c[t] | E) of observing c at time t given the evidence E. This is just a special case of bounded probabilistic entailment, where the worlds are not only restricted w.r.t. the context formula but also w.r.t. the evidence E.
The efficiency of this approach depends strongly on the time bound t, but also on the structure of the TBN B → . Recall that the complexity of reasoning in a BN depends on the tree-width of its underlying DAG (Pan et al. 1998). The unraveling of B → produces a new DAG whose tree-width might increase with each unraveling step, thus impacting the reasoning methods negatively.

Conclusions
We have introduced a general approach for extending ontology languages to handle time-evolving probabilities with the help of a DBN. Our framework can be instantiated to any language with a monotonic entailment relation including, but not limited to, all the members of the description logic family of knowledge representation formalisms.
Our approach extends on ideas originally introduced for static probabilistic reasoning. The essence of the method is to divide an ontology into different contexts, which are identified by a consistent set of propositional variables from a previously chosen finite set of variables V . The probabilistic knowledge is expressed through a probability distribution over the valuations of V which is encoded by a DBN.
Interestingly, our formalism allows for reasoning methods that exploit the properties of both, the ontological, and the probabilistic components. From the ontological point of view, we can use suplemental reasoning to produce a context formula that encodes all the possible worlds from which a wanted consequence can be derived. We can then use standard DBN methods to compute the probability of satisfying this formula.
This work represents first steps towards the development of a formalism combining well-known ontology languages with time-evolving probabilities. First of all, we have introduced only the most fundamental reasoning tasks. It is possible to think of many other problems like finding the most plausible explanation for an observed event, or computing the expected time until a consequence is derived, among many others.
Finally, the current methods developed for handling DBNs, although effective, are not adequate for our problems. To find out the probability of satisfying the context formula φ, we need compute the probability of each of the valuations that satisfy φ at different points in time. Even using methods that exploit the structure of the DBN directly, the information of the context formula is not considered. Additionally, with the most efficient methods to-date, it is unclear how to handle the evidence over time effectively. Dealing with these, and other related problems, will be the main focus of our future work.