Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons
The Minimum Weighted Feedback Arc Set (MWFAS) problem is fundamentally connected to the Ranking Problem -- the task of deriving global rankings from pairwise comparisons. Recent work [He et al. ICML2022] has advanced the state-of-the-art for the Ranking Problem using learning-based methods, improving upon multiple previous approaches. However, the connection to MWFAS remains underexplored. This paper investigates this relationship and presents efficient combinatorial algorithms for solving MWFAS, thus addressing the Ranking Problem. Our experimental results demonstrate that these simple, learning-free algorithms not only significantly outperform learning-based methods in terms of speed but also generally achieve superior ranking accuracy.
Code (1)
Tasks
ARCMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Density-Ratio Based Personalised Ranking from Implicit Feedback
Learning from implicit user feedback is challenging as we can only observe positive samples but never access negative ones. Most conventional methods cope with this issue by adopting a pairwise ranking approach with nega…
Density Ratio EstimationSQL-Rank: A Listwise Approach to Collaborative Ranking
In this paper, we propose a listwise approach for constructing user-specific rankings in recommendation systems in a collaborative fashion. We contrast the listwise approach to previous pointwise and pairwise approaches,…
Collaborative RankingRecommendation SystemsImproved Deep Hashing with Soft Pairwise Similarity for Multi-label Image Retrieval
Hash coding has been widely used in the approximate nearest neighbor search for large-scale image retrieval. Recently, many deep hashing methods have been proposed and shown largely improved performance over traditional …
Deep HashingImage RetrievalMulti-Label Image RetrievalRetrievalOn The Structure of Parametric Tournaments with Application to Ranking from Pairwise Comparisons
We consider the classical problem of finding the minimum feedback arc set on tournaments (MFAST). The problem is NP-hard in general and we study it for important classes of tournaments that arise naturally in the proble…
ARCLearning-To-RankAnnealed Entropic Allocation for Ranking and Selection
We propose annealed entropic allocation, an adaptive sampling policy based on an annealed, weighted soft-min formulation of static budget allocation. We replace the maximin large-deviation rate objective with a weighted …