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, Wouter1 W.W.M.KOOL@UVA.NL, van Hoof, Herke2 H.C.VANHOOF@UVA.NL, Welling, Max3 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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 142331004
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Ancestral Gumbel-Top-k Sampling for Sampling Without Replacement.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Kool%2C+Wouter%22">Kool, Wouter</searchLink><relatesTo>1</relatesTo><i> W.W.M.KOOL@UVA.NL</i><br /><searchLink fieldCode="AR" term="%22van+Hoof%2C+Herke%22">van Hoof, Herke</searchLink><relatesTo>2</relatesTo><i> H.C.VANHOOF@UVA.NL</i><br /><searchLink fieldCode="AR" term="%22Welling%2C+Max%22">Welling, Max</searchLink><relatesTo>3</relatesTo><i> M.WELLING@UVA.NL</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Machine+Learning+Research%22">Journal of Machine Learning Research</searchLink>. 2020, Vol. 21 Issue 26-47, p1-36. 36p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Multivariate+analysis%22">Multivariate analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Markov+processes%22">Markov processes</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=142331004
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 36
        StartPage: 1
    Subjects:
      – SubjectFull: Multivariate analysis
        Type: general
      – SubjectFull: Markov processes
        Type: general
    Titles:
      – TitleFull: Ancestral Gumbel-Top-k Sampling for Sampling Without Replacement.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Kool, Wouter
      – PersonEntity:
          Name:
            NameFull: van Hoof, Herke
      – PersonEntity:
          Name:
            NameFull: Welling, Max
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: 2020
              Type: published
              Y: 2020
          Identifiers:
            – Type: issn-print
              Value: 15324435
          Numbering:
            – Type: volume
              Value: 21
            – Type: issue
              Value: 26-47
          Titles:
            – TitleFull: Journal of Machine Learning Research
              Type: main
ResultId 1