The probabilistic retrieval unit ended with several scores for every Cranfield abstract and query 185, experimental studies on panel flutter: BM25, TF-IDF, the Binary Independence Model, query likelihood. Each was designed by hand, from a model of how words relate to relevance. A real engine has many more signals, such as matches in the title, the proximity of query words, and on the web, links and clicks. No one can hand-tune a formula over hundreds of them. Can the combination be learned, the way this unit's classifiers learned from labeled documents?
Learning to rank is the use of supervised machine learning to build a ranking function. Each query-document pair is described by a vector of features, numbers computed from the query, the document or both. A model is trained on queries whose documents have been judged, and learns to score pairs so that sorting by score puts the more relevant documents first. Manning, Raghavan and Schütze (2008, §15.4) introduce the idea in their chapter on support vector machines, as an application of classification. The weighted zone scoring article already learned one such combination, the weights of a document's zones, from judgments (§6.1.2).
Here is the route. First we treat ranking as classification and work the textbook's two-feature example. Then we see why ranking is better posed as ordering, and derive the three families of training objectives: pointwise, pairwise and listwise. Next we train all three on Cranfield with eight features and compare them with BM25 in cross-validation. Finally we look at where learning to rank pays off and where it went next. The article assumes linear classifiers and evaluating classifiers from this unit, and nDCG.
Ranking as classification
The textbook's example has two features for each query-document pair (Manning, Raghavan, and Schütze, 2008, Table 15.3):
- $\alpha$, the vector space cosine score of the document for the query;
- $\omega$, the width of the smallest window of text containing all the query terms. A small window means the words occur close together, which is often a sign that the document is about the query as a phrase.
Each pair is judged relevant or nonrelevant:
| Query | Document | $\alpha$ | $\omega$ | Judgment |
|---|---|---|---|---|
| linux operating system | 37 | 0.032 | 3 | relevant |
| penguin logo | 37 | 0.020 | 4 | nonrelevant |
| operating system | 238 | 0.043 | 2 | relevant |
| runtime environment | 238 | 0.004 | 2 | nonrelevant |
| kernel layer | 1741 | 0.022 | 3 | relevant |
| device driver | 2094 | 0.030 | 2 | relevant |
| device driver | 3191 | 0.027 | 5 | nonrelevant |
Coding relevant as 1 and nonrelevant as 0, we look for a linear score
$$\mathrm{Score}(d, q) = a\,\alpha + b\,\omega + c$$
that is high for the relevant examples and low for the others, then a threshold $\theta$ that separates them (§15.4.1). The set of points where the score equals $\theta$ is a line in the $(\alpha, \omega)$ plane, so this is exactly the linear classification problem of vector space classification, with query-document pairs in place of documents.
Check your understanding. Which signs should $a$ and $b$ have?
$a$ positive and $b$ negative: a higher cosine and a narrower window both indicate relevance. One line that works, found by inspection rather than by training, is $100\,\alpha - \omega = -1$. Scoring $100\,\alpha - \omega$, the relevant examples get $+0.2$, $+2.3$, $-0.8$ and $+1.0$, and the nonrelevant ones $-2.0$, $-1.6$ and $-2.3$. Every relevant example is above $-1$ and every nonrelevant one below it.
To rank, the threshold is dropped and documents are sorted by score. The textbook notes that ordering documents by a classifier's confidence in its relevance decision "is sometimes used in practice" (§15.4). Its next section explains why it is not the most natural formulation.
Why ranking is not classification
Look again at the table. Document 3191, nonrelevant for device driver, has a higher cosine (0.027) than document 1741, relevant for kernel layer (0.022). A classifier must put both on one scale of relevance, so the cosine alone cannot classify both correctly. A ranking never compares them: they answer different queries and never appear in the same list. Only one pair in the table is ever ranked against each other, the two device driver documents, 2094 (relevant) and 3191 (nonrelevant).
The textbook calls ranking an ordinal regression problem: the goal is an ordering of documents for each query, not a label for each pair (§15.4.2). That changes the problem in two ways. It adds power, since a document need only be compared with other candidates for the same query. It also weakens the requirement, since no absolute measure of relevance is needed. Relevance judgments are also often graded, and the evaluation measures that matter, such as nDCG and average precision, reward the top of the list far more than the bottom. Liu (2009) groups the training methods that followed into three approaches, by what a single training example is:
- Pointwise: one query-document pair, with its label. The model predicts relevance, as a classifier or a regression.
- Pairwise: two documents for the same query, with which should rank higher.
- Listwise: the whole candidate list for a query.
All three train the same kind of model, a function $f(\mathbf{x})$ that gives a score to a feature vector $\mathbf{x}$. They differ in the loss that training minimizes.
Pairwise learning
Here is the idea in one sentence: turn each pair of documents for the same query, one more relevant than the other, into a training example, and penalize the model when it scores the less relevant one higher.
Ranking SVM. For documents $d_i$ and $d_j$ with feature vectors $\Psi(d_i, q)$ and $\Psi(d_j, q)$, form the difference
$$\Phi(d_i, d_j, q) = \Psi(d_i, q) - \Psi(d_j, q).$$
If $d_i$ was judged more relevant, the model should satisfy $\mathbf{w}^{\mathsf{T}} \Phi(d_i, d_j, q) > 0$. The ranking SVM, which Cao et al. (2007) credit to Herbrich and colleagues, finds $\mathbf{w}$ by minimizing $\tfrac{1}{2}\mathbf{w}^{\mathsf{T}}\mathbf{w} + C \sum \xi_{i,j}$ subject to $\mathbf{w}^{\mathsf{T}}\Phi(d_i, d_j, q) \ge 1 - \xi_{i,j}$ and $\xi_{i,j} \ge 0$ for every such pair (Manning, Raghavan, and Schütze, 2008, eqs. 15.18 to 15.20). It is a two-class SVM on difference vectors. In the textbook's table, the one usable pair gives $\Phi = (0.030 - 0.027,\ 2 - 5) = (0.003, -3)$, and the line above scores it $100 \times 0.003 + 3 = 3.3 > 0$, ranking the pair correctly. Joachims (2002) trained a ranking SVM on preferences derived from the results that users clicked in a search engine's logs, in place of expert judgments.
RankNet. Burges and colleagues (2005) gave the pairwise idea a probabilistic loss, trained by gradient descent. The model scores two documents, $s_i = f(\mathbf{x}_i)$ and $s_j = f(\mathbf{x}_j)$, and the difference becomes the probability that $d_i$ should rank above $d_j$:
$$P_{ij} = \frac{1}{1 + e^{-\sigma (s_i - s_j)}},$$
where $\sigma$ sets the steepness of the sigmoid. The loss is the cross entropy between $P_{ij}$ and the target probability $\bar P_{ij}$, which is 1 if $d_i$ was judged more relevant:
$$C = -\bar P_{ij} \log P_{ij} - (1 - \bar P_{ij}) \log (1 - P_{ij}).$$
For a pair with $d_i$ more relevant, this is $C = \log\big(1 + e^{-\sigma(s_i - s_j)}\big)$ (Burges, 2010, §2). It equals $\log 2$ when the two scores are equal, falls toward 0 as $s_i$ pulls ahead, and grows linearly when the pair is misordered. Its derivative with respect to the score $s_i$ is
$$\lambda_{ij} = \frac{\partial C}{\partial s_i} = \frac{-\sigma}{1 + e^{\sigma (s_i - s_j)}},$$
and $\partial C / \partial s_j = -\lambda_{ij}$. Burges calls the $\lambda$s forces. Each document collects one from every pair it belongs to, and the sum says how far and in which direction its score should move.
Optimizing the measure directly
RankNet minimizes a smooth stand-in for the number of misordered pairs. The measures people care about are different. nDCG and average precision change only when two documents swap places, so as functions of the scores they are flat almost everywhere and jump at the swaps. Gradient descent cannot use them directly (Burges, 2010, §3).
Here is the problem in numbers. Take ten documents for a query with one relevant document at rank 1 and another at rank 10, and binary gains with the logarithmic discount of nDCG. The ranking's nDCG is $(1 + 1/\log_2 11)/(1 + 1/\log_2 3) = 1.289/1.631 = 0.790$. Moving the first relevant document from rank 1 to rank 3 creates two misordered pairs and lowers nDCG to $(1/\log_2 4 + 1/\log_2 11)/1.631 = 0.484$. Moving the second from rank 10 to rank 4 fixes six misordered pairs and raises nDCG only to $(1 + 1/\log_2 5)/1.631 = 0.877$. Counted in pairs, the second move is three times as important as the first; counted in nDCG, the first matters far more. Burges's schematic example makes the same point: a change that reduces pairwise errors from thirteen to eleven, by pushing the top relevant document down, is not what a top-weighted measure wants.
LambdaRank (Burges, Ragno, and Le, 2006) writes down the gradient it wants instead of deriving it from a loss. It multiplies RankNet's $\lambda_{ij}$ by the change in nDCG that swapping $d_i$ and $d_j$ would cause, with every other document left in place:
$$\lambda_{ij} = \frac{-\sigma}{1 + e^{\sigma (s_i - s_j)}}\, \big|\Delta \mathrm{NDCG}_{ij}\big|.$$
A misordered pair near the top of the current ranking now pushes much harder than one far down. Burges (2010, §4) reports that this was found empirically to optimize nDCG directly, and that replacing nDCG by another measure, such as MAP, adapts the method to that measure.
LambdaMART combines the same $\lambda$ gradients with gradient-boosted regression trees, a model that is built by adding small trees, each fitted to the current gradients (Wu, Burges, Svore, and Gao, 2010; see Boosting). Unlike a linear model, the trees can learn interactions between features. An ensemble of LambdaMART rankers won Track 1 of the 2010 Yahoo! Learning to Rank Challenge (Burges, 2010; Chapelle and Chang, 2011). PubMed's Best Match ranking, described in search in professional domains, re-ranks BM25's candidates with LambdaMART trained on clicks from PubMed's search logs (Fiorini et al., 2018).
Listwise learning
The listwise approach defines the loss on the whole candidate list. ListNet (Cao et al., 2007) turns a list of scores into a probability distribution over which document is ranked first, the top one probability:
$$P_s(j) = \frac{e^{s_j}}{\sum_{k} e^{s_k}}.$$
The judged relevance labels $y_j$ are turned into a distribution $P_y(j)$ the same way, and the loss is the cross entropy between them, $-\sum_j P_y(j) \log P_s(j)$. A model whose scores put the most probability on the most relevant documents has a low loss. Cao et al. reported that ListNet outperformed three pairwise methods, Ranking SVM, RankBoost and RankNet, on three retrieval datasets.
An experiment on Cranfield
Cranfield has 225 judged queries, enough to train and test a small learned ranker. The experiment follows the usual two-stage design: BM25 retrieves the top 100 abstracts for each query, a learned model re-orders them, and the documents below rank 100 keep BM25's order. The top 100 contain 1,114 of the collection's 1,612 relevant query-document pairs, 69%, so no re-ranker can reach the rest. Seven queries have no relevant abstract in their top 100.
Features
Every candidate is described by eight features, most of them scores from earlier articles:
- BM25 ($k_1 = 1.2$, $b = 0.75$);
- TF-IDF cosine (lnc.ltc);
- the Binary Independence Model without relevance information;
- query likelihood with Dirichlet smoothing, $\mu = 200$;
- BM25 over the title alone, a crude stand-in for the field weighting of BM25F;
- coverage, the fraction of the query's distinct terms that the abstract contains;
- proximity, the reciprocal of the smallest distance in tokens between two different query terms, a version of the textbook's window width;
- the logarithm of the abstract's length.
Each feature is rescaled to run from 0 to 1 within each query's candidates. Raw BM25 scores differ greatly between queries, and only comparisons within a query matter.
Before any learning, each feature alone can re-rank the candidates. MAP over all 225 queries, rounded to three decimals:
| Feature alone | MAP |
|---|---|
| BM25 | 0.307 |
| proximity | 0.299 |
| TF-IDF | 0.294 |
| query likelihood | 0.287 |
| title BM25 | 0.277 |
| BIM | 0.229 |
| coverage | 0.228 |
| length (shortest first) | 0.101 |
Four learned rankers
All four models are linear, $f(\mathbf{x}) = \mathbf{w}^{\mathsf{T}}\mathbf{x}$, trained by gradient descent:
- pointwise: logistic regression on relevant versus nonrelevant, with the classes weighted equally, ranking by the predicted score;
- RankNet: the pairwise loss above, $\sigma = 1$, over every pair of candidates with different relevance grades;
- LambdaRank: the same, with each pair's gradient multiplied by $|\Delta \mathrm{nDCG@10}|$;
- ListNet: the top one cross entropy, with targets from the graded labels.
The graded labels use the gains of the nDCG article (4 for Cranfield's grade 1 down to 1 for grade 4). Each model was evaluated by 5-fold cross-validation over queries: trained on four fifths of the queries, tested on the rest, five times, so that every query is ranked by a model that never saw its judgments. Because the assignment of queries to folds is random, the whole procedure was repeated with 30 seeded assignments.
Results:
| Ranker | MAP, median of 30 (IQR) | nDCG@10, median (IQR) | Improved / harmed vs. BM25 | $p$ |
|---|---|---|---|---|
| BM25 alone | 0.307 | 0.368 | ||
| Pointwise | 0.314 (0.313–0.314) | 0.385 (0.384–0.385) | 130 / 78 | 0.26 |
| RankNet | 0.314 (0.313–0.315) | 0.384 (0.383–0.384) | 126 / 84 | 0.49 |
| LambdaRank | 0.314 (0.314–0.315) | 0.382 (0.382–0.384) | 128 / 79 | 0.14 |
| ListNet | 0.315 (0.315–0.316) | 0.385 (0.384–0.386) | 130 / 77 | 0.16 |
IQR is the interquartile range over the 30 fold assignments. The counts and $p$ values are for the first fold assignment, from a paired randomization test on per-query average precision (see significance testing). Every learned ranker gained about 0.007 to 0.008 in MAP and 0.014 to 0.017 in nDCG@10, and none of the gains was significant. The four training objectives made almost no difference. LambdaRank, the one that weights its gradients by nDCG@10, had the lowest nDCG@10 of the four.
Check your understanding. The learned rankers combine eight signals, and BM25 is only one of them. Why might they gain so little?
Because the eight signals say nearly the same thing. Seven of them are computed from which query terms an abstract contains, how often, and where. When the learned rankers were trained and scored on all 225 queries, with no held-out data at all, their MAP was still only 0.314 to 0.316. A model that cannot do better on its own training queries is limited by its features, not by the amount of training data. The textbook observes that machine learning is good at weighting features in a linear combination but not at inventing the nonlinear scalings, such as the logarithm of term frequency or IDF, that traditional weighting relies on (§15.4.2). Every useful scaling here was already built into BM25.
Reading the weights
Fitted on all 225 queries, the pointwise model's weights were BM25 +2.08, title BM25 +2.17, TF-IDF +1.46, BIM +0.62, proximity +0.56, query likelihood −0.48, coverage −0.57 and length +0.01. RankNet's had the same signs, except for a small negative weight on length (−0.11), and gave query likelihood −2.01.
It would be tempting to read the negative weight on query likelihood as a finding that the score indicates non-relevance. That reading is wrong. Query likelihood alone ranks better than all but three features. Its correlation with BM25 over all candidates is 0.83, and with TF-IDF 0.87. When features are strongly correlated, a linear model can trade weight between them almost freely, and a negative weight on one often corrects for overcounting the evidence the others share. The weights describe the combination, not the value of each feature on its own.
Query 185
Learned rankers are judged on average, and individual queries can lose. For query 185, the RankNet model that held it out in the first fold assignment re-ranked BM25's list to an average precision of 0.511, against BM25's 0.784.
The trace shows why. With RankNet's weights from all queries, which give the same average precision, the top of the list is decided largely by title BM25 (weight +2.37), because proximity is no help: almost every candidate has panel and flutter side by side, so the feature is 1.0 for all ten. Abstract 864, "status of flutter of flat and curved panels", is nonrelevant, but its short title holds both words and it rises to rank 1. Relevant abstracts 766 and 858 have long titles (766 is "experimental investigation at mach number of 3.0 of effects of thermal stress and buckling on flutter characteristics of flat single-bay panels of length-width ratio 0.96") in which the query words weigh less, and they fall from ranks 3 and 5 to 12 and 10. A weight that helps on average, because titles usually state a paper's subject, hurts a query whose relevant documents have wordy titles.
Where learning to rank pays off
On Cranfield, learning had little to work with: few features, all variations on term matching, and a small number of judged queries. The settings in which learning to rank became standard differ on each count.
- Many and different signals. Web search combines text matches over many fields with link-based authority such as PageRank, freshness, and the behavior of past users (see how web search answers a query). Such signals are not variations on one another, and no single formula combines them well.
- Much more training data. The two datasets released for the Yahoo! challenge held about 36,000 queries and 883,000 documents, described by 700 different features (Chapelle and Chang, 2011). Logs of clicks supply preferences at a far larger scale, although clicks are biased toward the top of the ranking, as online evaluation shows.
- Nonlinear models. Gradient-boosted trees such as LambdaMART learn interactions and transformations that a linear model cannot.
The textbook places the ideas in history. Learned ranking was pioneered in the late 1980s and early 1990s, by Fuhr among others, but "limited training data and poor machine learning techniques meant that these pieces of work achieved only middling results" (§15.5). Section 15.4.2 expects the use of learned ranking to grow, because hand tuning "has to be done again for each new document collection and class of users" (§15.4.2).
Neural re-rankers
The same two-stage design now often ends in a neural network that reads the query and the document text together. Nogueira and Cho (2019) fine-tuned the pretrained language model BERT to judge whether a passage answers a query, and used it to re-rank the passages BM25 retrieved. It substantially outperformed previous methods on passage ranking benchmarks. Their model was trained pointwise, as a binary classifier of relevance with a cross-entropy loss, which is a reminder that the simplest formulation of learning to rank remains useful when the model is powerful enough to learn its own features.
What we have learned
A ranking function can be learned like a classifier, from judged query-document pairs described by features. Treating each pair separately ignores that only documents for the same query are ever compared, and that the top of the list matters most. Pairwise methods (Ranking SVM, RankNet) learn from preferences within a query, LambdaRank and LambdaMART scale each preference by its effect on nDCG, and listwise methods such as ListNet define the loss on whole lists. On Cranfield, four learned linear combinations of eight term-matching features came within about 0.01 of BM25 alone, and their own training queries showed that the features, not the learning, were the limit.
This closes the unit on text classification. Every method in it learned from documents that someone had labeled. What can be learned from a collection when nobody has labeled anything? Clustering and the cluster hypothesis begins the next unit.
References
- Burges, C. J. C. (2010). From RankNet to LambdaRank to LambdaMART: An overview. Microsoft Research Technical Report MSR-TR-2010-82. record
- 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
- 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 · 3 pages
- 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. record
- 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
- Fiorini, N., Canese, K., Starchenko, G., Kireev, E., Kim, W., Miller, V., Osipov, M., Kholodov, M., Ismagilov, R., Mohan, S., Ostell, J., and Lu, Z. (2018). Best Match: New relevance search for PubMed. PLOS Biology, 16(8), e2005343. record · 2 pages
- Joachims, T. (2002). Optimizing search engines using clickthrough data. In Proceedings of KDD 2002, 133–142. record
- Liu, T.-Y. (2009). Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 3(3), 225–331. record · 2 pages
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 6.1.2, 15.4 and 15.5. Cambridge University Press. record · 83 pages
- Nogueira, R., and Cho, K. (2019). Passage re-ranking with BERT. arXiv:1901.04085. record · 2 pages
- 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