Information Technology Reference
In-Depth Information
Actually the weighted Kendall's
τ
defined as above has a strong connection with
many other evaluation measures or loss functions for ranking. For example, the
weighted Kendall's
τ
is a natural extension of the Kendall's
τ
, a widely used rank-
ing measure in statistics. The weighted Kendall's
τ
is also equivalent to DCG with
certain gain and discount functions.
Given the weighted Kendall's
τ
as the true loss for ranking, the existence and
uniqueness of the optimal ranking is discussed in [
10
]. The sufficient conditions for
the existence and uniqueness of the optimal ranking are called
separability on pairs
and
transitivity over pairs
. An intuitive explanation of the separability on pairs is
that for any document pair all the optimal rankers obtained in learning can separate
(rank) the two documents with exactly the same order. The transitivity over pairs
guarantees that for any
x
s
,x
t
,x
l
,if
(x
s
,x
t
)
and
(x
t
,x
l
)
are separable with the same
order, then
(x
s
,x
l
)
is also separable with that order.
With the above two conditions, the statistical consistency for the so-called gener-
alized pairwise surrogate loss function and generalized listwise surrogate loss func-
tion are discussed. In particular, the generalized pairwise surrogate loss function is
defined by
m
−
1
m
D(u,v)φ
f(x
π
−
y
(u)
)
−
f(x
π
−
y
(v)
)
,
L
φ
(f
;
x
,π
y
)
=
u
=
1
v
=
u
+
1
and the generalization listwise surrogate loss function is defined by
m
−
1
m
α
f(x
π
−
y
(u)
)
+
β
γ
f(x
π
−
y
(v)
)
L
φ
(f
;
x
,π
y
)
=
D(u)
,
v
=
u
u
=
1
where
φ
is a convex function,
α(
·
)
and
β(
·
)
are non-increasing functions,
γ(
·
)
is a
non-decreasing function.
These two kinds of generalized loss functions can cover the loss functions
in Ranking SVM [
8
,
9
], RankBoost [
7
], RankNet [
3
] (when
D(u,v)
=
1), and
ListMLE [
13
](
α(
)
) as special cases.
The sufficient conditions for the consistency of these surrogate loss functions are
presented in the following two theorems.
·
)
=−
(
·
), β(
·
)
=−
log
(
·
), γ (
·
)
=
exp
(
·
Theorem 18.5
Let L
φ
(
) be a differentiable
,
non-negative
,
and non-increasing
function with φ
(
0
)<
0.
Then the generalized pairwise surrogate loss function is
consistent with the weighted Kendall's τ when D(u,v) are not identical
,
and is
consistent with the unweighted Kendall's τ when
·
∀
i, j, D(u, v)
=
c
,
where c is a
constant
.
Theorem 18.6
Let α(
·
) and β(
·
) be non-increasing functions
,
γ(
·
) be a non-
decreasing function
.
If α
(x) <
0
,
∀
x
,
β(
·
), γ (
·
) are differentiable
,
the general-
ized listwise surrogate loss function is consistent with the Difference-Weighting
Kendall's τ
;
if α(
x,β
(x) >
0
,γ
(x) >
0,
and
·
) is differentiable
,
∀
∀
i, D(u)
=
c
,
the generalized listwise surrogate loss is consistent with unweighted Kendall's τ
.
