Skip to yearly menu bar Skip to main content


Variational Inference in Mixed Probabilistic Submodular Models

Josip Djolonga · Sebastian Tschiatschek · Andreas Krause

Area 5+6+7+8 #70

Keywords: [ Variational Inference ] [ Combinatorial Optimization ]


We consider the problem of variational inference in probabilistic models with both log-submodular and log-supermodular higher-order potentials. These models can represent arbitrary distributions over binary variables, and thus generalize the commonly used pairwise Markov random fields and models with log-supermodular potentials only, for which efficient approximate inference algorithms are known. While inference in the considered models is #P-hard in general, we present efficient approximate algorithms exploiting recent advances in the field of discrete optimization. We demonstrate the effectiveness of our approach in a large set of experiments, where our model allows reasoning about preferences over sets of items with complements and substitutes.

Live content is unavailable. Log in and register to view live content