On the Partition Function and Random Maximum A-Posteriori Perturbations

Abstract

In this paper we relate the partition function to the max-statistics of random variables. In particular, we provide a novel framework for approximating and bounding the partition function using MAP inference on randomly perturbed models. As a result, we can use efficient MAP solvers such as graph-cuts to evaluate the corresponding partition function. We show that our method excels in the typical "high signal - high coupling" regime that results in ragged energy landscapes difficult for alternative approaches.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (1)

• Tightening LP Relaxations for MAP using Message Passing

Cited by in corpus (12)

• Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization
• On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations
• Gradient Estimation with Stochastic Softmax Tricks
• Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement
• A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules
• On Measure Concentration of Random Maximum A-Posteriori Perturbations
• Variable Elimination in the Fourier Domain
• LeMoNADe: Learned Motif and Neuronal Assembly Detection in calcium imaging videos
• Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions
• Learning Maximum-A-Posteriori Perturbation Models for Structured Prediction in Polynomial Time
• Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces
• Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models