研究排序算法对数据扰动的敏感性，揭示其可靠性隐患。
Perturbation Sensitivity of Maximum-Likelihood Pairwise Ranking in Computational Decision Systems
- 将数据扰动建模为有预算的子集选择问题，提出自适应攻击策略。
- 小规模协同扰动可显著改变排序结果，敏感性随预算和数据条件变化。
- 适用于评估依赖比较推理系统的稳定性与鲁棒性审计。
最大似然成对排序是优先级确定、声誉估计和基于比较的决策支持中的常见计算机制。尽管应用广泛，其在比较数据结构化变化下的扰动敏感性仍缺乏充分刻画。本文将其作为应用数学与计算科学中的稳定性分析问题进行研究，将协同扰动建模为成对观测上的预算约束子集选择问题，并提出一种可扩展的搜索启发式方法——自适应子集选择攻击（ASSA），用于探测高影响扰动集。在合成数据与真实偏好数据集上的实验表明，基于MLE的排序表现出显著的制度依赖敏感性：相对较小但协同的扰动可能引发输出排序的显著变化，且响应特征随扰动预算和数据条件而异。通过在重复试验中对比ASSA与随机、贪心及随机子集基线，我们刻画了扰动引起的排序偏移的幅度与变异性。这些结果将成对排序敏感性定位为工程系统中计算可靠性、数值稳定性和鲁棒性审计的关键问题。
原文摘要 · Abstract (English)
Maximum-likelihood pairwise ranking is a com- mon computational mechanism for prioritization, reputation estimation, and comparison-driven decision support. Despite its broad use, the perturbation sensitivity of this estimator under structured changes in comparison data remains insufficiently characterized. We study this question as an applied-mathematics and computational-science problem in stability analysis. We for- mulate coordinated perturbation as a budgeted subset-selection problem over pairwise observations and introduce an Adaptive Subset Selection Attack (ASSA) as a scalable search heuristic for probing high-impact perturbation sets. Through experiments on synthetic and observed preference datasets, we show that MLE-based ranking can exhibit pronounced regime-dependent sensitivity: relatively small but coordinated perturbations may in- duce meaningful changes in output orderings, while the response profile varies across budgets and data conditions. By comparing ASSA with random, greedy, and randomized subset baselines under repeated trials, we characterize both the magnitude and the variability of perturbation-induced ranking shifts. These results position pairwise ranking sensitivity as a problem in computational reliability, numerical stability, and robustness auditing for engineering systems built on comparison-driven inference.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。