RankNet

The pairwise cross-entropy cost of Burges and colleagues, derived in full. The logistic model of a pair and the rule for combining pair probabilities, the cost for any target with its convexity and its bound on misordered pairs, the gradient, and a proof of the factorization into one lambda per document that turns a sum over pairs into a sum over documents. Two steps of training are traced on four Cranfield abstracts, the role of sigma is settled, and the method is run with a linear model and a two-layer net on Cranfield and LETOR's MQ2008, and used to learn this site's BM25F field weights from its own judgments. Worked problems on lambdas by hand, pair counts, tied labels and a BM25F gradient.

Four of the abstracts that BM25 retrieves for Cranfield query 185, experimental studies on panel flutter, are enough to state the problem. Each is described here by two of the course article's eight features, its BM25 score and the BM25 score of its title alone, both rescaled to run from 0 to 1 over the query's hundred candidates:

Abstract BM25 Title BM25 Label $y$
856 1.000 1.000 2
766 0.769 0.499 3
390 0.764 0.900 0
285 0.580 0.794 1

The label is the gain the course uses for Cranfield, larger for a better answer, and 0 for an abstract not judged relevant. The four labels differ, so the four abstracts form six pairs in which one should rank above the other. A pairwise method has one complaint for each pair. A scoring function has one score for each abstract. How do six complaints about pairs become one correction for each of four documents, and why does that make training fast?

RankNet (Burges, Shaked, Renshaw, Lazier, Deeds, Hamilton, and Hullender, 2005) is a way to train any scoring model whose output is a differentiable function of its parameters. It turns the difference of two scores into a probability that one document should rank above the other, charges the model the cross entropy between that probability and the truth, and descends the gradient. The course article Learning to Rank gives the cost and the gradient of one pair in a paragraph. This article is the full derivation: where the cost comes from, what can be proved about it, and the regrouping of its gradient, found later, that LambdaRank and LambdaMART are built on.

Here is the route. First we model a pair and derive the cost for any target probability, with three properties: it is convex in the scores, it is never zero, and it bounds the number of misordered pairs. Then we derive the gradient and prove the factorization into one $\lambda$ per document. Next we trace two steps of training on the four abstracts. Then we settle what the parameter $\sigma$ does, extend the model from a linear function to a neural network, and run both on Cranfield and on LETOR's MQ2008. Finally we use the method on a model that is not linear at all, this site's BM25F score, to learn its field weights from the site's own relevance judgments. The article assumes the course article and logistic regression.

The numbers are computed by tools/experiments/ltr/ranknet.py and tools/experiments/ltr/site_bm25f_weights.py in the site's repository.

A probability for each pair

Fix the unit's notation. A query has candidates $d_1, \dots, d_n$ with feature vectors $\mathbf{x}_i$ and labels $y_i$. A model $f$ with parameters $\theta$ gives each a score $s_i = f(\mathbf{x}_i)$. The set $I$ holds the ordered pairs $(i, j)$ with $y_i > y_j$.

RankNet reads the difference of two scores as evidence about their order. It maps the difference to a probability with the logistic function:

$$P_{ij} = \frac{1}{1 + e^{-\sigma(s_i - s_j)}} .$$

$P_{ij}$ is the model's probability that $d_i$ should rank above $d_j$, and $\sigma > 0$ sets how fast it moves from 0 to 1 (Burges, 2010, §2; the 2005 paper has no $\sigma$, which is the case $\sigma = 1$). Equal scores give $P_{ij} = \tfrac{1}{2}$. Solving for the exponent gives the reading of a score difference: $\sigma(s_i - s_j) = \log\frac{P_{ij}}{1 - P_{ij}}$, the log odds that $d_i$ belongs above $d_j$.

Two properties show that the choice is coherent.

The two orders of a pair get complementary probabilities. Multiply the numerator and denominator of $P_{ji} = 1/(1 + e^{\sigma(s_i - s_j)})$ by $e^{-\sigma(s_i - s_j)}$ to get $e^{-\sigma(s_i - s_j)}/(1 + e^{-\sigma(s_i - s_j)}) = 1 - P_{ij}$. So $P_{ij} + P_{ji} = 1$.

Pair probabilities combine by multiplying odds. Because every pair's log odds is a difference of the same scores, the log odds add along a chain: $\sigma(s_i - s_k) = \sigma(s_i - s_j) + \sigma(s_j - s_k)$. Exponentiating, the odds multiply:

$$\frac{P_{ik}}{1 - P_{ik}} = \frac{P_{ij}}{1 - P_{ij}} \cdot \frac{P_{jk}}{1 - P_{jk}} .$$

Solve for $P_{ik}$. Write the right side as $a/b$ with $a = P_{ij}P_{jk}$ and $b = (1 - P_{ij})(1 - P_{jk}) = 1 - P_{ij} - P_{jk} + P_{ij}P_{jk}$. Then $P_{ik} = a/(a + b)$, that is,

$$P_{ik} = \frac{P_{ij}\,P_{jk}}{1 + 2\,P_{ij}P_{jk} - P_{ij} - P_{jk}},$$

which is eq. 5 of Burges et al. (2005). If the model is 80% sure that $d_i$ beats $d_j$ and 80% sure that $d_j$ beats $d_k$, it is $0.64/(1 + 1.28 - 1.6) = 0.9412$ sure that $d_i$ beats $d_k$: confidence grows along a chain. Two probabilities of $\tfrac{1}{2}$ combine to $\tfrac{1}{2}$, which the paper describes as complete uncertainty propagating. A confident pair and a doubtful one partly cancel: 0.9 and 0.3 give 0.7941. The paper proves more, that target probabilities given for adjacent pairs of any ordering of the documents determine consistent targets for all pairs (its §3.1); that theorem is cited here, and only the combination rule is derived.

The model cannot represent everything. No scores make $d_1$ beat $d_2$, $d_2$ beat $d_3$ and $d_3$ beat $d_1$, each with probability above $\tfrac{1}{2}$, since the three log odds would be positive and sum to $\sigma(s_1 - s_2 + s_2 - s_3 + s_3 - s_1) = 0$. Burges (2010, §2.1) points out that the training set may still contain such a cycle, from a confused judge, because RankNet needs only the set $I$ of preferences and not consistent labels. The cost then cannot reach its smallest conceivable value, and training settles for the best compromise.

The cost of a pair

Let $\bar P_{ij}$ be the target, the true probability that $d_i$ should rank above $d_j$. The cost of the pair is the cross entropy between target and model, the cost of logistic regression applied to a pair:

$$C_{ij} = -\bar P_{ij} \log P_{ij} - (1 - \bar P_{ij}) \log (1 - P_{ij}).$$

