Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity
Given a set $V$ of $n$ elements we wish to linearly order them using pairwise preference labels which may be non-transitive (due to irrationality or arbitrary noise). The goal is to linearly order the elements while disagreeing with as few pairwise preference labels as possible. Our performance is measured by two parameters: The number of disagreements (loss) and the query complexity (number of pairwise preference labels). Our algorithm adaptively queries at most $O(n\poly(\log n,\eps^{-1}))$ preference labels for a regret of $\eps$ times the optimal loss. This is strictly better, and often significantly better than what non-adaptive sampling could achieve. Our main result helps settle an open problem posed by learning-to-rank (from pairwise information) theoreticians and practitioners: What is a provably correct way to sample preference labels?
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningLearning-To-RankSimilar Papers 제목 키워드 기반
Clustering and Inference From Pairwise Comparisons
Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, ari…
ClusteringActive Ranking using Pairwise Comparisons
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of $n$ objects can be identified by standard sorting methods using $n log_2…
Consolidating Ranking and Relevance Predictions of Large Language Models through Post-Processing
The powerful generative abilities of large language models (LLMs) show potential in generating relevance labels for search applications. Previous work has found that directly asking about relevancy, such as ``How relevan…
Rate-Optimal Rank Aggregation with Private Pairwise Rankings
In various real-world scenarios, such as recommender systems and political surveys, pairwise rankings are commonly collected and utilized for rank aggregation to derive an overall ranking of items. However, preference ra…
Recommendation SystemsPrediction-Powered Ranking of Large Language Models
Large language models are often ranked according to their level of alignment with human preferences -- a model is better than other models if its outputs are more frequently preferred by humans. One of the popular ways t…
ChatbotLanguage ModellingLarge Language ModelPrediction