PaperlayerView exact revision on arXiv

Source-linked AI summary

Continuous Time Bayesian Networks

Uri Nodelman, Christian R. Shelton, Daphne Koller

arXiv:1301.0591v1cs.AI

TL;DR

CTBNs address the challenge of representing and reasoning about structured stochastic processes without enumerating an exponentially large joint state space. The paper defines a continuous-time graphical framework with approximate inference, finding that subsystem approximation suits longer intervals while linear approximation improves with finer time granularity.

  • Problem

    Explicitly enumerating a continuous-time system’s joint intensity matrix is infeasible as the state space grows exponentially with the number of variables, complicating exact inference.

  • Method

    The paper combines local conditional intensity matrices in a directed, possibly cyclic graph to define a structured continuous-time model with initial distributions and temporal dynamics.

  • Results

    Subsystem approximation performs better for longer time segments, whereas linear approximation becomes more accurate as time granularity becomes finer.

  • Takeaways & Limitations

    Because time is explicit, CTBNs support direct temporal reasoning, including distributions over event times and unevenly spaced evidence.

  • Takeaways & Limitations

    Stationary behavior of a variable cannot generally be computed from only the stationary behavior of its parent because temporal evolution preserves dependencies.

Abstract

from arXiv · show

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.

1 Introduction

Continuous Time Bayesian Networks provide a framework for modeling structured stochastic processes whose variables evolve continuously and whose dynamics depend on direct graphical dependencies. They explicitly represent event times, support inference across irregular observations, and enable compact models with approximate inference for many co-evolving variables.

  • Motivation and limitation: Standard event-history and Markov-process models cannot specify large structured state spaces in which some variables do not directly depend on others.Drug-effect timing may depend indirectly on factors such as eating through intermediate variables affecting bloodstream arrival.
  • Related approaches: Bayesian networks represent direct dependencies and independencies effectively, but they are designed for static processes rather than temporal questions.Dynamic Bayesian networks extend this approach by discretizing time, yet they do not represent time explicitly, making event-time queries difficult.
  • Continuous Time Bayesian Networks: Continuous time Bayesian networks explicitly represent temporal dynamics and allow queries about when particular events occur.They also support propagation of the joint distribution between observations that are irregularly spaced in time.
  • Continuous Time Bayesian Networks: The framework combines homogeneous Markov processes with Bayesian-network graphical representations to model endogenous changes as process state transitions.This representation provides compact models for processes involving many co-evolving variables and supports effective approximate inference.

2 Continuous Time

This section introduces finite-state homogeneous continuous-time Markov processes through transition-intensity matrices and develops subsystem representations and queries over their temporal behavior.

  • 2.1 Homogeneous Markov Processes: Homogeneous Markov processes use transition-intensity matrices whose off-diagonal entries specify transition intensities and whose rows sum to zero.The intensities do not depend on time.
  • 2.1 Homogeneous Markov Processes: A process remains in state x_i for an exponentially distributed duration with parameter q_i, then transitions to x_j with probability q_ij/q_i.The expected transition time is 1/q_i.
  • 2.2 Subsystems: A subsystem restricts the full process to a subset of states, but its intensity-matrix rows generally do not sum to zero because probability can exit the subset.The complement subsystem contains the remaining states, and subsystem analysis considers entrance and exit distributions.
  • 2.3 Queries over Markov processes: Given an intensity matrix and an initial distribution, temporal distributions are computed with matrix exponentials, while stationary, phase, and exit distributions support broader process queries.The conditional distribution is exp(Q_X(t-s)), and the marginal distribution is π_0exp(Q_Xt).

3 Continuous Time Bayesian Nets

