Abstract:
Logical and probabilistic reasoning are closely related. Many examples in each group have natural analogs in the other. One example is the strong relationship between weighted MAX-SAT and MPE. This paper presents a simple reduction of MPE to weighted MAX-SAT. It also investigates approximating MPE by converting it to a weighted MAX-SAT problem, then using the incomplete methods for solving weighted MAX-SAT to generate a solution. We show that converting MPE problems to MAX-SAT problems and using a method designed for MAX-SAT to solve them often produces solutions that are vastly superior to the previous local search methods designed directly for the MPE problem.