Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement

By Wouter Kool, Herke Van Hoof, Max Welling. 2019

330 citations recorded by the source corpus.

The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample $k$ elements without replacement. We show how to implicitly apply this 'Gumbel-Top-$k$' trick on a factorized distribution over sequences, allowing to draw exact samples without replacement using a Stochastic Beam Search. Even for exponentially large domains, the number of model evaluations grows only linear in $k$ and the maximum sampled sequence length. The algorithm creates a theoretical connection between sampling and (deterministic) beam search and can be used as a principled intermediate alternative. In a translation task, the proposed method compares favourably against alternatives to obtain diverse yet good quality translations. We show that sequences sampled without replacement can be used to construct low-variance estimators for expected sentence-level BLEU score and model entropy.

Subfields: Artificial Intelligence, Optimization & Training

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 Optimization & Training

Citations in the corpus

Predictive Sampling with Forecasting Autoregressive Models (2020, methodology): “(13) In the case of the Gumbel-Max reparametrization, the posterior Gumbel noise p ( (cid:15) | x ) can be computed straightfor-wardly by using the notion that the maximum and the location of the maximum are independent (Maddison et al., 2014; Kool et al., 2019).”
Adversarial Filters of Dataset Biases (2020, methodology): “The Gumbel method provides an efficient way to perform such sampling (Gumbel & Lieblein, 1954; Maddison et al., 2014; Kim et al., 2016; Balog et al., 2017; Kool et al., 2019), by independently perturbing each p̃(i) with a Gumbel random variable and identifying k instances with the highest perturbed ”
Online Coreset Selection for Rehearsal-based Continual Learning (2021, neutral): “[16] connect stochastic Gumbel-top-k trick and beam search to hierarchically sample sequences without replacement.”
Natural Language Processing Advancements By Deep Learning: A Survey (2020, background): “Although, there has been some recent studies [55], [56] on improving the beam search by incorporating a similar mechanism during training of them model, studying this is”
VX2TEXT: End-to-End Learning of Video-Based Text Generation From Multimodal Inputs (2021, background): “For detailed proof, we refer the reader to [22].”
Sticking to the Facts: Confident Decoding for Faithful Data-to-Text Generation (2019, methodology): “19 to make the ﬁnal objective: In order to sample sub-sequences from Q ( z | y , x ) , we apply the same Gumbel-max trick as in Kool et al. (2019).”
Differentiable Top-k with Optimal Transport (2020, methodology): “Specifically, Kool et al. (2019) adapted such a trick to sample k elements from n choices, and Xie and Ermon (2019) further applied the trick to stochastic kNN, where neural networks are used to approximating the sorting operator.”
Decomposition Enhances Reasoning via Self-Evaluation Guided Decoding (2023, neutral): “Furthermore, we incorporate temperaturecontrolled randomness (Ackley et al., 1985; Kool et al., 2019; Meister et al., 2021) into the traditional (deterministic) beam search to balance the quality–diversity trade-off in searching for better reasoning chains.”
Illuminating protein space with a programmable generative model (2022, background): “, 2020], and stochastic beam search [Kool et al., 2019].”
Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions (2021, neutral): “For a more extensive treatment see (Maddison et al., 2014; Kool et al., 2019).”
Argmax Flows and Multinomial Diffusion: Towards Non-Autoregressive Language Models (2021, neutral): “For a more extensive introduction see (Maddison et al., 2014; Kool et al., 2019).”