TY - GEN
T1 - An alternative ranking problem for search engines
AU - Cortes, Corinna
AU - Mohri, Mehryar
AU - Rastogi, Ashish
PY - 2007
Y1 - 2007
N2 - This paper examines in detail an alternative ranking problem for search engines, movie recommendation, and other similar ranking systems motivated by the requirement to not just accurately predict pairwise ordering but also preserve the magnitude of the preferences or the difference between ratings. We describe and analyze several cost functions for this learning 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 present algorithms optimizing these cost functions, and, in one instance, detail both a batch and an on-line version. For this algorithm, we also show how the leave-one-out error can be computed and approximated efficiently, which can be used to determine the optimal values of the trade-off parameter in the cost function. We report the results of experiments comparing these algorithms on several datasets and contrast them with those obtained using an AUC-maximization algorithm. We also compare training times and performance results for the on-line and batch versions, demonstrating that our on-line algorithm scales to relatively large datasets with no significant loss in accuracy.
AB - This paper examines in detail an alternative ranking problem for search engines, movie recommendation, and other similar ranking systems motivated by the requirement to not just accurately predict pairwise ordering but also preserve the magnitude of the preferences or the difference between ratings. We describe and analyze several cost functions for this learning 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 present algorithms optimizing these cost functions, and, in one instance, detail both a batch and an on-line version. For this algorithm, we also show how the leave-one-out error can be computed and approximated efficiently, which can be used to determine the optimal values of the trade-off parameter in the cost function. We report the results of experiments comparing these algorithms on several datasets and contrast them with those obtained using an AUC-maximization algorithm. We also compare training times and performance results for the on-line and batch versions, demonstrating that our on-line algorithm scales to relatively large datasets with no significant loss in accuracy.
UR - http://www.scopus.com/inward/record.url?scp=37149011781&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=37149011781&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72845-0_1
DO - 10.1007/978-3-540-72845-0_1
M3 - Conference contribution
AN - SCOPUS:37149011781
SN - 3540728449
SN - 9783540728443
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 22
BT - Experimental Algorithms - 6th International Workshop, WEA 2007, Proceedings
PB - Springer Verlag
T2 - 6th International Workshop on Experimental Algorithms, WEA 2007
Y2 - 6 June 2007 through 8 June 2007
ER -