For Cranfield query 185, experimental studies on panel flutter, BM25 returns six abstracts at the top whose gains, in order, are 2, 3, 3, 0, 3, 2. The list is good but not ideal: a nonrelevant abstract sits fourth, and the first abstract is less relevant than the next two. RankNet sees eleven pairs of abstracts with different gains and pushes on each of them with the same force when the scores are equal. A reader of the list would not weigh them equally: a nonrelevant abstract at rank 4 costs more than one at rank 6. How can training be made to care about the same things the evaluation measure does, when the measure itself has no usable gradient?
LambdaRank (Burges, Ragno and Le, 2006) answers by multiplying each pair's RankNet gradient by the amount the measure would change if the two documents swapped ranks. LambdaMART (Wu, Burges, Svore and Gao, 2010) uses those gradients to grow an ensemble of regression trees by gradient boosting. The overview article Learning to Rank states both in a paragraph each. This article derives them.
Here is the route. First we derive the change in nDCG caused by a swap and apply it to the six abstracts. Then we write LambdaRank's gradient and ask what cost, if any, it is the gradient of. Next we derive the Newton step that gradient boosting takes in each leaf of a tree, apply it to the LambdaRank cost to get LambdaMART, and find which approximation the published step makes. We then compute one boosting round by hand, run the method on Cranfield and on a LETOR dataset, and finish with the LambdaLoss account of what LambdaRank optimizes. The article assumes RankNet, which is the home of the pairwise cost and of the factorization into one $\lambda$ per document, the measure nDCG, and gradient boosting as the library's Boosting article derives it. The numbers are computed by tools/experiments/ltr/lambdarank-and-lambdamart.py.
What RankNet's gradient ignores
Recall the notation of RankNet. A query has candidates $d_1, \dots, d_n$ with gains $g_i$ and model scores $s_i$. The set $I$ holds the pairs $(i, j)$ with $g_i > g_j$, the more relevant document first. Each pair has the cost $C_{ij} = \log\big(1 + e^{-\sigma(s_i - s_j)}\big)$, with $\sigma > 0$ the steepness of the sigmoid, and
$$\lambda_{ij} = \frac{\partial C_{ij}}{\partial s_i} = \frac{-\sigma}{1 + e^{\sigma(s_i - s_j)}}, \qquad \lambda_i = \sum_{j : (i, j) \in I} \lambda_{ij} - \sum_{j : (j, i) \in I} \lambda_{ji} = \frac{\partial C}{\partial s_i},$$
where $C = \sum_{(i,j) \in I} C_{ij}$. A negative $\lambda_i$ means that lowering the cost raises the score of $d_i$. It helps to give the recurring factor a name:
$$\rho_{ij} = \frac{1}{1 + e^{\sigma(s_i - s_j)}}, \qquad \lambda_{ij} = -\sigma\,\rho_{ij}.$$
$\rho_{ij}$ is the model's probability that the pair is in the wrong order. It is $1/2$ when the scores are equal and falls toward 0 as $s_i$ pulls ahead.
The six abstracts are the running example. They are BM25's first six candidates for query 185, with the gains of the overview's experiment (5 minus the Cranfield grade, 0 for an unjudged abstract):
| Rank $r_i$ | Abstract | Gain $g_i$ | Discount $1/\log_2(1 + r_i)$ |
|---|---|---|---|
| 1 | 856 | 2 | 1.0000 |
| 2 | 857 | 3 | 0.6309 |
| 3 | 766 | 3 | 0.5000 |
| 4 | 390 | 0 | 0.4307 |
| 5 | 858 | 3 | 0.3869 |
| 6 | 1008 | 2 | 0.3562 |
For the hand computations the six are treated as the whole candidate list, with every score equal to 0 and ties in score broken by BM25's order, which is how a model that starts from nothing sees them. Then every $\rho_{ij}$ is $1/2$ and every pair contributes $\lambda_{ij} = -1/2$ with $\sigma = 1$. Abstract 390 is the less relevant member of five pairs and receives $\lambda = 5 \times \tfrac12 = 2.5$. Each abstract of gain 3 is the more relevant member of three pairs and receives $-1.5$. Each abstract of gain 2 beats 390 and loses to three others, for $-\tfrac12 + \tfrac32 = 1.0$. RankNet's forces are $(1.0, -1.5, -1.5, 2.5, -1.5, 1.0)$: they depend on the gains alone. Abstract 857 at rank 2 and abstract 858 at rank 5 are pushed up equally hard, although exchanges near the top of the list change nDCG far more than exchanges lower down.
The change in nDCG when two documents swap
The quantity LambdaRank needs is the change in the measure when two documents exchange ranks and every other document stays where it is. For nDCG it has a closed form.
With a cutoff $k$, write the discount of rank $r$ as $D(r) = 1/\log_2(1 + r)$ for $r \le k$ and $D(r) = 0$ for $r > k$. Then
$$\mathrm{nDCG}@k = \frac{1}{\mathrm{maxDCG}@k} \sum_{i=1}^{n} g_i\, D(r_i),$$
where $\mathrm{maxDCG}@k$ is the same sum for the ideal order, a constant for the query. Exchange the ranks of $d_i$ and $d_j$. Only two terms of the sum change. Before the swap they are $g_i D(r_i) + g_j D(r_j)$, and after it they are $g_i D(r_j) + g_j D(r_i)$. The difference is
$$g_i D(r_j) + g_j D(r_i) - g_i D(r_i) - g_j D(r_j) = (g_i - g_j)\big(D(r_j) - D(r_i)\big),$$
so
$$\big|\Delta \mathrm{nDCG}_{ij}\big| = \frac{|g_i - g_j|\; \big|D(r_i) - D(r_j)\big|}{\mathrm{maxDCG}@k}.$$
Three things can be read from the formula. The change is zero when the two gains are equal, and such pairs are not in $I$ anyway. It is zero when both documents lie beyond the cutoff, so a truncated measure gives no weight to pairs entirely below rank $k$. And it is large when the gains differ much and when one of the ranks is near the top, where the discount is steep: ranks 1 and 2 differ in discount by 0.3691, ranks 5 and 6 by 0.0306. The script confirms the formula against recomputing nDCG after every swap, on the six abstracts and on 2,000 seeded random lists with cutoffs.
For the six abstracts, with a cutoff of 10 that does not bind:
$$\mathrm{DCG} = 2(1.0000) + 3(0.6309) + 3(0.5000) + 0 + 3(0.3869) + 2(0.3562) = 7.2658.$$
The ideal order 3, 3, 3, 2, 2, 0 has $\mathrm{maxDCG} = 8.0278$, so the list's nDCG is $7.2658/8.0278 = 0.9051$. The eleven pairs of $I$ and their swap values:
| Pair $(i, j)$, more relevant first | Gains | Ranks | $\lvert\Delta \mathrm{nDCG}_{ij}\rvert$ |
|---|---|---|---|
| (856, 390) | 2, 0 | 1, 4 | 0.1418 |
| (857, 856) | 3, 2 | 2, 1 | 0.0460 |
| (857, 390) | 3, 0 | 2, 4 | 0.0748 |
| (857, 1008) | 3, 2 | 2, 6 | 0.0342 |
| (766, 856) | 3, 2 | 3, 1 | 0.0623 |
| (766, 390) | 3, 0 | 3, 4 | 0.0259 |
| (766, 1008) | 3, 2 | 3, 6 | 0.0179 |
| (858, 856) | 3, 2 | 5, 1 | 0.0764 |
| (858, 390) | 3, 0 | 5, 4 | 0.0164 |
| (858, 1008) | 3, 2 | 5, 6 | 0.0038 |
| (1008, 390) | 2, 0 | 6, 4 | 0.0186 |
For the first row, $|2 - 0| \times |1.0000 - 0.4307| / 8.0278 = 0.1418$. The eleven values add up to 0.5181. The largest belongs to a pair that is already in the right order, 856 above 390: exchanging them would put a nonrelevant abstract first. The smallest belongs to the pair (858, 1008) at ranks 5 and 6, where a swap changes little. The pair (858, 390) is in the wrong order, a relevant abstract below a nonrelevant one, and its value is only 0.0164, because ranks 4 and 5 have nearly the same discount. RankNet gave all eleven the same weight.
LambdaRank's gradient
LambdaRank multiplies each pair's RankNet gradient by its swap value:
$$\lambda_{ij} = \frac{-\sigma}{1 + e^{\sigma(s_i - s_j)}}\;\big|\Delta \mathrm{nDCG}_{ij}\big| = -\sigma\,\rho_{ij}\,\big|\Delta \mathrm{nDCG}_{ij}\big|, \qquad (i, j) \in I,$$
and accumulates $\lambda_i$ from the pairs exactly as RankNet does. The ranks $r_i$ in the swap values are the ranks under the current scores, so the weights are recomputed whenever the scores change.
This is the form of Burges (2010, §4.1), and its sign is this unit's: a negative $\lambda_i$ raises $d_i$. The original paper wrote the same quantity with $\sigma = 1$, the gain $2^{l_i}$ for a label $l_i$, and the opposite sign, so that the more relevant document "gets the positive increment" (Burges, Ragno and Le, 2006, §6.2, eq. 9). That paper did not derive the function. It describes trying ten candidate functions for the force on a document, among them step functions and spring models, and using for all its experiments the one that did best on validation data: the RankNet cost scaled by the nDCG gained by swapping the pair (§6.2). Its argument for specifying forces at all is that the measures of retrieval depend on the scores only through the sorted order, so their derivatives are zero or undefined, while a force can be written down after the sort.
On the six abstracts with all scores 0, each pair contributes $-\tfrac12 |\Delta \mathrm{nDCG}_{ij}|$ to its first member and the opposite to its second. For abstract 390, the less relevant member of five pairs:
$$\lambda_{390} = \tfrac12 (0.1418 + 0.0748 + 0.0259 + 0.0164 + 0.0186) = 0.1388.$$
All six, beside RankNet's:
| Abstract | Rank | Gain | RankNet $\lambda_i$ | LambdaRank $\lambda_i$ |
|---|---|---|---|---|
| 856 | 1 | 2 | 1.0 | 0.0214 |
| 857 | 2 | 3 | −1.5 | −0.0775 |
| 766 | 3 | 3 | −1.5 | −0.0531 |
| 390 | 4 | 0 | 2.5 | 0.1388 |
| 858 | 5 | 3 | −1.5 | −0.0483 |
| 1008 | 6 | 2 | 1.0 | 0.0187 |
In both columns the six values sum to zero, because every pair gives equal and opposite amounts to its two members. The pattern differs. Under RankNet the three abstracts of gain 3 are pushed equally. Under LambdaRank the push falls with rank, from 0.0775 for the abstract at rank 2 to 0.0483 for the one at rank 5. Most of 857's push comes from its pairs with 390 and 1008 (0.0748 and 0.0342 in the table). Abstract 858, at rank 5, sits between those two documents at ranks 4 and 6, whose discounts differ from its own by only 0.0438 and 0.0306, so the same pairs are worth only 0.0164 and 0.0038 to it. Abstract 856 is pushed down only weakly, 0.0214 against 390's 0.1388, a ratio of about 1 to 6.5 where RankNet's was 1 to 2.5. Its large pair with 390 pulls it up, and nearly cancels the three pairs that pull it down.
Example (a correctly ordered pair still pushes). It is tempting to think that LambdaRank acts only on misordered pairs, since only they lower nDCG. It does not. The pair (856, 390) is correctly ordered and carries the largest weight in the table. The factor $\rho_{ij}$ is $1/2$ at equal scores and stays positive however far apart the scores are. The weight $|\Delta \mathrm{nDCG}_{ij}|$ measures what a swap would change, in either direction, so a correctly ordered pair near the top is protected by a strong force until the scores are well separated.
Is there a cost?
A gradient that was written down instead of derived may not be the gradient of anything. Burges (2010, §4.3) puts the question in general: given functions $f_1, \dots, f_n$ of $n$ variables, a function $F$ with $\partial F / \partial x_i = f_i$ exists exactly when $\partial f_i / \partial x_j = \partial f_j / \partial x_i$ for all $i$ and $j$, on a suitable domain (the Poincaré lemma). He observes that for any particular sorting of the documents a cost is easy to write down, the RankNet cost with each pair multiplied by its swap value, but that the general expression depends on the model's parameters in a complicated way, because the swap values are computed after the sort.
The first half of that observation can be made exact. Fix the ranks, and so the weights $|\Delta \mathrm{nDCG}_{ij}|$, at their current values, and define
$$C = \sum_{(i, j) \in I} \big|\Delta \mathrm{nDCG}_{ij}\big|\, \log\big(1 + e^{-\sigma(s_i - s_j)}\big).$$
Each term is a constant times a RankNet pair cost, so $\partial C/\partial s_i$ is the sum of the constants times RankNet's pair gradients, which is LambdaRank's $\lambda_i$. Within any region of score space where the order of the documents does not change, the $\lambda$s are the gradient of this $C$. When a step changes the order, the weights change and $C$ is replaced by another function. On the six abstracts at equal scores, $C = \log 2 \times 0.5181 = 0.3591$.
What this does not say is that descending the $\lambda$s increases nDCG. That claim is empirical. Burges (2010, §4.2) describes the evidence: with the trained weights of a model, vary one weight at a time and observe that mean nDCG over the training queries peaks at the learned value, then test random directions in weight space. His calculation is that 459 random directions, with nDCG falling along every one, give 99 percent confidence that fewer than 1 percent of directions lead upward. He cites Donmez, Svore and Burges (2009) and an earlier technical report for the experiments, and adds that replacing the nDCG swap value by that of another measure adapts the method to that measure. The last section returns to what can be proved.
Gradient boosting with a Newton step in each leaf
LambdaRank was first used to train neural networks. LambdaMART trains a different model on the same gradients: a sum of regression trees, built by gradient boosting. The library's Boosting article derives gradient boosting and works it by hand for squared error. What it leaves in general form is the value each leaf adds, step 4 of its algorithm: in each leaf, choose the constant that minimizes the loss of the documents in the leaf. For squared error that constant is the mean residual. For other losses it has no closed form, and the standard answer is one step of Newton's method. The family is called MART, for multiple additive regression trees (Wu et al., 2010; Burges, 2010, §5).
Here is the idea in one sentence: approximate the loss in the leaf by a parabola in the leaf's value, and jump to the bottom of the parabola.
The formal version. Let the model so far be $F$, and let a leaf hold the training examples of a set $R$. Adding a constant $\gamma$ to the model's output on the leaf changes the training loss, as a function of $\gamma$ alone, to
$$h(\gamma) = \sum_{i \in R} L\big(y_i, F(x_i) + \gamma\big) + \text{terms that do not depend on } \gamma.$$
Expand $h$ to second order around $\gamma = 0$:
$$h(\gamma) \approx h(0) + h'(0)\,\gamma + \tfrac12 h''(0)\,\gamma^2.$$
If $h''(0) > 0$ the right side is a parabola opening upward, and setting its derivative $h'(0) + h''(0)\gamma$ to zero gives its minimum,
$$\gamma = -\frac{h'(0)}{h''(0)} = -\frac{\sum_{i \in R} G_i}{\sum_{i \in R} H_i}, \qquad G_i = \frac{\partial L(y_i, F)}{\partial F}\bigg|_{F = F(x_i)}, \quad H_i = \frac{\partial^2 L(y_i, F)}{\partial F^2}\bigg|_{F = F(x_i)}.$$
The second form holds when the loss is a sum of one term per example, each depending on that example's score only: then $h'$ and $h''$ are sums of the examples' first and second derivatives. The step is exact when the loss is quadratic. For squared error $L = \tfrac12 (y - F)^2$, $G_i = -(y_i - F(x_i))$ and $H_i = 1$, so $\gamma$ is the mean residual of the leaf, as in Boosting. For other losses it is one step toward the minimum, not the minimum.
Check: two-class classification. Burges (2010, §6) works the case of labels $y_i = \pm 1$ and the loss $\log(1 + e^{-2\sigma y F})$, and arrives at the leaf value
$$\gamma = \frac{\sum_{i \in R} \bar{y}_i}{\sum_{i \in R} |\bar{y}_i|\,(2\sigma - |\bar{y}_i|)}, \qquad \bar{y}_i = \frac{2 \sigma y_i}{1 + e^{2 \sigma y_i F(x_i)}},$$
where $\bar y_i = -G_i$ is the negative gradient. He notes that it corresponds to Algorithm 5 of Friedman (2001), the paper that introduced gradient boosting. The script evaluates this formula on 40 seeded examples for three values of $\sigma$ and confirms that it equals $-h'(0)/h''(0)$ computed by finite differences, and that the step lowers the loss.
The tree itself is always fitted by least squares to the negative gradients $-G_i$, whatever the loss (Burges, 2010, §5). The loss enters twice: through the targets the tree is fitted to, and through the leaf values.
LambdaMART
LambdaMART is this recipe with LambdaRank's quantities in the two places the loss enters. The negative gradient of document $i$ is $-\lambda_i$. For the leaf values we need second derivatives, and so a cost to differentiate twice: the cost $C$ of the previous section, with the ranks held fixed.
The second derivative. Take one pair $(i, j) \in I$ with weight $z_{ij} = |\Delta \mathrm{nDCG}_{ij}|$ and cost $z_{ij} \log(1 + e^{-\sigma(s_i - s_j)})$. Its first derivative in $s_i$ is $-\sigma z_{ij} \rho_{ij}$. Since $\rho_{ij} = 1/(1 + e^{\sigma(s_i - s_j)})$,
$$\frac{\partial \rho_{ij}}{\partial s_i} = \frac{-\sigma\, e^{\sigma(s_i - s_j)}}{\big(1 + e^{\sigma(s_i - s_j)}\big)^2} = -\sigma\,\rho_{ij}(1 - \rho_{ij}),$$
using $1 - \rho_{ij} = e^{\sigma(s_i - s_j)}/(1 + e^{\sigma(s_i - s_j)})$. So the pair's second derivative in $s_i$ is $-\sigma z_{ij} \cdot \big(-\sigma \rho_{ij}(1 - \rho_{ij})\big) = \sigma^2 z_{ij}\, \rho_{ij}(1 - \rho_{ij})$. The pair cost depends on the scores only through $s_i - s_j$, so differentiating twice in $s_j$ gives the same positive value, and differentiating once in each gives its negative. Adding over the pairs that contain document $i$, in either position,
$$w_i = \frac{\partial^2 C}{\partial s_i^2} = \sum_{\text{pairs containing } i} \sigma^2\, z_{ij}\, \rho_{ij}\,(1 - \rho_{ij}).$$
Unlike $\lambda_i$, this sum has no minus signs: every pair adds curvature to both its members. Burges (2010, §7) gives the same pair term, $\sigma^2 z_{ij}\rho_{ij}(1 - \rho_{ij})$, but writes the sum over pairs with the signed notation he defines just above it for $\lambda_i$, in which pairs where $d_i$ is the less relevant member are subtracted; as the derivation here shows, the second derivative needs the plain sum.
The leaf value. Substituting $\lambda_i$ for $G_i$ and $w_i$ for $H_i$:
$$\gamma = -\frac{\sum_{i \in R} \lambda_i}{\sum_{i \in R} w_i}.$$
A leaf whose documents should rise has a negative sum of $\lambda$s and gets a positive value. Wu and colleagues (2010, Algorithm 1) write the value as $\sum \lambda_i / \sum w_i$ with the convention that a positive $\lambda$ is a push toward the top; with this article's sign it is the step above. Burges (2010, §7) writes the same ratio, $\sum \partial C/\partial s_i \big/ \sum \partial^2 C/\partial s_i^2$, but keeps the sign convention of his §4, in which $\lambda$ is negative for a document that should rise, and calls the pairwise cost $C$ a utility to be maximized. Since that $C$ falls as $s_i - s_j$ grows, his formula read literally points the other way; it is the step above only under Wu and colleagues' convention.
The algorithm. With $N$ trees of $L$ leaves each and a learning rate $\eta$, in the form of Burges (2010, §7):
- Set every training document's score to 0, or to the score of an existing model.
- For each query, sort its documents by score and compute $\lambda_i$ and $w_i$ for every document.
- Fit a regression tree with $L$ leaves to the targets $-\lambda_i$ by least squares, over the documents of all queries together.
- Give each leaf the value $\gamma = -\sum \lambda_i / \sum w_i$ over the documents it holds.
- Add $\eta\,\gamma$ to the score of every document, according to the leaf it falls in. Return to step 2 until $N$ trees are built.
The pairs are formed within queries, but the tree sees one pooled set of documents: a split on a feature applies to every query at once. Wu and colleagues named the algorithm LambdaSMART, the S for a submodel used as the starting point in step 1, and LambdaMART when there is none; the technical report of Burges (2010) uses LambdaMART throughout, as has the literature since. Wu and colleagues suggest 500 trees of 15 leaves with a learning rate of 0.1 as usually good for training sets of a few thousand queries or more, and smaller trees for smaller data.
What the leaf step approximates
The formula $\gamma = -\sum \lambda_i/\sum w_i$ treats the cost as if it were a sum of separate terms, one per document. It is not: each term belongs to a pair. The exact Newton step for a leaf can be worked out, and comparing the two shows what the published step leaves out.
Let $h(\gamma)$ be the cost $C$ after $\gamma$ is added to the score of every document in the leaf $R$, with the weights held fixed. Take the pairs of $I$ one at a time.
- Both documents outside the leaf. The pair's cost does not change.
- Both inside. Both scores rise by $\gamma$, the difference $s_i - s_j$ is unchanged, and so is the pair's cost.
- $i$ inside, $j$ outside. The difference becomes $s_i - s_j + \gamma$. The pair contributes $-\sigma z_{ij}\rho_{ij} = \lambda_{ij}$ to $h'(0)$ and $\sigma^2 z_{ij}\rho_{ij}(1 - \rho_{ij})$ to $h''(0)$.
- $j$ inside, $i$ outside. The difference becomes $s_i - s_j - \gamma$. The pair contributes $-\lambda_{ij}$ to $h'(0)$ and the same positive amount to $h''(0)$.
So $h'(0)$ is the sum over pairs that straddle the leaf of $\pm\lambda_{ij}$. That equals $\sum_{i \in R} \lambda_i$: a pair with both members inside adds $\lambda_{ij}$ to one member's $\lambda$ and subtracts it from the other's, and cancels in the sum. The numerator of the published step is exact. The curvature is
$$h''(0) = \sum_{\text{pairs with exactly one member in } R} \sigma^2 z_{ij}\,\rho_{ij}(1 - \rho_{ij}) \;=\; \sum_{i \in R} w_i \;-\; 2 \sum_{\text{pairs with both members in } R} \sigma^2 z_{ij}\,\rho_{ij}(1 - \rho_{ij}),$$
because $\sum_{i \in R} w_i$ counts each straddling pair once and each inside pair twice. The published denominator is therefore too large by twice the curvature of the pairs inside the leaf. It uses only the diagonal entries $\partial^2 C/\partial s_i^2$ of the matrix of second derivatives and drops the negative off-diagonal entries $\partial^2 C / \partial s_i \partial s_j$ of pairs that share a leaf. Wu and colleagues (2010) use the phrase "(diagonalized) Newton-Raphson approximation" for their leaf steps. The consequence is a step in the right direction that is never longer than the exact one-dimensional Newton step, and strictly shorter whenever the leaf holds both members of a pair of positive weight and the step is not zero. (With a cutoff, a pair wholly below rank $k$ has weight 0 and adds no curvature, so it does not shorten the step. If no pair of positive weight straddles the leaf, both $h'(0)$ and $h''(0)$ vanish: the exact Newton step is undefined, and the published step is 0 whenever its denominator is positive.) The script checks these statements on 500 random leaves and score vectors, with the cutoff of 10 and with a cutoff of 3. A shorter step is not a defect in a method that multiplies every step by a small learning rate anyway; it is a fact about the formula worth knowing when reading an implementation.
One boosting round by hand
Now the six abstracts go through one round of the algorithm, with two of the overview's eight features, each scaled to run from 0 to 1 over the query's 100 candidates and rounded here to three decimals. Intermediate values are shown rounded to four decimals, and every result is computed from the unrounded values, so a last digit can differ from what the rounded figures give.
| Abstract | Gain | BM25 | Title BM25 | $-\lambda_i$ (target) | $w_i$ |
|---|---|---|---|---|---|
| 856 | 2 | 1.000 | 1.000 | −0.0214 | 0.0816 |
| 857 | 3 | 0.896 | 0.727 | 0.0775 | 0.0388 |
| 766 | 3 | 0.769 | 0.499 | 0.0531 | 0.0265 |
| 390 | 0 | 0.764 | 0.900 | −0.1388 | 0.0694 |
| 858 | 3 | 0.753 | 0.514 | 0.0483 | 0.0241 |
| 1008 | 2 | 0.742 | 0.000 | −0.0187 | 0.0186 |
Step 2: the second derivatives. With every score 0, $\rho_{ij}(1 - \rho_{ij}) = \tfrac14$, so $w_i$ is a quarter of the sum of the swap values of the pairs containing $d_i$. For abstract 856, which is in four pairs, $w = \tfrac14(0.1418 + 0.0460 + 0.0623 + 0.0764) = 0.0816$. For 390, in five pairs, $w = \tfrac14 (0.1418 + 0.0748 + 0.0259 + 0.0164 + 0.0186) = 0.0694$, half of its $\lambda$, since every one of its pairs pushes it the same way.
Step 3: the tree. A tree with two leaves is one split. The targets have mean 0, because the $\lambda$s sum to zero, and the squared error of predicting 0 for all six is 0.03121. Each feature offers five places to split six distinct values, ten candidate splits in all. For each, the squared error after the split is the sum over the two sides of the squared deviations from the side's mean:
| Split | Abstracts on the high side | Squared error |
|---|---|---|
| title BM25 at 0.8135 | 856, 390 | 0.01198 |
| BM25 at 0.7665 | 856, 857, 766 | 0.02327 |
| title BM25 at 0.6205 | 856, 857, 390 | 0.02666 |
| BM25 at 0.8325 | 856, 857 | 0.02885 |
| the other six | 0.03033 to 0.03079 |
The best split is on title BM25 at 0.8135, the midpoint of 0.727 and 0.900. It puts abstracts 856 and 390 in one leaf, with mean target $-0.0801$, and the other four in the other, with mean target $0.0400$. These are the two abstracts that RankNet and LambdaRank both push down, and the title score happens to separate them from the rest.
Step 4: the leaf values. For the leaf holding 856 and 390:
$$\gamma = -\frac{0.0214 + 0.1388}{0.0816 + 0.0694} = -\frac{0.1602}{0.1510} = -1.0606.$$
For the leaf holding the other four, $-\sum\lambda_i = 0.0775 + 0.0531 + 0.0483 - 0.0187 = 0.1602$ and $\sum w_i = 0.0388 + 0.0265 + 0.0241 + 0.0186 = 0.1081$, so $\gamma = 0.1602/0.1081 = 1.4822$. The two numerators are equal and opposite, as they must be when the $\lambda$s sum to zero. The leaf values are not the mean targets $-0.0801$ and $0.0400$: the Newton step divides by curvature, and the curvature here is small because the swap values are small numbers.
Step 5: the update. With $\eta = 0.1$ the scores become $-0.1061$ for abstracts 856 and 390 and $0.1482$ for the other four. Sorting by score, with ties in BM25's order, gives 857, 766, 858, 1008, 856, 390, whose gains are 3, 3, 3, 2, 2, 0: the ideal order. One round has raised nDCG from 0.9051 to 1. The cost $C$ computed with the old weights has fallen from 0.3591 to 0.3210. The script's general implementation, run for one tree on these six rows, produces the same scores.
Three remarks keep the example in proportion.
- The tree has learned that a high title score is bad, from one query in which a nonrelevant abstract and the least relevant of the relevant ones happen to have the two highest title scores. In the overview, a linear ranker trained on all the queries gave title BM25 a large positive weight, and query 185 suffered for it. A real run pools every training query, and a split must lower the squared error over all of them.
- The $\lambda$s do not vanish at the ideal order. At the start of round 2, with nDCG equal to 1, the $\lambda$s are $0.0490$ for abstract 856, $-0.1739$ for 857 and $0.1853$ for 390: larger for some abstracts than in round 1, because the ranks, and so the weights, have changed. A true gradient of nDCG would be zero here wherever it exists. LambdaRank keeps separating scores that are already in the right order, which is the behavior of the logistic factor $\rho_{ij}$, not of the measure.
- The exact step. Each leaf holds both members of some pair: (856, 390) in one, and 1008 with each of 857, 766 and 858 in the other. Their curvatures, counted once, are 0.0355 and 0.0140, so the exact curvatures are $0.1510 - 2(0.0355)$ and $0.1081 - 2(0.0140)$, both 0.0801 from the unrounded values. They are equal because the same seven straddling pairs are seen from both sides. The exact Newton steps are $\mp 0.1602/0.0801 = \mp 2.0000$, against the published $-1.0606$ and $1.4822$. The value 2 has a reason. At equal scores every straddling pair has $\rho = \tfrac12$, and here every one of the seven has its less relevant member in the leaf of 856 and 390, so all push the same way: the numerator is $\tfrac12$ of the sum of their weights and the curvature $\tfrac14$ of it, and the ratio is $\tfrac12 / \tfrac14$ whatever the weights. A split at equal scores whose straddling pairs pointed both ways would have a smaller numerator and an exact step below 2 in size.
Experiments
Cranfield
The setting is the overview's: BM25's top 100 abstracts for each of 225 queries, eight features, 5-fold cross-validation over queries repeated with 30 seeded fold assignments, the same assignments the overview used, so its linear rankers can stand beside the boosted ones. LambdaMART is run with 50 trees of 4 leaves and $\eta = 0.1$, small values fixed in advance for a small collection, with $\sigma = 1$ and the swap values of nDCG@10. The second boosted ranker is the same code without the swap values, that is, RankNet's gradients on trees. Medians over the 30 assignments, with interquartile ranges:
| Ranker | MAP | nDCG@10 |
|---|---|---|
| BM25 alone | 0.307 | 0.368 |
| Linear RankNet (from the overview) | 0.314 | 0.384 |
| Linear LambdaRank (from the overview) | 0.314 | 0.382 |
| Boosted trees, RankNet gradients | 0.314 (0.311 to 0.316) | 0.381 (0.379 to 0.383) |
| LambdaMART | 0.313 (0.310 to 0.315) | 0.379 (0.375 to 0.382) |
Trees do not help here, and neither do the swap values. LambdaMART had a higher MAP than the overview's linear LambdaRank in 9 of the 30 fold assignments. This agrees with what the overview found: the eight features are variations on term matching, and a model trained and scored on the same queries could not do much better than BM25. Interactions between features that say nearly the same thing are not worth much, and 180 training queries are few for a model that can fit them.
LETOR MQ2008
MQ2008 (Qin and Liu, 2013) has 784 queries, 15,211 query-document rows with 46 features, labels 0 to 2 and five predefined folds with training, validation and test parts; Features for Ranking describes it. The measure is nDCG@10 with gain $2^y - 1$ on each fold's test queries, leaving out the queries with no relevant document (220 of the 784, so 564 are scored), and averaged over the five folds. The boosted rankers use up to 200 trees of 8 leaves, at least 10 documents in a leaf, and $\eta = 0.1$; the number of trees is the one with the best nDCG@10 on the fold's validation queries. They have no random element, so each is run once. The linear rankers are trained by stochastic gradient descent in batches of 16 queries for 40 passes, keeping the weights of the pass that was best on the validation queries, with 30 seeds for the order of the batches. The learning rate of each linear ranker was chosen from 0.01, 0.03, 0.1, 0.3, 1 and 3 by the best validation nDCG@10 on the first fold with one seed, so no test query played a part; the selection chose 1 for both.
| Ranker | Test nDCG@10, mean of five folds | Range over folds, or IQR over seeds |
|---|---|---|
| BM25 of the whole document, alone | 0.645 | 0.605 to 0.673 |
| Linear, RankNet gradients | 0.687 | 0.681 to 0.691 (seeds) |
| Linear LambdaRank | 0.696 | 0.693 to 0.699 (seeds) |
| Regression trees on the labels (scikit-learn) | 0.702 | |
| Boosted trees, RankNet gradients | 0.694 | 0.662 to 0.731 |
| LambdaMART | 0.698 | 0.663 to 0.729 |
Every learned ranker is between 0.04 and 0.06 above BM25 of the whole document alone, and the learned rankers are within 0.015 of one another: 0.687 to 0.702. BM25 is not the best single column. The best is column 39, a language model score of the whole document, which scores 0.687 under this page's measure (the mean over the five folds) and 0.689 averaged over the 564 queries, as Features for Ranking reports it. The learned rankers other than the linear pairwise one are between 0.007 and 0.015 above that column, and the linear pairwise ranker at its selected rate is level with it, less than 0.001 below. The spread between folds for one method, from 0.663 to 0.729, a range of 0.067 for LambdaMART, is 4.5 times the spread between methods. LambdaMART is level with linear LambdaRank and a little above the same trees without the swap values, by 0.004. Fold by fold it was ahead in 3 folds and behind in 2, and the differences ran from −0.012 to 0.020; their paired t statistic of 0.73 on 4 degrees of freedom is far below the two-sided 5 percent point of 2.776, so these five folds give no evidence of a difference, although five pairs could detect only a large one. The pointwise regression has the highest mean of all. The linear pairwise ranker has the lowest, and its result depends on its learning rate: with 0.03, the rate that came second on the first fold's validation queries, its median over the seeds is 0.698 (0.693 to 0.700), level with the others. At the selected rate, the change of rate moves it by 0.011, about as much as the swap weights do (linear LambdaRank is 0.009 above it), and linear LambdaRank was not run at 0.03, so these runs do not separate the two effects. The same linear model trained on RankNet's cost scores differently under the unit's other protocols: 0.703 in RankNet, trained by full-batch gradient descent with learning rate 10, and 0.696 in Features for Ranking, trained by Adam, both averaged over the 564 queries. Here it is trained in minibatches with a learning rate selected on one fold, and the value is the median over seeds of the mean over folds; this protocol gives it less, so its place at the bottom of the table is an observation under this protocol, not a finding about the pairwise cost.
The third row from the bottom is a library comparison: scikit-learn's GradientBoostingRegressor with the same number and size of trees, fitted by squared error to the labels themselves, a pointwise method. The validation queries chose between 30 and 190 trees for LambdaMART, depending on the fold.
The honest reading of both collections is that they are too small, or too uniform in their features, to separate these methods. The published evidence for the swap weights and for trees comes from much larger data: an ensemble built mostly of LambdaMART models won Track 1 of the 2010 Yahoo! Learning to Rank Challenge, whose datasets had hundreds of features and tens of thousands of queries, as the overview recounts (Burges, 2010; Chapelle and Chang, 2011).
What is being optimized: the LambdaLoss account
LambdaRank was defined by its gradient, and for more than a decade the question of what loss it minimizes had only the local answer given above. Wang, Li, Golbandi, Bendersky and Najork (2018) proposed a global one. This section reports their account as the paper states it, and proves the two inequalities it rests on.
The framework. The scores are taken to determine a distribution $P(\pi \mid s)$ over ranked lists $\pi$. The loss of a query is the negative logarithm of the likelihood of its labels, with the ranked list as a hidden variable (their eq. 7):
$$l(y, s) = -\log_2 \sum_{\pi} P(y \mid s, \pi)\, P(\pi \mid s).$$
A loss with a hidden variable can be minimized by the expectation-maximization algorithm, which alternates between estimating the distribution of the hidden variable under the current model and re-fitting the model given that distribution, and which the authors note converges to a local minimum.
LambdaRank as a special case. Two choices recover LambdaRank (their §4.3). The distribution over lists is the "hard assignment" that puts all its mass on the list sorted by the current scores. The likelihood of the labels is a product over the pairs with $y_i > y_j$ of a logistic probability raised to a power that depends on the two ranks:
$$P(y_i > y_j \mid s_i, s_j, \pi) = \left( \frac{1}{1 + e^{-\sigma(s_i - s_j)}} \right)^{|G_i - G_j| \,\left| \frac{1}{D(\pi_i)} - \frac{1}{D(\pi_j)} \right|},$$
where $G_i$ is the gain of document $i$ divided by the ideal DCG and $D(r) = \log_2(1 + r)$. In this section $D$ has the paper's meaning, the reciprocal of the discount written $D(r)$ earlier in this article. The exponent is the swap value $|\Delta \mathrm{nDCG}_{ij}|$ of this article. The expectation step is then the sort, and the maximization step minimizes
$$\sum_{y_i > y_j} \big|\Delta \mathrm{nDCG}_{ij}\big| \,\log_2\big(1 + e^{-\sigma(s_i - s_j)}\big)$$
with the ranks fixed (their eq. 11), which is the cost $C$ above measured in bits. In this reading LambdaRank is an expectation-maximization procedure for a well-defined likelihood, and the recomputation of the weights after each sort is its expectation step. The authors add that LambdaMART's way of carrying out the maximization step, adding one tree fitted to the gradient to the existing model, is from this point of view a heuristic.
What the loss bounds. The paper's Proposition 5.1 states that the LambdaRank loss is a bound for the metric
$$\mathrm{Metric}_{\text{LambdaRank}} = \sum_{i=1}^{n} G_i \sum_{j=1}^{i-1} \left| \frac{1}{D_i} - \frac{1}{D_j} \right|,$$
where the documents are numbered by their current rank, so $G_i$ and $D_i = \log_2(1 + i)$ belong to the document at rank $i$. It then observes that the cost form of nDCG, $\mathrm{NDCG}_{\text{cost}} = \sum_i G_i (1 - 1/D_i)$, which is $\sum_i G_i$ minus the nDCG, is no larger than this metric, and concludes that LambdaRank optimizes a coarse upper bound of the nDCG cost. Both steps can be checked directly.
The metric is at least the nDCG cost. Since $D_1 = 1$, the term $j = 1$ of the inner sum is $|1/D_i - 1| = 1 - 1/D_i$ for every $i \ge 2$, and the other terms are not negative. So the inner sum is at least $1 - 1/D_i$. For $i = 1$ both are zero. Multiplying by $G_i \ge 0$ and adding gives $\mathrm{NDCG}_{\text{cost}} \le \mathrm{Metric}_{\text{LambdaRank}}$.
The loss bounds the part of the metric that depends on the scores. Write $\rho^{D}_{ij} = |1/D_i - 1/D_j|$, which is symmetric in $i$ and $j$. The metric charges each document for every document ranked above it, so it is a sum over unordered pairs of $\rho^{D}_{ij}$ times the $G$ of the lower-ranked member. For a pair with $G_i > G_j$, the lower-ranked member's $G$ is $G_j$ if the pair is correctly ordered and $G_i = G_j + (G_i - G_j)$ if it is misordered, that is, if $d_i$ is ranked below $d_j$. Write $\pi_i$ for the rank of $d_i$ in the current list. The pair contributes $\rho^{D}_{ij} G_j$ in either case, plus $\rho^{D}_{ij}(G_i - G_j)$ if it is misordered:
$$\mathrm{Metric}_{\text{LambdaRank}} = \sum_{G_i > G_j} \rho^{D}_{ij}\,(G_i - G_j)\,\big[\,\pi_i > \pi_j\,\big] \;+\; C_3 + C_2,$$
where $C_3 = \sum_{G_i > G_j} \rho^{D}_{ij} G_j$ and $C_2$ collects the pairs of equal gain. The indicator is written by rank because the metric is a function of the ranks. Wang and colleagues write it by score, $[\,s_i < s_j\,]$ (their eq. 16 and the proof of Proposition 5.1), which is the same thing when no two scores are equal and is wrong at a tie: on the six abstracts below, every score is 0, every score indicator is 0, and yet five pairs are misordered by rank. The product $\rho^{D}_{ij}(G_i - G_j)$ is the swap value. The indicator of a misordered pair is at most $\log_2(1 + e^{-\sigma(s_i - s_j)})$: that quantity is at least 1 whenever $s_i \le s_j$, a pair ranked the wrong way has $s_i \le s_j$ (ties in score being broken one way or the other), and the quantity is positive otherwise. Hence the first sum is at most the LambdaRank loss. The paper notes that $C_2$ and $C_3$ depend on the current ranking only and are constant in the maximization step. They are not constants of the problem: they change when the order changes.
On the six abstracts, with $G_i = g_i/8.0278$: $\sum_i G_i = 1.6194$ and the nDCG cost is $1.6194 - 0.9051 = 0.7143$. The metric is 1.0435, of which 0.2196 is the misordered sum and the rest is $C_3 + C_2$. The LambdaRank loss in bits is 0.5181, which is indeed above 0.2196. The script checks the decomposition and the first inequality on 2,000 random lists.
What follows. The bound is loose, as the authors say, and they derive tighter ones for nDCG, of which the one they call NDCG-Loss2 has the same structure as LambdaRank's loss with a different weight for each pair. They report that boosted trees trained with these losses improved on LambdaMART on three public datasets. The account does not make LambdaRank a gradient method for nDCG. It says that LambdaRank is a sound procedure for minimizing a bound on a quantity that is itself above the nDCG cost, and it leaves the empirical findings of the earlier section as they were.
What is proved, what is cited, what the experiment shows
Proved on this page: the closed form of the change in nDCG under a swap; that LambdaRank's $\lambda$s are the gradient of the weighted pairwise cost while the order of the documents is unchanged; the Newton step for a leaf, for any twice-differentiable loss; the second derivative $w_i$; that the numerator of LambdaMART's leaf value is exact and its denominator exceeds the exact curvature by twice the curvature of the pairs inside the leaf; the two inequalities behind the LambdaLoss account.
Cited: that the weighting was chosen empirically among ten candidates (Burges, Ragno and Le, 2006); the evidence that LambdaRank finds local optima of nDCG (Burges, 2010, citing Donmez, Svore and Burges, 2009); the algorithm and its suggested settings (Wu et al., 2010; Burges, 2010); the two-class Newton step and its attribution to Friedman (2001), which is reported from Burges (2010) and was not read for this article; the LambdaLoss framework and its results (Wang et al., 2018); the Yahoo! challenge (Chapelle and Chang, 2011).
Shown by the experiment: on Cranfield and MQ2008, neither the swap weights nor the trees produced a gain that stands out from the variation between folds and seeds, or, for the linear pairwise ranker on MQ2008, from the effect of its learning rate.
Worked problems
This unit has no course assignments, so the problems below are posed on the six abstracts and on one pair. The script recomputes every number.
Problem 1 (swap values with a cutoff). For the six abstracts in BM25's order, compute $|\Delta \mathrm{nDCG}@3|$ for the swaps of ranks 1 and 2, of ranks 4 and 5, and of ranks 1 and 5.
Solution. The values are 0.0577, 0 and 0.1564. With a cutoff of 3 the ideal list 3, 3, 3 has $\mathrm{maxDCG}@3 = 3(1 + 0.6309 + 0.5) = 6.3928$, and the discount is 0 beyond rank 3. Ranks 1 and 2 hold gains 2 and 3: $|2 - 3| \times |1 - 0.6309|/6.3928 = 0.0577$. Ranks 4 and 5 are both beyond the cutoff, so both discounts are 0 and the swap changes nothing, although it would repair a misordered pair. Ranks 1 and 5 hold gains 2 and 3, and only rank 1 is inside the cutoff: $|2 - 3| \times |1 - 0|/6.3928 = 0.1564$. A truncated measure makes LambdaRank blind to pairs that lie wholly below the cutoff, and gives its largest weights to pairs that would bring a better document across it.
Problem 2 (a leaf with one document). Suppose a tree isolates abstract 390 in a leaf of its own in the first round. Find the leaf value, and say whether the diagonal approximation matters.
Solution. The value is $-2.0000$, and the approximation changes nothing. From the tables, $\lambda_{390} = 0.1388$ and $w_{390} = 0.0694$, so $\gamma = -0.1388/0.0694 = -2.0000$. A leaf with one document holds no pair, so the sum of the pairs inside it is empty and the published step is the exact Newton step. The value is exactly 2 in size because every pair containing 390 pushes it the same way with $\rho = \tfrac12$: the numerator is $\tfrac12$ of the sum of its swap values and the denominator $\tfrac14$ of the same sum.
Problem 3 (the steepness $\sigma$). Redo the leaf value of the leaf holding 856 and 390 with $\sigma = 2$, and explain why the choice of $\sigma$ does not change what LambdaMART learns.
Solution. The value is $-0.5303$, half of $-1.0606$. At equal scores $\rho_{ij} = \tfrac12$ whatever $\sigma$ is. Each $\lambda_{ij} = -\sigma z_{ij}\rho_{ij}$ doubles, and each second derivative $\sigma^2 z_{ij}\rho_{ij}(1 - \rho_{ij})$ is multiplied by four, so the ratio halves. In general the leaf value is proportional to $1/\sigma$ for given values of $\sigma s_i$. The scores enter the cost only through the products $\sigma(s_i - s_j)$, so a model trained with $\sigma = 2$ has scores half as large and the same products, the same $\rho$s, the same order and the same trees. Burges (2010, §7) makes this observation: the leaf values scale as $1/\sigma$ and the scores always appear multiplied by $\sigma$. The targets of the tree are all multiplied by the same $\sigma$, which does not change which split has the least squared error.
Problem 4 (one Newton step on one pair). A pair $(i, j)$ in $I$ has weight 1, $\sigma = 1$ and scores $s_i = 1$, $s_j = 0$. Compute $\rho_{ij}$, $\lambda_i$ and $w_i$, and the Newton step for a leaf that holds $d_i$ alone. Does the step reach the minimum of the pair's cost?
Solution. $\rho_{ij} = 0.2689$, $\lambda_i = -0.2689$, $w_i = 0.1966$, and the step is 1.3679; it does not reach a minimum, because there is none. $\rho_{ij} = 1/(1 + e^{1}) = 0.2689$, so $\lambda_i = -\rho_{ij} = -0.2689$ and $w_i = \rho_{ij}(1 - \rho_{ij}) = 0.2689 \times 0.7311 = 0.1966$. The step is $-\lambda_i/w_i = 1/(1 - \rho_{ij}) = 1.3679$. Afterwards the gap is $2.3679$ and $\rho_{ij} = 1/(1 + e^{2.3679}) = 0.0857$, not zero. The cost $\log(1 + e^{-(s_i - s_j)})$ decreases for ever as the gap grows and has no minimum, so every Newton step is finite and leaves some gradient. In boosting the learning rate and the number of trees, not the loss, decide where the scores stop.
What we have learned
Swapping two documents changes nDCG by the product of the difference of their gains and the difference of their discounts, divided by the ideal DCG. LambdaRank multiplies each pair's RankNet gradient by that amount, which concentrates the forces on pairs that span the top of the list, including pairs that are already in the right order. The result is the gradient of a weighted pairwise cost only while the order of the documents stays fixed. LambdaMART fits a regression tree to the negative gradients of all documents and gives each leaf one Newton step, the sum of the gradients over the sum of the second derivatives; the numerator is exact and the denominator ignores that both members of a pair may share a leaf, which shortens the step. On six Cranfield abstracts one round, computed by hand, turned an nDCG of 0.9051 into 1. The LambdaLoss framework reads the whole procedure as expectation-maximization for a likelihood that bounds a quantity above the nDCG cost. On Cranfield and MQ2008 the method was level with simpler ones.
The next article, Listwise Losses, takes the other route to the whole list: a probability model of permutations in place of weighted pairs.
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. J. C., Ragno, R., and Le, Q. V. (2006). Learning to rank with nonsmooth cost functions. In Advances in Neural Information Processing Systems 19 (NIPS 2006), 193–200. record · 2 pages
- Chapelle, O., and Chang, Y. (2011). Yahoo! Learning to Rank Challenge overview. In Proceedings of the Learning to Rank Challenge, PMLR 14, 1–24. record · 7 pages
- Donmez, P., Svore, K. M., and Burges, C. J. C. (2009). On the local optimality of LambdaRank. In Proceedings of SIGIR 2009, 460–467. record
- Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5), 1189–1232. record · 3 pages
- Qin, T., and Liu, T.-Y. (2013). Introducing LETOR 4.0 datasets. arXiv:1306.2597. record · 6 pages
- Wang, X., Li, C., Golbandi, N., Bendersky, M., and Najork, M. (2018). The LambdaLoss framework for ranking metric optimization. In Proceedings of CIKM 2018, 1313–1322. record
- Wu, Q., Burges, C. J. C., Svore, K. M., and Gao, J. (2010). Adapting boosting for information retrieval measures. Information Retrieval, 13(3), 254–270. record · 2 pages