Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Optimization With Parity Constraints: From Binary Codes to Discrete Integration
Stefano Ermon, Carla Gomes, Ashish Sabharwal, Bart Selman
Abstract:
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.
Keywords:
Pages: 202-211
PS Link:
PDF Link: /papers/13/p202-ermon.pdf
BibTex:
@INPROCEEDINGS{Ermon13,
AUTHOR = "Stefano Ermon and Carla Gomes and Ashish Sabharwal and Bart Selman",
TITLE = "Optimization With Parity Constraints: From Binary Codes to Discrete Integration",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "202--211"
}


hosted by DSL   •   site info   •   help