Monte Carlo algorithms simulate some prescribed number of samples, taking some random real time to complete the computations necessary. This work considers the converse: to impose a real-time budget on the computation, which results in the number of samples simulated being random. To complicate matters, the real time taken for each simulation may depend on the sample produced, so that the samples themselves are not independent of their number, and a length bias with respect to compute time is apparent. This is especially problematic when a Markov chain Monte Carlo (MCMC) algorithm is used and the final state of the Markov chain -- rather than an average over all states -- is required, which is the case in parallel tempering implementations of MCMC. The length bias does not diminish with the compute budget in this case. It also occurs in sequential Monte Carlo (SMC) algorithms, which is the focus of this paper. We propose an anytime framework to address the concern, using a continuous-time Markov jump process to study the progress of the computation in real time. We first show that for any MCMC algorithm, the length bias of the final state's distribution due to the imposed real-time computing budget can be eliminated by using a multiple chain construction. The utility of this construction is then demonstrated on a large-scale SMC^2 implementation, using four billion particles distributed across a cluster of 128 graphics processing units on the Amazon EC2 service. The anytime framework imposes a real-time budget on the MCMC move steps within the SMC$^{2}$ algorithm, ensuring that all processors are simultaneously ready for the resampling step, demonstrably reducing idleness to due waiting times and providing substantial control over the total compute budget.


翻译:蒙特卡洛算法模拟一些指定数量的样本, 以一些随机实时时间来完成必要的计算。 这项工作考虑到反面因素: 在计算上强制实行实时预算, 从而导致模拟样本数量随机。 复杂的事情是, 每次模拟的实时时间可能取决于所生产的样本, 这样样本本身并不独立于其数量, 而计算时间的长度偏差是显而易见的。 当使用Markov连锁 Monte Carlo( MC ) 算法, 而需要马可夫链的最后状态 -- -- 而不是所有各州的平均水平 -- -- 需要这样的最终状态时, 这在同时调节执行MCM 时就是这种情况。 长度偏差不会随着本案的计算预算的计算而减少。 连环的蒙特卡洛(SMC)算法(SMC)算法(这是本文的重点)。 我们提议一个随时可以解决这一关切的框架, 使用连续的 Markov 跳动过程来研究实时计算结果的进展。 我们首先显示, 在任何MC 任何 MAC 算法中, 最后状态分配的长度偏差是最终的长度, 因为这个预算的计算过程是连续的连续的运行过程, 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
60+阅读 · 2020年3月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
蒙特卡罗方法(Monte Carlo Methods)
数据挖掘入门与实战
6+阅读 · 2018年4月22日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
5+阅读 · 2018年4月22日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
蒙特卡罗方法(Monte Carlo Methods)
数据挖掘入门与实战
6+阅读 · 2018年4月22日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员