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.
