%0 Conference Paper %1 Sang2007Dynamic %A Sang, Tian %A Beame, Paul %A Kautz, Henry %B IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence %C San Francisco, CA, USA %D 2007 %I Morgan Kaufmann Publishers Inc. %K ecai2010-maxdlsat %P 173--179 %T A dynamic approach to MPE and weighted MAX-SAT %U http://portal.acm.org/citation.cfm?id=1625302 %X 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.

@inproceedings{Sang2007Dynamic, 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.}, added-at = {2010-01-13T09:24:50.000+0100}, address = {San Francisco, CA, USA}, author = {Sang, Tian and Beame, Paul and Kautz, Henry}, biburl = {https://www.bibsonomy.org/bibtex/23e6821cfb06b57d2c1e8820ede2b95e3/casi}, booktitle = {IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence}, description = {A dynamic approach to MPE and weighted MAX-SAT}, interhash = {2582bc70c6e37614adf1e90fae9c56b7}, intrahash = {3e6821cfb06b57d2c1e8820ede2b95e3}, keywords = {ecai2010-maxdlsat}, location = {Hyderabad, India}, pages = {173--179}, publisher = {Morgan Kaufmann Publishers Inc.}, timestamp = {2010-02-16T10:19:57.000+0100}, title = {A dynamic approach to MPE and weighted MAX-SAT}, url = {http://portal.acm.org/citation.cfm?id=1625302}, year = 2007 }