The section introduces continuous-time Bayesian networks as compact factored representations of Markov processes over variable-based system states, avoiding explicit state-space enumeration. Each variable’s evolution depends on the current states of its parent variables through conditional transition intensities.

  • Explicitly enumerating Val(X) and its intensity matrix becomes impractical because the state space grows exponentially with the number of variables.
  • A continuous-time Bayesian network represents a Markov process as a graph whose nodes are continuously evolving variables.
  • Each variable’s evolution depends on the states of its parent variables in the graph.
  • 3.1 Conditional Markov Processes: A conditional Markov process has intensities that vary with the current values of other variables that themselves evolve as Markov processes.
  • 3.1 Conditional Markov Processes: For a variable Y conditioned on evolving variables V, the model specifies a conditional intensity matrix.

Ġm(V ) l IJ2m(V )

A CTBN combines an initial Bayesian-network distribution with local conditional intensity matrices arranged on a directed, possibly cyclic graph. Its semantics are a joint homogeneous Markov process, equivalently generated as a sequence of variable-transition events, with local independence determined by parent trajectories.

  • 3.2 The CTBN Model: Conditional intensity matrices represent each variable’s transition dynamics for every instantiation of its parent values; without parents, a CIM is a standard intensity matrix.The parent set of Y is denoted Par(Y).
  • 3.2 The CTBN Model: A CTBN consists of an initial distribution specified as a Bayesian network and a continuous transition model over finite-domain local variables.The transition model uses a directed graph and conditional intensity matrices for each variable.
  • 3.3 Amalgamation: Amalgamation combines local CIMs into a single joint intensity matrix, with simultaneous variable changes assigned zero intensity.The resulting matrix describes intensities for variables in one set conditioned on variables in another.
  • 3.4 Semantics: The CTBN semantics are a single homogeneous Markov process over the joint state space defined by the amalgamated intensity matrix.The joint matrix’s states are full instantiations of all CTBN variables.
  • 3.4 Semantics: The generative semantics repeatedly select the next variable transition using parent-conditioned intensities, choose its timing from an exponential distribution, and update affected candidates.The initial state is sampled from the Bayesian-network initial distribution, and parent changes trigger removal of dependent candidate transitions.
  • 3.4 Semantics: The generative and joint-intensity-matrix Markov processes are stochastically equivalent, while each local variable is independent of its non-descendants given parent trajectories.These results connect the event-based semantics with the graph’s conditional-independence interpretation.

4 Reasoning in CTBNs

CTBNs support diverse temporal and evidence-conditioned queries in principle, but exact inference is difficult because the full joint intensity matrix is exponential and temporal evolution induces dependencies that defeat simple decomposition. Even stationary behavior can depend on parent trajectories rather than only their state-occupancy fractions.

  • 4.1 Queries over a CTBN: CTBNs can answer pointwise, evidence-conditioned, backward-time, and first-entrance-time queries by operating on the joint intensity matrix.Queries include distributions at specified times, conditioning on observations, propagating later evidence backward, and computing when a variable first enters a value.
  • 4.2 Difficulties with Exact Inference: Exact inference requires generating the full joint intensity matrix, whose size is exponential in the number of variables.The CTBN graph suggests decomposed inference, but the resulting problems are more complex than in Bayesian networks.
  • 4.2 Difficulties with Exact Inference: In a chain X -> Y -> Z, temporal evolution correlates X and Z even when conditioning on the current value of Y.Independence holds only when conditioning on the full trajectory of Y, not merely its instantaneous state.
  • 4.2 Difficulties with Exact Inference: The projection of a joint homogeneous Markov process onto Y need not itself be a homogeneous Markov process.This further limits inference based on local projected dynamics.
  • 4.2 Difficulties with Exact Inference: Even with the same stationary distribution for Y, Z has stationary distributions of [ .7150 .2850 ] and [ .7418 .2582 ] under different parent processes.Thus, Z's stationary behavior depends on Y's specific trajectory, not merely the fraction of time Y spends in each state.

5 Approximate Inference

