用组合算法解决排序中的反馈弧集问题，速度快且精度高。
Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons
- 基于组合优化求解最小加权反馈弧集
- 运行速度远快于学习方法，精度相当或更优
- 适合大规模排序任务，无需深度学习
最小加权反馈弧集（MWFAS）问题与从成对比较中推导全局排名密切相关。近期基于学习的方法在排名基准上取得了进展，但未深入探讨其与MWFAS的内在联系。本文研究该关系，提出高效的组合算法求解MWFAS以解决排序问题。实验表明，这些无需学习的简单方法在运行时间上显著优于最新的学习方法，同时排名准确率具有竞争力，甚至在多数情况下更优。结果表明，轻量级组合技术为大规模排序任务提供了高效可扩展的替代方案。
原文摘要 · Abstract (English)
The Minimum Weighted Feedback Arc Set (MWFAS) problem is closely related to the task of deriving a global ranking from pairwise comparisons. Recent work by He et al. (ICML 2022) advanced the state of the art on ranking benchmarks using learning based methods, but did not examine the underlying connection to MWFAS. In this paper, we investigate this relationship and introduce efficient combinatorial algorithms for solving MWFAS as a means of addressing the ranking problem. Our experimental results show that these simple, learning free methods achieve substantially faster runtimes than recent learning based approaches, while also delivering competitive, and in many cases superior, ranking accuracy. These findings suggest that lightweight combinatorial techniques offer a scalable and effective alternative to deep learning for large scale ranking tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。