The course ended its treatment of ranking with an overview, Learning to Rank: describe each query-document pair by a vector of features, and learn from judged queries how to combine them. That article names the families of methods, gives the main formulas, and runs four linear rankers on Cranfield, where they barely improve on BM25. It moves fast, because it has one article for a subject that fills books. This unit is the full account behind it. Each method the overview names gets its own article, with its loss derived from first principles, its gradient derived step by step, and its claims separated into what is proved on the page, what is cited from the paper that measured it, and what this site's own experiments show.
The unit has three stages, listed below in four groups. It starts with the inputs, since every method takes the feature vectors as given and no loss can recover information the features lack. It then takes the losses in the order they were invented, which is also the order of their logic: learn from pairs of documents (two articles), then weight the pairs by what the evaluation measure cares about, then define the loss on the whole list. It ends with the source of training data that a working search engine has in abundance, its users' clicks, and the bias that has to be removed before clicks can stand in for judgments. Read the articles in the order listed; each assumes the ones before it.
Start here
- Learning to Rank is the unit's entry point and stays among the course pages. It works the textbook's two-feature example as a classifier, explains why ranking is better posed as ordering than as classification, introduces the pointwise, pairwise and listwise approaches with the Ranking SVM, RankNet, LambdaRank, LambdaMART and ListNet, and reports the Cranfield experiment that the articles below extend. Read it first; every article of the unit assumes it and none repeats it.
What the unit assumes
Besides the overview: nDCG and average precision, the measures the methods are judged by; BM25 and BM25F, which supply features and one of the worked cases; and from the library, logistic regression for the cross entropy, support vector machines for the margin, and regression trees and boosting for the tree ensembles. Online evaluation introduces clicks and their position bias.
What is proved, cited and measured
Derived or proved on the page: that a linear ranker cannot use a feature constant within a query, and exactly what normalization within a query changes; that the Ranking SVM is a support vector machine on difference vectors with no intercept, and that its slack bounds the number of misordered pairs; the RankNet cost, its convexity, its gradient, and the factorization of that gradient into one $\lambda$ per document; the leaf values of a boosted tree as a Newton step; the gradients of the listwise losses; and that the propensity-weighted click loss is unbiased. Cited and not proved: every published experimental result, the consistency theorems for listwise losses, and Joachims's bound relating misordered pairs to average precision.
The experiments use three bodies of data. The first is the overview's: the Cranfield collection, BM25's top 100 candidates for each of 225 queries, eight features, and 5-fold cross-validation repeated for 30 seeded assignments of queries to folds. The second is MQ2008 from the LETOR 4.0 benchmark: 784 web queries with 15,211 judged documents, 46 features, and five predefined folds. The third is this site's own search engine and its 60 judged queries, whose judgments cover only the pages that the site's hand-tuned BM25F placed in each query's top 20; RankNet uses them to learn the BM25F field weights and says what such judgments can and cannot show. All three are small. They are large enough to check derivations and to show mechanisms at work, and too small to rank the methods against each other; where the published record does that, on far larger collections, the articles cite it. Across the unit's experiments the learned rankers end close together. On MQ2008, the learned rankers of the first three articles (linear and two-layer RankNet, the Ranking SVM, least squares, boosted regression trees, under several normalizations) scored between 0.677 and 0.706 in nDCG@10, against 0.689 for the best single feature, a language model score of the whole document; these are means over the 564 test queries that have a relevant document. The next two articles train their linear rankers in minibatches with a learning rate selected on one fold, and report the mean over the five folds (the median over 30 seeds where training is random), under which the same feature scores 0.687. The learned rankers in their MQ2008 tables fall inside the same range, from 0.687 to 0.702, and the lowest of them, a linear model on RankNet's pairwise cost, is level with that feature. Because the protocols differ, one model can score differently on two pages: that linear model scored 0.703 by full-batch gradient descent in RankNet, 0.696 by Adam in Features for Ranking and 0.687 in LambdaRank and LambdaMART; each article states its protocol. Most of the differences between learned rankers are within the variation between folds and seeds or fail a paired test, and the articles say where one does not (the two-layer network on MQ2008 was below the linear model for every seed, and a least-squares regression did worse on features normalized by min-max within queries than on any of the three other versions, by margins that paired tests support before correction for multiple comparisons, and after a Bonferroni correction only against the z-score within queries). The experiments therefore illustrate the methods; they do not decide between them.
Notation
The unit uses one notation, taken from the overview. A query $q$ has candidates $d_1, \dots, d_n$. The pair of the query and candidate $d_i$ has a feature vector $\mathbf{x}_i \in \mathbb{R}^m$ and a label $y_i$, the relevance grade, larger for a better document. A model $f$ gives the score $s_i = f(\mathbf{x}_i)$; a linear model is $f(\mathbf{x}) = \mathbf{w}^{\mathsf{T}}\mathbf{x}$. The set $I$ holds the pairs $(i, j)$ of candidates of one query with $y_i > y_j$, the more relevant first. $\lambda_i$ is the derivative of a query's cost with respect to $s_i$, so a gradient step taken in the scores themselves raises the score of a document whose $\lambda_i$ is negative; a step in a model's parameters moves every score through the shared parameters, and RankNet shows that a document's score can then fall although its $\lambda_i$ is negative. $C$ is a cost, except in Ranking SVM, where it is the support vector machine's constant.
The inputs
- Features for Ranking: the three kinds of feature, by whether they depend on the query, the document or both, with a proof that a linear ranker cannot see the first kind; the LETOR feature lists as a catalogue, checked against the released files; normalization within a query, with proofs of what it can and cannot change and an experiment in which it changes little; and feature importance in tree ensembles, by split gain and by permutation.
Learning from pairs
- Ranking SVM: ordinal regression on pairs. The optimization problem with one slack per pair, a proof that it is a support vector machine on difference vectors, the margin and the support pairs solved exactly on three and four documents, the slack as a bound on misordered pairs, and the preferences that Joachims extracted from clicks.
- RankNet: the pairwise cross entropy and its gradient, derived in full; a proof of the factorization into one $\lambda$ per document that turns a sum over pairs into a sum over documents; two steps of training traced on four Cranfield abstracts; and this site's BM25F field weights learned from its judgments.
Learning for the measure, and from the whole list
- LambdaRank and LambdaMART: the $\lambda$s of RankNet scaled by the change in nDCG that swapping a pair would cause; gradient boosting with regression trees and the Newton step in each leaf, derived; one boosting round computed by hand; and the LambdaLoss account of what is being optimized.
- Listwise Losses: the Plackett-Luce model of permutations; ListNet's top one cross entropy and ListMLE's likelihood, with their gradients; and the consistency results, stated.
Learning from use
- Learning from Clicks: position bias and the examination hypothesis; inverse propensity weighting and the proof that the weighted loss is unbiased; estimating the propensities by swapping results; and a simulation over the Cranfield judgments in which counting clicks misranks the rankers and the weighted estimate recovers their order.
References
- Burges, C. J. C. (2010). From RankNet to LambdaRank to LambdaMART: An overview. Microsoft Research Technical Report MSR-TR-2010-82. record · 4 pages
- Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and Hullender, G. (2005). Learning to rank using gradient descent. In Proceedings of ICML 2005, 89–96. record · 6 pages
- 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
- Herbrich, R., Graepel, T., and Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. In A. J. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans (Eds.), Advances in Large Margin Classifiers, 115–132. MIT Press. record · 2 pages
- Joachims, T. (2002). Optimizing search engines using clickthrough data. In Proceedings of KDD 2002, 133–142. record · 4 pages
- Qin, T., and Liu, T.-Y. (2013). Introducing LETOR 4.0 datasets. arXiv:1306.2597. record · 6 pages
- Qin, T., Liu, T.-Y., Xu, J., and Li, H. (2010). LETOR: A benchmark collection for research on learning to rank for information retrieval. Information Retrieval, 13(4), 346–374. record · 2 pages