奇异值分解的成对测量排名和同步
通过使用自适应选择的成对比较来学习排名,我们的目标是准确地恢复排名但节省比较样本。对于使用快速排序算法等有效算法的所有比较结果一致的情况,最优解为使用有效排序算法。我们在Bradley-Terry模型下给出了Quicksort的优异保证,并通过实证证明了排序算法导致了非常简单有效的积极学习策略。
Feb, 2015
本研究旨在通过成对比较的数据形式,使用 Copeland 计数算法实现对 n 个项目的排序,使其具有计算效率高,鲁棒性强,接近信息论极限等特点,并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。
Dec, 2015
提出了新的基于对偶平均的聚众算法,用于解决分散点之间的成对函数最小化问题,该算法的灵活性足以处理最优化问题的约束和规则的变体,并通过实证仿真验证了其实用性。
Jun, 2016
该论文研究如何采用严谨的方法证明低秩矩阵的对称秩一情况的互信息,进而表达最小均方误差和表征检测相位转变;同时介绍了一种被称为近似消息传递的迭代算法在贝叶斯最优条件下的优越性,并提出了通用的解决其他问题的方法。
Jun, 2016
文中提出了一种基于序列或主动排名的算法,该算法基于嘈杂的成对比较将一组n个项目排名并将这些项根据其得分分成预先指定大小的集合;本文针对这种算法进行了分析,证明了在某些情况下具有最优性并且不需要任何假设,比如在参数模型下进行的排名。
Jun, 2016
该论文提出了一种基于物理学原理的模型和高效算法,用于推断有向网络中节点的层次排名,并介绍了一种更精确的排名方式,并提供了一种对强度进行统计显著性检验的方法,应用于预测边的存在性和方向,并在实际和合成数据上分析展示出算法的效率与可扩展度。
Sep, 2017
提出了一种高效的算法用于解决在高噪声和污染水平下的群组同步问题,并侧重于旋转同步;使用基于消息传递算法的方法来估计群组比率的污染水平和一种基于加权最小二乘法的新算法来估计群组元素,其中权重是使用估计的污染水平初始化并迭代更新的;在合成数据和实际数据上展示了我们的算法相对于最先进的旋转同步方法的卓越性能。
Jul, 2020
本文关注Bradley-Terry-Luce模型中的成对比较问题,并通过对图论的分析,提出了能够在有限条件下对排名进行准确估计的算法,并在大规模实验中证实了该算法的可行性。
Apr, 2023
给定多个项目之间的成对比较,如何对它们进行排名,以使得排名与观察结果相匹配?本研究关注基于Erdos-Renyi异常值(ERO)模型的排名问题,在该问题中,每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法,我们提供了每个项目从观察数据中恢复出其潜在分数的性能,并得出了非归一化/归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术,我们提供了更精确的最大特征向量的l∞范数扰动界限,并在只有Ω(nlogn)个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果,并通过数值实验验证了这些理论发现。
Sep, 2023
在本文中,我们考虑了角度同步问题的动态版本,其中角度和测量图在T个时间点上演变。在假设潜在角度的演变具有平滑性条件的基础上,我们推导了三种算法来联合估计所有时间点的角度。此外,对于其中一种算法,我们在不同统计模型下建立了均方误差(MSE)的非渐近恢复保证。特别是,我们证明了在较静态设置下更温和的条件下,MSE随着T的增加收敛于零。这包括测量图高度稀疏且不连通的情况,以及测量噪声较大且可能随着T的增加而增加的情况。我们通过对合成数据进行实验来补充我们的理论结果。
Jun, 2024