Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement
arXiv:1903.06059
Abstract
The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample elements without replacement. We show how to implicitly apply this 'Gumbel-Top-' 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 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.
ICML 2019 ; 13 pages, 4 figures
References in corpus (6)
- Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
- The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
- A Simple, Fast Diverse Decoding Algorithm for Neural Generation
- On the Partition Function and Random Maximum A-Posteriori Perturbations
- Structured Training for Neural Network Transition-Based Parsing
- Neural Machine Translation with Gumbel-Greedy Decoding