2013/09/26 by Stefano Ermon, Ermon, Stefano, Carla P. Gomes +5
Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Error Correcting Code Techniques #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1309.6827
openalex publication_date 2013/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many probabilistic inference tasks involve summations over exponentially\nlarge sets. Recently, it has been shown that these problems can be reduced to\nsolving a polynomial number of MAP inference queries for a model augmented with\nrandomly generated parity constraints. By exploiting a connection with\nmax-likelihood decoding of binary codes, we show that these optimizations are\ncomputationally hard. Inspired by iterative message passing decoding\nalgorithms, we propose an Integer Linear Programming (ILP) formulation for the\nproblem, enhanced with new sparsification techniques to improve decoding\nperformance. By solving the ILP through a sequence of LP relaxations, we get\nboth lower and upper bounds on the partition function, which hold with high\nprobability and are much tighter than those obtained with variational methods.\n