Elamur Research
☰
home / papers / 2005 / Learning to Rank using Gradient Descent

Learning to Rank using Gradient Descent

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "author's copy (Microsoft Research) — read only" does not allow redistributing the text itself. Original — microsoft.com/en-us/research/wp-content/uploads/2005/08/icml ranking.pdf

Summary

The paper addresses learning to rank web search results. Documents are compared only against others returned for the same query, and only their relative order matters. Earlier methods such as PRank framed this as ordinal regression with learned rank thresholds. The authors argue that this solves a harder problem than necessary. Instead, they learn a real-valued scoring function from ordered pairs of documents. A logistic function maps the difference between two scores to the probability that one document should outrank the other, and the model is trained with cross-entropy against target pair probabilities. This cost works with any differentiable model. Here it is paired with neural networks trained by an extended backpropagation, a combination they call RankNet. They also show how pairwise target probabilities can be combined consistently. On data from a commercial search engine, RankNet beat PRank variants and RankProp on NDCG, while remaining reasonably fast to train. The work matters because it provides a simple, probabilistic, scalable pairwise ranking loss. It became a foundation for later learning-to-rank systems.

Key points

  • The dataset contains 17,004 queries, each with up to 1,000 documents pre-ranked by a simpler system. It was split into 11,336 training, 2,834 validation and 2,834 test queries, and only about 1% of test documents carry relevance labels.
  • Test NDCG@15 results:
    • two-layer RankNet (10 hidden units): 0.488
    • linear RankNet: 0.477
    • RankProp: 0.460
    • OAP-BPM (large-margin PRank): 0.454
    • linear PRank: 0.412
    • quadratic PRank: 0.327
  • Kernel PRank needed over 12 hours per epoch, so it was approximated with explicit quadratic features (162,734 dimensions). Training that version took about 40 hours, compared with about 6 hours for the two-layer RankNet.
  • A theorem shows that target probabilities for adjacent pairs in any ordering are enough to determine consistent probabilities for every pair. Setting a target of 0.5 provides a principled way to train on items of equal rank.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

139 papers of our library cite it (of the 140673 whose bibliographies we read); 8 of them have a page here, 131 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/1102351.1102363

@inproceedings{burges2005learning,
  title = {{Learning to Rank using Gradient Descent}},
  author = {Burges, Chris and Shaked, Tal and Renshaw, Erin and Lazier, Ari and Deeds, Matt and Hamilton, Nicole and Hullender, Greg},
  booktitle = {ICML 2005},
  year = {2005},
  doi = {10.1145/1102351.1102363},
  url = {https://doi.org/10.1145/1102351.1102363}
}

References

18 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Baum, E., & Wilczek, F. (1988). Supervised learning of probability distributions by neural networks. Neural Information Processing Systems (pp. 52–61). find
  2. Bradley, R., & Terry, M. (1952). The Rank Analysis of Incomplete Block Designs 1: The Method of Paired Comparisons. Biometrika, 39, 324–245. find
  3. Bromley, J., Bentz, J.W., Bottou, L., Guyon, I., Le-Cun, Y., Moore, C., Sackinger, E., & Shah, R. (1993). Signature Verification Using a ”Siamese” Time Delay Neural Network. Advances in Pattern Recognition Systems using Neural Network Technologies, World Scientific (pp. 25–44) find
  4. Burges, C. (1996). Simplified support vector decision rules. Proc. International Conference on Machine Learning (ICML) 13 (pp. 71–77). find
  5. Caruana, R., Baluja, S., & Mitchell, T. (1996). Using the future to “sort out” the present: Rankprop and multitask learning for medical risk evaluation. Advances in Neural Information Processing Systems (NIPS) 8 (pp. 959–965). find
  6. Crammer, K., & Singer, Y. (2002). Pranking with ranking. NIPS 14. find
  7. Dekel, O., Manning, C., & Singer, Y. (2004). Log-linear models for label-ranking. NIPS 16. find
  8. Freund, Y., Iyer, R., Schapire, R., & Singer, Y. (2003). An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4, 933–969. find
  9. Harrington, E. (2003). Online ranking/collaborative filtering using the Perceptron algorithm. ICML 20. find
  10. Hastie, T., & Tibshirani, R. (1998). Classification by pairwise coupling. NIPS 10. find
  11. Herbrich, R., Graepel, T., & Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers, MIT Press (pp. 115–132). find
  12. Jarvelin, K., & Kekalainen, J. (2000). IR evaluation methods for retrieving highly relevant documents. Proc. 23rd ACM SIGIR (pp. 41–48). find
  13. Kimeldorf, G. S., & Wahba, G. (1971). Some results on Tchebycheffian Spline Functions. J. Mathematical Analysis and Applications, 33, 82–95. find
  14. LeCun, Y., Bottou, L., Orr, G. B., & Müller, K.-R. (1998). Efficient backprop. Neural Networks: Tricks of the Trade, Springer (pp. 9–50). find
  15. Mason, L., Baxter, J., Bartlett, P., & Frean, M. (2000). Boosting algorithms as gradient descent. NIPS 12 (pp. 512–518). find
  16. Mitchell, T. M. (1997). Machine learning. New York: McGraw-Hill. find
  17. Refregier, P., & Vallet, F. (1991). Probabilistic approaches for multiclass classification with neural networks. International Conference on Artificial Neural Networks (pp. 1003–1006). find
  18. Schölkopf, B., & Smola, A. (2002). Learning with kernels. MIT Press. find