2 Christopher J.C. Burges Microsoft Research Technical Report MSR-TR-2010-82
that is not necessary for understanding the main thread. These ideas were originated
over several years and appeared in several papers; the purpose of this report is to
collect all of the ideas into one, easily accessible place (and to add background and
more details where needed). To keep the exposition brief, no experimental results are
presented in this chapter, and we do not compare to any other methods for learning
to rank (of which there are many); these topics are addressed extensively elsewhere.
2 RankNet
For RankNet [2], the underlying model can be any model for which the output of the
model is a differentiable function of the model parameters (typically we have used
neural nets, but we have also implemented RankNet using boosted trees, which we
will describe below). RankNet training works as follows. The training data is par-
titioned by query. At a given point during training, RankNet maps an input feature
vector x ∈ R
n
to a number f (x). For a given query, each pair of urls U
i
and U
j
with differing labels is chosen, and each such pair (with feature vectors x
i
and x
j
)
is presented to the model, which computes the scores s
i
= f (x
i
) and s
j
= f (x
j
). Let
U
i
B U
j
denote the event that U
i
should be ranked higher than U
j
(for example, be-
cause U
i
has been labeled ’excellent’ while U
j
has been labeled ’bad’ for this query;
note that the labels for the same urls may be different for different queries). The two
outputs of the model are mapped to a learned probability that U
i
should be ranked
higher than U
j
via a sigmoid function, thus:
P
i j
≡ P(U
i
B U
j
) ≡
1
1 + e
−σ(s
i
−s
j
)
where the choice of the parameter σ determines the shape of the sigmoid. The use
of the sigmoid is a known device in neural network training that has been shown to
lead to good probability estimates [1]. We then apply the cross entropy cost function,
which penalizes the deviation of the model output probabilities from the desired
probabilities: let
¯
P
i j
be the known probability that training url U
i
should be ranked
higher than training url U
j
. Then the cost is
C = −
¯
P
i j
logP
i j
− (1 −
¯
P
i j
)log(1 − P
i j
)
For a given query, let S
i j
∈ {0,±1} be defined to be 1 if document i has been la-
beled to be more relevant than document j, −1 if document i has been labeled to
be less relevant than document j, and 0 if they have the same label. Throughout
this paper we assume that the desired ranking is deterministically known, so that
¯
P
i j
=
1
2
(1 + S
i j
). (Note that the model can handle the more general case of mea-
sured probabilities, where, for example,
¯
P
i j
could be estimated by showing the pair
to several judges). Combining the above two equations gives
