Perturb-and-MAP random fields: Using discrete optimization to learn and sample from energy models

By George Papandreou, Alan L. Yuille. 2011

191 citations recorded by the source corpus.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Probabilistic & Bayesian Methods

In Signal Processing

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “Our work provides a fast deterministic alternative to recently proposed Perturb-and-MAP algorithms (Papandreou and Yuille, 2011; Hazan and Jaakkola, 2012; Ermon et al., 2013).”
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…”
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].”
Noisy Parallel Approximate Decoding for Conditional Recurrent Language Model (2016, methodology): “Perturb-and-MAP Perturb-and-MAP [21] is an algorithm that reduces probabilistic inference, such as sampling, to energy minimization in a Markov random ﬁeld (MRF) [20].”
Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts (2021, methodology): “we observe how the Gumbel-Matching distribution approximates (5) through the use of rank-one perturbations [31, 15, 42] ∑ ij zijgij instead of gz.”
Diverse M-Best Solutions in Markov Random Fields (2012, background): “An interesting approach by Papandreou and Yuille [24] shows that approximate samples may be drawn from the Gibbs distribution by injecting a certain noise into the parameters and solving for MAP on these perturbed parameters.”
Learning Latent Permutations with Gumbel-Sinkhorn Networks (2018, methodology): “To this aim, we start by considering a generic distribution on the discrete set Y , with potential function X : Y → R : Regarding i), the Gumbel trick arises in the context of Perturb and MAP methods (Papandreou & Yuille, 2011) for sampling in discrete graphical models.”
Black-box Importance Sampling (2016, methodology): “Beyond MCMC, black-box 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 ”
Federating Recommendations Using Differentially Private Prototypes (2020, methodology): “The algorithm increases overall eﬃciency by exploiting the sparsity of the data and the Gumbel trick, often used to eﬃciently sample from discrete distributions Papandreou and Yuille (2011); Balog et al. (2017); Durfee and Rogers (2019).”
Empirical Minimum Bayes Risk Prediction: How to Extract an Extra Few % Performance from Vision Models with Just Three More Parameters (2014, background): “This paper presents results only with DivMBest, which performed best; comparisons to [17] can be found in the supplemental document (available from the author webpages).”
Randomized Optimum Models for Structured Prediction (2012, methodology): “Recent work by Papandreou and Yuille (2011) has taken a step in this direction, in the particular case of Markov random ﬁelds.”