Discrete Integration by Decoding Binary Codes

Many probabilistic inference and learning tasks involve summations over exponentially large sets. Recently, it has been shown that these problems can be reduced to solving a polynomial number of MAP inference queries for a model augmented with randomly gener-ated parity constraints. By exploiting a con-nection with max-likelihood decoding of bi-nary codes, we show that these optimizations are computationally hard. Inspired by iter-ative message passing decoding algorithms, we propose an Integer Linear Programming (ILP) formulation for the problem, enhanced with new sparsification techniques to improve decoding performance. By solving the ILP through a sequence of LP relaxations, we get both lower and upper bounds on the parti-tion function, which hold with high probabil-ity and are much tighter than those obtained with variational methods