Learning to rank: from pairwise approach to listwise approach

Learning to rank: from pairwise approach to listwise approach Cao, ICML, 2007
==================================================

When use only pairwise method to solve the problem of ordinal learning. it comes out that this will induce some problem. First, the objective of learning is formalized as minimizing errors in classification of document pairs, disobey the goal of minimizing errors in ranking of documents. Second, the training process is computationally costly because it based on pairwise learning style. Third, the assumption of that the document pairs are generated i.i.d. is also too strong. Fourth, the number of generated document pairs varies largely from query to query, which will result in training a model biased toward queries with more document pairs.
Thus, in this paper, they propose the list-wise approach.
The followings are the concept of listwise ranking

where q are set of queries, d(i) associated with respect to query q(i), The judgment y⁽ⁱ⁾j represents the relevance degree of d⁽ⁱ⁾j to q(i).

x are the feature vectors and z are the list of scores obtained, the objective of learning is formalized as minimization of the total losses with respect to the training data (the formula in the above figure at the right)

In order to measure the loss function of two different ranking, we first convert the ranking into probability distribution, and measure the loss function by using Cross Entropy.The following definition  convert the ranking into probability distribution.

to simplify the computation procedure,  calculating the top one permutation probability

using this representation, then we can use Cross Entropy as metric

phi-function is defined as exponential function 

Then use gradient descent method to solve this optimization problem.
The ranking function f_w is based on the Neural Network model w.
Given a feature vector x⁽ⁱ⁾_j, f_w(x⁽ⁱ⁾_j) assigns a score to it.
Finally, learn a linear combination that minimize the loss function measure by Cross Entropy.
Following is the deatail of the algorithn.

 

==============================================

Comment:

The listwise learing style improve the drawback that pairwise learing has. It's more efficient and have more physical by training naturally based on list ranking style.