Name
Title | ||
|---|---|---|
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-symmetricfunction for some constant r. Our polynomial time algorithms work directly on the unmoralized graph. Our results significantly extend 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. |
Year | Venue | Field |
|---|---|---|
2014 | UNCERTAINTY IN ARTIFICIAL INTELLIGENCE | Bayesian inference,Computer science,Artificial intelligence,Treewidth,Time complexity,Discrete mathematics,Mathematical optimization,Combinatorics,Inference,Bayesian network,Graphical model,Machine learning,Conditional probability table,Bounded function |
DocType | Citations | PageRank |
Conference | 1 | 0.35 |
References | Authors | |
19 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel J. Rosenkrantz | 1 | 2647 | 1114.92 |
| Madhav Marathe | 2 | 2775 | 262.17 |
| Ravi Sundaram | 3 | 762 | 72.13 |
| Anil Kumar S. Vullikanti | 4 | 1135 | 98.30 |