Learning to rank: construct absolute ranking using pair-wise ranking approach

Question

I am learning about the "pairwise approach" for learning to rank. As far as I understood, the training output is a partial ranking function $r$ that:

• given given some query $q$ and two document $d_i$ and $d_j$
• predicts whether $$r(d_i)>r(d_j)$$ or not

However, for a IR system to work, the ranking should be absolute.

The natural question next is how to construct the absolute rank using only the partial ranks output by $r$?

But partial ranks does not guarantee absolute rank. For example

$$r(x)>r(y), r(y)>r(z), r(z)>r(x)$$ gives a cycle.

I guess I am misunderstanding about how pairwise approach works for IR system. Can anyone correct me?

Answer 1

Creating a total ranking from pairwise comparisons that don’t necessarily follow the axioms or rational preferences would certainly require some optimization, and you would need to compute a quadratic number of such comparisons in order to produce a ranking.

There is however one trick to do this easily: if the function that classifies whether one element is ranked above the other is linear in all the features, you can, intuitively, compare each element to a null element (i.e. just apply the decision function to the element alone), get a score assigned to them, and sort them by this score.

So, intuitively, your linear classifier would be something like this: element 1 is above element 2 if: F(el1 – el2)>0 [function has to be symmetrical, thus there can't be a non-zero threshold] --> F(el1) – F(el2) >0 (only when F is linear!!!) Which implies that el1 > el2 iff F(el1)>F(el2)