A Dynamic Approach to MPE and Weighted MAX-SAT

Tian Sang, Paul Beame, Henry Kautz

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.

Subjects: 15.2 Constraint Satisfaction; 3.4 Probabilistic Reasoning

Submitted: Oct 16, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.