Linear programming-based submodular extensions for marginal estimation

Submodular extensions of an energy function can be used to efficiently compute approximate marginals via variational inference. The accuracy of the marginals depends crucially on the quality of the submodular extension. To identify accurate extensions for different classes of energy functions, we establish a relationship between the submodular extensions of the energy and linear programming (LP) relaxations for the corresponding MAP estimation problem. This allows us to (i) establish the worst-case optimality of the submodular extension for Potts model used in the literature; (ii) identify the worst-case optimal submodular extension for the more general class of metric labeling; (iii) efficiently compute the marginals for the widely used dense CRF model with the help of a recently proposed Gaussian filtering method; and (iv) propose an accurate submodular extension based on an LP relaxation for a higher-order diversity model. Using synthetic and real data, we show that our approach provides comparable upper bounds on the log-partition function to those obtained using tree-reweighted message passing (TRW) in cases where the latter is computationally feasible. Importantly, unlike TRW, our approach provides the first computationally tractable algorithm to compute an upper bound on dense CRF model with higher-order Potts potentials