Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints
Abstract
We present new polynomial time algorithms for inference problems in Bayesian networks (BNs) when restricted to instances that satisfy the following two conditions: they have bounded treewidth and the conditional probability table (CPT) at each node is specified concisely using an r-symmetric function for some constant r. Our polynomial time algorithms work directly on the unmoralized graph. Our results significantly ex-tend known results regarding inference problems on treewidth bounded BNs to a larger class of problem instances. We also show that relaxing either of the conditions used by our algorithms leads to computational intractability.
Cite
Text
Rosenkrantz et al. "Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints." Conference on Uncertainty in Artificial Intelligence, 2014.Markdown
[Rosenkrantz et al. "Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints." Conference on Uncertainty in Artificial Intelligence, 2014.](https://mlanthology.org/uai/2014/rosenkrantz2014uai-bayesian/)BibTeX
@inproceedings{rosenkrantz2014uai-bayesian,
title = {{Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints}},
author = {Rosenkrantz, Daniel J. and Marathe, Madhav V. and Sundaram, Ravi and Vullikanti, Anil},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2014},
pages = {702-711},
url = {https://mlanthology.org/uai/2014/rosenkrantz2014uai-bayesian/}
}