统计排名与组合霍奇理论
我们提出了基于原理的高斯过程(GPs)来建模在简单二维复合物的边集上定义的函数,一种类似于图形的结构,在其中边可以形成三角面。这种方法旨在用于学习在边流可以由离散的散度和旋度描述网络上的流动类型数据。
Oct, 2023
给定多个项目之间的成对比较,如何对它们进行排名,以使得排名与观察结果相匹配?本研究关注基于 Erdos-Renyi 异常值(ERO)模型的排名问题,在该问题中,每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法,我们提供了每个项目从观察数据中恢复出其潜在分数的性能,并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术,我们提供了更精确的最大特征向量的 l∞范数扰动界限,并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果,并通过数值实验验证了这些理论发现。
Sep, 2023
本文分析了 HodgeRank 估算器的两种随机抽样方法 —— 有替换和无替换的方法,并使用随机图理论中的工具来测量估算器的稳健性,提供了这两种随机图模型的 Fiedler 值的新估计,基于我们的发现,对于需要比较的项目较少的情况下,我们建议采用两阶段取样策略,并在第二阶段采用无替换的随机取样方法。而对于需要比较的项目较多的情况,则建议使用带替换的随机取样方法,此方法计算廉价且易于并行化。
Feb, 2015
本文将利用相关的 Hodge 拉普拉斯矩阵的特征向量以及对应的单纯复形的关联矩阵进行 Hodge 分解,为观测数据提供梯度、旋度和谐波流形式的稀疏、可解释表示,从而解决了在图的边缘流中获得稀疏、可解释表示的问题,并通过引入一种高效的近似算法来解决本文介绍的细胞推断优化问题。实验结果表明,该算法在真实数据和合成数据上表现优于当前最先进的方法,并且计算效率高。
Sep, 2023
该研究提出了一个用于直接优化排名度量的高效框架 ——CatBoost,并介绍了两种重要的技术:随机平滑和基于部分积分的新梯度估计,证明了经典平滑方法可能会引入偏差,并提出了一个通用解决方案进行去偏差,该算法保证全局收敛性并在多个学习排名数据集上优于现有方法。
Mar, 2020
提出一种称为 Pref-Rank 的算法,它利用结构丰富的图形嵌入来预测排名。通过在坐标点上建立强乘积空间,该算法通过 SVM 方法从结果图嵌入中提取关键信息并在两种排序 Loss 上提供了统计一致性。实验结果表明,此算法优于现有的状态 - of-the-art 方法。
Nov, 2018
该论文提出了一种基于物理学原理的模型和高效算法,用于推断有向网络中节点的层次排名,并介绍了一种更精确的排名方式,并提供了一种对强度进行统计显著性检验的方法,应用于预测边的存在性和方向,并在实际和合成数据上分析展示出算法的效率与可扩展度。
Sep, 2017
本文关注 Bradley-Terry-Luce 模型中的成对比较问题,并通过对图论的分析,提出了能够在有限条件下对排名进行准确估计的算法,并在大规模实验中证实了该算法的可行性。
Apr, 2023
本研究旨在通过成对比较的数据形式,使用 Copeland 计数算法实现对 n 个项目的排序,使其具有计算效率高,鲁棒性强,接近信息论极限等特点,并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。
Dec, 2015