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.

本研究关注了对指数级别集合进行求和的概率推断任务，并提出了一种基于随机生成奇偶约束模型的多项式数量级别的 MAP 推断查询的求解方法，结合迭代消息传递解码算法和整数线性规划 (ILP) 方案以及新的稀疏化技术，可以得到分割函数的下限和上限，与变分方法相比，具有更高的概率和更紧的限制。