Bayesian inference in treewidth-bounded graphical models without indegree constraints
Daniel J. Rosenkrantz, MADHAV V. MARATHE, S. S. Ravi, Anil Kumar S. Vullikanti · 2014
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.