English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of learning to rank from pairwise preferences, and solvea long-standing open problem that has led to development of many heuristics butno provable results for our particular problem. Given a set $V$ of $n$elements, we wish to linearly order them given pairwise preference labels. Apairwise preference label is obtained as a response, typically from a human, tothe question "which if preferred, u or v?$ for two elements $u,v\in V$. Weassume possible non-transitivity paradoxes which may arise naturally due tohuman mistakes or irrationality. The goal is to linearly order the elementsfrom the most preferred to the least preferred, while disagreeing with as fewpairwise preference labels as possible. Our performance is measured by twoparameters: The loss and the query complexity (number of pairwise preferencelabels we obtain). This is a typical learning problem, with the exception thatthe space from which the pairwise preferences is drawn is finite, consisting of${n\choose 2}$ possibilities only. We present an active learning algorithm forthis problem, with query bounds significantly beating general (non active)bounds for the same error guarantee, while almost achieving the informationtheoretical lower bound. Our main construct is a decomposition of the inputs.t. (i) each block incurs high loss at optimum, and (ii) the optimal solutionrespecting the decomposition is not much worse than the true opt. Thedecomposition is done by adapting a recent result by Kenyon and Schudy for arelated combinatorial optimization problem to the query efficient setting. Wethus settle an open problem posed by learning-to-rank theoreticians andpractitioners: What is a provably correct way to sample preference labels? Tofurther show the power and practicality of our solution, we show how to use itin concert with an SVM relaxation.

An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity