On the Partition Function and Random Maximum A-Posteriori Perturbations

By Tamir Hazan, Tommi S. Jaakkola. 2012

98 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Probabilistic & Bayesian Methods

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Probabilistic & Bayesian Methods

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “Hazan and Jaakkola (2012) estimate logZ by averaging MAP estimates obtained on randomly perturbed inflated graphs.”
A* Sampling (2014, methodology): “Previous work [1, 3] has used this property to motivate samplers based on optimizing random energy functions but has been forced to resort to approximate sampling due to the fact that in structured output spaces, exact sampling appears to require instantiating exponentially many Gumbel perturbations”
The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables (2016, methodology): “To motivate the construction of Concrete random variables, we review a method for sampling from discrete distributions called the Gumbel-Max trick (Luce, 1959; Yellott, 1977; Papandreou & Yuille, 2011; Hazan & Jaakkola, 2012; Maddison et al., 2014).”
Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement (2019, methodology): “The idea of sampling by solving optimization problems has been used for various purposes (Papandreou & Yuille, 2011; Hazan & Jaakkola, 2012; Tarlow et al., 2012; Ermon et al., 2013; Maddison et al., 2014; Chen & Ghahramani, 2016; Balog et al., 2017), but to our knowledge this idea has not been used…”
Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization (2013, methodology): “We do not directly compare with the work of Hazan and Jaakkola [14] as we did not have access to their code.”
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).”
On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations (2013, methodology): “the computational complexity of our unbiased sampling procedure to the gap between the logarithm of the partition function and its upper bound in [5].”
Gradient Estimation with Stochastic Softmax Tricks (2020, methodology): “Perturb & MAP models [63, 33] were designed to approximate the Gibbs distribution over a combinatorial output space using low-order, additive Gumbel noise.”
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions (2013, methodology): “[23] describes the Bayesian perspectives, while [17, 8] describe their relations to the Gibbs distribution and moment matching.”
Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Models (2019, unknown): “& L, 2011; Hazan & Jaakkola, 2012; Maddison et al., 2014; Hazan et al., 2016; Maddison et al., 2017): Definition 6 (Gumbel-Max Trick).”
LiteEval: A Coarse-to-Fine Framework for Resource Efficient Video Recognition (2019, unknown): “More specifically, given a discrete categorical variable B̂ with class probabilities P (B̂ = k) ∝ bk, where bk ∈ (0,∞) and k ≤ K (K denotes the total number of classes; in our framework K = 2), the Gumbel-Max [9, 23] trick indicates the sampling from a categorical distribution can be performed in th”