Approximating MAP by Compensating for Structural Relaxations
We introduce a new perspective on approximations to the maximum a posteriori (MAP) task in probabilistic graphical models, that is based on simplifying a given instance, and then tightening the approximation. First, we start with a structural relaxation of the original model. We then infer from the relaxation its deficiencies, and compensate for them. This perspective allows us to identify two distinct classes of approximations. First, we find that max-product belief propagation can be viewed as a way to compensate for a relaxation, based on a particular idealized case for exactness. We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties. We go on to propose a new class of algorithms that, starting with a relaxation, iteratively yields tighter approximations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Dataset of Random Relaxations for Crystal Structure Search of Li-Si System
Crystal structure search is a long-standing challenge in materials design. We present a dataset of more than 100,000 structural relaxations of potential battery anode materials from randomized structures using density fu…
Data AugmentationDomain GeneralizationGlobal Optimization: A Machine Learning Approach
Many approaches for addressing Global Optimization problems typically rely on relaxations of nonlinear constraints over specific mathematical primitives. This is restricting in applications with constraints that are blac…
global-optimizationOn the Expressiveness of Multi-Neuron Convex Relaxations
To provide robustness guarantees, neural network certification methods heavily rely on convex relaxations. The imprecision of these convex relaxations, however, is a major obstacle: even the most precise single-neuron re…
Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions
Combining discrete probability distributions and combinatorial optimization problems with neural network components has numerous applications but poses several challenges. We propose Implicit Maximum Likelihood Estimatio…
Combinatorial OptimizationStructural Incompatibility of Differentiable Sorting and Within-Vector Rank Normalization
We show that differentiable sorting and ranking operators are structurally incompatible with within-vector rank normalization. We formalize admissibility through monotone invariance (C1), batch independence (C2), and a r…