Reasoning at the Right Time Granularity

[PDF] Winner of the Best Student Paper Award


Most real-world dynamic systems are composed of different components that often evolve at very different rates. In traditional temporal graphical models, such as dynamic Bayesian networks, time is modeled at a fixed granularity, generally selected based on the rate at which the fastest compoenent evolves. Inference must then be performed at this fastest granularity, potentially at significant computational cost. Continuous Time Bayesian Networks (CTBNs) avoid time-slicing in the representation by modeling the system as evolving continuously over time. The expectation-propagation (EP) inference algorithm of Nodelman et al. (2005) can then vary the inference granularity over time, but the granularity is uniform across all parts of the system, and must be selected in advance. In this paper, we provide a new EP algorithm that utilizes a general cluster graph architecture where clusters contain distributions that can overlap in both space (set of variables) and time. This architecture allows different parts of the system to be modeled at very different time granularities, according to their current rate of evolution. We also provide an information-theoretica criterion for dynamically re-partitioning the clusters during inference to tune the level of approximation to the current rate of evolution. This avoids the need to hand-select the appropriate granularity, and allows the granularity to adapt as information is transmitted across the network. We present experiments demonstrating that this approach can result in significant computational savings.

Full Citation

S. Saria, U. Nodelman, and D. Koller (2007). "Reasoning at the Right Time Granularity." Proceedings of the Twenty-third Conference on Uncertainty in AI (UAI).


  title = {Expectation Maximization and Complex Duration Distributions for
     Continuous Time Bayesian Networks},
  author = {U. Nodelman and C.R. Shelton and D. Koller},
  booktitle = {Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI)},  
  address = {Edinburgh, Scottland, UK},
  month = {July},
  year = 2005,
  pages = {421--430},