Just Sort It! A Simple and Effective Approach to Active Preference Learning
We address the problem of learning a ranking by using adaptively chosen pairwise comparisons. Our goal is to recover the ranking accurately but to sample the comparisons sparingly. If all comparison outcomes are consistent with the ranking, the optimal solution is to use an efficient sorting algorithm, such as Quicksort. But how do sorting algorithms behave if some comparison outcomes are inconsistent with the ranking? We give favorable guarantees for Quicksort for the popular Bradley-Terry model, under natural assumptions on the parameters. Furthermore, we empirically demonstrate that sorting algorithms lead to a very simple and effective active learning strategy: repeatedly sort the items. This strategy performs as well as state-of-the-art methods (and much better than random sampling) at a minuscule fraction of the computational cost.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningSimilar Papers 제목 키워드 기반
Sorting and filtering as effective rational choice procedures
Many online shops offer functionality that help their customers navigate the available alternatives. For instance, options to filter and to sort goods are wide-spread. In this paper we show that sorting and filtering can…
NavigateA Novel Machine Learning Method for Preference Identification
Human preference or taste within any domain is usually a difficult thing to identify or predict with high probability. In the domain of chess problem composition, the same is true. Traditional machine learning approaches…
BIG-bench Machine LearningActive Learners as Efficient PRP Rerankers
Pairwise Ranking Prompting (PRP) elicits pairwise preference judgments from an LLM, which are then aggregated into a ranking, usually via classical sorting algorithms. However, judgments are noisy, order-sensitive, and s…
Active LearningAn incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting
This paper introduces a novel incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting (MCS) problems, enabling decision makers to progressively provid…
Active LearningQuestion SelectionA preference learning framework for multiple criteria sorting with diverse additive value models and valued assignment examples
We present a preference learning framework for multiple criteria sorting. We consider sorting procedures applying an additive value model with diverse types of marginal value functions (including linear, piecewise-linear…