Here is the plan of the derivation: substitute the logistic model, simplify to one expression in the score difference, then read off the three cases of the labels.

Write $o = \sigma(s_i - s_j)$. Then $\log P_{ij} = -\log(1 + e^{-o})$, and $\log(1 - P_{ij}) = \log\frac{e^{-o}}{1 + e^{-o}} = -o - \log(1 + e^{-o})$. Substituting,

$$C_{ij} = \bar P_{ij} \log(1 + e^{-o}) + (1 - \bar P_{ij})\big(o + \log(1 + e^{-o})\big) = (1 - \bar P_{ij})\, o + \log(1 + e^{-o}).$$

With labels the target is known. Burges (2010, §2) writes $S_{ij} = 1$ if $d_i$ is labeled more relevant than $d_j$, $-1$ if less, and $0$ if the labels are equal, and sets $\bar P_{ij} = \tfrac{1}{2}(1 + S_{ij})$. Then $1 - \bar P_{ij} = \tfrac{1}{2}(1 - S_{ij})$ and

$$C_{ij} = \tfrac{1}{2}(1 - S_{ij})\,\sigma(s_i - s_j) + \log\big(1 + e^{-\sigma(s_i - s_j)}\big).$$

The three cases:

  • $S_{ij} = 1$: $C_{ij} = \log\big(1 + e^{-\sigma(s_i - s_j)}\big)$, the form in the course article. It is the only case needed when pairs are taken from $I$.
  • $S_{ij} = -1$: $C_{ij} = \sigma(s_i - s_j) + \log(1 + e^{-\sigma(s_i - s_j)}) = \log\big(e^{\sigma(s_i - s_j)} + 1\big) = \log\big(1 + e^{-\sigma(s_j - s_i)}\big)$. This is the first case with $i$ and $j$ exchanged, so the cost does not depend on which document of a pair is named first.
  • $S_{ij} = 0$: $C_{ij} = \tfrac{1}{2}\sigma(s_i - s_j) + \log(1 + e^{-\sigma(s_i - s_j)})$, which is symmetric in the two scores and smallest when they are equal, as the next paragraph shows. A tied pair is pulled together.

The cost is smallest where the model matches the target. Differentiate $C_{ij} = (1 - \bar P_{ij})\,o + \log(1 + e^{-o})$ with respect to $o$: the derivative is $(1 - \bar P_{ij}) - \frac{e^{-o}}{1 + e^{-o}} = (1 - \bar P_{ij}) - (1 - P_{ij}) = P_{ij} - \bar P_{ij}$. It is zero exactly when $P_{ij} = \bar P_{ij}$, that is, at $o = \log\frac{\bar P_{ij}}{1 - \bar P_{ij}}$. That zero is a minimum: differentiating again, the target term $(1 - \bar P_{ij})\,o$ is linear and drops out, and $\frac{d P_{ij}}{d o} = P_{ij}(1 - P_{ij}) > 0$, so the cost is convex in $o$ for every target $\bar P_{ij}$, and a convex function is smallest where its derivative is zero. A target of $\tfrac{3}{4}$ puts the minimum at a scaled score difference of $\log 3 = 1.0986$, and a target of $\tfrac{1}{2}$ puts it at 0. For the certain targets 0 and 1 there is no finite minimum: the cost keeps falling as the scores separate.

Burges et al. (2005, §5.2) tried training on tied pairs, with target $\tfrac{1}{2}$, on artificial data, and concluded that "for this kind of data at least, training on ties makes little difference". The rest of this article uses only the pairs of $I$.

Three properties

Take a pair of $I$, so $C_{ij} = \log(1 + e^{-\sigma(s_i - s_j)})$.

1. It is never zero, and it is $\log 2$ at equal scores. Since $e^{-\sigma(s_i - s_j)} > 0$, the cost is positive for all scores. At $s_i = s_j$ it is $\log 2 = 0.693$. A pair that is ordered correctly still costs something, more the closer the two scores are. Burges (2010, §2) puts it this way: the model "incorporates a margin", in that documents with different labels and equal scores "are still pushed away from each other". As the pair becomes badly misordered the cost approaches the straight line $\sigma(s_j - s_i)$, and as it becomes well ordered the cost approaches zero.

2. It is convex in the scores. The derivative of $C_{ij}$ with respect to $o = \sigma(s_i - s_j)$ is $P_{ij} - 1$, from the calculation above with $\bar P_{ij} = 1$. Differentiating again, $\frac{d P_{ij}}{d o} = P_{ij}(1 - P_{ij})$, which is positive. So $C_{ij}$ is a convex function of the score difference, with second derivative

$$\frac{\partial^2 C_{ij}}{\partial s_i^2} = \sigma^2\, P_{ij}(1 - P_{ij}) > 0 .$$

A convex function of a linear function of the scores is convex in the scores, and a sum of convex functions is convex, so the whole cost $C = \sum_{(i,j) \in I} C_{ij}$ is convex in $(s_1, \dots, s_n)$. For a linear model the scores are linear in $\mathbf{w}$, so $C$ is convex in $\mathbf{w}$ too: gradient descent on a linear RankNet cannot be trapped in a local minimum that is not global. For a neural network the scores are not linear in the parameters and the guarantee is lost. The second derivative is also the quantity that the Newton step of LambdaMART needs.

3. It bounds the number of misordered pairs. If a pair is misordered or tied, $s_i \le s_j$, then $e^{-\sigma(s_i - s_j)} \ge 1$ and $C_{ij} \ge \log 2$. Every other pair has $C_{ij} > 0$. Therefore

$$\#\{(i,j) \in I : s_i \le s_j\} \ \le\ \frac{1}{\log 2} \sum_{(i,j) \in I} C_{ij} .$$

RankNet minimizes a smooth upper bound on the number of pairwise errors, scaled by $\log 2$. The hinge loss of the Ranking SVM is another such bound, with the difference that the hinge is exactly zero beyond the margin and this cost never is.

Example (a cost that is never zero has no minimum on orderable data). One might expect training to stop when every pair is ordered correctly. It does not, and for orderable data it never stops by itself. Suppose a linear model has a $\mathbf{w}$ that orders every pair, $\mathbf{w}^{\mathsf{T}}(\mathbf{x}_i - \mathbf{x}_j) > 0$ for all of $I$. Then the cost at $t\mathbf{w}$ is $\sum \log(1 + e^{-\sigma t\, \mathbf{w}^{\mathsf{T}}(\mathbf{x}_i - \mathbf{x}_j)})$, which tends to 0 as $t$ grows, while by property 1 no weight vector attains 0. The cost has no minimizer, and gradient descent keeps lengthening $\mathbf{w}$. The four abstracts below show it. In practice training is stopped early on held-out queries, as this article's MQ2008 runs are, or a penalty on the weights is added, as the course article's experiment does.

