Information Technology Reference
In-Depth Information
Algorithm 1
: Learning algorithms for AdaRank
Input
: the set of documents associated with each query
Given
: initial distribution
D
1
on input queries
For
t
1
,...,T
Train weak ranker
f
t
(
=
·
)
based on distribution
D
t
.
2
log
i
=
1
D
t
(i)(
1
+
M(f
t
,
x
(i)
,
y
(i)
))
1
Choose
α
t
=
i
=
1
D
t
(i)(
1
−
M(f
t
,
x
(i)
,
y
(i)
))
M(
s
=
1
α
s
f
s
,
x
(i)
,
y
(i)
))
exp
(
−
Update
D
t
+
1
(i)
=
j
=
1
exp
(
−
M(
s
=
1
α
s
f
s
,
x
(j )
,
y
(j )
))
.
Output
:
t
α
t
f
t
(
·
)
.
evaluation measures to be continuous and differentiable. The resultant algorithm is
called AdaRank.
As we know, in the conventional AdaBoost algorithm, the exponential loss is
used to update the distribution of input objects and to determine the combination
coefficient of the weak learners at each round of iteration (see Chaps. 21 and 22).
In AdaRank, evaluation measures are used to update the distribution of queries and
to compute the combination coefficient of the weak rankers. The algorithm flow is
shown in Algorithm
1
, where
M(f,
x
,
y
)
represents the evaluation measure. Due to
the analogy to AdaBoost, AdaRank can focus on those hard queries and progres-
sively minimize 1
M(f,
x
,
y
)
.
The condition for the convergence of the training process is given in [
32
],
with a similar derivation technique to that for AdaBoost. The condition requires
|
−
M(
s
=
1
α
s
f
s
,
x
,
y
)
M(
t
−
1
s
to be very small. This
implies the assumption on the linearity of the evaluation measure
M
, as a function
of
f
t
. However, this assumption may not be well satisfied in practice. Therefore, it is
possible that the training process of AdaRank does not naturally converge and some
additional stopping criteria are needed.
−
1
α
s
f
s
,
x
,
y
)
−
α
t
M(f
t
,
x
,
y
)
|
=
4.2.3.2 Genetic Programming Based Algorithms
Genetic programming is a method designed for optimizing complex objectives. In
the literature of learning to rank, there have been several attempts on using ge-
netic programming to optimize evaluation measures. Representative algorithms in-
clude [
1
,
8
-
13
,
28
,
34
].
Here we take the algorithm named RankGP [
34
] as an example to illustrate how
genetic programming can be used to learn the ranking model. In this algorithm, the
ranking model is defined as a tree, whose leaf nodes are features or constants, and
non-leaf nodes are operators such as
(see Fig.
4.1
). Then single popu-
lation genetic programming is used to perform the learning on the tree. Cross-over,
mutation, reproduction, and tournament selection are used as evolution mechanisms,
and the evaluation measure is used as the fitness function.
+
,
−
,
×
,
÷
