View in EDS

Ancestral Gumbel-Top-k Sampling for Sampling Without Replacement.

Saved in:

Bibliographic Details
Title:	Ancestral Gumbel-Top-k Sampling for Sampling Without Replacement.
Authors:	Kool, Wouter¹ W.W.M.KOOL@UVA.NL, van Hoof, Herke² H.C.VANHOOF@UVA.NL, Welling, Max³ M.WELLING@UVA.NL
Source:	Journal of Machine Learning Research. 2020, Vol. 21 Issue 26-47, p1-36. 36p.
Subjects:	Multivariate analysis, Markov processes
Abstract:	We develop ancestral Gumbel-Top-k sampling: a generic and efficient method for sampling without replacement from discrete-valued Bayesian networks, which includes multivariate discrete distributions, Markov chains and sequence models. The method uses an extension of the Gumbel-Max trick to sample without replacement by finding the top k of perturbed log-probabilities among all possible configurations of a Bayesian network. Despite the exponentially large domain, the algorithm has a complexity linear in the number of variables and sample size k. Our algorithm allows to set the number of parallel processors m, to trade off the number of iterations versus the total cost (iterations times m) of running the algorithm. For m = 1 the algorithm has minimum total cost, whereas for m = k the number of iterations is minimized, and the resulting algorithm is known as Stochastic Beam Search.¹ We provide extensions of the algorithm and discuss a number of related algorithms. We analyze the properties of Gumbel-Top-k sampling and compare against alternatives on randomly generated Bayesian networks with different levels of connectivity. In the context of (deep) sequence models, we show its use as a method to generate diverse but high-quality translations and statistical estimates of translation quality and entropy. [ABSTRACT FROM AUTHOR]
	Copyright of Journal of Machine Learning Research is the property of Microtome Publishing and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	We develop ancestral Gumbel-Top-k sampling: a generic and efficient method for sampling without replacement from discrete-valued Bayesian networks, which includes multivariate discrete distributions, Markov chains and sequence models. The method uses an extension of the Gumbel-Max trick to sample without replacement by finding the top k of perturbed log-probabilities among all possible configurations of a Bayesian network. Despite the exponentially large domain, the algorithm has a complexity linear in the number of variables and sample size k. Our algorithm allows to set the number of parallel processors m, to trade off the number of iterations versus the total cost (iterations times m) of running the algorithm. For m = 1 the algorithm has minimum total cost, whereas for m = k the number of iterations is minimized, and the resulting algorithm is known as Stochastic Beam Search.¹ We provide extensions of the algorithm and discuss a number of related algorithms. We analyze the properties of Gumbel-Top-k sampling and compare against alternatives on randomly generated Bayesian networks with different levels of connectivity. In the context of (deep) sequence models, we show its use as a method to generate diverse but high-quality translations and statistical estimates of translation quality and entropy. [ABSTRACT FROM AUTHOR]
ISSN:	15324435