Sparse Message Passing Algorithms for Weighted Maximum Satisfiability
Aron Culotta, Andrew McCallum, Bart Selman, Ashish Sabharwal · 2007
Weighted maximum satisfiability is a well-studied problem that has important applicability to artificial intelligence (for instance, MAP in-ference in Bayesian networks). General-purpose stochastic search algorithms have proven to be accurate and efficient for large problem in-stances; however, these algorithms largely ignore structural properties of the input. For example, many problems are highly clustered, in that they contain a collection of loosely coupled subprob-lems (e.g. pipelines of NLP tasks). In this pa-per, we propose a message passing algorithm to solve weighted maximum satisfiability problems that exhibit this clustering property. Our algo-rithm fuses local solutions to each subproblem into a global solution by iteratively passing sum-mary information between clusters and recom-puting local solutions. Because the size of these messages can become unwieldy for large prob-lems, we explore several message compression techniques to transmit the most valuable infor-mation as compactly as possible. We empirically compare our algorithm against a state-of-the-art stochastic solver and show that for certain classes of problems our message passing algorithm finds significantly better solutions.