Information Technology Reference

In-Depth Information

Fig. 3.5
Fidelity loss as a

function of
f(x
u
)
−
f(x
v
)

Algorithm 1
: Learning algorithm for RankBoost

Input
: training data in terms of document pairs

Given
: initial distribution

D
1
on input document pairs.

=

For
t

1
,...,T

Train weak ranker
f
t
based on distribution

D
t
.

Choose
α
t

Update

D
t
+
1
(x
(i
u
,x
(i
v
)

Z
t
D
t
(x
(i
u
,x
(i
v
)
exp
(α
t
(f
t
(x
(i
u
)

f
t
(x
(i
v
)))

1

=

−

where
Z
t
=
i
=
1
u,v
:
y
(i)

u,v

1
D
t
(x
(i
u
,x
(i
v
)
exp
(α
t
(f
t
(x
(i
u
)
−
f
t
(x
(i
v
)))
.

=

Output
:
f(x)
=
t
α
t
f
t
(x)
.

Fig. 3.6
Exponential loss for

RankBoost

D
t
is the dis-

tribution on document pairs,
f
t
is the weak ranker selected at the
t
th iteration, and

α
t
is the weight for linearly combining the weak rankers. The RankBoost algorithm

actually minimizes the exponential loss defined below (also shown in Fig.
3.6
). It is

clear that this exponential loss is also an upper bound of the pairwise 0-1 loss.

The algorithm flow of RankBoost is given in Algorithm
1
, where