T. Sang, P. Beame, und H. Kautz. IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence, Seite 173--179. San Francisco, CA, USA, Morgan Kaufmann Publishers Inc., (2007)
Zusammenfassung
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.
%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
}