Optimization With Parity Constraints: From Binary Codes to Discrete Integration
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Discrete Graph Hashing
Hashing has emerged as a popular technique for fast nearest neighbor search in gigantic databases. In particular, learning based hashing has received considerable attention due to its appealing storage and search efficie…
Discrete Hashing with Deep Neural Network
This paper addresses the problem of learning binary hash codes for large scale image search by proposing a novel hashing method based on deep neural network. The advantage of our deep model over previous deep model used …
Image RetrievalAsymmetric Correlation Quantization Hashing for Cross-modal Retrieval
Due to the superiority in similarity computation and database storage for large-scale multiple modalities data, cross-modal hashing methods have attracted extensive attention in similarity retrieval across the heterogene…
Cross-Modal RetrievalQuantizationRetrievalA Scalable Optimization Mechanism for Pairwise based Discrete Hashing
Maintaining the pair similarity relationship among originally high-dimensional data into a low-dimensional binary space is a popular strategy to learn binary codes. One simiple and intutive method is to utilize two ident…
A Stochastic Optimization Framework for Fair Risk Minimization
Despite the success of large-scale empirical risk minimization (ERM) at achieving high accuracy across a variety of machine learning tasks, fair ERM is hindered by the incompatibility of fairness constraints with stochas…
Binary ClassificationFairnessStochastic Optimization