The gradient of a pair

The cost depends on the model only through the scores, so the first step is its derivative with respect to a score. From the general form, with $o = \sigma(s_i - s_j)$ and $\partial o/\partial s_i = \sigma$:

$$\lambda_{ij} \equiv \frac{\partial C_{ij}}{\partial s_i} = \sigma\Big(\tfrac{1}{2}(1 - S_{ij}) - \frac{e^{-o}}{1 + e^{-o}}\Big) = \sigma\Big(\tfrac{1}{2}(1 - S_{ij}) - \frac{1}{1 + e^{\sigma(s_i - s_j)}}\Big),$$

where the last step multiplies numerator and denominator of the fraction by $e^{o}$. This is eq. 3 of Burges (2010). Since $C_{ij}$ depends on the two scores only through their difference, $\partial C_{ij}/\partial s_j = -\lambda_{ij}$. For a pair of $I$, $S_{ij} = 1$ and

$$\lambda_{ij} = \frac{-\sigma}{1 + e^{\sigma(s_i - s_j)}} = -\sigma\,(1 - P_{ij}) = -\sigma\, P_{ji},$$

the course article's formula. It has a plain reading: $\lambda_{ij}$ is $\sigma$ times the probability the model still gives to the wrong order, with a minus sign because raising $s_i$ lowers the cost. It lies between $-\sigma$ (badly misordered) and 0 (well ordered), and equals $-\sigma/2$ at equal scores.

One lambda per document

Here is the idea in one sentence: the parameters affect the cost only through the $n$ scores, so the gradient with respect to the parameters is a sum of $n$ terms, one per document, each weighted by the total push that all the pairs exert on that document's score.

The formal version. The cost of a query is $C = \sum_{(i,j) \in I} C_{ij}$. Let $\theta_k$ be any parameter of the model. By the chain rule, each pair contributes through its two scores:

$$\frac{\partial C}{\partial \theta_k} = \sum_{(i,j) \in I} \Big( \frac{\partial C_{ij}}{\partial s_i} \frac{\partial s_i}{\partial \theta_k} + \frac{\partial C_{ij}}{\partial s_j} \frac{\partial s_j}{\partial \theta_k} \Big) = \sum_{(i,j) \in I} \lambda_{ij} \Big( \frac{\partial s_i}{\partial \theta_k} - \frac{\partial s_j}{\partial \theta_k} \Big).$$

This is a sum of $2\lvert I \rvert$ terms, but it contains only $n$ different derivatives $\partial s_a/\partial \theta_k$. Collect the terms by document. The derivative $\partial s_a/\partial \theta_k$ appears with coefficient $+\lambda_{aj}$ in every pair $(a, j) \in I$, where $d_a$ is the more relevant document, and with coefficient $-\lambda_{ia}$ in every pair $(i, a) \in I$, where $d_a$ is the less relevant one. So

$$\frac{\partial C}{\partial \theta_k} = \sum_{a=1}^{n} \lambda_a\, \frac{\partial s_a}{\partial \theta_k}, \qquad \lambda_a = \sum_{j : (a, j) \in I} \lambda_{aj} \ -\ \sum_{i : (i, a) \in I} \lambda_{ia} .$$

The regrouping is exact: the two expressions are the same finite sum in a different order. Burges (2010, eq. 4) states the result and gives the smallest example: with one pair, $I = \{(1, 2)\}$, $\lambda_1 = \lambda_{12} = -\lambda_2$. The gradient descent update is

$$\theta_k \leftarrow \theta_k - \eta \sum_{a=1}^{n} \lambda_a \frac{\partial s_a}{\partial \theta_k},$$

with $\eta > 0$ the learning rate. Three facts about the $\lambda_a$ follow at once.

Each $\lambda_a$ is the derivative of the query's cost with respect to that document's score. Differentiating $C$ with respect to $s_a$ directly picks out the same pairs with the same signs, so $\lambda_a = \partial C/\partial s_a$. The factorization is the chain rule applied in two stages, parameters to scores and scores to cost, with the sum over pairs done once, at the second stage.

The sign says which way the document should move. Every $\lambda_{aj}$ is negative. A document that is the more relevant member of all its pairs has a negative $\lambda_a$; one that is the less relevant member of all its pairs has a positive $\lambda_a$. The sign of $\lambda_a = \partial C/\partial s_a$ is the direction in which a step taken in the scores themselves would move $s_a$: a negative $\lambda_a$ says the cost falls as $s_a$ rises. A step in the parameters is different, because the documents share the parameters. For a linear model the update adds $-\eta\sum_b \lambda_b \mathbf{x}_b$ to $\mathbf{w}$, which changes $s_a$ by $-\eta\lambda_a \lVert \mathbf{x}_a \rVert^2$ through the document's own term and by $-\eta\sum_{b \ne a} \lambda_b\, \mathbf{x}_b^{\mathsf{T}}\mathbf{x}_a$ through the others' terms, and the second part can outweigh the first. In step 1 of the trace below, abstract 856 has $\lambda = -0.5$ and its score still falls, from 0 to $-0.2810$. Burges (2010, §2.1) describes the $\lambda$s as "little arrows (or forces), one attached to each (sorted) url", whose direction says which way the document should move and whose length says by how much.

The forces on a query balance. Each pair $(i, j)$ adds $\lambda_{ij}$ to $\lambda_i$ and subtracts the same number from $\lambda_j$. Summing over documents, every pair's contribution cancels:

$$\sum_{a=1}^{n} \lambda_a = 0 .$$

Pairs move scores apart, never the whole list up or down, which is as it should be for a cost that depends only on score differences.

Why this is fast

The expensive operation in training is evaluating $\partial s_a/\partial \theta$, the gradient of one score with respect to all the parameters. For a neural network that is a backward pass.

  • Pair by pair. The original procedure (Burges et al., 2005, eqs. 12 to 15) takes a pair, runs the network forward on both documents, computes $\lambda_{ij}$, runs it backward for both, and updates the weights. One pass over a query costs $2\lvert I \rvert$ score gradients and $\lvert I \rvert$ updates.
  • Factored. Run the network forward once on each of the $n$ documents. Compute every $\lambda_{ij}$ from the scores, which is arithmetic on numbers already in hand, and add them into the $\lambda_a$. Then run the network backward once per document, weighted by $\lambda_a$, and make one update. One pass costs $n$ score gradients.

