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
