计算机科学 > 机器学习
[提交于 2016年1月28日
(v1)
,最后修订 2016年5月23日 (此版本, v2)]
标题: 关于扩散网络结构恢复的信息论下界
标题: Information-Theoretic Lower Bounds for Recovery of Diffusion Network Structures
摘要: 我们研究了正确恢复扩散网络结构的样本复杂度的信息论下界。 我们介绍了一个基于独立级联模型的离散时间扩散模型,在该模型中,对于节点数为$p$的有向图,每个节点最多有$k$个父节点,我们得到了一个阶数为$\Omega(k \log p)$的下界。 接下来,我们引入了一个连续时间扩散模型,在该模型中获得了相似的阶数为$\Omega(k \log p)$的下界。 我们的结果显示 Pouget-Abadie 等人的算法在离散时间框架下是统计最优的。 我们的工作也提出了是否有可能设计出针对连续时间框架下的最优算法的问题。
文献和引用工具
与本文相关的代码,数据和媒体
alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)
演示
推荐器和搜索工具
arXivLabs:与社区合作伙伴的实验项目
arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.