The ratio is $2\lvert I \rvert / n$. For query 185 the hundred candidates have labels 3, 2, 1 and 0 in numbers 4, 2, 3 and 91, so $\lvert I \rvert = 4 \times 96 + 2 \times 94 + 3 \times 91 = 845$: the pair-by-pair pass needs 1,690 score gradients where the factored pass needs 100. Over all of Cranfield there are 105,334 pairs among 22,500 candidates, 210,668 against 22,500, a factor of 9.4 before counting that the factored pass makes 225 updates and not 105,334. The number of pairs grows with the square of the list length when the labels are mixed, since $n/2$ documents of one grade and $n/2$ of another make $n^2/4$ pairs, while the number of documents is $n$. Burges (2010, §2.1) reports the effect on Microsoft's implementation: training time "dropped from close to quadratic in the number of urls per query, to close to linear".

The factored procedure is not the same algorithm as the pair-by-pair one, only a cheaper way to follow the same gradient. Pair-by-pair training updates the weights between pairs, so each pair sees slightly different weights. The factored procedure evaluates all the pairs of a query at the same weights and then moves once. Burges notes that this is mini-batch learning with the query as the batch, "but the speedup results from the way the problem factorizes, not from using mini-batch alone". The experiment below compares the two.

Two steps on four abstracts

Back to the four abstracts, with a linear model $s = w_1 \cdot \text{BM25} + w_2 \cdot \text{title BM25}$, $\sigma = 1$ and learning rate $\eta = 1$. The six pairs of $I$, more relevant abstract first, are (766, 856), (766, 390), (766, 285), (856, 390), (856, 285) and (285, 390).

Step 1, from $\mathbf{w} = (0, 0)$. All scores are 0, so every pair has $P_{ij} = \tfrac{1}{2}$, cost $\log 2$ and $\lambda_{ij} = -\tfrac{1}{2}$. The cost is $6 \log 2 = 4.159$. Each abstract collects $-\tfrac{1}{2}$ for every abstract it should beat and $+\tfrac{1}{2}$ for every abstract that should beat it:

Abstract Label Should beat Should lose to $\lambda_a$
766 3 3 0 $-1.5$
856 2 2 1 $-0.5$
285 1 1 2 $+0.5$
390 0 0 3 $+1.5$

The four sum to zero. For a linear model $\partial s_a/\partial \mathbf{w} = \mathbf{x}_a$, so the gradient is $\sum_a \lambda_a \mathbf{x}_a$:

$$-1.5\,(0.769, 0.499) - 0.5\,(1, 1) + 0.5\,(0.580, 0.794) + 1.5\,(0.764, 0.900) = (-0.2175,\ 0.4985).$$

The update is $\mathbf{w} \leftarrow (0, 0) - (-0.2175, 0.4985) = (0.2175, -0.4985)$. The first step already says what these four abstracts teach: BM25 should count for, and the title score against, because the abstract that should be last, 390, has a strong title match and the abstract that should be first, 766, a weak one.

Step 2, from $\mathbf{w} = (0.2175, -0.4985)$. The scores are now $-0.2810$ for 856, $-0.0815$ for 766, $-0.2825$ for 390 and $-0.2697$ for 285. The pairs:

Pair $(i, j)$ $s_i - s_j$ $P_{ij}$ $C_{ij}$ $\lambda_{ij}$
(766, 856) 0.1995 0.5497 0.5984 $-0.4503$
(766, 390) 0.2010 0.5501 0.5977 $-0.4499$
(766, 285) 0.1882 0.5469 0.6035 $-0.4531$
(856, 390) 0.0015 0.5004 0.6924 $-0.4996$
(856, 285) $-0.0113$ 0.4972 0.6988 $-0.5028$
(285, 390) 0.0128 0.5032 0.6868 $-0.4968$

The cost has fallen from 4.159 to 3.878. Abstract 766 is now first, and its three pairs have the smallest $\lambda$s. One pair is misordered, (856, 285), and it has the largest. Collecting by document:

Abstract As the better document As the worse document $\lambda_a$
766 $-0.4503 - 0.4499 - 0.4531$ $-1.3533$
856 $-0.4996 - 0.5028$ $+0.4503$ $-0.5522$
285 $-0.4968$ $+0.4531 + 0.5028$ $0.4591$
390 $+0.4499 + 0.4996 + 0.4968$ $1.4463$

They sum to zero again. The gradient is $\sum_a \lambda_a \mathbf{x}_a = (-0.2216, 0.4388)$ and the new weights are $(0.4391, -0.9373)$, with cost 3.647.

What happens next. After the third step all six pairs are ordered correctly, but descent does not stay there. A weight vector $(a, -b)$ with $a, b > 0$ orders all six pairs only when $1.736\,a < b < 2.039\,a$: the pair (285, 390) needs $b > 1.736\,a$ and the pair (856, 285) needs $b < 2.039\,a$, and the other four pairs hold throughout the band. Steps 3, 4 and 5 land inside this narrow band, at step 6 the ratio $b/a$ falls below it, and from step 6 to step 3,908 the pair (285, 390) is misordered again. Training does not stop at any of these points. The four abstracts can be ordered by a line, so by the example above the cost has no minimum, and it keeps falling throughout: it is 2.674 after 10 steps, 1.589 after 100, 1.317 after 1,000 and 1.195 after 2,000, by which time the weights have grown to $(19.89, -32.22)$, still with (285, 390) misordered. (While that pair stays misordered the cost cannot fall below $\log 2$, the least cost a misordered pair can have; the converse does not hold, since after step 3 every pair was ordered and the cost was 3.455.) From step 3,909 on, all six pairs are ordered again. A cost that only bounds the number of misordered pairs need not reduce that number at every step.

Example (four documents are not a training set). The trace gives the title score a negative weight. It would be wrong to conclude that a title match is evidence against relevance. Trained on all 225 Cranfield queries, the same cost gives title BM25 a weight of +2.37, the second largest of the eight, as the course article reports. These four abstracts were chosen to show, in miniature, what the course article describes for query 185: there a nonrelevant abstract with a short, matching title outranks relevant ones with long titles, and here the nonrelevant 390 has a strong title match while 766, the best of the four, has a weak one. A model fitted to four documents fits their accident.

What sigma does

The parameter $\sigma$ looks like something to tune. For the models used here it is not a separate degree of freedom.

Claim. For a linear model, the cost with parameter $\sigma$ at weights $\mathbf{w}$ equals the cost with parameter 1 at weights $\sigma\mathbf{w}$. Gradient descent with $\sigma$ and learning rate $\eta$ from $\mathbf{w}_0$ visits, after rescaling by $\sigma$, exactly the points that gradient descent with parameter 1 and learning rate $\sigma^2\eta$ visits from $\sigma\mathbf{w}_0$.

