Learning to Rank: From Pairwise Approach to Listwise Approach

In the previous paper, support vector learning for ordinal regression, it use pairwise method to solve the problem of ordinal learning. However, using pairwise approach to solve this problem will induce some problem.
First, the objective of learning is formalized as minimizing errors in classification of document pairs, rather than minimizing errors in ranking of documents.Second, the training process is computationally costly, as the number of document pairs is very large. 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 problem setting.

In training, a set of queryies Q=(q⁽¹⁾,q⁽²⁾, ... ,q^(m)) is given.
Each query q^(m) is associated with a list of documents d⁽ⁱ⁾ = (d⁽ⁱ⁾₁, d⁽ⁱ⁾₂, ...,d⁽ⁱ⁾_n(i)).
Each list of documents  d⁽ⁱ⁾ is associated with a list of judgments (scores) y⁽ⁱ⁾= (y⁽ⁱ⁾₁, y⁽ⁱ⁾₂, ...,y⁽ⁱ⁾_n(i)). The judgment y⁽ⁱ⁾_j represents the relevance degree of d⁽ⁱ⁾_j to q⁽ⁱ⁾.
A feature vector x⁽ⁱ⁾_j=ψ(q⁽ⁱ⁾,d⁽ⁱ⁾_j) is created from each query-document pair.
Note that there is a  q⁽ⁱ⁾  in ψ function. If it doesn't have this item, then the ranking list will be always the same no matter what query is.

We want to find a ranking function f, which will output the score by taking one feature vector.
For the list of feature vectors x⁽ⁱ⁾, we can obtain a list of scores z⁽ⁱ⁾ = (f(x⁽ⁱ⁾₁), ... ,f(x⁽ⁱ⁾_n(i))).

The objective of learning is formalized as minimization of the total losses with respect to the training data.

Where L is the loss function.

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

However, if we want to derive this probability distribution precisely, we need lots of computation overhead.
Thus, instead of calculating this probability, they calculate top one probability.
Then, for top one probability, the value can be derived more easily.

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

And phi-function is defined as exponential function.

Then, they 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.
Thus, for a query q⁽ⁱ⁾, the score list z⁽ⁱ⁾(f_w) = (f_w(x⁽ⁱ⁾₁), f_w(x⁽ⁱ⁾₂), ..., f_w(x⁽ⁱ⁾_n(i))).
For simplicity, they use linear Neural Network model in the experiment, f_w(x⁽ⁱ⁾_j) = w × x⁽ⁱ⁾_j.
That is, they tried to learn a linear combination that minimize the loss function measure by Cross Entropy.
And they show their list-wise method really performs better than other methods