Article

Magnitude-preserving ranking algorithms

Authors:

Corinna Cortes,

Ashish RastogiAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 169 - 176

https://doi.org/10.1145/1273496.1273518

Published: 20 June 2007 Publication History

Abstract

This paper studies the learning problem of ranking when one wishes not just to accurately predict pairwise ordering but also preserve the magnitude of the preferences or the difference between ratings, a problem motivated by its key importance in the design of search engines, movie recommendation, and other similar ranking systems. We describe and analyze several algorithms for this problem and give stability bounds for their generalization error, extending previously known stability results to non-bipartite ranking and magnitude of preference-preserving algorithms. We also report the results of experiments comparing these algorithms on several datasets and compare these results with those obtained using an algorithm minimizing the pairwise misranking error and standard regression.

References

[1]

Agarwal, S., & Niyogi, P. (2005). Stability and generalization of bipartite ranking algorithms. Proceedings of the Conference on Learning Theory (COLT 2005) (pp. 32--47). Springer, Heidelberg.

Digital Library

[2]

Bousquet, O., & Elisseeff, A. (2000). Algorithmic stability and generalization performance. Advances in Neural Information Processing Systems (NIPS 1999) (pp. 196--202).

[3]

Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499--526.

Digital Library

[4]

Chu, W., & Keerthi, S. S. (2005). New approaches to support vector ordinal regression. Proceedings of International Conference on Machine Learning (ICML 2005) (pp. 145--152).

Digital Library

[5]

Cossock, D., & Zhang, T. (2006). Subset ranking using regression. Proceedings of the Conference on Learning Theory (COLT 2006) (pp. 605--619). Springer, Heidelberg.

Digital Library

[6]

Crammer, K., & Singer, Y. (2002). Pranking with ranking. Advances in Neural Information Processing Systems (NIPS 2001) (pp. 641--647).

[7]

Freund, Y., Iyer, R., Schapire, R. E., & Singer, Y. (1998). An efficient boosting algorithm for combining preferences. Proceedings of International Conference on Machine Learning (ICML 1998) (pp. 170--178).

Digital Library

[8]

Herbrich, R., Graepel, T., & Obermayer, K. (2000). Large margin rank boundaries for ordinal regression. In Advances in large margin classifiers, 115--132. MIT Press, Cambridge, MA.

[9]

Joachims, T. (2002). Evaluating retrieval performance using clickthrough data. Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information 2002.

[10]

McCullagh, P. (1980). Regression models for ordinal data. Journal of the Royal Statistical Society, B, 42.

[11]

McCullagh, P., & Nelder, J. A. (1983). Generalized linear models. Chapman & Hall, London.

[12]

McDiarmid, C. (1998). Concentration. Probabilistic Methods for Algorithmic Discrete Mathematics (pp. 195--248).

[13]

Rudin, C., Cortes, C., Mohri, M., & Schapire, R. E. (2005). Margin-based ranking meets boosting in the middle. Proceedings of the Conference on Learning Theory (COLT 2005) (pp. 63--78). Springer, Heidelberg.

Digital Library

[14]

Shashua, A., & Levin, A. (2003). Ranking with large margin principle: Two approaches. Advances in Neural Information Processing Systems (NIPS 2002) (pp. 937--944).

[15]

Vapnik, V. N. (1998). Statistical learning theory. New York: Wiley-Interscience.

Cited By

Lei GShi L(2024)Pairwise ranking with Gaussian kernelAdvances in Computational Mathematics10.1007/s10444-024-10165-050:4Online publication date: 10-Jul-2024
https://doi.org/10.1007/s10444-024-10165-0
Vella EChapman ALipovetzky N(2023)Learning User Preferences for Complex Cobotic Tasks: Meta-Behaviors and Human GroupsIEEE Robotics and Automation Letters10.1109/LRA.2023.32796198:7(4123-4130)Online publication date: Jul-2023
https://doi.org/10.1109/LRA.2023.3279619
Mo YChen HHan YDeng H(2022)Error bounds of adversarial bipartite rankingNeurocomputing10.1016/j.neucom.2021.12.078478(81-88)Online publication date: Mar-2022
https://doi.org/10.1016/j.neucom.2021.12.078
Show More Cited By