Proof. The cost depends on $\sigma$ and $\mathbf{w}$ only through $\sigma(s_i - s_j) = (\sigma\mathbf{w})^{\mathsf{T}}(\mathbf{x}_i - \mathbf{x}_j)$, which proves the first sentence: $C_\sigma(\mathbf{w}) = C_1(\sigma\mathbf{w})$. Differentiating, $\nabla C_\sigma(\mathbf{w}) = \sigma\, \nabla C_1(\sigma\mathbf{w})$. Let $\mathbf{u} = \sigma\mathbf{w}$. A step $\mathbf{w} \leftarrow \mathbf{w} - \eta\nabla C_\sigma(\mathbf{w})$ becomes, after multiplying by $\sigma$, $\mathbf{u} \leftarrow \mathbf{u} - \sigma^2\eta\, \nabla C_1(\mathbf{u})$, which is a step of the second procedure. By induction the two sequences agree at every step. $\blacksquare$

The script confirms it on the four abstracts, with the cost taken as the mean over the six pairs: 50 steps with $\sigma = 2$ and $\eta = 0.3$ from $(0.1, -0.2)$ end at $(1.1176, -1.6387)$, and 50 steps with $\sigma = 1$ and $\eta = 1.2$ from the doubled start $(0.2, -0.4)$ end at $(2.2352, -3.2774)$, exactly twice as far. The rankings are identical, since multiplying all scores by a positive number changes no order. For a model whose final layer is linear with free weights, such as the network below, the cost identity carries over, since that layer can absorb the factor: $C_\sigma(\mathbf{v}, W, \mathbf{b}) = C_1(\sigma\mathbf{v}, W, \mathbf{b})$. Under plain gradient descent the paths agree only if that last layer's learning rate is multiplied by $\sigma^2$ and the other layers' are left unchanged, because the gradients of the inner layers carry no extra factor of $\sigma$, and only from matching starts, $(\mathbf{v}_0, W_0, \mathbf{b}_0)$ with $\sigma$ against $(\sigma\mathbf{v}_0, W_0, \mathbf{b}_0)$ with parameter 1. (The network below is trained by Adam, whose steps do not scale in this way, so this statement is about plain descent, not about that experiment.) So for a linear model $\sigma$ sets the unit in which scores are measured and nothing else, and this unit takes $\sigma = 1$; Burges (2010, §2) says only that it "determines the shape of the sigmoid". It stops being harmless when something else fixes the scale of the scores, such as a penalty on the weights.

From a line to a network

Nothing in the derivation used the form of $f$. For a network with one hidden layer of $h$ units,

$$s = \mathbf{v}^{\mathsf{T}} \tanh(W\mathbf{x} + \mathbf{b}),$$

with $W$ an $h \times m$ matrix, $\mathbf{b}$ and $\mathbf{v}$ vectors of length $h$. Write $\mathbf{h}_a = \tanh(W\mathbf{x}_a + \mathbf{b})$ for the hidden activations of document $a$. The derivative of $\tanh$ is $1 - \tanh^2$, so the three gradients of a score are $\partial s_a/\partial \mathbf{v} = \mathbf{h}_a$, $\partial s_a/\partial \mathbf{b} = \mathbf{v} \odot (1 - \mathbf{h}_a^2)$ and $\partial s_a/\partial W = \big(\mathbf{v} \odot (1 - \mathbf{h}_a^2)\big)\mathbf{x}_a^{\mathsf{T}}$, where $\odot$ multiplies entry by entry. The factorization says to weight each by $\lambda_a$ and add:

$$\frac{\partial C}{\partial \mathbf{v}} = \sum_a \lambda_a \mathbf{h}_a, \qquad \frac{\partial C}{\partial \mathbf{b}} = \sum_a \lambda_a\, \mathbf{v} \odot (1 - \mathbf{h}_a^2), \qquad \frac{\partial C}{\partial W} = \sum_a \lambda_a \big(\mathbf{v} \odot (1 - \mathbf{h}_a^2)\big)\mathbf{x}_a^{\mathsf{T}} .$$

This is ordinary backpropagation with $\lambda_a$ in the place where a regression network would put its residual. The script checks these formulas against numerical derivatives on query 185. Burges et al. (2005, eqs. 12 to 15) wrote the pair-by-pair version, in which each gradient is the difference of a term from one document and a term from the other, and described it as "a straightforward modification of back-prop".

What the original paper found. Burges et al. (2005, §6) trained on data from a commercial search engine: 17,004 queries, of which 11,336 were used for training, with up to 1,000 documents each and 569 features, counts replaced by their logarithms. Labels ran from 1 (poor match) to 5 (excellent), and unlabeled documents were given 0. Training used 384,314 feature vectors and 3,464,289 pairs. The measure was nDCG at rank 15 (their Table 4, test set, with 95% confidence intervals):

Method Mean nDCG@15
PRank, quadratic features 0.327 ± 0.011
PRank, linear 0.412 ± 0.010
Large-margin PRank (OAP-BPM) 0.454 ± 0.011
RankProp 0.460 ± 0.011
RankNet, one layer 0.477 ± 0.010
RankNet, two layers, 10 hidden units 0.488 ± 0.010

Both RankNets were ahead of the other methods. The paper is careful about the gap between the two: it is "not statistically significant at the 5% standard error level", and a Wilcoxon rank test rejects equal medians only at the 16% level. Scored on its own training queries the linear net reached 0.479 and the two-layer net 0.500 (their Table 5), from which the authors conclude that the linear net was "functioning at capacity" while the two-layer net might still benefit from more data. A hundred epochs took 1 hour 7 minutes for the linear net and 5 hours 51 minutes for the two-layer net (Table 6), with pair-by-pair training.

Experiments

Cranfield

The setting is the course article's: 225 queries, BM25's top 100 candidates each, eight features rescaled within each query, labels 0 to 4 from the Cranfield grades, 5-fold cross-validation over queries, and 30 seeded assignments of queries to folds.

The factored code reproduces the course article. With that article's training settings (300 full-batch steps on the mean pair cost, a small weight penalty), this unit's factored implementation returns the same weights as the course article's script to within $10^{-12}$, including +2.37 for title BM25 and −2.01 for query likelihood, and the same table row.

Pair by pair against factored. On the first fold assignment, a linear model was trained for five passes over the training pairs in each of two ways with the same learning rate, 0.01: updating after every pair, in a seeded random order, and updating once per query from its $\lambda$s.

Training MAP nDCG@10 Score gradients evaluated
Pair by pair 0.311 0.382 4,213,360
Factored, one update per query 0.310 0.381 436,000

In this single run (one fold assignment, one seeded order of the pairs) the two rankings scored within 0.001 of each other, and the factored run evaluated 9.7 times fewer score gradients. (The count for the factored run is five passes over the 21,800 candidates of the 218 queries that have at least one pair, in four of five folds each.) For a linear model a score gradient is just the feature vector, so the saving here is in arithmetic only; for a network each one is a backward pass.

