Three documents $a$, $b$ and $c$ are scored 2, 1 and 0 by a model, and only $a$ is relevant. A pairwise loss such as RankNet's looks at this list two documents at a time: $a$ against $b$, $a$ against $c$. The list as a whole, the thing a user sees and an evaluation measure scores, appears nowhere in it. What would a loss look like that is a function of the whole list at once?
Listwise losses answer with a probability model. The scores are turned into a probability distribution over orderings of the documents, the judgments are turned into a target, and the loss measures how far the first is from the second. Two losses of this kind are standard. ListNet (Cao, Qin, Liu, Tsai and Li, 2007) compares two distributions by cross entropy. ListMLE (Xia, Liu, Wang, Zhang and Li, 2008) asks for the probability of one ordering, the judged one. Both rest on the same model of permutations, named after Plackett and Luce.
Here is the route. First we build the Plackett-Luce model from repeated choices and prove the four properties the losses depend on. Then we derive ListNet's loss and gradient, and ListMLE's. Next we state what has been proved about whether minimizing these losses gives good rankings, and work an example in which it does not. Finally we train both on Cranfield and on a LETOR dataset. The overview defines ListNet in a paragraph and works one example of its loss, which this article continues. The article assumes RankNet and nDCG, and uses the softmax function of the library's logistic regression. The numbers are computed by tools/experiments/ltr/listwise-losses.py.
A probability for every ordering
Here is the idea in one sentence: fill the ranking from the top, each time choosing one of the documents not yet placed with probability proportional to $e^{\text{score}}$.
Write $v_i = e^{s_i}$ for the positive weight of document $i$. A permutation $\pi$ lists the documents in order: $\pi(1)$ is the document in first position, $\pi(2)$ the one in second, and so on to $\pi(n)$. The Plackett-Luce probability of $\pi$ given the scores is
$$P_s(\pi) = \prod_{j=1}^{n} \frac{v_{\pi(j)}}{\sum_{k=j}^{n} v_{\pi(k)}} = \prod_{j=1}^{n} \frac{e^{s_{\pi(j)}}}{\sum_{k=j}^{n} e^{s_{\pi(k)}}}.$$
The $j$-th factor is the probability of choosing $\pi(j)$ among the documents still unplaced, $\pi(j), \pi(j+1), \dots, \pi(n)$. The last factor is always 1, since one document is left.
This is Definition 1 of Cao and colleagues, who allow any increasing positive function of the score in place of the exponential and take the exponential in their method. They describe their distribution as similar to those Plackett (1975) defined on ranking lists following the work of Luce (1959). Xia and colleagues (2008) call it a Plackett-Luce model, the name now usual.
The three documents. With scores $(2, 1, 0)$ the weights are $e^2 = 7.389$, $e = 2.718$ and 1, with total 11.107. The ordering $a, b, c$ has probability
$$\frac{7.389}{11.107} \cdot \frac{2.718}{2.718 + 1} \cdot \frac{1}{1} = 0.6652 \times 0.7311 = 0.4863.$$
All six, each computed the same way:
| Ordering | Probability |
|---|---|
| $a, b, c$ | 0.4863 |
| $b, a, c$ | 0.2156 |
| $a, c, b$ | 0.1789 |
| $c, a, b$ | 0.0658 |
| $b, c, a$ | 0.0292 |
| $c, b, a$ | 0.0242 |
They add up to 1. The ordering that sorts the documents by score is the most probable, its reverse is the least, and no ordering is impossible. The model does not say the ranker might return another list. It is a device for making the scores comparable with a target, smoothly.
Four properties of the model are used below. Each is proved here, and the script checks each by enumerating all permutations for 300 seeded random score lists of up to six documents.
1. The probabilities sum to 1. By induction on $n$. For one document the single ordering has probability 1. For $n$ documents, group the orderings by their first document $i$. Every ordering that starts with $i$ has first factor $v_i/V$, where $V = \sum_k v_k$, and its remaining factors are exactly the Plackett-Luce probability of an ordering of the other $n - 1$ documents. Those sum to 1 by the induction hypothesis. So the orderings that start with $i$ have total probability $v_i/V$, and the total over all $i$ is $\sum_i v_i / V = 1$. Cao and colleagues state this as their Lemma 2.
2. The first $k$ positions. The probability that given documents $i_1, \dots, i_k$ occupy the first $k$ positions in that order is the product of the first $k$ factors alone:
$$P_s(i_1, \dots, i_k \text{ first}) = \prod_{j=1}^{k} \frac{v_{i_j}}{V - v_{i_1} - \dots - v_{i_{j-1}}}.$$
The proof is the same grouping. The orderings that begin $i_1, \dots, i_k$ share their first $k$ factors, and their remaining factors are the probabilities of all orderings of the other $n - k$ documents, which sum to 1 by property 1. With $k = 1$ this is the top one probability, the probability that document $j$ is ranked first:
$$P_s(j) = \frac{e^{s_j}}{\sum_{k} e^{s_k}},$$
the softmax of the scores. For the three documents it is 0.6652, 0.2447 and 0.0900, and indeed $0.4863 + 0.1789 = 0.6652$. Computing it takes $n$ exponentials, not $n!$ permutations. Cao and colleagues prove this as Theorem 6 of the technical report version of their paper; the overview records that the conference version defines the general top $k$ probability and uses $k = 1$.
3. Any two documents. The probability that document $i$ is placed before document $j$ is
$$P_s(i \text{ before } j) = \frac{v_i}{v_i + v_j} = \frac{1}{1 + e^{-(s_i - s_j)}},$$
whatever the other documents and their scores. By induction on $n$: for two documents it is the first factor. For $n > 2$, the first choice is $i$ with probability $v_i/V$, in which case $i$ is before $j$. It is $j$ with probability $v_j/V$, in which case it is not. Otherwise it is some other document, with total probability $(V - v_i - v_j)/V$, after which the rest is a Plackett-Luce model on the remaining documents, where the induction hypothesis gives $v_i/(v_i + v_j)$. So
$$P_s(i \text{ before } j) = \frac{v_i}{V} + \frac{V - v_i - v_j}{V} \cdot \frac{v_i}{v_i + v_j} = \frac{v_i (v_i + v_j) + (V - v_i - v_j)\, v_i}{V (v_i + v_j)} = \frac{v_i}{v_i + v_j}.$$
This is RankNet's pair probability $P_{ij}$ with $\sigma = 1$. The Plackett-Luce model is a model of whole lists whose view of any single pair is RankNet's. In the example, $b$ precedes $c$ with probability $e/(e + 1) = 0.7311$, which is $0.4863 + 0.2156 + 0.0292$.
4. Sorting by score gives the most probable ordering. Take an ordering in which document $x$ stands at position $p$ and document $y$ at a later position $q$, with $s_x > s_y$, and exchange the two. The numerators of the product are the same before and after, since each document's weight appears once. The denominator of factor $l$ is the total weight of the documents at positions $l$ to $n$. For $l \le p$ and for $l > q$ that set is unchanged. For $p < l \le q$ it contained $y$ and not $x$, and after the exchange it contains $x$ and not $y$, so it is larger. Larger denominators mean a smaller product: putting the lower-scored document ahead lowers the probability. Any ordering can be sorted by such exchanges, each of which raises the probability, so the sorted ordering is the most probable, and by the same argument reversed the anti-sorted one is the least. These are Theorems 3 and 4 of Cao and colleagues' technical report.
ListNet: cross entropy between top one distributions
ListNet turns the scores into a distribution, the judged labels into another, and takes the cross entropy between them. In full, the two distributions would be over permutations: $P_y(\pi)$, the Plackett-Luce distribution with the labels $y_i$ used as scores, and $P_s(\pi)$. The loss would be $-\sum_\pi P_y(\pi) \log P_s(\pi)$, a sum over $n!$ orderings, which is 3,628,800 for ten documents. Cao and colleagues replace the permutation distributions by their top one probabilities:
$$L_{\text{ListNet}} = -\sum_{j=1}^{n} P_y(j) \log P_s(j), \qquad P_y(j) = \frac{e^{y_j}}{\sum_k e^{y_k}}, \quad P_s(j) = \frac{e^{s_j}}{\sum_k e^{s_k}}.$$
For the three documents with labels $(1, 0, 0)$ the target is $(0.5761, 0.2119, 0.2119)$ and the loss is 1.043, as the overview computes in its fifth worked problem.
Does the shortcut lose information? About the model, none. The ratio of two top one probabilities is $P_s(j)/P_s(k) = e^{s_j - s_k}$, so the top one distribution determines every difference of scores, and with them the whole permutation distribution. Two score lists have the same top one distribution exactly when they differ by a constant. The two losses are still different functions. On the three documents the permutation-level cross entropy is 1.776, with a smallest possible value of 1.621, against 1.043 and 0.975 for the top one loss. Both are smallest at the same scores, $s_j = y_j$ plus any constant: a cross entropy is least when the two distributions are equal, and by the remark just made that happens for the permutation distributions exactly when it happens for the top one distributions.
The gradient. Here is the plan: write $\log P_s(j)$ as a score minus one shared term, and differentiate. Since $\log P_s(j) = s_j - \log \sum_k e^{s_k}$ and the target probabilities sum to 1,
$$L_{\text{ListNet}} = -\sum_j P_y(j)\, s_j + \log \sum_k e^{s_k}.$$
The derivative of the first term with respect to $s_i$ is $-P_y(i)$. The derivative of the second is $e^{s_i}/\sum_k e^{s_k} = P_s(i)$. So
$$\frac{\partial L_{\text{ListNet}}}{\partial s_i} = P_s(i) - P_y(i).$$
The gradient is the difference between the two distributions, document by document, the same form as the gradient of multiclass logistic regression. Its components sum to zero. For the three documents it is $(0.0891, 0.0328, -0.1219)$. The first component is positive: gradient descent would lower the score of the relevant document $a$. That is correct for this loss. The scores $(2, 1, 0)$ give $a$ a top one probability of 0.6652, more than the target's 0.5761, and they separate $b$ from $c$, which the labels do not.
Example (ListNet does not want the relevant document as far ahead as possible). Take two documents with labels $(1, 0)$ and let $d = s_1 - s_2$. The loss is $-P_y(1) \log \frac{1}{1 + e^{-d}} - P_y(2) \log \frac{1}{1 + e^{d}}$, and it is smallest at $d = 1$, the difference of the labels, where it equals 0.5822. At $d = 5$, with the relevant document far ahead, it is 1.3514. The labels act as target scores. A model that ranks perfectly but with wide margins is penalized, and relabeling the grades changes what is asked: with labels $(2, 0)$ the best gap is 2. This two-document analysis is Xia and colleagues' (2008, §4.3.3 and Fig. 3), made for the permutation-level cross entropy, which for two documents is the same function as the top one loss: they show that the loss reaches its minimum at a finite gap and then increases, so that it can heavily penalize correct rankings made with higher confidence, and that the mapping from judgments to target scores affects the penalty, which under some mappings can be larger for a correct ranking than for an incorrect one; they call the loss "not very sound" for this reason. They also observe the same sensitivity in their experiments, where ListNet's accuracy varied with that mapping function.
ListMLE: the likelihood of the judged ordering
ListMLE uses the model more directly. If the judgments give a complete ordering $\pi$ of the documents, the loss is minus the logarithm of the probability the model gives to that ordering (Xia et al., 2008, eq. 9):
$$L_{\text{ListMLE}} = -\log P_s(\pi) = \sum_{j=1}^{n} \Big( \log \sum_{k=j}^{n} e^{s_{\pi(k)}} - s_{\pi(j)} \Big).$$
Minimizing it over a training set is maximum likelihood estimation of the scores under the Plackett-Luce model, which is the name: listwise maximum likelihood. For the three documents and the judged ordering $a, b, c$ it is $-\log 0.4863 = 0.7209$. Term by term: $\log 11.107 - 2 = 2.4076 - 2$ for the first position and $\log(e + 1) - 1 = 1.3133 - 1$ for the second. If the judged ordering were $c, b, a$ it would be $-\log 0.0242 = 3.7209$, with gradient $(1.3963, -0.4863, -0.9100)$ by the formula derived next.
The gradient. Here is the plan: each position of the ordering is a small classification problem, choosing the right document among those remaining, and the gradient adds up the softmax gradients of those problems. Write $Z_l = \sum_{k \ge l} e^{s_{\pi(k)}}$ for the total weight of the documents at positions $l$ to $n$, and $P_l(i) = e^{s_i}/Z_l$ for the probability of choosing document $i$ at stage $l$, defined for the documents still unplaced at that stage. Then $L_{\text{ListMLE}} = \sum_l \big(\log Z_l - s_{\pi(l)}\big)$. Consider the document at position $j$, $i = \pi(j)$. Its score appears once as the subtracted term, at $l = j$, with derivative $-1$. It appears inside $Z_l$ for every stage at which it is still unplaced, $l \le j$, and the derivative of $\log Z_l$ with respect to it is $e^{s_i}/Z_l = P_l(i)$. So
$$\frac{\partial L_{\text{ListMLE}}}{\partial s_{\pi(j)}} = \sum_{l=1}^{j} P_l\big(\pi(j)\big) - 1.$$
A document's gradient is the total probability the model gave it at the stages where it was available, minus 1 for the one stage at which it should have been chosen. For the ordering $a, b, c$ and scores $(2, 1, 0)$: document $a$ has $0.6652 - 1 = -0.3348$; document $b$ has $0.2447 + 0.7311 - 1 = -0.0242$; document $c$ has $0.0900 + 0.2689 + 1 - 1 = 0.3590$. The components sum to zero, as they must for a loss that depends only on differences of scores.
Three properties follow from the formula for the loss.
For two documents ListMLE is RankNet. With the judged ordering $(1, 2)$, $L = \log(e^{s_1} + e^{s_2}) - s_1 = \log\big(1 + e^{-(s_1 - s_2)}\big)$, RankNet's pair cost with $\sigma = 1$. Unlike ListNet's, it falls toward zero as the gap grows.
It is convex. Each term is a log-sum-exp of some of the scores minus a linear function. The log-sum-exp function $f(\mathbf{s}) = \log \sum_k e^{s_k}$ is convex: its gradient is the softmax vector $\mathbf{p}$, and its matrix of second derivatives has entries $p_k [k = m] - p_k p_m$, so for any vector $\mathbf{u}$ the quadratic form is $\sum_k p_k u_k^2 - \big(\sum_k p_k u_k\big)^2$, the variance of $u$ under the distribution $\mathbf{p}$, which is never negative. A sum of convex functions is convex. For a linear model the loss is then convex in the weights, so gradient descent has no local minima to be caught in. ListNet's loss, in the form written above, is convex for the same reason. Xia and colleagues list convexity among the properties of the likelihood loss.
It costs one pass. The sums $Z_l$ are suffix sums and can all be computed in one backward pass over the ordering, so the loss and gradient take time linear in $n$ once the documents are in the judged order. Xia and colleagues contrast this with the permutation-level cross entropy, whose cost is exponential in $n$.
Ties, and where to stop
Judgments are grades, not orderings. The six abstracts that LambdaRank and LambdaMART works on, BM25's first six candidates for Cranfield query 185, have gains 2, 3, 3, 0, 3, 2. Twelve orderings are consistent with those grades: the three abstracts of gain 3 in any of $3! = 6$ orders, then the two of gain 2 in either order, then the nonrelevant one. A likelihood needs one ordering. In their experiment on graded data, Xia and colleagues chose one of the perfect orderings at random for each query, and this article's experiments do the same with a seeded generator.
With all six scores equal to 0, every ordering has probability $1/6! = 1/720$ and the loss is $\log 720 = 6.5793$. For the ordering that keeps tied abstracts in BM25's order, the gradient is
| Abstract | 856 | 857 | 766 | 390 | 858 | 1008 |
|---|---|---|---|---|---|---|
| Gain | 2 | 3 | 3 | 0 | 3 | 2 |
| Position in the judged ordering | 4 | 1 | 2 | 6 | 3 | 5 |
| $\partial L/\partial s$ | −0.0500 | −0.8333 | −0.6333 | 1.4500 | −0.3833 | 0.4500 |
Abstract 857 is first in the ordering and has gradient $\tfrac16 - 1 = -0.8333$. Abstract 766 is second: $\tfrac16 + \tfrac15 - 1 = -0.6333$. The nonrelevant abstract 390 is last and collects every stage: $\tfrac16 + \tfrac15 + \tfrac14 + \tfrac13 + \tfrac12 + 1 - 1 = 1.4500$.
The table shows a weakness of the arbitrary choice among ties. Abstracts 857, 766 and 858 have the same gain and receive different gradients, $-0.8333$, $-0.6333$ and $-0.3833$, only because of the order in which the tie happened to be broken. Abstract 1008, which is relevant, is pushed down, because the ordering puts it fifth of six. Among many nonrelevant documents the effect is larger: the likelihood rewards the model for reproducing an arbitrary order among them.
One remedy uses property 2. The probability that the relevant documents fill the first positions in their judged order is the product of the first factors only. Stopping the sum after the last relevant document gives the loss
$$L_{\text{top}} = -\log P_s\big(\pi(1), \dots, \pi(R) \text{ first}\big) = \sum_{j=1}^{R} \Big( \log \sum_{k=j}^{n} e^{s_{\pi(k)}} - s_{\pi(j)} \Big),$$
where $R$ is the number of relevant documents. It is a likelihood too, of an event that says nothing about the order of the nonrelevant documents. It is also convex, and its gradient is the same sum of stage probabilities with the stages limited to $l \le R$. On the six abstracts the restriction happens to change nothing: five of the six abstracts have positive gain, so $R = 5$, and the product of the first five factors is the whole likelihood, because the sixth factor is always 1. The loss is still $\log 720$ and the gradient is the table's. Among BM25's 100 candidates for a Cranfield query, as in the experiments below, the nonrelevant documents are the great majority and the restriction removes most of the factors. To see on the six abstracts what it does to tied grades, stop instead after the top grade, the three abstracts of gain 3, a variant of the definition. The loss at equal scores is then $\log(6 \cdot 5 \cdot 4) = \log 120 = 4.7875$, and the gradient is $-0.8333$, $-0.6333$ and $-0.3833$ for the three and $\tfrac16 + \tfrac15 + \tfrac14 = 0.6167$ for each of the other abstracts, which are now treated alike. The experiments below run the whole ordering and the restricted form, with $R$ the number of documents of positive gain.
Do these losses produce good rankings?
A surrogate loss is minimized in place of the measure that matters. The question of whether that works has a precise form. A loss is consistent with a measure if, with unlimited data and an unrestricted model, minimizing the expected loss yields scores whose ordering is optimal for the measure. This section states what the literature proves, as far as the sources read for this article support, and then works one case by hand.
For the zero-one loss on permutations. Xia and colleagues (2008, §4.2) define consistency with respect to a loss that is 0 when the predicted permutation equals the true one and 1 otherwise. Their Theorem 5 gives sufficient conditions: the loss must be what they call order sensitive, and the distribution of permutations must be order preserving. They state that the likelihood loss (Proposition 6) and the permutation-level cross entropy of ListNet (Proposition 8) are order sensitive and hence consistent in this sense. The paper gives a sketch of the proof of Theorem 5 and omits the proofs of the propositions for space. The measure in question is strict: it gives no credit to an ordering that is right in its first ten positions and wrong in its last.
For nDCG. Ravikumar, Tewari and Yang (2011) study consistency with respect to nDCG. They characterize the consistent surrogates (their Theorem 6) and show that three common ones are not consistent as usually written, among them ListNet's cross entropy between the softmax of the labels and the softmax of the scores (their Proposition 7). They show how to restore consistency by normalizing the targets by a quantity derived from the discounted gain.
An upper bound. Chen, Liu, Lan, Ma and Li (2009) show that the losses of several methods, ListMLE's among them, are upper bounds on $1 - \mathrm{nDCG}$ and on $1 - \mathrm{MAP}$ up to stated constants, so that driving the loss down also drives down a bound on the measure's error. A bound of this kind does not by itself imply consistency.
An inconsistency worked by hand
The reason ListNet can fail for nDCG shows in the smallest possible case, and the argument is short enough to prove here.
Setting. One query has two documents, $A$ and $B$. Judgments vary from one occasion to the next, as they do when assessors or users disagree. With probability $p = 0.55$ the labels are $(y_A, y_B) = (1, 0)$, and otherwise they are $(0, 2)$. The gain is $2^{y} - 1$, so the gains are $(1, 0)$ or $(0, 3)$.
The order that is best for nDCG. In either case exactly one document is relevant. A ranking that puts it first has nDCG 1, and one that puts it second has nDCG $1/\log_2 3 = 0.6309$, whatever its gain, because nDCG divides by the ideal. Ranking $A$ first is right with probability 0.55, for an expected nDCG of $0.55 + 0.45 \times 0.6309 = 0.8339$. Ranking $B$ first gives $0.45 + 0.55 \times 0.6309 = 0.7970$. So $A$ should be first.
What ListNet's minimizer does. The expected loss is $\mathbb{E}\big[-\sum_j P_y(j) \log P_s(j)\big] = -\sum_j \mathbb{E}[P_y(j)] \log P_s(j)$, because the loss is linear in the target. That is a cross entropy with the averaged target, and it is smallest when $P_s(j) = \mathbb{E}[P_y(j)]$. The softmax of the labels $(1, 0)$ is $(0.7311, 0.2689)$, and of $(0, 2)$ it is $(0.1192, 0.8808)$. So
$$\mathbb{E}[P_y(A)] = 0.55 \times 0.7311 + 0.45 \times 0.1192 = 0.4557, \qquad \mathbb{E}[P_y(B)] = 0.5443.$$
The minimizing scores have $s_A - s_B = \log(0.4557/0.5443) = -0.1776$: ListNet puts $B$ first. With all the data in the world it converges on the ordering with the lower expected nDCG. The cause is visible in the two softmax vectors. A label of 2 makes a more confident target than a label of 1, so the less frequent case outweighs the more frequent one, although for nDCG, which normalizes each occasion, the two cases count equally.
A repair. Replace the target by the normalized gain $t_j = g_j / \mathrm{maxDCG}$, without rescaling it to sum to 1, and minimize $-\sum_j t_j \log P_s(j)$. The same linearity argument gives $P_s(j)$ proportional to $\mathbb{E}[t_j]$ at the minimum, which here is $(0.55, 0.45)$, so $s_A - s_B = \log(0.55/0.45) = 0.2007$ and $A$ is first. In general, expected nDCG without a cutoff is $\sum_j D(r_j)\, \mathbb{E}[t_j]$, which is largest when the documents are sorted by $\mathbb{E}[t_j]$, by the exchange argument that nDCG uses for the ideal ranking. So this target orders documents optimally for expected nDCG whenever the minimizer can be reached. It is in the spirit of the normalization Ravikumar and colleagues propose; their construction is more general and is not reproduced here.
ListMLE in this example sees the ordering $(A, B)$ with probability 0.55 and $(B, A)$ otherwise. Its expected loss is $0.55 \log(1 + e^{-d}) + 0.45 \log(1 + e^{d})$ with $d = s_A - s_B$, smallest where $1/(1 + e^{-d}) = 0.55$, that is $d = 0.2007$. It orders the two correctly here. The example was built to separate the losses and does not show that ListMLE is consistent for nDCG in general.
Experiments
Cranfield
The setting is the overview's: BM25's top 100 abstracts for each of 225 queries, eight features, a linear model, 5-fold cross-validation over queries repeated with 30 seeded fold assignments, the same assignments the overview used. The labels are the gains 0 to 4. ListMLE is trained as the overview trained ListNet, by 300 steps of batch gradient descent, with a smaller step because its gradients are larger. As a check on the code, this article's implementation of ListNet reproduces the overview's ListNet result for the first fold assignment to five decimals.
| Loss | MAP, median of 30 (IQR) | nDCG@10, median (IQR) |
|---|---|---|
| BM25 alone | 0.307 | 0.368 |
| ListNet (from the overview) | 0.315 (0.315 to 0.316) | 0.385 (0.384 to 0.386) |
| ListMLE, whole ordering | 0.315 (0.314 to 0.315) | 0.382 (0.381 to 0.383) |
| ListMLE, relevant positions only | 0.311 (0.310 to 0.312) | 0.379 (0.379 to 0.380) |
All three land within 0.004 of each other in MAP and 0.006 in nDCG@10, close to the pairwise methods of the overview and for the reason given there: the eight features carry nearly the same evidence. The differences between the losses are small but consistent across the fold assignments, which are the same for all three: ListNet had the higher nDCG@10 than the whole-ordering likelihood in 26 of the 30, the whole-ordering likelihood higher than the restricted form in 28, and ListNet higher than the restricted form in 30. On this collection ListNet is not worse than either likelihood.
Fitting each loss to all the queries shows how differently they behave even when their rankings are similar.
- ListNet. The mean loss per query falls from $\log 100 = 4.605$ at zero weights to 4.464. The largest weights are 0.88 on title BM25 and 0.75 on BM25.
- ListMLE on the whole ordering. The loss starts at $\log 100! = 363.74$ and ends at 363.33, a fall of 0.11 percent, and no weight exceeds 0.25 in size (the largest is 0.22, on title BM25). Nearly all of the loss is the cost of predicting an arbitrary order among some 95 nonrelevant abstracts, which no model can predict. That part pulls every score toward equality, since equal scores are the best guess about a random order, and it dominates the few terms that concern the relevant abstracts.
- ListMLE on the relevant positions. The loss falls from 23.37 to 19.39, and the weights are the largest of the three: 1.95 on title BM25 and 1.34 on BM25.
A ranking depends only on the direction of the weight vector, which is why three models with such different scales rank almost alike.
LETOR MQ2008
MQ2008 is one of the LETOR 4.0 datasets (Qin and Liu, 2013): 784 queries, 15,211 query-document rows, 46 features and labels 0, 1 and 2, with five predefined folds, each splitting the queries into training, validation and test parts. Features for Ranking describes it. Following the unit's convention, the measure is nDCG@10 with gain $2^y - 1$, averaged over the test queries that have at least one relevant document and then over the five folds. The models are linear and trained by stochastic gradient descent in batches of 16 queries for 40 passes, keeping the weights from the pass with the best validation nDCG@10. The learning rate of each loss 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: 0.3 for ListNet, 0.03 for ListMLE on the whole ordering and 0.3 for the restricted form. The seed sets the order of the batches and, for ListMLE, the choice among tied orderings.
| Loss | Test nDCG@10, median of 30 seeds (IQR) |
|---|---|
| ListNet | 0.696 (0.695 to 0.698) |
| ListMLE, whole ordering | 0.689 (0.686 to 0.694) |
| ListMLE, relevant positions only | 0.698 (0.696 to 0.702) |
Here the likelihood restricted to the relevant positions is level with ListNet, and the likelihood of the whole ordering is lower by about 0.007 to 0.009, with interquartile ranges that do not overlap the others'. In MQ2008, 81 percent of the rows have label 0, so here too most positions of an ordering are filled by documents whose order is arbitrary, and the whole-ordering likelihood spends its effort on that order. On Cranfield the restricted form was the lowest of the three, so the two collections do not agree on its merit. These are observations on two small collections with linear models. They do not establish an ordering of the losses, and the experiments of Xia and colleagues, who report ListMLE ahead of ListNet on their data, used different datasets and target mappings.
What is proved, what is cited, what the experiment shows
Proved on this page: that the Plackett-Luce probabilities sum to 1; the product form for the first $k$ positions and the softmax form of the top one probability; that the pairwise marginal is RankNet's probability; that the sorted ordering is the most probable; that the top one distribution determines the scores up to a constant; the gradients of ListNet and ListMLE; the convexity of both; that ListMLE on two documents is RankNet's cost; the minimizer of the expected ListNet loss and the two-document case in which it contradicts expected nDCG, with a target that repairs it.
Cited: the definitions (Cao et al., 2007; Xia et al., 2008); the consistency of the likelihood loss and of the permutation-level cross entropy for the zero-one loss on permutations (Xia et al., 2008, Theorem 5 and Propositions 6 and 8, whose proofs the paper omits or sketches); the characterization of nDCG consistency and the inconsistency of ListNet's loss in general (Ravikumar et al., 2011); the upper bounds on $1 - \mathrm{nDCG}$ (Chen et al., 2009). The works of Plackett (1975) and Luce (1959) are cited for the model's origin as Cao and colleagues describe it; they were not read for this article.
Shown by the experiment: on Cranfield and MQ2008 with linear models, the three losses differ by less than 0.01 in nDCG@10; the whole-ordering likelihood is dominated by the order of nonrelevant documents; which form of ListMLE does better differs between the two collections.
Worked problems
This unit has no course assignments, so the problems below are posed on small exact cases. The script recomputes every number.
Problem 1 (a model with a tie). Three documents have scores $(1, 0, 0)$. Find the Plackett-Luce probability of each of the six orderings, and check that they sum to 1.
Solution. The orderings that start with $a$ have probability 0.2881 each; $b, a, c$ and $c, a, b$ have 0.1549 each; $b, c, a$ and $c, b, a$ have 0.0570 each. The weights are $e = 2.718$, 1 and 1, with total 4.718. For $a, b, c$: the first factor is $2.718/4.718 = 0.5761$ and the second is $1/(1 + 1) = 0.5$, giving 0.2881; $a, c, b$ is the same by symmetry. For $b, a, c$: $\tfrac{1}{4.718} \cdot \tfrac{2.718}{2.718 + 1} = 0.2119 \times 0.7311 = 0.1549$. For $b, c, a$: $\tfrac{1}{4.718} \cdot \tfrac{1}{1 + 2.718} = 0.2119 \times 0.2689 = 0.0570$. The total is $2(0.2881) + 2(0.1549) + 2(0.0570) = 1.0000$. Equal scores give equal probabilities to orderings that differ only by exchanging the tied documents. This is the target distribution $P_y$ that ListNet would use for the labels $(1, 0, 0)$ at the level of permutations.
Problem 2 (ListMLE by hand). Three documents have scores $s_a = 0.5$, $s_b = 1.5$, $s_c = 0$, and the judged ordering is $a, b, c$. Compute the ListMLE loss and its gradient.
Solution. The loss is 1.6658 and the gradient is $(-0.7688, 0.4461, 0.3227)$. The stage totals are $Z_1 = e^{0.5} + e^{1.5} + 1 = 7.1304$ and $Z_2 = e^{1.5} + 1 = 5.4817$. The loss is $(\log Z_1 - 0.5) + (\log Z_2 - 1.5) = (1.9644 - 0.5) + (1.7014 - 1.5) = 1.6658$. For the gradient, document $a$ is available at stage 1 only: $e^{0.5}/Z_1 - 1 = 0.2312 - 1 = -0.7688$. Document $b$ is available at stages 1 and 2: $e^{1.5}/Z_1 + e^{1.5}/Z_2 - 1 = 0.6285 + 0.8176 - 1 = 0.4461$. Document $c$ is available at every stage: $1/Z_1 + 1/Z_2 + 1 - 1 = 0.1402 + 0.1824 = 0.3227$ from the unrounded values. The three sum to zero. The model has $b$ ahead of $a$, against the judgment, and the gradient lowers $b$ and raises $a$; it also lowers $c$, which is correctly last but not yet far enough behind for the likelihood.
Problem 3 (what the labels' scale does to ListNet). For the scores $(2, 1, 0)$, compare the ListNet loss and its smallest possible value under the labels $(1, 0, 0)$ and under $(2, 0, 0)$.
Solution. Under $(1, 0, 0)$ the loss is 1.043 and its minimum is 0.975; under $(2, 0, 0)$ the loss is 0.727 and its minimum is 0.666. The target for $(2, 0, 0)$ is the softmax $(0.7870, 0.1065, 0.1065)$. The model's top one probabilities are $(0.6652, 0.2447, 0.0900)$ in both cases. The loss is $-(0.7870 \log 0.6652 + 0.1065 \log 0.2447 + 0.1065 \log 0.0900) = 0.727$, and the minimum, attained at scores equal to the labels, is the entropy of the target, 0.666. The excess over the minimum is 0.068 under the first labels and 0.062 under the second. More telling is the direction of the gradient $P_s - P_y$ for document $a$: $0.6652 - 0.5761 > 0$ under the first labels, so $a$'s score should fall, and $0.6652 - 0.7870 < 0$ under the second, so it should rise. The same judgment, "only $a$ is relevant", asks for opposite changes depending on the number used to write it.
Problem 4 (a top two probability). Under the scores $(2, 1, 0)$, find the probability that $b$ is ranked first and $a$ second, and relate it to the table of six orderings.
Solution. It is 0.2156. By property 2 it is the product of the first two factors: $b$ is chosen first with probability $e/11.107 = 0.2447$, and then $a$ is chosen from $\{a, c\}$ with probability $e^2/(e^2 + 1) = 0.8808$, giving $0.2447 \times 0.8808 = 0.2156$ from the unrounded values. With three documents, fixing the first two fixes the third, so this is the probability of the single ordering $b, a, c$ in the table. With more documents it would be the sum over all orderings that begin $b, a$, and the product form saves the enumeration.
What we have learned
The Plackett-Luce model gives every ordering of a list a probability by choosing documents one at a time with probability proportional to $e^{\text{score}}$. Its probabilities sum to 1, its first positions have a product form, any two documents are ordered with RankNet's probability, and the sorted ordering is the most probable. ListNet takes the cross entropy between the top one distributions of the labels and of the scores; its gradient is their difference, and its minimum is at scores equal to the labels, so it depends on the numbers used for the grades. ListMLE takes the negative log-likelihood of a judged ordering; its gradient adds up the probability each document received while it was available, it is convex and linear-time, and it must break ties among equal grades arbitrarily unless the product is stopped after the relevant documents. Both are consistent for the strict zero-one loss on permutations according to Xia and colleagues, and ListNet's loss is not consistent for nDCG, as a two-document example shows directly. On Cranfield and MQ2008 the losses differed by less than 0.01 in nDCG@10.
Every method so far has learned from judgments. The last article of the unit, Learning from Clicks, takes up what changes when the labels are clicks, which are observed only where a user looked.
References
- Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., and Li, H. (2007). Learning to rank: From pairwise approach to listwise approach. In Proceedings of ICML 2007, 129–136. Definition, lemma and theorem numbers follow the technical report version, Microsoft Research MSR-TR-2007-40. record · 2 pages
- Chen, W., Liu, T.-Y., Lan, Y., Ma, Z., and Li, H. (2009). Ranking measures and loss functions in learning to rank. In Advances in Neural Information Processing Systems 22 (NIPS 2009). record
- Luce, R. D. (1959). Individual Choice Behavior. Wiley. record
- Plackett, R. L. (1975). The analysis of permutations. Applied Statistics, 24(2), 193–202. record
- Qin, T., and Liu, T.-Y. (2013). Introducing LETOR 4.0 datasets. arXiv:1306.2597. record · 6 pages
- Ravikumar, P., Tewari, A., and Yang, E. (2011). On NDCG consistency of listwise ranking methods. In Proceedings of AISTATS 2011, PMLR 15, 618–626. record
- Xia, F., Liu, T.-Y., Wang, J., Zhang, W., and Li, H. (2008). Listwise approach to learning to rank: Theory and algorithm. In Proceedings of ICML 2008, 1192–1199. record