We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm can be made reversible and able to sample from a specified measure on partitions. Both of these properties are critical to some important applications and computational Bayesian statistics in general. Our proposal chain modifies the recently developed method called Recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the state space from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities. We demonstrate this method by sampling redistricting plans and find promising convergence results on several key observables of interest.


翻译:我们在图形分区上开发一个新的Markov链条,使相对全球移动,但在计算上是可行的,可以用作大都会-哈斯廷斯法中的建议。我们所产生的算法可以被逆转,并且能够从分区的某一特定测量中取样。这两个属性对于一些重要的应用和一般的计算巴耶斯统计至关重要。我们的建议链条修改了最近开发的称为再组合(ReCommination)的方法,该方法在连接的分区上画树,然后随机将其切换为再分割。我们通过扩大从分区到横跨森林的状态空间来提高计算效率。额外信息加快了前向和后向建议概率的计算。我们通过取样重新分区计划来展示这一方法,并在一些关键的兴趣观测中找到有希望的趋同结果。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
51+阅读 · 2020年12月10日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年6月30日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员