分布式采样理论综述
作者:
作者单位:

作者简介:

理论计算机科学

通讯作者:

尹一通,yinyt@nju.edu.cn

中图分类号:

基金项目:

国家重点研发计划重点专项(2018YFB1003202)


Survey on Theory of Distributed Sampling
Author:
Affiliation:

Fund Project:

National Key R&D Program of China (2018YFB1003202)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    采样是一类基本的计算问题.从一个解空间中依特定概率分布进行随机采样,这一问题在近似计数、概率推断、统计学习等方面都有着诸多重要的应用.在大数据时代,采样问题的分布式算法与分布式计算复杂性受到越来越多的关注.近年来,有一系列的工作对分布式采样理论展开系统性的研究.综述了分布式采样的重要结论,主要包括有严格理论保障的分布式采样算法、采样问题在分布式模型上的计算复杂性以及采样与推断等问题在分布式计算模型中的相互联系.

    Abstract:

    Sampling is a fundamental class of computational problems. The problem of generating random samples from a solution space according to certain probability distribution has numerous important applications in approximate counting, probability inference, statistical learning, etc. In the big data era, the distributed sampling attracts considerably more attentions. In recent years, there is a line of research works that systematically study the theory of distributed sampling. This study surveys important results on distributed sampling, including distributed sampling algorithms with theoretically provable guarantees, the computational complexity of sampling in the distributed computing model, and the mutual relation between sampling and inference in the distributed computing model.

    参考文献
    相似文献
    引证文献
引用本文

凤维明,尹一通.分布式采样理论综述.软件学报,2022,33(10):3673-3699

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-03-24
  • 最后修改日期:2021-05-04
  • 录用日期:
  • 在线发布日期: 2021-05-21
  • 出版日期: 2022-10-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号