Optimization With Parity Constraints: From Binary Codes to Discrete Integration
This addresses computational challenges in probabilistic inference for researchers in machine learning and AI, offering improved bounds but is incremental as it builds on existing MAP and decoding methods.
The paper tackles the problem of probabilistic inference tasks involving summations over exponentially large sets by reducing them to MAP inference queries with parity constraints, showing these optimizations are computationally hard and proposing an ILP formulation with sparsification techniques to compute tighter bounds on the partition function than variational methods.
Many probabilistic inference 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 generated parity constraints. By exploiting a connection with max-likelihood decoding of binary codes, we show that these optimizations are computationally hard. Inspired by iterative 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 partition function, which hold with high probability and are much tighter than those obtained with variational methods.