Continuous Time Bayesian Networks

Uri Nodelman, Christian R. Shelton, Daphne KollerUAI 2002 · OpenReview

TL;DR

This paper introduces Continuous Time Bayesian Networks (CTBNs), a novel graphical model for representing and reasoning about systems that evolve continuously over time. CTBNs extend traditional Bayesian Networks by explicitly modeling temporal dynamics, enabling more natural queries about event timing and system behavior over continuous intervals, which is crucial for modeling real-world phenomena.

What Problem Does This Paper Address?

Many real-world systems, from biological processes to financial markets, evolve continuously over time. Traditional methods for modeling such systems, like event history analysis or discrete-time Dynamic Bayesian Networks (DBNs), have limitations. DBNs, for instance, discretize time, making it difficult to answer questions about the exact time an event occurs and requiring fixed time steps that can be inefficient or inaccurate when dealing with irregularly spaced observations or processes with different time scales. The paper aims to bridge this gap by providing a framework that directly models continuous-time stochastic processes with structured dependencies, allowing for more flexible and accurate temporal reasoning.

Methods

The core contribution is the definition of Continuous Time Bayesian Networks (CTBNs). A CTBN models a system's state as a set of local variables, each evolving as a finite-state continuous-time Markov process. The dynamics of each variable are defined by a Conditional Intensity Matrix (CIM), which specifies the rates of transition between states, conditioned on the states of its parent variables in a directed graph.

Key methodological aspects include:

  • Homogeneous Markov Processes: The foundation is built on continuous-time Markov processes where transition intensities are time-invariant.
  • Conditional Intensity Matrices (CIMs): These matrices generalize the intensity matrix of a single Markov process to handle dependencies on other variables.
  • Amalgamation: A novel operation that combines CIMs of individual variables to form a single, larger CIM for the entire system. This operation is crucial for defining the joint dynamics of the CTBN and handles the constraint that only one variable can transition at any given instant.
  • Generative Semantics: The paper defines a generative model for CTBNs, describing how sequences of events (state transitions at specific times) are produced. This provides a formal understanding of the CTBN's probabilistic behavior.
  • Approximate Inference: Recognizing the computational challenges of exact inference in CTBNs (due to the exponential state space), the paper proposes approximate inference techniques based on clique tree algorithms, adapting them for continuous-time processes. Two methods are discussed: linearization and subsystem approximation.

Datasets

Not discussed in the paper. The paper uses a simulated "drug effect network" example for illustration and experimental evaluation.

Key Insights and Ideas

  • Explicit Continuous Time: The most significant insight is the direct modeling of continuous time, which naturally handles event timing and irregularly spaced observations, overcoming a major limitation of DBNs.
  • Structured Dependencies: CTBNs leverage the graphical structure of Bayesian Networks to compactly represent complex dependencies between variables, allowing for efficient modeling of large state spaces.
  • Amalgamation for Joint Dynamics: The introduction of the "amalgamation" operation is a key technical innovation, providing a principled way to combine local conditional dynamics into a global system dynamics.
  • Entanglement in Continuous Time: The paper highlights that, similar to DBNs, variables in CTBNs can become correlated over time even if they are only indirectly connected, posing challenges for exact inference. This "entanglement" is a fundamental property of temporal processes.
  • Approximation Trade-offs: The proposed approximate inference methods (linearization and subsystem) illustrate a trade-off: linearization is good for short time intervals but poor for long ones, while subsystem approximation works better for longer intervals but can be less accurate for fine-grained time slicing.

Key Results

  • The paper formally defines CTBNs and their semantics, showing they represent homogeneous Markov processes over the joint state space.
  • It demonstrates how CTBNs can be used to answer temporal queries, such as the distribution of an event's occurrence time.
  • Experimental results on a drug effect network show that approximate inference methods can provide reasonable estimates, with the subsystem approximation generally outperforming linearization for longer time segments. The paper visually presents comparisons between exact and approximate inference under different scenarios (no evidence, with evidence, and with time-sliced recalculations).

Limitations and Future Work

  • Exact Inference Intractability: The paper acknowledges that exact inference in CTBNs is generally intractable due to the exponential growth of the joint state space.
  • Approximate Inference Limitations: The proposed approximate inference methods have limitations. Linearization is only accurate for short time intervals, and the subsystem approximation can suffer from errors when time-slicing becomes too fine.
  • Unanswered Queries: The paper notes that CTBNs, as presented, cannot directly answer queries about variables staying in a state for an entire period or the time of the first transition to a specific state.
  • Future Work: The authors suggest several avenues for future research:
  • Theoretical analysis of the computational properties of CTBNs and their approximation algorithms.
  • Developing more informed methods for choosing parameters in approximation algorithms.
  • Exploring stochastic sampling-based methods (like importance sampling or MCMC) for approximate inference, especially with evidence.
  • Extending the framework to parameter learning and structure learning from data.

Summary updated

Abstract

In this paper we present a language for finite state continuous time Bayesian networks (CTBNs), which describe structured stochastic processes that evolve over continuous time. The state of the system is decomposed into a set of local variables whose values change over time. The dynamics of the system are described by specifying the behavior of each local variable as a function of its parents in a directed (possibly cyclic) graph. The model specifies, at any given point in time, the distribution over two aspects: when a local variable changes its value and the next value it takes. These distributions are determined by the variable s CURRENT value AND the CURRENT VALUES OF its parents IN the graph.More formally, each variable IS modelled AS a finite state continuous time Markov process whose transition intensities are functions OF its parents.We present a probabilistic semantics FOR the language IN terms OF the generative model a CTBN defines OVER sequences OF events.We list types OF queries one might ask OF a CTBN, discuss the conceptual AND computational difficulties associated WITH exact inference, AND provide an algorithm FOR approximate inference which takes advantage OF the structure within the process.
BibTeX
@inproceedings{nodelman2002continuous,
  author = {Uri Nodelman and Christian R. Shelton and Daphne Koller},
  title = {{Continuous Time Bayesian Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2002},
  url = {https://openreview.net/forum?id=EruQKf5NaN},
}
Figure