Scalable variational inference in logsupermodular models. arXiv preprint arXiv:1502.06531

We consider the problem of approximate Bayesian inference in log-supermodular models. These models encompass regular pairwise MRFs with binary variables, but allow to capture high-order interactions, which are intractable for ex-isting approximate inference techniques such as belief propagation, mean field, and variants. We show that a recently proposed variational ap-proach to inference in log-supermodular models –L-FIELD – reduces to the widely-studied min-imum norm problem for submodular minimiza-tion. This insight allows to leverage power-ful existing tools, and hence to solve the vari-ational problem orders of magnitude more effi-ciently than previously possible. We then pro-vide another natural interpretation of L-FIELD, demonstrating that it exactly minimizes a spe-cific type of Rényi divergence measure. This in-sight sheds light on the nature of the variational approximations produced by L-FIELD. Further-more, we show how to perform parallel inference as message passing in a suitable factor graph at a linear convergence rate, without having to sum up over all the configurations of the factor. Fi-nally, we apply our approach to a challenging image segmentation task. Our experiments con-firm scalability of our approach, high quality of the marginals, and the benefit of incorporating higher-order potentials. 1