Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints
Daniel Rosenkrantz, Madhav Marathe, S. Ravi, Anil Vullikanti
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.
Pages: 702-711
PS Link:
PDF Link: /papers/14/p702-rosenkrantz.pdf
AUTHOR = "Daniel Rosenkrantz and Madhav Marathe and S. Ravi and Anil Vullikanti",
TITLE = "Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "702--711"

hosted by DSL   •   site info   •   help