Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909942179430400 |
|---|---|
| author | Vahidi, Soroush Koutis, Ioannis |
| author_facet | Vahidi, Soroush Koutis, Ioannis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16181 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons Vahidi, Soroush Koutis, Ioannis Information Retrieval Artificial Intelligence Data Structures and Algorithms Machine Learning 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. |
| title | Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons |
| topic | Information Retrieval Artificial Intelligence Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2412.16181 |