A two-layer net. The network above with 10 hidden units was trained on the same folds, by the Adam variant of gradient descent on the mean pair cost (learning rate 0.02, decay rates 0.9 and 0.999), 400 full-batch steps. The starting weights are seeded: $W$ drawn from a normal distribution with standard deviation $1/\sqrt{m}$, $\mathbf{v}$ with standard deviation $1/\sqrt{h}$, and $\mathbf{b} = \mathbf{0}$.

Ranker MAP, median of 30 (IQR) nDCG@10, median (IQR) Improved / harmed vs. BM25
BM25 alone 0.307 0.368
RankNet, linear 0.314 (0.313–0.315) 0.384 (0.383–0.384) 126 / 84
RankNet, two layers 0.315 (0.314–0.318) 0.383 (0.380–0.385) 127 / 79

IQR is the interquartile range over the 30 fold assignments, and the counts are for the first one. To four places, the network's median MAP is 0.3153 against the linear model's 0.3136, and its median nDCG@10 is 0.3826 against 0.3837, with a wider spread (its random starting weights are a second source of variation, besides the fold assignment). Its MAP was the higher of the two in 21 of the 30 fold assignments. Trained and scored on all 225 queries, with nothing held out, the linear model reaches a MAP of 0.315 and the network 0.325. In this experiment the network fitted the training queries better, and the advantage did not carry over to held-out queries. The course article found the same pattern with four losses and a linear model; together the two observations suggest that on these eight features the model class is not what limits the result, though neither experiment tests that directly.

MQ2008

LETOR 4.0's MQ2008 (Qin and Liu, 2013) has 784 queries from the TREC 2008 Million Query track, 15,211 judged documents with 46 features normalized within each query, labels 0 to 2, and five predefined folds with training, validation and test parts. Features for Ranking describes the features. The 784 queries have 80,925 pairs in all, and 220 queries have no relevant document; nDCG@10 (gain $2^y - 1$) and average precision are undefined for those, so means are over the other 564. Each model was trained on a fold's training part and stopped at the step with the best nDCG@10 on its validation part. The linear model was trained by plain full-batch gradient descent on the mean pair cost (learning rate 10, no weight penalty, up to 500 steps, validation checked every 10), which makes it deterministic; the network as on Cranfield, by Adam, up to 300 steps, from 30 seeded starting points, with validation checked every 10 steps.

Ranker nDCG@10 MAP
Best single feature (column 39) 0.689
RankNet, linear 0.703 0.665
RankNet, two layers, median of 30 seeds (IQR) 0.687 (0.683–0.689) 0.647 (0.643–0.651)

The best single feature is the column that alone ranks the test queries best; by the grouping established in Features for Ranking, column 39 is a language model score of the whole document. The linear RankNet scored 0.014 above it. Validation stopped the linear model early: in the five folds it was stopped after 100, 50, 30, 10 and 20 steps, that is, validation nDCG@10 was highest within the first 100 of the 500 steps in every fold. The two-layer network did worse than the linear model: over the 30 seeds the network's nDCG@10 ran from 0.677 to 0.692, and none of the 30 seeds reached the linear model's 0.703. This experiment does not show why. Each fold trains on 470 or 471 queries, many with few judged documents, and stops on validation parts of 105 to 122 usable queries, far less evidence than the commercial data of Burges et al. (2005); that is a possible reason, not a tested one. The other articles of the unit report their MQ2008 runs under their own training protocols (LambdaRank and LambdaMART, Listwise Losses); the protocols differ, so small differences between those pages and this one are not comparisons of the losses.

A worked case: this site's field weights

The search box of this site ranks pages with BM25F over five fields. The weights of its fields (12 for the title, 1 for the summary, 4 for the headings, 1 for the body and 0.1 for mathematics) were set by a grid search on known-item queries, each with one page that should come first. BM25F says that field weights are tuned on judged queries. Here they are learned from graded judgments with the RankNet cost.

The site's evaluation set (tools/search/eval/ in the repository) has 60 topical queries, each with a stated information need, and 1,199 judged query-page pairs on a scale of 0 to 3. Which pages were judged matters here. For each query the judged pages are the top 20 that BM25F with the hand-tuned weights returned, and nothing else (one of the 1,200 pooled pages was left unjudged): no other ranker contributed to the pool. A language model graded all of them against a written guide; for 150 of them, chosen to calibrate the judges, the site's owner and a second, full-reading pass of the model graded them as well, and the evaluation uses the mean of the grades a pair received, so 54 pairs carry a fractional grade.

That origin limits what learning from these judgments can show. Every training pair is a pair of pages that the hand-tuned BM25F already placed in a query's top 20. Weights learned from them can only learn to re-order BM25F's own candidates, and a gain measured on the same judgments says nothing about relevant pages that the hand-tuned BM25F does not put in its top 20: such pages are neither in the training pairs nor counted as relevant when a ranking is scored.

This case is worth working despite that, because the model is not linear in its parameters, so the factorization has to do real work.

The score and its gradient

For a query with terms $t$ and a page, let $x_{tf}$ be the term's frequency in field $f$ divided by that field's length normalizer, as in BM25F. The site's score is

$$s = \sum_t \mathrm{idf}_t\, \frac{T_t}{k_1 + T_t} + \text{bonus}, \qquad T_t = \sum_f w_f\, x_{tf},$$

with $k_1 = 1.2$ and a title bonus that does not depend on the weights. $T_t$ is the pseudo frequency of BM25F. The weights $w_f$ sit inside the saturation, so the score is not a linear function of them. Its derivative follows from $\frac{d}{dT}\frac{T}{k_1 + T} = \frac{k_1}{(k_1 + T)^2}$ and $\partial T_t/\partial w_f = x_{tf}$:

$$\frac{\partial s}{\partial w_f} = \sum_t \mathrm{idf}_t\, \frac{k_1}{(k_1 + T_t)^2}\, x_{tf} .$$

The weights must stay positive, so the script learns $\theta_f = \log w_f$, for which $\partial s/\partial \theta_f = w_f\, \partial s/\partial w_f$. Everything else is the general recipe: compute the scores of a query's judged pages, form the $\lambda_a$ from the pairs with different grades, and descend $\sum_a \lambda_a\, \partial s_a/\partial \theta_f$. The script checks this gradient against a numerical derivative.

One remark before the numbers. Multiplying all five weights by a constant $c$ multiplies every $T_t$ by $c$, and $\frac{cT}{k_1 + cT} = \frac{T}{k_1/c + T}$. Scaling the weights together is the same as dividing $k_1$ by $c$. So learning five weights with $k_1$ fixed also learns $k_1$, and only the ratios of the weights say how the fields compare.

