Lost Relatives of the Gumbel Trick
Lost Relatives of the Gumbel Trick
复制标题
DOI：
10.17863/cam.11066
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Matej Balog;Nilesh Tripuraneni;Zoubin Ghahramani;Adrian Weller
中科院分区：
文献类型：
--
作者：
Matej Balog;Nilesh Tripuraneni;Zoubin Ghahramani;Adrian Weller
©2017国际机器学习学会(IMLS)。版权所有。Gumbel技巧是一种从离散概率分布中抽样或估计其归一化配分函数的方法。该方法依赖于以特定方式对分布重复施加随机扰动，每次求解最可能的配置。我们推导了一整套相关的方法，其中Gumbel技巧是其中的一个成员，并证明了新方法在几种情况下具有优越的性质，而增加的计算代价最小。特别是，为了使Gumbel技巧产生离散图形模型的计算效益，所有构型上的Gumbel扰动通常被所谓的低阶扰动所取代。我们展示了我们的新方法的子族如何适应这种设置，证明了对数分配函数的新的上下界，并导出了Gibbs分布的一族序贯采样器。最后，我们通过展示更简单的Gumbel技巧的解析形式如何使更多的理论结果成为可能，来平衡讨论。
© 2017 International Machine Learning Society (IMLS). All rights reserved. The Gumbel trick is a method to sample from a discrete probability distribution, or to estimate its normalizing partition function. The method relies on repeatedly applying a random perturbation to the distribution in a particular way, each time solving for the most likely configuration. We derive an entire family of related methods, of which the Gumbel trick is one member, and show that the new methods have superior properties in several settings with minimal additional computational cost. In particular, for the Gumbel trick to yield computational benefits for discrete graphical models, Gumbel perturbations on all configurations are typically replaced with socalled low-rank perturbations. We show how a subfamily of our new methods adapts to this setting, proving new upper and lower bounds on the log partition function and deriving a family of sequential samplers for the Gibbs distribution. Finally, we balance the discussion by showing how the simpler analytical form of the Gumbel trick enables additional theoretical results.