Information Technology Reference
In-Depth Information
By normalizing DCG@
k
with its maximum possible value (denoted as
Z
k
), we
will get another measure named Normalized DCG (NDCG). That is,
k
1
Z
k
NDCG@
k(π,l)
=
G(l
π
−
1
(j)
)η(j ).
(1.9)
j
=
1
It is clear that NDCG takes values from 0 to 1.
If we want to consider all the labeled documents (whose number is
m
) to compute
NDCG, we will get NDCG@
m
(and sometimes NDCG for short).
Consider the example as shown in Fig.
1.4
. It is easy to see that DCG@3
=
1
.
5,
1
.
5
and
Z
3
=
1
.
63. Correspondingly, NDCG
=
NDCG@3
=
1
.
63
=
0
.
92.
Rank Correlation (RC)
The correlation between the ranked list given by the
model (denoted as
π
) and the relevance judgment (denoted as
π
l
) can be used as a
measure. For example, when the weighted Kendall's
τ
[
43
] is used, the rank correla-
tion measures the weighted pairwise inconsistency between two lists. Its definition
is given by
u<v
w
u,v
(
1
+
−
−
sgn
((π(u)
π(v))(π
l
(u)
π
l
(v))))
2
u<v
w
u,v
τ
K
(π, π
l
)
=
,
(1.10)
where
w
u,v
is the weight, and
π(u)
means the rank position of document
d
u
in a
permutation
π
.
Note that the above rank correlation is defined with the assumption that the judg-
ment is given as total order
π
l
. When the judgments are in other forms, we need
to introduce the concept of an equivalent permutation set to generalize the above
definition. That is, there will be multiple permutations that are consistent with the
judgment in terms of relevance degrees or pairwise preferences. The set of such
permutations is called the equivalent permutation set, denoted as
Ω
l
.
Specifically, for the judgment in terms of relevance degree, the equivalent per-
mutation set is defined as follows.
Ω
l
={
π
l
|
u<v,
if
l
π
−
1
l
(u)
l
π
−
1
l
(v)
}
.
Similarly, for the judgment in terms of pairwise preferences,
Ω
l
is defined as
below.
Ω
l
={
π
l
|
u<v,
if
l
π
−
1
l
(v)
=
1
}
.
(u),π
−
1
l
Then, we can refine the definition of weighted Kendall's
τ
as follows.
τ
K
(π, Ω
l
)
=
max
π
l
∈
Ω
l
τ
K
(π, π
l
).
(1.11)
Consider the example as shown in Fig.
1.4
. It is clear that there are multiple
permutations consistent with the labels: (1, 3, 2) and (3, 1, 2). Since the ranking
result is (1, 2, 3), it is not difficult to compute that the
τ
K
between (1, 2, 3) and