Setup

The index was built from the 679 pages that existed at a fixed earlier commit of the site's repository (643484d), so that pages added since do not move the numbers. The 60 queries are split, by the evaluation set's own seeded assignment, into 29 for tuning and 31 held out. Training used the 3,668 pairs of judged pages with different grades among the 29 tuning queries, 2,000 full-batch steps of plain gradient descent on the mean pair cost, with step size 0.5 on the log-weights $\theta_f$. It was started from the hand-tuned weights, from all weights equal to 1, and from 30 seeded random points, at which each $\theta_f$ is drawn from a standard normal distribution (seeds 0 to 29), so that each starting weight is $e^{\theta_f}$, between about 0.1 and 10 for most draws.

Results

The weights, before and after:

Weights title summary headings body math
Hand-tuned 12 1 4 1 0.1
Learned, started from the hand-tuned weights 13.58 1.63 0.91 0.31 0.10
Learned, started from all ones 1.08 1.48 0.55 0.28 1.00
Learned, 30 random starts: median (IQR) 1.06 (0.55–1.59) 1.49 (1.48–1.52) 0.52 (0.40–0.68) 0.28 (0.28–0.29) 1.53 (0.72–3.13)

How well each set fits the judgments, on the judged pages of each query:

Weights Mean pair cost, tuning queries Misordered pairs, tuning Misordered pairs, held nDCG@10, tuning nDCG@10, held
Hand-tuned 0.510 24.8% 29.2% 0.743 0.777
Learned, from the hand-tuned weights 0.483 23.1% 27.4% 0.799 0.803
Learned, from all ones 0.483 22.5% 27.6% 0.808 0.802

Over the 30 random starts the held nDCG@10 has median 0.800 (0.798–0.802), and every start ends above the hand-tuned 0.777.

The cost is the same from every start, and the weights are not. All 32 runs end at a mean pair cost of 0.483, to three decimals. Two weights are pinned by the data: the summary's and the body's hardly vary between starts. The other three are not, and for one of them the reason is exact. No judged page contains a query term in its math field, so every $x$ of that field is 0, the derivative of every score with respect to the math weight is 0, and the math weight never leaves its starting value: 0.10 from the hand-tuned start, 1.00 from all ones, and a different value from each random start. The title weight ends near 1 from random starts and at 13.58 when started at 12, with the same cost. For the title the data suggest a reason, though the run does not prove it, and for the headings this article offers none. A query term occurs in the title in 34% of the judged pages, and at the hand-tuned weights such a term has $T_t/(k_1 + T_t) = 0.974$ (IQR 0.958–0.983) at the median: close to its ceiling, where, as Problem 4 below computes, the derivative is small. The site's title bonus and its rule for exact title matches play no part here: the title bonus or the exact-title rule applies to 1 of the 1,199 judged pages. What the judgments do determine is a ratio: the summary should count about 5.3 times as much as the body, where the hand-tuned weights count them equally. This is the course article's warning about reading weights, in a model that is not even linear: a learned weight is meaningful only as far as the cost depends on it.