Magnitude-preserving ranking algorithms
1. Computing methodologies

Recommendations

Re-ranking search results using query logs
CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management

This work addresses two common problems in search, frequently occurring with underspecified user queries: the top-ranked results for such queries may not contain documents relevant to the user's search intent, and fresh and relevant pages may not get ...
Approximation algorithms for diversified search ranking
ICALP'10: Proceedings of the 37th international colloquium conference on Automata, languages and programming: Part II

A fundamental issue in Web search is ranking search results based on user logs, since different users may have different preferences and intents with regards to a search query. Also, in many search query applications, users tend to look at only the top ...
An efficient privacy-preserving multi-keyword search over encrypted cloud data with ranking

Information search and retrieval from a remote database (e.g., cloud server) involves a multitude of privacy issues. Submitted search terms and their frequencies, returned responses and order of their relevance, and retrieved data items may contain ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Machine Learning Journal

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
344
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lei GShi L(2024)Pairwise ranking with Gaussian kernelAdvances in Computational Mathematics10.1007/s10444-024-10165-050:4Online publication date: 10-Jul-2024
https://doi.org/10.1007/s10444-024-10165-0
Vella EChapman ALipovetzky N(2023)Learning User Preferences for Complex Cobotic Tasks: Meta-Behaviors and Human GroupsIEEE Robotics and Automation Letters10.1109/LRA.2023.32796198:7(4123-4130)Online publication date: Jul-2023
https://doi.org/10.1109/LRA.2023.3279619
Mo YChen HHan YDeng H(2022)Error bounds of adversarial bipartite rankingNeurocomputing10.1016/j.neucom.2021.12.078478(81-88)Online publication date: Mar-2022
https://doi.org/10.1016/j.neucom.2021.12.078
Krettler CThallinger G(2021) A map of mass spectrometry-based in silico fragmentation prediction and compound identification in metabolomics Briefings in Bioinformatics10.1093/bib/bbab073Online publication date: 24-Mar-2021
https://doi.org/10.1093/bib/bbab073
Tkachenko PSchmid Cdel Re L(2021)The Linear Functional Strategy for Maneuvers Identification Using Elastic Template MatchingIFAC-PapersOnLine10.1016/j.ifacol.2021.08.39754:7(427-432)Online publication date: 2021
https://doi.org/10.1016/j.ifacol.2021.08.397
Xu QXiong JCao XHuang QYao Y(2021)Evaluating Visual Properties via Robust HodgeRankInternational Journal of Computer Vision10.1007/s11263-021-01438-y129:5(1732-1753)Online publication date: 4-Mar-2021
https://doi.org/10.1007/s11263-021-01438-y
Werner T(2021)A review on instance ranking problems in statistical learningMachine Language10.1007/s10994-021-06122-3111:2(415-463)Online publication date: 18-Nov-2021
https://dl.acm.org/doi/10.1007/s10994-021-06122-3
Lei YLedent AKloft MLarochelle HRanzato MHadsell RBalcan MLin H(2020)Sharper generalization bounds for pairwise learningProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497507(21236-21246)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3497507
Chen HWang YSong BLi H(2020)Debiased magnitude-preserving ranking: Learning rate and bias characterizationJournal of Mathematical Analysis and Applications10.1016/j.jmaa.2020.123881(123881)Online publication date: Jan-2020
https://doi.org/10.1016/j.jmaa.2020.123881
Raschid LSayyadi HHristidis V(2019)Learning to Rank in Entity Relationship GraphsINFORMS Journal on Computing10.1287/ijoc.2018.083731:4(671-688)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1287/ijoc.2018.0837
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents