Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons

• URL: http://arxiv.org/abs/2412.16181v2
• Date: Tue, 07 Jan 2025 22:12:47 GMT
• Title: Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons
• Authors: Soroush Vahidi, Ioannis Koutis,
• Abstract summary: Recent work has advanced the state-of-the-art for the Ranking Problem using learning-based methods. This paper presents efficient 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.
• Score: 1.5653612447564105
• License:
• Abstract: 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.

Related papers

• TSPRank: Bridging Pairwise and Listwise Methods with a Bilinear Travelling Salesman Model [19.7255072094322]
  Travelling Salesman Problem Rank (TSPRank) is a hybrid pairwise-listwise ranking method. TSPRank's robustness and superior performance across different domains highlight its potential as a versatile and effective LETOR solution.
  arXiv  Detail & Related papers  (2024-11-18T21:10:14Z)
• Efficient Pointwise-Pairwise Learning-to-Rank for News Recommendation [6.979979613916754]
  News recommendation is a challenging task that involves personalization based on the interaction history and preferences of each user. Recent works have leveraged the power of pretrained language models (PLMs) to directly rank news items by using inference approaches that predominately fall into three categories: pointwise, pairwise, and listwise learning-to-rank. We propose a novel framework for PLM-based news recommendation that integrates both pointwise relevance prediction and pairwise comparisons in a scalable manner.
  arXiv  Detail & Related papers  (2024-09-26T10:27:19Z)
• Evaluating Ensemble Methods for News Recommender Systems [50.90330146667386]
  This paper demonstrates how ensemble methods can be used to combine many diverse state-of-the-art algorithms to achieve superior results on the Microsoft News dataset (MIND) Our findings demonstrate that a combination of NRS algorithms can outperform individual algorithms, provided that the base learners are sufficiently diverse.
  arXiv  Detail & Related papers  (2024-06-23T13:40:50Z)
• Federated Compositional Deep AUC Maximization [58.25078060952361]
  We develop a novel federated learning method for imbalanced data by directly optimizing the area under curve (AUC) score. To the best of our knowledge, this is the first work to achieve such favorable theoretical results.
  arXiv  Detail & Related papers  (2023-04-20T05:49:41Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  We propose a new algorithm selector leveraging special forests, combining the strengths of both approaches while alleviating their weaknesses. HARRIS' decisions are based on a forest model, whose trees are created based on optimized on a hybrid ranking and regression loss function.
  arXiv  Detail & Related papers  (2022-10-31T14:06:11Z)
• Federated Learning via Inexact ADMM [46.99210047518554]
  In this paper, we develop an inexact alternating direction method of multipliers (ADMM) It is both- and communication-efficient, capable of combating the stragglers' effect, and convergent under mild conditions. It has a high numerical performance compared with several state-of-the-art algorithms for federated learning.
  arXiv  Detail & Related papers  (2022-04-22T09:55:33Z)
• Heuristic Search for Rank Aggregation with Application to Label Ranking [16.275063634853584]
  We propose an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem. The algorithm features a semantic crossover based on concordant pairs and a late acceptance local search reinforced by an efficient incremental evaluation technique. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on benchmark instances.
  arXiv  Detail & Related papers  (2022-01-11T11:43:17Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics.
  arXiv  Detail & Related papers  (2021-07-28T05:18:10Z)
• SIMPLE: SIngle-network with Mimicking and Point Learning for Bottom-up Human Pose Estimation [81.03485688525133]
  We propose a novel multi-person pose estimation framework, SIngle-network with Mimicking and Point Learning for Bottom-up Human Pose Estimation (SIMPLE) Specifically, in the training process, we enable SIMPLE to mimic the pose knowledge from the high-performance top-down pipeline. Besides, SIMPLE formulates human detection and pose estimation as a unified point learning framework to complement each other in single-network.
  arXiv  Detail & Related papers  (2021-04-06T13:12:51Z)
• Optimal Full Ranking from Pairwise Comparisons [16.852801934478475]
  The minimax rate of ranking exhibits a transition between an exponential rate and a rate depending on the magnitude of the signal-to-noise ratio of the problem. To achieve the minimax rate, we propose a divide-and-conquer ranking algorithm that first divides the $n$ players into groups of similar skills and then computes local MLE within each group.
  arXiv  Detail & Related papers  (2021-01-21T03:34:44Z)
• AP-Loss for Accurate One-Stage Object Detection [49.13608882885456]
  One-stage object detectors are trained by optimizing classification-loss and localization-loss simultaneously. The former suffers much from extreme foreground-background imbalance due to the large number of anchors. This paper proposes a novel framework to replace the classification task in one-stage detectors with a ranking task.
  arXiv  Detail & Related papers  (2020-08-17T13:22:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.