Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints
Daniel Rosenkrantz, Madhav Marathe, S. Ravi, Anil Vullikanti
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.
Keywords:
Pages: 702-711
PS Link:
PDF Link: /papers/14/p702-rosenkrantz.pdf
BibTex:
@INPROCEEDINGS{Rosenkrantz14,
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)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "702--711"
}


hosted by DSL   •   site info   •   help