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.
- 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. Google ScholarDigital Library
- Bousquet, O., & Elisseeff, A. (2000). Algorithmic stability and generalization performance. Advances in Neural Information Processing Systems (NIPS 1999) (pp. 196--202).Google Scholar
- Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499--526. Google ScholarDigital Library
- 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). Google ScholarDigital Library
- Cossock, D., & Zhang, T. (2006). Subset ranking using regression. Proceedings of the Conference on Learning Theory (COLT 2006) (pp. 605--619). Springer, Heidelberg. Google ScholarDigital Library
- Crammer, K., & Singer, Y. (2002). Pranking with ranking. Advances in Neural Information Processing Systems (NIPS 2001) (pp. 641--647).Google Scholar
- 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). Google ScholarDigital Library
- 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.Google Scholar
- Joachims, T. (2002). Evaluating retrieval performance using clickthrough data. Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information 2002.Google Scholar
- McCullagh, P. (1980). Regression models for ordinal data. Journal of the Royal Statistical Society, B, 42.Google Scholar
- McCullagh, P., & Nelder, J. A. (1983). Generalized linear models. Chapman & Hall, London.Google Scholar
- McDiarmid, C. (1998). Concentration. Probabilistic Methods for Algorithmic Discrete Mathematics (pp. 195--248).Google Scholar
- 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. Google ScholarDigital Library
- Shashua, A., & Levin, A. (2003). Ranking with large margin principle: Two approaches. Advances in Neural Information Processing Systems (NIPS 2002) (pp. 937--944).Google Scholar
- Vapnik, V. N. (1998). Statistical learning theory. New York: Wiley-Interscience.Google Scholar
- Magnitude-preserving ranking algorithms
Recommendations
Re-ranking search results using query logs
CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge managementThis 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 IIA 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