The section presents an approximate CTBN inference method based on clique-tree propagation, representing inter-clique messages and calibrated clique distributions as homogeneous Markov processes over trajectories. It supports queries and evidence incorporation but relies on approximate marginalization, whose linearization assumptions degrade over longer intervals unless time slicing is used.

  • 5 Approximate Inference: The approximate inference technique adapts clique-tree inference by passing distributions over entire trajectories, represented as homogeneous Markov processes.The messages are not exact distributions but often provide useful approximations.
  • 5.1 The Clique Tree Algorithm: Clique-tree calibration uses amalgamation instead of products and approximate marginalization instead of standard marginalization to compute approximate trajectory distributions.Cliques send messages after receiving all neighboring messages except the destination, eliminating variables not shared with the receiving clique.
  • 5.1 The Clique Tree Algorithm: After calibration, each clique’s initial distribution and joint intensity matrix define a homogeneous Markov process for answering queries about variables within that clique.Evidence is incorporated by choosing a tree root, performing a downward calibration pass, and propagating observations forward or backward across query times.
  • 5.2 Marginalization: Approximate marginalization removes variables from an intensity matrix and replaces the resulting process with a simpler reduced CIM.The method seeks to approximate transition probabilities that generally cannot be represented exactly after variables are eliminated.
  • 5.2.1 The Linearization Method: The linearization method assumes eliminated variables remain unchanged over the interval and uses exp(QΔt) ≈ I + QΔt.It averages over eliminated-variable values using their distribution at the interval’s beginning and applies a linear approximation to the matrix exponential.
  • 5.2.1 The Linearization Method: Without significant time slicing, the linearization assumptions fail over longer intervals because eliminated variables can change over time.The method sacrifices some short-interval accuracy to improve performance over longer intervals.

6 Experimental Results

Experiments compare exact inference with linear and subsystem approximations across unobserved and evidence-conditioned scenarios. The subsystem method is more accurate over longer intervals, whereas finer time-slicing improves linear accuracy but can increase subsystem error.

  • Experimental setup: The experiments compare exact inference with linear and subsystem approximations on an example continuous-time Bayesian network.Both methods were implemented and evaluated against exact inference.
  • Scenarios: The evaluation considers trajectories with no observed evidence and trajectories with observations at t = 1 and t = 3.The evidence specifies that the person is not hungry at t = 1 and drowsy at t = 3.
  • Approximation results: The subsystem approximation performs better for longer time segments, but its errors grow when time-slicing becomes too fine.The experiments also use a single approximation between evidence points and repeatedly recalculate dynamics at regular intervals.
  • Approximation results: The linear approximation performs poorly over long intervals, while its accuracy improves as time granularity becomes finer.These findings accord with the assumptions underlying the linear approximation.

7 Discussion

The discussion emphasizes that CTBNs represent continuous time directly, supporting time-distributed queries and irregularly spaced evidence propagation. It also contrasts CTBNs with DBNs, identifies unsupported query types, and outlines theoretical, empirical, sampling, and learning directions for future work.

  • Capabilities: CTBNs represent time explicitly, enabling distributions over time and evidence propagation between observations even when observation times are unevenly spaced.The model propagates value distributions from one observation time to the next without requiring evenly spaced evidence.
  • CTBNs and DBNs: For any finite time interval, probabilistic influence can flow along every connected path in a CTBN, making an equivalent DBN fully connected regardless of slice duration.A DBN can approximate a CTBN by retaining a subset of connections, such as those with strongest influence.
  • Limitations: Current inference cannot answer queries asserting that a variable remains fixed throughout an interval or asking about another variable when the first variable transitions.These limitations concern evidence over an entire period and distributions conditioned on a first-transition time.
  • Future work: Open problems include theoretical and empirical analysis of computational properties and approximation behavior, plus extending stochastic sampling to evidence using importance sampling or MCMC.The generative semantics provide a basis for sampling-based approximation, but the discussion calls for extending it to evidence.
  • Future work: Future work also includes learning CTBN parameters and graph structure from data.The paper identifies both parameter learning and structure learning as broader research goals.
Loading 1301.0591v1…