Information Technology Reference
In-Depth Information
The advantages of using the worst-case disagreement as compared to using other
kinds of disagreements, such as the average disagreement, are as follows. First, the
worst-case disagreement is much easier to calculate because it does not consider
the detailed data distribution. Second, if the worst-case disagreement is small, we
can come to the conclusion that the two measures are highly correlated everywhere
in the input space. As a result, their global optima will be very close. However, if
we only know that the average disagreement is small, it is still possible that the
two measures are largely different at some point. As a consequence, we can hardly
come to any conclusion about the relationship between the global optima of the two
measures.
With the concept of tendency correlation, the following theoretical results have
been proven in [
5
]. Note that although not all the direct optimization methods in-
troduced in this topic have been covered by these theorems, the extensions to them
are not difficult based on the proofing techniques given in [
5
]. The following results
have also been empirically verified in [
5
] and are in accordance with the experimen-
tal results reported in other work.
For SoftRank [
9
], one can obtain the following result, which basically indicates
that SoftNDCG can have an arbitrarily strong tendency correlation with NDCG if
the parameter
σ
s
is set to be arbitrarily small.
Theorem 5.4
For query q
,
suppose its associated documents and ground-truth la-
bels are (
x
,
y
)
.
Assume
w
T
x
i
−
w
T
x
j
|≥
δ>
0,
4
∀
i and j
,
|
and
∀
q,m
≤
m
0
.
If
δ
2erf
−
1
(
5
m
0
−
9
σ
s
<
,
then SoftNDCG has ε tendency correlation with NDCG and ε
5
m
0
−
5
)
satisfies that
2
L
ε
≤
N
·
·
(ε
1
+
ε
2
),
δ
2
4
σ
s
,ε
2
=
e
−
erf
2
(
δ
2
σ
s
)
(m
0
−
1
)
[
1
−
]
(m
0
1
)
σ
s
2
δ
√
π
−
ε
3
where ε
1
=
5
ε
3
+
5
ε
3
,ε
3
=
.
1
−
4
For Approximate Rank [
8
], one can obtain the following result for AppNDCG,
which indicates that AppNDCG can have an arbitrarily strong tendency correlation
with NDCG if the parameter
α
is set to be arbitrarily large. As for AppMAP, similar
result can also be obtained.
Theorem 5.5
For query q
,
suppose its associated documents and ground-truth
labels are (
x
,
y
)
.
Assume
w
T
x
i
−
w
T
x
j
|≥
∀
i and j
,
|
δ>
0,
and
∀
q,m
≤
m
0
.
If
α>
log
(
max
{
0
,
2
m
0
−
3
}
)
δ
,
then AppNDCG has ε tendency correlation with NDCG and
4
Note that this assumption is made in order that one can obtain a unique ranked list by sorting
the scores assigned by
f
=
w
T
x
to the documents. Otherwise, the output of the ranking model
will correspond to different evaluation-measure values depending upon how we rank the docu-
ments with the same score. In this case, it makes no sense how the evaluation measure is directly
optimized since the evaluation measure is not a single value.
