Information Technology Reference

In-Depth Information

Chapter 5

Analysis of the Approaches

Abstract
In this chapter, we introduce the analysis on the major approaches to

learning to rank, which looks at the relationship between their loss functions and

widely used evaluation measures. Basically, for many state-of-the-art ranking meth-

ods, it has been proven that their loss functions can upper bound measure-based

ranking errors. Therefore the minimization of these loss functions can lead to the

optimization of the evaluation measures in certain situations.

5.1 Overview

In the previous three chapters, we have introduced the pointwise, pairwise, and

listwise approaches to learning to rank. The major differences between these ap-

proaches lie in their loss functions. Note that it is these loss functions that guide the

learning process; however, the evaluation of the learned ranking models is based on

the evaluation measures. Therefore, an important issue to discuss is the relationship

between the loss functions used in these approaches and the evaluation measures.

This is exactly the motivation of this chapter.
1

Without loss of generality, we will take NDCG (more accurately NDCG@
m
,

where
m
is the total number of documents associated with the query) and MAP as

examples in the discussions. Furthermore, we assume that the ground-truth label is

given as the relevance degree of each document.

5.2 The Pointwise Approach

As mentioned in Chap. 2, Cossock and Zhang [
4
] have established the theoretical

foundation for reducing ranking to regression.
2

m

j
=

Given
x

={

x
j
}

1
, a set of docu-

1
Note that based on our current understanding on the issue, it is possible that we cannot establish

connections between the evaluation measures and the loss functions in all the algorithms intro-

duced in the previous chapters. However, it would be already very helpful if we can establish the

connection between some popularly used loss functions and evaluation measures.

2
Note that the bounds given in the original papers are with respect to DCG, and here we give their

equivalent form in terms of NDCG for ease of comparison.