Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints

Daniel J. Rosenkrantz, Madhav V.Marathe Virginia Tech, S. S. Ravi, Anil K. Vullikanti Virginia Tech
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:725-734, 2014.

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 this Paper

BibTeX
@InProceedings{pmlr-vR12-rosenkrantz14a, title = {{B}ayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints}, author = {Rosenkrantz, Daniel J. and Tech, Madhav V.Marathe Virginia and Ravi, S. S. and Tech, Anil K. Vullikanti Virginia}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {725--734}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/rosenkrantz14a/rosenkrantz14a.pdf}, url = {https://proceedings.mlr.press/r12/rosenkrantz14a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints %A Daniel J. Rosenkrantz %A Madhav V.Marathe Virginia Tech %A S. S. Ravi %A Anil K. Vullikanti Virginia Tech %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-rosenkrantz14a %I PMLR %P 725--734 %U https://proceedings.mlr.press/r12/rosenkrantz14a.html %V R12 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Rosenkrantz, D.J., Tech, M.V.V., Ravi, S.S. & Tech, A.K.V.V.. (2014). Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:725-734 Available from https://proceedings.mlr.press/r12/rosenkrantz14a.html. Reissued by PMLR on 04 October 2026.

Related Material