We consider the problem of variational inference in probabilistic models with bothlog-submodular and log-supermodular higher-order potentials. These models canrepresentarbitrary distributionsover binary variables, and thus generalize thecommonly used pairwise Markov random fields and models with log-supermodularpotentials only, for which efficient approximate inference algorithms are known.While inference in the considered models is #P-hard in general, we present effi-cient approximate algorithms exploiting recent advances in the field of discreteoptimization. We demonstrate the effectiveness of our approach in a large set ofexperiments, where our model allows reasoning about preferences over sets ofitems with complements and substitutes.

Top