Inference Complexity in Continuous Time Bayesian Networks
Abstract
The continuous time Bayesian network (CTBN) enables temporal reasoning by rep-resenting a system as a factored, finite-state Markov process. The CTBN uses a tra-ditional Bayesian network (BN) to specify the initial distribution. Thus, the complex-ity results of Bayesian networks also apply to CTBNs through this initial distribution. However, the question remains whether prop-agating the probabilities through time is, by itself, also a hard problem. We show that exact and approximate inference in continu-ous time Bayesian networks is NP-hard even when the initial states are given. 1
Cite
Text
Sturlaugson and Sheppard. "Inference Complexity in Continuous Time Bayesian Networks." Conference on Uncertainty in Artificial Intelligence, 2014.Markdown
[Sturlaugson and Sheppard. "Inference Complexity in Continuous Time Bayesian Networks." Conference on Uncertainty in Artificial Intelligence, 2014.](https://mlanthology.org/uai/2014/sturlaugson2014uai-inference/)BibTeX
@inproceedings{sturlaugson2014uai-inference,
title = {{Inference Complexity in Continuous Time Bayesian Networks}},
author = {Sturlaugson, Liessman and Sheppard, John W.},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2014},
pages = {772-779},
url = {https://mlanthology.org/uai/2014/sturlaugson2014uai-inference/}
}