Unifying Local Consistency and MAX SAT Relaxations for Scalable Inference with Rounding Guarantees
Stephen H. Bach, Bert Huang, Lise Getoor · 2015
We prove the equivalence of first-order lo-cal consistency relaxations and the MAX SAT relaxation of Goemans and Williamson (1994) for a class of MRFs we refer to as logi-cal MRFs. This allows us to combine the ad-vantages of each into a single MAP inference technique: solving the local consistency re-laxation with any of a number of highly scal-able message-passing algorithms, and then obtaining a high-quality discrete solution via a guaranteed rounding procedure when the relaxation is not tight. Logical MRFs are a general class of models that can incorpo-rate many common dependencies, such as logical implications and mixtures of super-modular and submodular potentials. They can be used for many structured prediction tasks, including natural language processing, computer vision, and computational social science. We show that our new inference technique can improve solution quality by as much as 20 % without sacrificing speed on problems with over one million dependencies. 1