Reasoning at the Right Time Granularity Export

@inproceedings{Saria+al:UAI07EP, abstract = {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 component 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-theoretic 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.}, address = {Edinburgh, Scottland, UK}, author = {Suchi, S. and Nodelman, U. and Koller, D.}, booktitle = {Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI)}, citeulike-article-id = {2881227}, comment = {Conclusions of the paper as follows (CTBN = continuous time Bayesian network, EP = expectation propogation). The maths is very very dense in this paper (undigestable in any reasonable amount of time). "We have presented a highly flexible cluster graph architecture for passing messages across both time and space in CTBNs. We also presented Dynamic-EP, a new algorithm for approximate inference in CTBNs. This algorithm adaptively assigns computational resources to parts of the inference where greater accuracy is required, and can provide a much better tradeoff between computational cost and accuracy than previous algorithms. Most importantly, Dynamic-EP deals well with situations where some components of the system evolve much more rapidly than others, allowing each part of the system to adaptively choose the time granularity most appropriate to it at that time. There are many useful extensions of this work. Clearly, we plan to test whether the computational gains on simple, synthetic networks also manifest in real-world problems. More broadly, our framework allows a highly flexible inference architecture, where process variables can dynamically change their cluster assignments over time. Thus, if two variables undergo a strong interaction, we can temporarily put them in the same cluster. It would be interesting to design an algorithm that dynamically determined an appropriate cluster structure as the process evolves. Finally, there are many probabilistic models other than CTBNs where EP is used to provide a parametric approximation to complex messages in a cluster graph. In some cases, there may be a need for a richer, more flexible representation of the messages (one of the key motivations for the development of non-parametric belief propagation (Sudderth et al., 2003).) The algorithmthatwe proposed provides a semi-parametric message representation. It would be interesting to explore the viability of a similar approach in other types of probabilistic graphical models." }, keywords = {file-import-08-06-11}, pages = {421--430}, posted-at = {2008-06-11 02:20:45}, priority = {5}, title = {Reasoning at the Right Time Granularity}, year = {2005} }

TY - CONF ID - Saria+al:UAI07EP L3 - citeulike-article-id:2881227 N2 - 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 component 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-theoretic 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. AD - Edinburgh, Scottland, UK EP - 430 TI - Reasoning at the Right Time Granularity T2 - Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI) SP - 421 KW - file-import-08-06-11 N1 - Conclusions of the paper as follows (CTBN = continuous time Bayesian network, EP = expectation propogation). The maths is very very dense in this paper (undigestable in any reasonable amount of time). "We have presented a highly flexible cluster graph architecture for passing messages across both time and space in CTBNs. We also presented Dynamic-EP, a new algorithm for approximate inference in CTBNs. This algorithm adaptively assigns computational resources to parts of the inference where greater accuracy is required, and can provide a much better tradeoff between computational cost and accuracy than previous algorithms. Most importantly, Dynamic-EP deals well with situations where some components of the system evolve much more rapidly than others, allowing each part of the system to adaptively choose the time granularity most appropriate to it at that time. There are many useful extensions of this work. Clearly, we plan to test whether the computational gains on simple, synthetic networks also manifest in real-world problems. More broadly, our framework allows a highly flexible inference architecture, where process variables can dynamically change their cluster assignments over time. Thus, if two variables undergo a strong interaction, we can temporarily put them in the same cluster. It would be interesting to design an algorithm that dynamically determined an appropriate cluster structure as the process evolves. Finally, there are many probabilistic models other than CTBNs where EP is used to provide a parametric approximation to complex messages in a cluster graph. In some cases, there may be a need for a richer, more flexible representation of the messages (one of the key motivations for the development of non-parametric belief propagation (Sudderth et al., 2003).) The algorithmthatwe proposed provides a semi-parametric message representation. It would be interesting to explore the viability of a similar approach in other types of probabilistic graphical models." AU - Suchi, S AU - Nodelman, U AU - Koller, D PY - 2005/// ER -