研究了随机约束满足性问题的两个典型集合,并主要考虑其相空间的纯态、相变等问题,阐述了相变精确位置和多种算法在不同相的表现,包括局部蒙特卡罗马尔科夫链、置信传播和调查传播技术。
Dec, 2006
该综述从物理学角度介绍了用于解决组合优化问题的工具和概念,特别是与相变以及统计物理学相关的部分,并给出了物理学对计算机科学的跨学科贡献的观点。
Apr, 2001
本文通过对稀疏图上的推理问题的描述和分析,研究了随机块模型的相变以及在信息论上最优化问题变得容易但是在计算上仍具挑战性的的混合硬相位,并阐明了消息传递算法的贝叶斯最优性及其在这些问题中的作用,并通过数值模拟验证了该方法的有效性。
Jun, 2018
本文研究了基于测度理论的交换性研究框架,并基于一种称为完全随机测度的随机过程推导了网络结构的重要性质,提出了一种哈密顿蒙特卡罗算法,实现了网络结构的后验分布探索和图形生成,并在包括社交网络、政治博客、蛋白质网络、引用网络以及互联网网络等多个真实数据集上进行检验。
Jan, 2014
介绍了推断问题中的相变和统计物理之间的联系,详细阐述了类似 Ising 模型的推断问题,以及解决图和网络上的聚类和稀疏估计问题的应用。
Nov, 2015
该论文提出了一种算法,用于在连续和非高斯概率分布中识别稀疏的依赖结构,并利用依赖结构来进行更准确的分布估计和推理。
Nov, 2017
本文介绍了一种扩展了边远离独立性的稀疏随机图的一般模型,并且通过构造非齐性随机超图来替代每个超边,再通过与某个积分算子的范数相关来解释巨型连通性的临界点,并将该巨型连通量与某些(非 Poisson)多类型分支过程的生存概率关联起来,同时研究度分布和数量小子图的细节。
Jul, 2008
通过对随机凸优化问题进行第一次严格分析,本文提出了描述随机凸优化问题中相变现象的工具,以及可靠地预测转变区域位置和宽度的技术,这些技术适用于具有随机测量的正则化线性逆问题、随机不连贯模型下的分离问题以及随机仿射约束锥形程序等;该文还引入了统计维度这一概要参数来说明这一应用结果依赖于锥形几何的基础研究,并且通过展示锥形几何中一系列内固体积集中分布在其上,得到了对于随机旋转锥体和一个固定锥体共享射线的概率的准确上界。
Mar, 2013
本文研究了在具有一致稀疏图序列的随机树 T 上的同质化因子模型的自由能密度存在性,并通过新的插值方案证明了存在性并具体计算了该量。通过实例计算,我们证明了该极限与在 T 上的 Belief Propagation(Bethe)递归的适当不动点处的 Bethe 自由能函数重合。
Oct, 2011
提出了一种基于点过程的稀疏网络重叠社区结构的统计模型,采用完全随机测度向量分配节点所属的潜在社区,并开发了推断方法和图形模拟方法。在实际的网络应用中,该方法能够处理包含成千上万个节点和数万条边的网络,并能恢复出可解释的结构。
Feb, 2016