Information Technology Reference
In-Depth Information
•
The property of order preserving implies the ranking of a document is inherently
determined by its own. This property has been explicitly or implicitly used in
many previous works. For example, in [
6
], it is argued that one can make the
relevance score of a document independent of other documents, by choosing an
appropriately defined feature function.
•
The property of order sensitive shows that when starting with a ground-truth per-
mutation, the loss will increase if we exchange the positions of two documents
in it, and the speed of increase in loss is sensitive to the positions of the two
documents.
Based on the above two concepts, the following theorem has been obtained.
Theorem 18.3
Let L
φ
(f
;
∀
m documents
,
if its permutation probability space is order preserving with respect to m
−
x
,π
y
) be an order sensitive loss function
.
1
docu-
ment pairs (j
1
,j
2
), (j
2
,j
3
),...,(j
m
−
1
,j
m
)
,
then the loss L
φ
(f
;
x
,π
y
) is consis-
tent with respect to the permutation-level
0
-
1
loss
.
Further studies show that the surrogate loss functions in ListNet [
4
] and ListMLE
[
13
] both have the property of order sensitive. Then if the probability space is order
preserving, these loss functions will be statistically consistent with the permutation-
level 0-1 loss.
18.3.3 Regarding Top-k True Loss
In [
12
], it is argued that the use of a permutation-level 0-1 loss is not appropriate
for ranking in information retrieval. Instead, a top-
k
true loss can better describe the
real applications. The top-
k
true loss takes a value of 0 if the top-
k
documents and
their orders in the ranked list given by the ranking function are exactly the same as
the top-
k
documents in the ground-truth label; and takes a value of 1 otherwise.
By extending the concepts of order preserving and order sensitive in [
13
], the au-
thors proposed the new concepts of top-
k
order preserving and top-
k
order sensitive.
The
top-k order preserving property
indicates that if the top-
k
subgroup probability
for a permutation
π
π
−
1
(i) < π
−
1
(j )
∈
Ω
i,j
(here
Ω
i,j
{
π
∈
Ω
:
}
) is larger than
that for permutation
σ
−
1
i,j
π
, then the relation holds for any other permutation
π
in
Ω
i,j
and the corresponding
σ
−
1
i,j
π
provided that the top-
k
subgroup of the former
is different from that of the latter. The
top-k order sensitive
property of a surrogate
loss function
L
φ
(f
x
,π
y
)
exhibits a symmetry in
the sense that simultaneously exchanging the positions of documents
i
and
j
in the
ground truth and their scores given by the ranking function will not make the sur-
rogate loss change; (ii) when a permutation is transformed to another permutation
by exchanging the positions of two documents of it, if the two permutations do not
belong to the same top-
k
subgroup, the loss on the permutation that ranks the two
documents in the decreasing order of their scores will not be greater than the loss on
;
x
,π
y
)
indicates that (i)
L
φ
(f
;
