On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations

By Tamir Hazan, Subhransu Maji, Tommi S. Jaakkola. 2013

57 citations recorded by the source corpus.

In this paper we describe how MAP inference can be used to sample efficiently from Gibbs distributions. Specifically, we provide means for drawing either approximate or unbiased samples from Gibbs' distributions by introducing low dimensional perturbations and solving the corresponding MAP assignments. Our approach also leads to new ways to derive lower bounds on partition functions. We demonstrate empirically that our method excels in the typical "high signal -high coupling" regime. The setting results in ragged energy landscapes that are challenging for alternative approaches to sampling and/or lower bounds.

Subfields: Cognitive Neuroscience, Molecular Biology, Probabilistic & Bayesian Methods, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Cognitive Neuroscience

In Molecular Biology

In Probabilistic & Bayesian Methods

In Signal Processing

Citations in the corpus

A* Sampling (2014, background): “In the discrete case, recent work on “Perturb and MAP” (P&M) methods [1, 19, 2] that draw samples as the argmaxes of random energy functions has shown value in developing approximate, correlated perturbations.”
Advanced Structured Prediction (2014, background): “An extension of the probit loss to more general distributions of was presented by Hazan et al. (2013), which might correspond to the noise of the problem.”
Direct Optimization through arg max for Discrete Variational Auto-Encoder (2019, methodology): “The Gumbel-Softmax approach is motivated by the connection of the Gumbel-Max perturbation model and the Gibbs distribution [27, 34, 7, 18].”
Learning Latent Permutations with Gumbel-Sinkhorn Networks (2018, background): “Although ultimately heuristic, they lead to bounds in the partition function (Hazan & Jaakkola, 2012; Balog et al., 2017), and can also be understood as providing approximate or unbiased samples from the true density (Hazan et al., 2013; Tomczak, 2016).”
Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts (2021, methodology): “[15] Tamir Hazan, Subhransu Maji, and Tommi Jaakkola.”
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions (2013, methodology): “[9] provide unbiased samples form the Gibbs distribution using MAP predictors and [16] present their measure concentration properties.”
Learning and Inference via Maximum Inner Product Search (2016, methodology): “See (Gumbel & Lieblein, 1954; Papandreou & Yuille, 2011; Hazan et al., 2013; Maddison et al., 2014) If ai = θ ·xi are the log probabilities in a log-linear model, Lemma 2.1 can be used for inference.”
Gradient Estimation with Stochastic Softmax Tricks (2020, background): “Characterizing the marginal of X in general is difﬁcult [76, 34], but U that are efﬁcient to sample from typically induce conditional independencies in p θ [27].”
Black-box Importance Sampling (2016, methodology): “…IS can be used to reﬁne many other approximation methods related to complex generation mechanisms, including variational inference with complex proposals (e.g., Rezende and Mohamed, 2015), bootstrapping (Efron, 2012) and perturb-and-MAP methods (Hazan et al., 2013; Papandreou and Yuille, 2011).”