Information Technology Reference
In-Depth Information
Chapter 18
Statistical Consistency for Ranking
Abstract
In this chapter, we introduce the statistical consistency of learning-to-
rank methods. In particular, we will introduce the existing results on statistical
consistency under different ranking frameworks, and with respect to different true
losses, e.g., the pairwise 0-1 loss, the permutation-level 0-1 loss, the top-
k
loss, and
the weighted Kendall's
τ
loss. Then we will make discussions on these results and
point out the ways of further improving them.
18.1 Overview
As we can see, for the ranking algorithms introduced in this topic, a common prac-
tice is to use a surrogate loss function instead of the true loss in the learning process
(this is true even for some direct optimization algorithms). However, it is unclear
whether the ranking function learned by minimizing the surrogate loss function can
have good ranking performances in terms of the true loss function. This is just what
statistical consistency is concerned about.
Specifically, when the number of training samples approaches infinity, if the ex-
pected true risk of the ranking function learned by minimizing an expected surrogate
risk can converge to the minimum expected true risk, we say that the algorithm min-
imizing the surrogate risk is
statistically consistent
. In practice, in order to prove the
statistical consistency, one usually needs to derive a regret bound. That is, if the
difference between the expected true risk of a ranking function and the minimum
expected true risk can be bounded by the difference between the expected surro-
gate risk of the ranking function and the minimum expected surrogate risk, we can
come to the conclusion that the learning method that minimizes the surrogate risk is
statistically consistent.
In this chapter, we will introduce some previous works that analyze the statistical
consistency of ranking methods. As can be seen later, these works are different
from each other, in terms of the statistical ranking frameworks and the true loss
functions.
