Name
Abstract | ||
|---|---|---|
Over the past decade general satisfiability testing algorithms have proven to be surprisingly effective at solving a wide variety of constraint satisfaction problem, such as planning and scheduling (Kautz and Selman 2003). Solving such NP-complete tasks by "compilation to SAT" has turned out to be an approach that is of both practical and theoretical interest. Recently, (Sang et al. 2004) have shown that state of the art SAT algorithms can be efficiently extended to the harder task of counting the number of models (satisfying assignments) of a formula, by employing a technique called component caching. This paper begins to investigate the question of whether "compilation to model-counting" could be a practical technique for solving real-world #P-complete problems, in particular Bayesian inference. We describe an efficient translation from Bayesian networks to weighted model counting, extend the best model-counting algorithms to weighted model counting, develop an efficient method for computing all marginals in a single counting pass, and evaluate the approach on computationally challenging reasoning problems. |
Year | Venue | Keywords |
|---|---|---|
2005 | AAAI | bayesian network,efficient translation,np-complete task,weighted model counting,efficient method,single counting,art sat algorithm,model-counting algorithm,particular bayesian inference,practical technique,satisfiability,bayesian inference,constraint satisfaction problem |
Field | DocType | ISBN |
#SAT,Bayesian inference,Scheduling (computing),Computer science,Satisfiability,Constraint satisfaction problem,Theoretical computer science,Bayesian network,Artificial intelligence,Bayesian statistics,Machine learning,Model counting | Conference | 1-57735-236-x |
Citations | PageRank | References |
91 | 3.33 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tian Sang | 1 | 231 | 9.69 |
| Paul Beame | 2 | 2234 | 176.07 |
| Henry A. Kautz | 3 | 9271 | 1010.27 |