Scalable Discrete Sampling as a Multi-Armed Bandit Problem
Scalable Discrete Sampling as a Multi-Armed Bandit Problem
复制标题
DOI：
--
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Yutian Chen;Zoubin Ghahramani
中科院分区：
文献类型：
--
作者：
Yutian Chen;Zoubin Ghahramani
从离散分布中抽取样本是蒙特卡罗方法的基本组成部分之一。与其他抽样算法一样，离散抽样算法在大规模推理问题中具有较高的计算负担。我们研究了大规模贝叶斯推理和图模型中典型的具有高度依赖性的离散随机变量的抽样问题，并提出了一种用子抽样方法的有效近似解。我们在离散采样和有限报酬群体的多武装盗匪问题之间建立了一种新的联系，并提供了三种具有理论保证的算法。经验评估表明，在综合和现实世界的大规模问题近似算法的鲁棒性和效率。
Drawing a sample from a discrete distribution is one of the building components for Monte Carlo methods. Like other sampling algorithms, discrete sampling suffers from the high computational burden in large-scale inference problems. We study the problem of sampling a discrete random variable with a high degree of dependency that is typical in large-scale Bayesian inference and graphical models, and propose an efficient approximate solution with a subsampling approach. We make a novel connection between the discrete sampling and Multi-Armed Bandits problems with a finite reward population and provide three algorithms with theoretical guarantees. Empirical evaluations show the robustness and efficiency of the approximate algorithms in both synthetic and real-world large-scale problems.