一般图上的自我排斥随机游走 - 通过非线性马尔可夫链实现最小采样方差
使用一种非线性 Markov 链 - 即自排斥随机游走(SRRW)驱动分布式随机优化算法,证明了该算法的迭代误差趋于零,同时导出了迭代误差对应的渐近协方差矩阵的显式形式。
Jan, 2024
我们提出了一种新颖的准蒙特卡罗机制 —— 排斥随机游走,该机制通过在一个交互集合的轨迹之间引入相关性,使它们的边际转移概率保持不变,从而能够更有效地探索图形,提高统计估计的集中度,同时保持其无偏性。我们展示了排斥随机游走在一系列设置中的有效性,包括图核的估计、PageRank 向量和图结构浓度。我们提供了详细的实验评估和稳健的理论保证。据我们所知,排斥随机游走是第一个对图中行者的方向进行严格研究的准蒙特卡罗方案,为这个令人兴奋的新领域带来了新的研究。
Oct, 2023
我们提出了一种新的准蒙特卡洛机制,用于改进基于图的采样,称为斥力随机游走。通过在相互作用的集合中引入轨迹之间的相关性,使其边际转移概率不变,我们能够更高效地探索图,并提高统计估计量的集中度,同时保持其无偏性。该机制具有简单易用的实现方法。我们展示了斥力随机游走在估计图核、PageRank 向量和图图案集中度等各种环境中的有效性,并提供了详细的实验评估和稳健的理论保证。据我们所知,斥力随机游走是第一个对图上行走者的方向进行严格研究的准蒙特卡洛方案,在这个令人兴奋的初创领域中引发了新的研究。
Oct, 2023
本文研究了一类有限状态空间上的非 Markov 离散随机过程,探讨了状态访问次数和先验概率矩阵对转移概率的影响以及分数占用向量的极限行为,证明了极限点集合为满足某些特定条件的二次型的临界点集,具有一定的概率极限,否则极限为 0。
Apr, 2004
提出了 NBRW-rw 和 MHDA 算法分别解决了 SRW-rw 和 MH 算法扩散速度慢的问题,提供更高效率的无偏图采样。
Apr, 2012
本文介绍了一种非马尔可夫随机过程,其稳态分布由张量特征向量给出。该随机过程的离散动态与连续动态系统相关,并用于人口遗传学、排名和聚类数据的几个应用以及纽约出租车轨迹数据的分析中。
Feb, 2016
本文提出了一种新的算法 Waddling Random Walk(WRW),用于估计任意大小的图相对浓度,并通过在可访问的节点路径上进行随机游走来采样子图以提高计算效率、精度与准确性。通过使用广泛使用的图形数据集,该算法在速度、精度和准确性方面都优于当前最先进的挖掘子图统计算法。
May, 2016
本文提出了一种改进 reSGLD 的方法来加速处理非凸学习,采用方差约减的策略并在 Markov jump process 下进行非渐进的分析,结果表明我们在优化和不确定性预测方面实现了最先进的效果。
Oct, 2020
本研究提出一组技术,允许在每台机器的空间强烈次线性的情况下,在 Massive Parallel Computation(MPC)模型中高效生成许多独立的随机游走,从而突破了 PageRank 等在有向和无向图的应用中遇到的局限性。
Jul, 2019