The fit improves, modestly, and not significantly. On the tuning queries the share of misordered pairs falls from 24.8% to 22.5%. On the held queries nDCG@10 over the judged pages rises from 0.777 to about 0.80. The learned weights (from all ones) do better than the hand-tuned ones on 19 of the 31 held queries and worse on 12, and a paired randomization test on those 31 differences gives $p = 0.18$. Ranking the whole index and not only the judged pages, the held nDCG@10 goes from 0.771 to 0.790, with 0.789 (0.787–0.791) over the random starts and $p = 0.30$. (Over all 60 queries the hand-tuned weights score 0.753, with the search's correction of misspelled queries switched off. The weights learned from the hand-tuned start score 0.792 on the held queries, with 0.958 of their top ten judged.) That comparison is tilted against the learned weights: the share of the top ten that has a judgment falls from 0.984 to 0.942, because new weights bring up pages that were never pooled, and an unjudged page counts as not relevant.

What the result does not show. Four cautions keep this from being a recommendation to change the site's weights. There are 29 training queries. The differences on held queries are within what chance produces. Every judgment comes from the hand-tuned ranker's own top 20, so the learned weights were rewarded only for re-ordering those pages, and nothing here measures whether they find relevant pages that the hand-tuned weights miss. And the evaluation set's own documentation warns that its queries were written by a language model from the pages' summaries, and that most judgments were made from the summary, the headings and the sections bearing on the need. Both would favor the summary field, which is exactly the weight the learning raised. The same weights, applied to the set's 200 known-item queries, raise the mean reciprocal rank from 0.942 to 0.975 and success at rank 1 from 0.905 to 0.960, and that set carries the same warning even more plainly. The learned weights may describe how the test was written as much as what readers want. What the case does show is the method: a pairwise cost, a per-document $\lambda$ and the derivative of a scoring function are enough to fit the parameters of a classical ranking formula to graded judgments, and the starts that disagree show which parameters the judgments determine.

What is proved, what is cited, what the experiments show

Proved on this page. The combination rule for pair probabilities. The closed form of the pair cost for any target and its minimum where model and target agree. That the cost of a pair of $I$ is positive, convex in the scores with second derivative $\sigma^2 P_{ij}(1 - P_{ij})$, and at least $\log 2$ for a misordered pair, so that the total cost divided by $\log 2$ bounds the number of misordered pairs. That the cost has no minimizer when a linear model can order every pair. The gradient $\lambda_{ij}$, the factorization $\partial C/\partial\theta = \sum_a \lambda_a\, \partial s_a/\partial\theta$, that $\lambda_a = \partial C/\partial s_a$ and that the $\lambda_a$ of a query sum to zero. That $\sigma$ can be absorbed into the weights of a linear model. The gradient of the BM25F score with respect to its field weights.

Cited. The consistency theorem for target probabilities and all experimental results of Burges et al. (2005); the report in Burges (2010) that factoring took training time from near quadratic to near linear in the list length.

Shown by the experiments. On Cranfield, in one run, pair-by-pair and factored training gave rankings within 0.001 of each other at very different cost in score gradients. On Cranfield a two-layer net did not improve on a linear model on held-out queries, and on MQ2008 it did worse. On this site's judgments, which cover only the hand-tuned BM25F's own top 20 for each query, learned field weights fit the held-out judgments somewhat better than the hand-tuned ones, by a margin that chance could produce, and only two of the five weights were determined by the data. These are observations on small collections with the features and settings stated.

Worked problems

The problems are posed on small exact cases and on this article's data; the unit has no course assignments. The script recomputes each answer.

Problem 1 (lambdas by hand). Three documents of a query have labels $y = (2, 1, 0)$ and current scores $s = (0.5, 1.5, 0)$. With $\sigma = 1$, compute the cost of each pair, the three $\lambda_a$, and say which way each score will move.

Solution. The costs are 1.3133, 0.4741 and 0.2014, and $\lambda = (-1.1086,\ 0.5486,\ 0.5600)$. The set $I$ is $\{(1, 2), (1, 3), (2, 3)\}$.

Pair $s_i - s_j$ $C_{ij} = \log(1 + e^{-(s_i - s_j)})$ $\lambda_{ij} = -1/(1 + e^{s_i - s_j})$
(1, 2) $-1$ 1.3133 $-0.7311$
(1, 3) 0.5 0.4741 $-0.3775$
(2, 3) 1.5 0.2014 $-0.1824$

Document 1 is the better member of two pairs: $\lambda_1 = -0.7311 - 0.3775 = -1.1086$. Document 2 is the worse member of (1, 2) and the better of (2, 3): $\lambda_2 = +0.7311 - 0.1824 = 0.5486$ (from unrounded values). Document 3 is the worse member of two pairs: $\lambda_3 = 0.3775 + 0.1824 = 0.5600$. Their sum is zero. Descent raises $s_1$ and lowers $s_2$ and $s_3$. The misordered pair (1, 2) supplies most of the force on both of its documents. Document 3 is already last, yet it is pushed down as hard as document 2, because the cost of a correctly ordered pair is not zero. The total cost is 1.9888, and $1.9888/\log 2 = 2.87$ bounds the one misordered pair.

Problem 2 (counting pairs). A query has 100 candidates: 5 with label 2, 15 with label 1 and 80 with label 0. Find $\lvert I \rvert$ and the number of score gradients one pass costs pair by pair and factored. Then do the same for 50 candidates of label 1 and 50 of label 0.

Solution. The first query has $\lvert I \rvert = 5 \times 95 + 15 \times 80 = 475 + 1{,}200 = 1{,}675$ pairs: each label-2 document is paired with the 95 documents below it, and each label-1 document with the 80 below it. A pair-by-pair pass costs $2 \times 1{,}675 = 3{,}350$ score gradients and a factored pass 100, a ratio of 33.5. The second query has $50 \times 50 = 2{,}500$ pairs, the most that 100 documents on two labels can have, and the ratio is $5{,}000/100 = 50 = n/2$.

Problem 3 (a tied pair). Two documents have the same label, and scores with $s_i - s_j = 1$. With $\sigma = 1$, compute the cost of the pair under the target $\bar P_{ij} = \tfrac{1}{2}$, the cost if the scores were equal, and $\lambda_{ij}$.

Solution. The cost is 0.8133, against 0.6931 at equal scores, and $\lambda_{ij} = 0.2311$. With $S_{ij} = 0$, $C_{ij} = \tfrac{1}{2}(s_i - s_j) + \log(1 + e^{-(s_i - s_j)}) = 0.5 + \log(1 + e^{-1}) = 0.5 + 0.3133 = 0.8133$. At equal scores it is $\log 2 = 0.6931$, the minimum. The gradient is $\lambda_{ij} = \tfrac{1}{2} - \frac{1}{1 + e^{1}} = 0.5 - 0.2689 = 0.2311$, positive, so descent lowers $s_i$ and raises $s_j$: the tied pair is pulled together.

Problem 4 (a BM25F gradient). A query has one term with idf 2. A page has $x = 1$ in the title field and $x = 3$ in the body, and nothing in the other fields. With title weight 12, body weight 1 and $k_1 = 1.2$, compute the term's score and its derivatives with respect to the two weights. Which weight would descent change more if this page had $\lambda_a = -1$, first for descent on the weights themselves, then for descent on the log-weights $\theta_f = \log w_f$ that the worked case uses?

Solution. The score is 1.8519, and the derivatives are 0.0091 for the title weight and 0.0274 for the body weight. The pseudo frequency is $T = 12 \times 1 + 1 \times 3 = 15$, so the score is $2 \times 15/16.2 = 1.8519$, close to its ceiling of 2. The common factor of the derivatives is $\mathrm{idf} \cdot k_1/(k_1 + T)^2 = 2 \times 1.2/16.2^2 = 0.009145$. Multiplying by $x$ gives $0.0091$ for the title and $0.0274$ for the body. With $\lambda_a = -1$, descent on the weights adds $\eta \times 0.0091$ to the title weight and $\eta \times 0.0274$ to the body weight: the body moves three times as much, because the page has three times the normalized frequency there. On the log-weights the answer reverses. Since $\partial s/\partial\theta_f = w_f\,\partial s/\partial w_f$, the derivatives become $12 \times 0.009145 = 0.1097$ for the title and $1 \times 0.0274 = 0.0274$ for the body: descent moves the title's log-weight four times as much as the body's, and since the title weight is twelve times larger, it changes by more in absolute terms too (to first order, $w_f$ changes by $w_f$ times the change in $\theta_f$: $\eta \times 1.317$ for the title against $\eta \times 0.0274$ for the body). Both derivatives are small because the term is nearly saturated; at $T = 1$ the common factor would be $2.4/2.2^2 = 0.496$, fifty-four times larger. A term that is already near its ceiling tells the weights almost nothing.

What we have learned

RankNet models the probability that one document should rank above another as a logistic function of their score difference and minimizes the cross entropy over the pairs with different labels. The cost of a pair is positive, convex in the scores, and at least $\log 2$ when the pair is misordered. Its gradient with respect to a score is $-\sigma$ times the probability still given to the wrong order. Summing those gradients over the pairs a document belongs to gives one $\lambda$ per document, the gradient of the whole cost is $\sum_a \lambda_a\, \partial s_a/\partial \theta$, and training costs one score gradient per document where it used to cost two per pair. On the four abstracts, the $\lambda$s of the first step were $-1.5$, $-0.5$, $0.5$ and $1.5$, and after three steps all six pairs were in order, though later steps, still lowering the cost, put one pair out of order again for a long stretch.

Every pair counts the same in this cost, wherever its documents stand in the list. The measures a search engine is judged by count the top of the list far more. LambdaRank and LambdaMART keep the $\lambda$s and change their sizes.

References

  • Burges, C. J. C. (2010). From RankNet to LambdaRank to LambdaMART: An overview. Microsoft Research Technical Report MSR-TR-2010-82. record · 4 pages
  • Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and Hullender, G. (2005). Learning to rank using gradient descent. In Proceedings of ICML 2005, 89–96. record · 6 pages
  • Qin, T., and Liu, T.-Y. (2013). Introducing LETOR 4.0 datasets. arXiv:1306.2597. record · 6 pages