Abstract | ||
---|---|---|
The problem of Most Probable Explanation (MPE) arises in the scenario of probabilistic inference: finding an assignment to all variables that has the maximum likelihood given some evidence. We consider the more general CNF-based MPE problem, where each literal in a CNF-formula is associated with a weight. We describe reductions between MPE and weighted MAX-SAT, and show that both can be solved by a variant of weighted model counting. The MPE-SAT algorithm is quite competitive with the state-of-the-art MAX-SAT, WCSP, and MPE solvers on a variety of problems. |
Year | Venue | Keywords |
---|---|---|
2007 | IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence | MPE solvers,general CNF-based MPE problem,state-of-the-art MAX-SAT,weighted MAX-SAT,weighted model counting,MPE-SAT algorithm,Probable Explanation,maximum likelihood,probabilistic inference,dynamic approach |
Field | DocType | Citations |
Probabilistic inference,Maximum satisfiability problem,Computer science,Maximum likelihood,Artificial intelligence,Machine learning,Model counting | Conference | 3 |
PageRank | References | Authors |
0.54 | 7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tian Sang | 1 | 231 | 9.69 |
Paul Beame | 2 | 2234 | 176.07 |
Henry A. Kautz | 3 | 9271 | 1010.27 |