Information Technology Reference
In-Depth Information
exp
−
y
u,v
f(x
u
)
f(x
v
)
.
;
=
−
L(f
x
u
,x
v
,y
u,v
)
(3.12)
From Algorithm
1
, one can see that RankBoost learns the optimal weak ranker
f
t
and its coefficient
α
t
based on the current distribution of the document pairs (
D
t
).
Three ways of choosing
α
t
are discussed in [
18
].
•
First, most generally, for any given weak ranker
f
t
, it can be shown that
Z
t
,
viewed as a function of
α
t
, has a unique minimum, which can be found numeri-
cally via a simple line search.
•
The second method is applicable in the special case that
f
t
takes a value
from {0,1}. In this case, one can minimize
Z
t
analytically as follows. For
b
∈{−
1
,
0
,
+
1
}
,let
n
1
D
t
x
(i)
,x
(i
v
I
W
t,b
=
.
(3.13)
{
f
t
(x
(i
u
)
−
f
t
(x
(i
v
)
=
b
}
u
i
=
1
y
(i)
u,v
u,v
:
=
Then
2
log
W
t,
−
1
.
1
α
t
=
(3.14)
W
t,
+
1
•
The third way is based on the approximation of
Z
t
, which is applicable when
f
t
takes a real value from [0, 1]. In this case, if we define
n
D
t
x
(i
u
,x
(i
v
f
t
x
(i
u
−
f
t
x
(i
v
,
r
t
=
(3.15)
i
=
1
y
(i)
u,v
:
=
1
u,v
then
2
log
1
.
1
+
r
t
α
t
=
(3.16)
1
−
r
t
Because of the analogy, RankBoost inherits many nice properties from Ad-
aBoost, such as the ability in feature selection, convergence in training, and certain
generalization abilities.
3.2.6 Ranking SVM
Ranking SVM [
22
,
23
] applies the SVM technology to perform pairwise classifica-
tion.
2
i
=
1
, their associated document pairs
(x
(i
u
,x
(i
v
)
,
n
Given
n
training queries
{
q
i
}
2
Note that Ranking SVM was originally proposed in [
22
] to solve the problem of ordinal regres-
sion. However, according to its formulation, it solves the problem of pairwise classification in an
even more natural way.