Information Technology Reference

In-Depth Information

•

=

·

If the judgment is given as the total order
π
l
, one can define
y
u,v

2

I
{
π
l
(u)<π
l
(v)
}
−

1.

The
hypothesis
space contains bi-variate functions
h
that take a pair of documents

as input and output the relative order between them. While some pairwise ranking

algorithms directly define their hypotheses as such [
18
], in some other algorithms,

the hypothesis is defined with a scoring function
f
for simplicity, i.e.,
h(x
u
,x
v
)

=

2

1.

The
loss function
measures the inconsistency between
h(x
u
,x
v
)
and the ground

truth label
y
u,v
. In many pairwise ranking algorithms, ranking is modeled as a pair-

wise classification, and the corresponding classification loss on a pair of documents

is used as the loss function. When scoring function
f
is used, the classification

loss is usually expressed in terms of the difference
(f (x
u
)
−
f(x
v
))
, rather than the

thresholded quantity
h(x
u
,x
v
)
.

Example algorithms belonging to the pairwise approach include [
8
,
18
,
25
,
27
,

37
,
41
,
69
,
76
,
94
,
95
]. We will introduce some of them in Chap. 3.

Note that the loss function used in the pairwise approach only considers the rel-

ative order between two documents. When one looks at only a pair of documents,

however, the position of the documents in the final ranked list can hardly be derived.

Furthermore, the approach ignores the fact that some pairs are generated from the

documents associated with the same query. Considering that most evaluation mea-

sures for information retrieval are query level and position based, we can see a gap

between this approach and ranking for information retrieval.

·

I
{
f(x
u
)>f (x
v
)
}
−

1.3.3.3 The Listwise Approach

The
input space
of the listwise approach contains a set of documents associated with

query
q
, e.g.,
x

m

j
=

1
.

The
output space
of the listwise approach contains the ranked list (or permuta-

tion) of the documents. Different kinds of judgments can be converted to ground

truth labels in terms of a ranked list:

•

={

x
j
}

If the judgment is given as relevance degree
l
j
, then all the permutations that are

consistent with the judgment are ground truth permutations. Here we define a per-

mutation
π
y
as consistent with relevance degree
l
j
,if

u, v
satisfying
l
u
>l
v
,we

always have
π
y
(u) < π
y
(v)
. There might be multiple ground truth permutations

in this case. We use
Ω
y
to represent the set of all such permutations.
21

∀

•

If the judgment is given as pairwise preferences, then once again all the permuta-

tions that are consistent with the pairwise preferences are ground truth permuta-

tions. Here we define a permutation
π
y
as consistent with preference
l
u,v
,if

∀

u, v

satisfying
l
u,v
=+

1, we always have
π
y
(u) < π
y
(v)
. Again, there might also be

multiple ground truth permutations in this case, and we use
Ω
y
to represent the

set of all such permutations.

21
Similar treatment can be found in the definition of Rank Correlation in Sect.
1.2.2
.