Scalable Variational Inference in Log-supermodular Models

Abstract

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 existing approximate inference techniques such as belief propagation, mean field, and variants. We show that a recently proposed variational approach to inference in log-supermodular models -L-FIELD- reduces to the widely-studied minimum norm problem for submodular minimization. This insight allows to leverage powerful existing tools, and hence to solve the variational problem orders of magnitude more efficiently than previously possible. We then provide another natural interpretation of L-FIELD, demonstrating that it exactly minimizes a specific type of Rényi divergence measure. This insight sheds light on the nature of the variational approximations produced by L-FIELD. Furthermore, 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. Finally, we apply our approach to a challenging image segmentation task. Our experiments confirm scalability of our approach, high quality of the marginals, and the benefit of incorporating higher-order potentials.

References in corpus (6)

• Rényi Divergence and Kullback-Leibler Divergence
• Near-optimal Nonmyopic Value of Information in Graphical Models
• Efficient Minimization of Decomposable Submodular Functions
• Modular proximal optimization for multidimensional total-variation regularization
• Structured sparsity-inducing norms through submodular functions
• Provable Submodular Minimization using Wolfe's Algorithm

Cited by in corpus (7)

• Submodular Functions: from Discrete to Continous Domains
• Total positivity in exponential families with application to binary variables
• Revisiting Decomposable Submodular Function Minimization with Incidence Relations
• Provable Non-Convex Optimization and Algorithm Validation via Submodularity
• Flexible Modeling of Diversity with Strongly Log-Concave Distributions
• Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
• Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models