A Dynamic Approach for MPE and Weighted MAX-SAT
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.
Cite
Text
Sang et al. "A Dynamic Approach for MPE and Weighted MAX-SAT." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Sang et al. "A Dynamic Approach for MPE and Weighted MAX-SAT." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/sang2007ijcai-dynamic/)BibTeX
@inproceedings{sang2007ijcai-dynamic,
title = {{A Dynamic Approach for MPE and Weighted MAX-SAT}},
author = {Sang, Tian and Beame, Paul and Kautz, Henry A.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {173-179},
url = {https://mlanthology.org/ijcai/2007/sang2007ijcai-dynamic/}
}